0
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ Something is terribly wrong: your QFT matrix is 4x4, your state vector is 4x1, but your QFT matrix * Psi looks like 4x4 again. Where did the state vector go? $\endgroup$
    – udrv
    Mar 3, 2017 at 16:18
  • $\begingroup$ Sorry for the confusion, the program I wrote prints out the QFTPsi matrix in the manner I originally included in this question. I have rectified this for clearer clarification that the QFTPsi matrix is in fact a 4x1 matrix. $\endgroup$
    – Catherine
    Mar 4, 2017 at 15:35
  • $\begingroup$ It's ok, now I see what u did. If you look at the computational basis states as indexed by binary numbers $x$, their amplitudes define a function $f(x)$ on the set spanned by $x$. The QFT replaces each $f(x)$ by its discrete Fourier transform. The point is that while a classical computation would have to calculate the transform for each f(x) separately, the QFT does this simultaneously for all f(x) at once. See this answer and the link therein for extra math physics.stackexchange.com/questions/219581/… $\endgroup$
    – udrv
    Mar 4, 2017 at 16:51

1 Answer 1

3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ very nice explanation!) but what is the reason to change Z-basis to the Fourier-basis? the numbers can be very well represented in Z-basis $\endgroup$
    – Curious
    May 18, 2023 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.