# Questions tagged [quantum-fourier-transform]

Quantum Fourier Transform (QFT) is a linear transformation on quantum bits and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. (Wikipedia)

175 questions
Filter by
Sorted by
Tagged with
334 views

### qiskit: IQFT acting on subsystem of reversed-ordered qubits state

I have a state psi as an ndarray of shape (2 ** 3,) s.t. psi[0]= amplitude of 000 ...
29 views

### How to create a quantum algorithm to determine unknown coefficients in a linear function

I am trying to solve the following practice question shown below. I am stuck on part (c) where I must design a quantum algorithm to solve the stated problem. I can tell that the solution is probably ...
65 views

### Fourier transform of the product of two wave functions

Good day, I have a wave function in the coordinate representation $\Psi(x)$. The Fourier transform I am interested in is: $$\int e^{-i a x} \Psi(x) \Psi^{\star}(x-b) dx,$$ where $a$, $b$ are some ...
892 views

### Does the Quantum Fourier Transform require universality?

Background: In most setups of fault-tolerant quantum computation, universality is achieved using Clifford gates such as $(S, H, \text{CNOT})$ and the $T$-gate. The Eastin-Knill theorem can be ...
1 vote
212 views

### How do you retrieve the Quantum Fourier Transform matrix from superposition expansion?

So I am trying to wrap my head around QFT working out the details. I have managed to retrieve the 2 qubit QFT matrix by expanding out the superposition of 2 qubits through QFT gate. I am now trying ...
52 views

### Failed - Internal Error when running on ibmq

I tried to apply a series of an inverse QFT on a single qubit depending on a previous measurement, but when a depth of a circuit became longer I encountered an internal error, ...
201 views

### Inverse Quantum Fourier Transformation

I have the exercise to implement the Inverse QFT with Qiskit for any number of qubits without the swapping part. I tried to implement something like this for any $n$. Now I got this code but it doesn'...
72 views

### In the QFT, do the basis states $\{|k\pmod N\rangle\}_{k=0}^N$ only make sense when $N=2^n$?

When I started learning quantum computing, I learned that for an $n$ qubit system, the basis states look like $$\bigg\{ |\text{n-bit strings}\rangle\bigg\}\,.$$ So an $n$ qubit system has $2^n$ basis ...
61 views

### Why FACTORING is in second level of Fourier hierarchy?

As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is: $FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
2k views

### Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?

The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical ...
67 views

### Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state ...
376 views

171 views

### Estimating $\pi$ using Quantum Computing - why does it work only in simulator?

I followed the steps from the Qiskit tutorial on YouTube titled "How can I estimate Pi using a quantum computer? - 1 Minute Qiskit" The code uses Qiskit and apparently works successfully ...
1 vote
97 views

1 vote
51 views

### Question regarding a step in the computation of $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$

In clas we computed the Quantum Fourier Transformation $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$. We started with the following computation: \begin{...
198 views

### In the qiskit QFT demonstration, how to implement CPHASE between Q0 and Q1?

In the qiskit example for QFT demonstration the ibm_q_bogota is used, it has the following layout: in the same time the measurement circuit for QFT demonstration is: For such a linear layout how is ...
101 views

### Inverse quantum Fourier transformation (QFT) on a 4 qubit state

I'm looking to calculate explicitly the inverse QFT acting on a four qubit state. Would the inverse just be calculated as the following: \label{QFTProduct} \frac{1}{\sqrt{N}} \left( |0&...
1 vote
368 views

### Is QFT really faster FFT?

The standard DFT: $$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$ takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT ...
41 views

### Convolution using QFT with 2 vectors

I am doing an experiment in Qiskit - trying to mimic convolution of 2 vectors and getting the result of convolution using element-wise approach. However, I as doing necessary steps the result I get is ...
1 vote
43 views

### Translation by $s \in G$ is diagonal in the Fourier basis

Let $G$ be any finite abelian group and let $P_s$ be the map that sends $|x\rangle \to |x+s\rangle$. In the standard basis $\{|x\rangle : x \in G\}$, the matrix representation is a permutation matrix. ...
144 views

1 vote
136 views

### Why is the application of a Quantum Fourier Transform constant time?

I am just curious (complexity theory wise) why the unitary matrix for the QFT (Quantum Fourier Transform) is constant time. From what I know, there is no general way to represent it as a sequence of ...
1 vote
42 views

### modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible

I am supposed to modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible. Beforehand, I already did an exercise where I showed that the inverse Quantum ...
142 views

### Is the phase-estimation a specific case of the Hidden Subgroup Problem?

I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation. In Exercise 5.14 (Section 5.3.1 "Application: order-...
66 views

### Period finding for amplitude encoding of function

In quantum Fourier transform, amplitude encoding is used to represent function $f(x)$ such that $|\psi\rangle = \sum_x f(x)|x\rangle$, with $f(x)$ being amplitude. In Shor's algorithm, it is not this ...
284 views

### Solution to Nielsen & Chuang Exercise 5.3 (FFT)

Can somebody help me with the solution of Nielsen Chuang, where we are supposed to derive the FFT from the equation (5.4): |j_1,\ldots,j_n\rangle\rightarrow\frac{\big(|0\rangle+e^{2\pi i 0.j_n}|1\...
290 views

### How is the fractional binary notation used in the QFT?

I am studying the Quantum Fourier Transform and my question regards section 4 from this link. Specifically, I do not understand the step where they rewrite in fractional binary notation- could someone ...