# How does the QFT represent the frequency domain?

QFT is often explained through the classical analogue which converts a certain function from the time domain to the frequency domain. When looking at the discrete Fourier transform, it makes sense to see a sin wave become a spike at a certain frequency.

However, I don't see how this "frequency domain" notion applies to the quantum fourier transform. How does the Fourier basis represent this frequency domain?

If we apply a QFT on a quantum "sin wave" will it output a certain frequency?

• The quantum Fourier transformation adds phases to each superposition state, and this relative phase might be the quantum correspondence of the frequency in the classical case. Dec 27 '20 at 5:29

The Fourier transform is more general than moving from the time domain to the frequency domain. For example, physicists regularly Fourier transform from position space to momentum space.

In both of these examples, the Fourier transform is a basis transformation, i.e. it is transforming the basis vectors used to represent some state without changing the state itself. Likewise, the QFT is simply a basis transformation from the computational basis to the Fourier basis.

To see how the QFT relates to more familiar Fourier transforms, it may be helpful to consider how integers are represented over both the computational basis and the Fourier basis. To illustrate, I'll walk through a specific example of the QFT for a four-qubit system.

In the computational basis, integers are represented in binary form (with the MSB on the left by convention). So for four qubits $$\vert 0 \rangle=\vert 0000 \rangle, \;\;\vert 1 \rangle=\vert 0001 \rangle, \;\; \vert 2 \rangle=\vert 0010 \rangle,\;\; ..., \;\; \vert 15 \rangle =\vert 1111 \rangle.$$ Algebraically this is given by $$\vert n \rangle=\vert a(2^3)+b(2^2)+c(2^1)+d(2^0) \rangle=\vert abcd \rangle, \;\; a,b,c,d \in \lbrace 0,1 \rbrace, \; n \in \lbrace 0,...,15\rbrace.$$ On the four Bloch spheres associated with $$\vert abcd \rangle$$, counting from $$\vert 0 \rangle$$ to $$\vert 15 \rangle$$ looks like: (Image Source, with $$\vert d \rangle=\text{qubit 0}$$, $$\vert c \rangle=\text{qubit 1}$$, ...)

You can see that in the Bloch spheres representation, distinct values of $$\vert n \rangle$$ are distinguished by ordered sets of qubits at either their north pole, $$\vert 0 \rangle$$, or their south pole, $$\vert 1 \rangle$$. Intuitively, while counting, the qubit associated with the LSB, $$\vert d \rangle$$, changes state every step, whereas the qubit associated with the MSB, $$\vert a \rangle$$, changes state every eighth step. [Note that the Bloch sphere is actually a Riemann sphere (i.e. the complex projective line), so orthogonal states, such as $$\vert 0 \rangle$$ and $$\vert 1 \rangle$$, are represented by antipodal points.]

The same 16 integers represented over the Fourier basis, $$\text{QFT} \vert n \rangle = \vert \tilde n \rangle =\vert \tilde a \tilde b \tilde c \tilde d \rangle$$, is given algebraically by $$\vert \tilde n \rangle = \tfrac{1}{\sqrt{2^4}}(\vert 0 \rangle + e^{2\pi in/2} \vert 1 \rangle) \otimes (\vert 0 \rangle + e^{2\pi in/2^2} \vert 1 \rangle) \otimes (\vert 0 \rangle + e^{2\pi in/2^3} \vert 1 \rangle) \otimes (\vert 0 \rangle + e^{2\pi in/2^4} \vert 1 \rangle).$$ Now as we count in the Fourier basis from $$\vert \tilde n \rangle = \vert \tilde a \tilde b \tilde c \tilde d \rangle = \vert \tilde 0 \rangle$$ to $$\vert \tilde {15} \rangle$$ all four qubits change state every step, with $$\vert \tilde a \rangle$$ taking the largest steps (i.e. swapping between $$\vert + \rangle$$ and $$\vert - \rangle$$, which is $$\frac{1}{2}$$ of a turn per step) and $$\vert \tilde d \rangle$$ taking the smallest steps ($$\frac{1}{16}$$ of a turn per step).

On the four Bloch spheres associated with $$\vert \tilde a \tilde b \tilde c \tilde d \rangle$$, counting in the Fourier basis appears as each qubit state rotating in the equatorial plane with decreasing frequency from $$\vert \tilde a \rangle$$ to $$\vert \tilde d \rangle$$.

(Image Source, with $$\vert \tilde d \rangle=\text{qubit 0}$$, $$\vert \tilde c \rangle=\text{qubit 1}$$, ..., $$\vert + \rangle = x$$)

In a single counting sequence from $$\vert \tilde 0 \rangle$$ to $$\vert \tilde {16} = \tilde 0 \, (\text{mod} \, \tilde {16}) \rangle$$ the qubits associated with $$\vert \tilde a \rangle, \, \vert \tilde b \rangle, \, \vert \tilde c \rangle$$, and $$\vert \tilde d \rangle$$ make exactly $$2^3, \, 2^2, \, 2^1$$, and $$2^0$$ full rotations in their respective equatorial planes. Similarly, if we consider "no rotation" in the equatorial plane as the state $$H\vert 0 \rangle=\vert+\rangle$$, then $$\vert \tilde 0 \rangle = \vert ++++ \rangle$$ gives all qubits unrotated, while $$\vert \tilde {15} \rangle$$ gives all qubits at their maximal rotation (in the positive direction). [Note that the single qubit QFT is just the Hadamard gate, $$H$$. In turn, $$H$$ is simply the 2-level DFT as noted in this previous answer.]

In this example you can see how the high magnitude associated with $$\vert a \rangle$$ as a constituent of $$\vert n \rangle$$ in the computational basis corresponds to a high frequency associated with $$\vert \tilde a \rangle$$ as a constituent of $$\vert \tilde n \rangle$$ in the Fourier basis, and so forth for $$\vert b \rangle \,, \vert c \rangle$$, and $$\vert d \rangle$$. Hopefully this helps to make the analogy between QFT and DFT more tangible.

The equations used above were specific to the example of a four-qubit system. They generalize naturally to $$N$$-qubit systems as $$\vert n \rangle = {\Big \vert} \sum_{k=0}^{N-1} x_k 2^k {\Big \rangle} = \vert x_0 ... x_{N-1} \rangle, \; x_k = \lbrace 0,1 \rbrace, \, n= \lbrace 0,...,2^N-1 \rbrace,$$ $$\text{QFT}\vert n \rangle = \vert \tilde n \rangle = \frac{1}{\sqrt{2^N}}(\vert 0 \rangle + e^{2 \pi i n / 2} \vert 1 \rangle) \otimes ... \otimes (\vert 0 \rangle + e^{2 \pi i n / 2^N} \vert 1 \rangle).$$

If you're looking for additional familiarity and comfort with the QFT, it's a great exercise to convince yourself that both $$\vert n \rangle$$ and $$\vert \tilde n \rangle$$ are orthonormal bases for $$\mathbb{C}^{2^N}$$. Another great exercise is to convince yourself that $$QFT = \frac{1}{\sqrt{2^N}} \sum_{n=0}^{2^N-1} \, \sum_{\tilde n=0}^{2^N-1}e^{2 \pi i n \tilde n/2^N} \vert \tilde n \rangle \langle n \vert$$ is a unitary operator on $$\mathbb{C}^{2^N}$$. (Note that the validity of either of the statements in these two excercises implies the validity of the other.)

If you apply the $$n$$-qubit QFT defined as $$\frac{1}{\sqrt{N}}\sum_{k = 0}^{N - 1}\sum_{n = 0}^{N - 1}a_n e^{2 \pi i n k/N}\left|k \right>$$ acting on a state $$\sum_{x = 0}^{N - 1}a_x\left|x\right>$$ with $$N = 2^{n}$$ on a sin wave with a frequency $$k$$ defined as $$\frac{1}{2^{(n - 1)/2}}\sum_{x = 0}^{N -1}\sin(\frac{2 \pi x k}{N})\left|x\right>$$ with $$n > 1$$ and $$k \neq 0$$ to avoid having only zero values, the result will be $$\frac{i}{\sqrt{2}}\left|k\right> - \frac{i}{\sqrt{2}}\left|N - k\right>$$. This intuitively matches the regular Fourier transform which gives $$\frac{i \sqrt{\pi}}{\sqrt{2}}\delta(\omega - 2 \pi k) - \frac{i \sqrt{\pi}}{\sqrt{2}}\delta(\omega + 2 \pi k)$$ for $$sin(2 \pi kx)$$ if using the modern physics form ($$\hat f(\omega) = \frac{1}{\sqrt{2 \pi}}\int_{-\infty}^{\infty}f(t)e^{i \omega t}dt$$) and with $$\omega$$ denoting frequency. On the other hand, the wave $$\frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}e^{-2 \pi x k/N}\left|x\right>$$ that combines a real cosine wave with an imaginary sin wave is much more naturally transformed directly into $$\left|k\right>$$.

The correspondence to the "time variable" in the QFT is not time but rather the computational basis states, but the relationship between the two bases is similar to that of time and frequency. If you take $$N$$ evenly spaced points on the complex unit circle that together go across the entire circle ($$e^{-2\pi i x/N}$$ for $$x$$ from $$0$$ to $$N - 1$$ goes through clockwise), then with the probability amplitude $$a_k$$ each frequency $$k$$ corresponds to $$\frac{a_k}{\sqrt{N}}\sum_{x=0}^{N - 1}e^{-2 \pi i x k /N}\left|x\right>$$: the intuitive link to traditional "frequency" is how many times the complex unit circle is fully circled as you go across the basis states. The sum of these for all frequencies returns the original state as usual.