Skip to main content

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)

Filter by
Sorted by
Tagged with
2 votes
2 answers
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 ...
3 votes
0 answers
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 ...
2 votes
1 answer
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 ...
12 votes
1 answer
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
1 answer
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 ...
3 votes
0 answers
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, ...
2 votes
1 answer
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'...
2 votes
2 answers
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 ...
3 votes
0 answers
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 ...
13 votes
3 answers
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 ...
3 votes
1 answer
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 ...
2 votes
1 answer
376 views

Question regarding the notation of QFT

I have a question about the notation of QFT. I would like to present briefly what my problem is. So given is the QFT as a mapping with: $$|j_1,...,j_n\rangle \rightarrow \frac{(|0\rangle + e^{2\pi i 0....
1 vote
1 answer
148 views

DFT like operation in the third step of Period finding and Discrete Logarithm algorithm

In the third step of the algorithm for discrete logarithm, the state $$ |\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle $$ is introduced which is stated to ...
3 votes
1 answer
40 views

Unexpected Rotations in QFT Implementation with Qiskit vs. Expected Behavior in Quirk

I'm working on implementing the Quantum Fourier Transform (QFT) using Qiskit. I've encountered an issue where unexpected rotations occur in the presence of a Hadamard circuit, which contrasts with the ...
2 votes
1 answer
129 views

How to understand Quantum Fourier Transform measurement output?

I have implemented the following 8 qubit QFT circuit similar to the following: and loaded the coefficients as follows: The output of the QFT is as follows: Could anyone help interpret the above ...
3 votes
1 answer
303 views

4 qubit QFT decomposition in the qiskit textbook

I am reading about the quantum Fourier transform (QFT) in the qiskit textbook, but got stuck at the last part of it which shows a decomposed version of the 4 qubit QFT circuit. It seems that the ...
2 votes
1 answer
90 views

Is it possible to modify the QFT circuit to use only 1-qubit gates?

[Measured Quantum Fourier Transform] I've recently learned the Quantum Fourier Transform, and was shown its circuit. The circuit I've seen is composed of Hadamard gates and controlled Rotation gates. ...
2 votes
0 answers
20 views

Quantum Fourier Transform : amplitude encoding of the time series?

I try to understand how to concretely use the Quantum Fourier Transform so as to retrieve the frequency amplitudes $g_{0},\dots, g_{N-1}$ out of the discrete time series $f_{0},\dots, f_{N-1}$ ($f_k\...
6 votes
1 answer
283 views

Is QFT qubit recycling compatible with Zeckendorf's Fibonacci representation of integers?

Background Phase estimation circuits prepare $n$ qubits $Q_0, \dots, Q_{n-1}$ in the $|+\rangle$ state, then apply $U^{2^q}$ controlled by $Q_q$ for each $q$, then apply a quantum Fourier transform, ...
5 votes
2 answers
240 views

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)...
2 votes
1 answer
421 views

How to construct a quantum circuit for quantum Fourier transform in a prime dimensional Hilbert space?

This problem is given as a problem in Nielsen and Chuang. Consider a Hilbert space of dimension $p$ where $p$ is a prime number. Quantum Fourier transform (QFT) in this space is defined as $$ |j\...
3 votes
1 answer
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
1 answer
97 views

Problem with the mathematical definition of the eigenvalue algorithm on a specific exercise

I think I understand well how the eigenvalue algorithm works but when I try to define it mathematically I have problems. Specifically I have the matrix U: $$ U = \begin{pmatrix} 0 & i \\ i & 0 ...
4 votes
0 answers
32 views

Fourier sampling in positive characteristic

Fourier sampling is used in the hidden subgroup problem in Shor's algorithm for $\mathbb{Z}/N\mathbb{Z}$ in the abelian case and the symmetric group $S_n$ for attempts at graph isomorphism in the ...
0 votes
2 answers
142 views

Help debugging implementation of Draper QFT adder

I am attempting to implement the adder found in this paper. Here is the code: ...
2 votes
1 answer
334 views

Constructing a controlled phase gate from given gates

As part of a project in a quantum computing course we were asked to classically simulate the quantum phase estimation algorithm, which has inverse QFT as one of its components. On the Wikipedia page ...
2 votes
0 answers
76 views

Is the QFT optimal in the quantum phase estimation algorithm?

We can concisely summarise the quantum phase estimation (QPE) algorithm as follows: Generate the state $\sum_{k=0}^{2^n-1} \lambda^k |k\rangle$ efficiently using a series of controlled-unitary ...
0 votes
0 answers
32 views

Can I simulate a quantum walk in fourier space?

I would like to simulate a simple quantum walk in Fourier space in Python. I am hoping just to run a 1D quantum walk with a simple Hadamard coin in Fourier space. Is this possible? Do I just need to ...
6 votes
1 answer
153 views

Is the quantum Fourier transform efficient if only one control-phase is allowed in the gate set

I have seen Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?. This is not a duplicate. I am familiar with the decomposition of the QFT from Nielsen&Chuang ...
0 votes
0 answers
33 views

QFT butterfly structure

Any idea why QFT does not require butterfly structure ? or probably it is already implied in https://medium.com/a-bit-of-qubit/quantum-fourier-transform-qubits-and-discrete-fourier-transform-...
1 vote
1 answer
135 views

Why can you check for entanglement using the quantum Fourier transform?

I'm reading this paper on quantum random oracles, and I have some fundamental questions about certain statements that seem to be intuitive (but I can't seem to figure it out). My goal is to have a ...
3 votes
1 answer
234 views

Is there a way to access the value of a classical bit after measurement and store it as a variable (qiskit)?

I am trying to implement the one-qubit Approximate QFT for Shor's Algorithm in qiskit as described in this paper, which requires the gate $$ R_j^{\prime}=\left(\begin{array}{c} 1 \hspace{0.5em} 0 \\ 0 ...
1 vote
1 answer
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{...
2 votes
2 answers
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 ...
0 votes
0 answers
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: \begin{equation}\label{QFTProduct} \frac{1}{\sqrt{N}} \left( |0&...
1 vote
1 answer
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 ...
2 votes
0 answers
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
1 answer
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. ...
5 votes
2 answers
144 views

Is it true that if $U$ sends computational basis states to product states, then it sends product states to product states?

Let $U$ be a unitary such that for all $n$-qubit computational basis states $|x\rangle$, the state $U |x\rangle$ is a product state. I am trying to prove that for all $n$-qubit product states $|w\...
5 votes
1 answer
481 views

What is the quantum query complexity of the period finding routine of Shor's algorithm?

It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention: Thus we solve Period Finding if the ...
10 votes
3 answers
710 views

Does the Quantum Fourier Transform (QFT) preserve entanglement?

It is well known that entanglement in a quantum state is not affected when you perform a combination of 1-qubit unitary transformations. I have seen that the QFT can be decomposed into product of 1-...
5 votes
1 answer
1k views

How to apply QFT to the last two qubits of a Qiskit quantum circuit?

I'm pretty new in Qiskit and quantum circuits. I'm using Qiskit to implement a quantum circuit and I followed this tutorial to implement a QFT. The way this QFT was built, it applies QFT in the first $...
1 vote
1 answer
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
0 answers
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 ...
4 votes
1 answer
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-...
0 votes
0 answers
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 ...
2 votes
1 answer
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\...
2 votes
1 answer
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 ...
4 votes
1 answer
281 views

How does the Hadamard gate work?

I'm learning about the Quantum Fourier Transform (QFT) and from what I can see the Hadamard gate equation doesn't make sense from what I have learnt so far. Here's a link to the resource (Example 2). ...
1 vote
1 answer
50 views

Alternative Versions of Quantum Fourier Transform (Decimation in Time/Frequency)

Is there a good comparison of alternative versions of the Quantum Fourier Transform (QFT) that mirror the alternative decimation-in-time or decimation in frequency versions for the conventional Fast ...