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
17
votes
4answers
614 views

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

It is a well known result that the Discrete Fourier Transform (DFT) of $N=2^n$ numbers has complexity $\mathcal O(n2^n)$ with the best known algorithm, while performing the Fourier transform of the ...
10
votes
3answers
1k views

Why does the “Phase Kickback” mechanism work in the Quantum phase estimation algorithm?

I've probably read the chapter The quantum Fourier transform and its applications from Nielsen and Chuang (10 th anniversary edition) a couple of times before and this took this thing for granted, but ...
4
votes
1answer
324 views

Implementation of inverse QFT?

When implementing the inverse quantum Fourier transform, in addition to reversing the circuit, does one need to take the conjugate transpose of the phase shift gates in the circuit as well?