What is the purpose of the Quantum Fourier Transform or what does it operation achieve?

Question

As far as I understand it aids with period finding which can help factor large numbers (i.e why it is used in Shor's algorithm).

What I want to know is if I have a quantum system and I apply the Quantum Fourier Transform (QFT) what does the output actually mean?

Example:

If I have:

psi = 1.0|00> + 1.0|01> + 0.0|10> + 0.0|11>  

or

psi =

[[ 1.]
 [ 1.]
 [ 0.]
 [ 0.]]

and I apply the QFT for a 2-qubit system:

QFT 2-Qubit matrix =

[[  5.0000e-01 +0.0000e+00j   5.0000e-01 +0.0000e+00j  5.0000e-01 +0.0000e+00j   5.0000e-01 +0.0000e+00j]
 [  5.0000e-01 +0.0000e+00j   3.0616e-17 +5.0000e-01j -5.0000e-01 +6.1232e-17j  -9.1849e-17 -5.0000e-01j]
 [  5.0000e-01 +0.0000e+00j  -5.0000e-01 +6.1232e-17j  5.0000e-01 -1.2246e-16j  -5.0000e-01 +1.8370e-16j]
 [  5.0000e-01 +0.0000e+00j  -9.1849e-17 -5.0000e-01j -5.0000e-01 +1.8370e-16j   2.7555e-16 +5.0000e-01j]]

I get the following:

QFT matrix * Psi =

[[  (5.0e-01 +0.0e+00j) + (5.0e-01 +0.0e+00j)  + (5.0e-01 +0.0e+00j)  + (5.0e-01 +0.0e+00j)]
 [  (5.0e-01 +0.0e+00j) + (3.1e-17 +5.0e-01j)  + (-5.0e-01 +6.1e-17j) +(-9.2e-17 -5.0e-01j)]
 [  (0.0e+00 +0.0e+00j) + (-0.0e+00 +0.0e+00j) + (0.0e+00 +0.0e+00j)  + (-0.0e+00 +0.0e+00j)]
 [  (0.0e+00 +0.0e+00j) + (0.0e+00 -0.0e+00j)  + (-0.0e+00 +0.0e+00j) +(0.0e+00 +0.0e+00j)]]

OR

QFT matrix * Psi =
[ 1.0 +0.0e+00j  
  0.5 +5.0e-01j  
  0.0 +6.1e-17j  
  0.5 -5.0e-01j]

In ket notation this is:

(1+0j)|00> + (0.5+0.5j)|01> + (0+0j)|10> + (0.5-0.5j)|11> 

But what does this tell me about psi? Sorry if this seems to be an obvious or silly question but I am still new to the field of Quantum Computing! Any help is appreciated!

Answer 1

I think the simplest answer is that the quantum Fourier transform maps the computation basis to the Fourier basis. Here, the value of each bit in the computational basis is encoded into fractional phases applied to each qubit. I built a circuit in quirk to help develop intuition for counting in the Fourier basis.

The Fourier basis is a natural basis for many different operations because of the easy access to these fractional phases. Some operations like addition and multiplication are more natural in the Fourier basis!

For a more in-depth understanding for how this transform behaves, we can derive the quantum Fourier transform from the classical Fourier transform. Classically, the discrete Fourier transform maps a discrete periodic function in real space to frequency space, or the decomposition of the function into sinusoidal or complex exponential functions of different frequencies. If the set of points to be mapped are denoted by $x_j$, then the mapping to frequency space is a set of points $y_k$ given by $$ y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1} x_je^{2\pi i\frac{ j k}{N}} $$ The quantum Fourier transform performs the same transformation, mapping the state $$ \sum_{j=0}^{N-1}x_j|j\rangle \mapsto \sum_{k=0}^{N-1}y_k |k \rangle $$ Since the Fourier transform is linear (and unitary) transformation, it can be defined by its action on an arbitrary computational basis state $|x\rangle$ via $$ |x \rangle \mapsto \frac{1}{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi i\frac{ xy}{N}}|y \rangle $$ Since we are dealing with qubits, the number of states $N$ will be $N=2^{n-1}$, where $n$ is the number of qubits. This affords a more intuitive representation. We begin be writing $y$ in binary notation, with the digits of $y$ being $y_1,y_2...y_n$ in order most to least significant: $$ y = \sum_{k=1}^n y_k2^{n-k} $$ We can use this to rewrite the state (neglecting normalization) as $$ \begin{align*} \sum_{y=0}^{N-1}e^{2\pi i\frac{ xy}{N}}|y \rangle &= \sum_{y=0}^{N-1}e^{2\pi i x\left( \sum_{k=1}^n y_k2^{n-k}\right)/2^{n}}|y \rangle \\ &= \sum_{y=0}^{N-1}e^{2\pi i x\sum_{k=1}^n y_k2^{-k}}|y \rangle \end{align*} $$ The exponent can be split into a product, and $|y\rangle$ can be split into a tensor product of the single-qubit states $|y_k \rangle$: $$ \begin{align*} &= \sum_{y=0}^{N-1}\prod_{k=1}^n e^{2\pi i x y_k2^{-k}}\bigotimes _{k=1}^n|y_k \rangle \end{align*} $$ Then the product can be distributed using the multilinearity of the tensor product: $$ \begin{align*} &= \sum_{y=0}^{N-1}\bigotimes _{k=1}^ne^{2\pi i x y_k2^{-k}}|y_k \rangle\\ &= \sum_{y\in\{0,1\}^{\otimes n}}\bigotimes _{k=1}^ne^{2\pi i x y_k2^{-k}}|y_k \rangle\\ &= \bigotimes _{k=1}^n \sum_{y_k\in\{0,1\}} e^{2\pi i x y_k2^{-k}}|y_k \rangle\\ &=\bigotimes _{k=1}^n\left(|0\rangle + e^{2\pi i x 2^{-k}}|1 \rangle\right)\\ \end{align*} $$ This reveals that in fact the final state is an unentangled "product state". Now, we can break down the representation further using binary decimal notation, where $0.x_nx_{n-1} ... x_1 = \sum_{j=1}^n x_{n-j+1}2^{-j}$. After the Fourier transform, the $k$th qubit is in the state $$ \begin{align*} |q_k\rangle & = (|0\rangle + e^{2\pi i x 2^{-k}}|1 \rangle)\\ &= (|0\rangle + e^{2\pi i (x_1x_2...x_{k-1}.x_kx_{k+1}...x_n})|1 \rangle) \\ &= (|0\rangle + e^{2\pi i (x_1x_2...x_{k-1})}e^{2\pi i(0.x_kx_{k+1}...x_n})|1 \rangle)\\ &= (|0\rangle + e^{2\pi i(0.x_kx_{k+1}...x_n})|1 \rangle)\\ &= (|0\rangle + e^{\frac{2\pi ix_k}{2}}e^{\frac{2\pi i x_{k+1}}{4}}...e^{\frac{2\pi i x_n}{2^{n-k+1}}}|1 \rangle)) \end{align*} $$ This representation gives a suggestion for constructing a circuit to perform the transformation, by conditioning $Z$ rotations on the bits of $x$. In addition, it shows what the transformed state actually represents. The most significant bit makes of the output makes a full rotation every time the input counts to $2^{n}-1$ and then swings back to $0$. The least significant bit flips back and forth between the $|+\rangle$ and $-\rangle$ state depending on the least significant bit of the input. The most significant bit of the output carries information in its phase about all of the input bits, and the least significant bit of the output only carries information about the least significant bit of the input.

I did my best to weed out mistakes in my math, but some (especially in the indices) may have survived. I learned this from the qiskit textbook, which has been an invaluable resource for me. I hope my answer helps someone out!

Cheers!

Answer 2

I've checked through the answer above and it's really a good one especially for newbies! Truth be told, it's my first time to learn about other applications of Quantum Fourier Transform (QFT) rather than Shor's algorithm alone. I mean, addition and multiplication.

Well, the answer above has already established basic mathematics about QFT. Here, I'd like present a visual and down-to-earth way to introduce QFT as well as its results.

Once again, I want appreciate the introductory circuit built by Ben McDonough. Thus I hope you can open that webpage while reading my answer.

By direct observation of the results in that page, one can easily see all five vectors on Bloch spheres are rotating! Besides, all of them lie straightly on the X-Y plane. Does this apparent fact remind you of something? Maybe you are wearing THAT THING right on your wrist, by which I mean a watch.

The vectors lying on X-Y plane resemble hour hand, minute hand, second hand in your watch. So, with the help of this analogy, you can explain QFT program as translating seconds into "Hour-Minute-Second" format.

Let me give you two little example.

First one, we have 18160 seconds and want to translate it into "Hour-Minute-Second" format. As we all know, 1 hour = 3600 seconds and 1 minute = 60 seconds and 1 second = 1 second. So what we need to do is simply calculate as follows:

$Hour = 18160 // 3600 = 5$

$Minute = (18160 - 3600 * 5) // 60 = 2$

$Second = 18160 - 3600 * 5 - 60 * 2 = 40$

Finally, we have 18160 seconds = 5 hours 2 minutes 40 seconds

Second example is similar to the first one. However, we no longer use period T = 60. Instead we use T = 1 / 2.

Suppose we have a binary string 10100 leaving the first qubit as 0(numbering backwards). And we want to perform QFT on it. Since the length of it is 5, we need 5 qubits and 5 clocks with different periods (just like hour hand is different from minute hand).

Clock number	Clock 1	Clock 2	Clock 3	Clock 4	Clock 5
Angular velocity	1 / 2	1 / 4	1 / 8	1 / 16	1 / 32

(For simplicity, we transform 10100 from binary one to decimal one in advance, which is $2^4 + 2 ^2 = 16 + 4=20$)

Thus, the first clock need to rotate $20 \times 1 / 2 = 10$ times = $0$ time, the second one $20 \times 1 / 4 = 5$ times = $0$ time, the third is $20 \times 1 / 8 = 5 / 2$ times = $1 / 2$ time, the fourth is $5 / 4 = 1 / 4$ time and the fifth is $5 / 8$ time. This fact implies every single clock recorded the same data! Even though they hold completely different period.

If you really draw a big clock with 5 hands, you can visually and easily see what the "time" is right now.

But how has the Quantum Circuit done this job? (Sorry, Ben. Let me borrow your pic for a moment.)

Let the first qubit in. And it will encounter an H gate which turn it into a |+> state (parallel to X-axis) which means the hand of the first clock doesn't rotate at all!

Then the second qubit comes in. Old school. We have to put it on X-Y plane. That's why we need an H gate. But what's the use of S gate, which would rotate a vector by the half of the phase of an H gate? Well, since the second clock has exactly half of the angular velocity of H gate, when the first clock rotates ( if the 1st qubit is 1), it has to rotate 90° instead of 180° by H gate. However, the first qubit is 0, we don't have to rotate the second clock.

To save time, we just skip to the fifth clock and check how it rotates. First, since the 5th qubit is 1, the 5th clock now reads 6 o'clock (180° = 360° / 2 for the sake of H gate). Notice that the 3rd qubit is 1, too! So it has to rotate another 360° / 8. Add them up we get $360° \times (1 / 2 + 1 / 8) = 360° \times 5 / 8 = 5 / 8$ times！

Conclusion: QFT turns a binary data into indications of clocks. No matter which way you choose to express your data, they are actually the same thing. Someone may argue that the hour hand only tells us HOURs, it can't tell us MINUTEs and SECONDs. Well, that depends on how your watch rotates, discretely or continuously. For continuous one, the introduction above explains well.