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
943 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 ...
13
votes
3answers
2k 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 ...
5
votes
1answer
986 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?
3
votes
1answer
242 views

Cannot replicate results in article on pricing financial derivatives on IBM Q

I am trying to implement a circuit for searching for the largest eigenvalue and respective eigenvector of an operator, i.e. phase estimation, introduced in article Towards Pricing Financial ...