In quantum computing, the 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 ...
4
votes
2answers
53 views
Simplifying Quantum Tensor products with coefficients
$\newcommand{\ket}[1]{\lvert#1\rangle}$I am trying to show equality of two intermediate steps in the rearrangement of the Quantum Fourier transform definition, but I do not know how to rearrange the ...
8
votes
2answers
146 views
Quantum Algorithms for Convolution
I was looking into applications of Quantum Computing for machine learning and encountered the following pre-print from 2003. Quantum Convolution and Correlation Algorithms are Physically Impossible. ...
8
votes
2answers
184 views
Simplified explanation of Shor/QFT transformation as thumbtack
As a non-mathematician/software programmer I'm trying to grasp how QFT (Quantum Fourier Transformation) works.
Following this YouTube video: https://www.youtube.com/watch?v=wUwZZaI5u0c
And this ...
7
votes
3answers
118 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
74 views
Example of Quantum Fourier Computation for three qubits
I am currently going through Nielsen's QC bible and having still some foundational / conceptual problems with the matter.
I have tried to retrieve this $8 {\times} 8$ matrix describing the QFT of 3 ...
13
votes
4answers
266 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 ...
