Questions tagged [quantum-fourier-transform]
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 ...
2
votes
0answers
20 views
Why does Fourier sampling allow to efficiently recover hidden subgroups?
The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and ...
4
votes
2answers
68 views
Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?
I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used.
For example, if the QFT of three quantum bits is
$a_1|000\rangle + ...
2
votes
0answers
21 views
Weak Fourier Sampling vs Strong Fourier Sampling?
I'm having trouble understanding the difference between weak fourier sampling and strong fourier sampling. From this paper:
...two important variants of the Fourier sampling paradigm have been
...
1
vote
1answer
39 views
Quantum Fourier Transform on two qubits: Non orthogonal outputs
We know the QFT gives us a new orthogonal basis from the original one, however, when I apply it on two qubits, I am not getting the output vectors orthogonal.
$|out(k)\rangle = \Sigma^{N-1}_{j=0} e^...
5
votes
2answers
72 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
184 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
222 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
245 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
91 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 ...
15
votes
4answers
311 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 ...
