## What the Quantum Fourier Transform is (and isn’t)

In the last post, I discussed the Fourier Transform on finite groups $G$. Here I’ll discuss in more detail the case $G=Z_N$, the finite cyclic groups. This is what is usually called the Discrete Fourier Transform.

The (Quantum) Fourier Transform is a unitary transformation on $\mathcal{H}=\ell^2(Z_N)=C^N$, which in the standard basis is expressed by the matrix

with $\omega=e^{2\pi i/N}$. It turns out that if $N=2^n$ and we interpret the Hilbert space $\mathcal{H}=C^N$ as the state space of $n$ qubits, $U_\text{QFT}$ can be implemented efficiently, using only about $n^2$ elementary (1- and 2-qubit) gates.

Efficient Circuit for the QFT

Consider an $n$-qubit state
\begin{aligned} \left\vert\psi\right\rangle=\sum_{s=0}^{2^n-1}\alpha(s)\left\vert s\right\rangle. \end{aligned}
The $n$-qubit QFT acts on this state as follows:

where the $P$ and $cP$ gates are phase and controlled phase gates defined implicitly, and $H$ is the Hadamard gate. Therefore, we have

\begin{aligned} U_\text{QFT}^{(n)}=\left(I_{n-1}\otimes H\right)cP^{(n-1)}\left(U_\text{QFT}^{n-1}\otimes I\right). \end{aligned}
The controlled phase gate can be implemented with $n-1$ elementary (2-qubit) controlled gates, and the Hadamard gate $H$ is a single qubit gate, so if we can implement the $(n-1)$-qubit QFT, we just need $n$ additional elementary gates to implement the $n$-qubit QFT. The 1-qubit QFT is just a Hadamard gate, so we can implement the $n$-qubit QFT with $n+(n-1)+(n-2)+\ldots +1=n(n+1)/2$ elementary 1- and 2-qubit gates. I won’t reproduce the circuit here – nice drawings are available anywhere qubits are sold.

That’s the good news. The bad news is that the QFT is not an algorithm for the Discrete Fourier Transform in the sense we would really like it to be, i.e. a black box that takes a vector of classical data and outputs, as classical (i.e., readable) data, the Fourier transform of that vector. Instead, the QFT is a unitary transformation that takes as input a quantum state and gives as output another quantum state. So the QFT is not an exponentially faster replacement for the classical FFT algorithm, which does precisely this in time $N\log N=n 2^n$. In order to make use of the QFT as a limited replacement for the FFT, we need to figure out (1) what classical data can be efficiently encoded in the proper form and (2) what data can be efficiently extracted from the output state.

Efficiently Encodable Data

One example of data that can be efficiently encoded into a quantum state, given that it is already stored in a quantum accessible manner, is the following. Suppose that we have an oracle $\mathcal{D}$ that was capable of performing the transformation $\mathcal{D}:\left\vert s\right\rangle\mapsto\left\vert s\right\rangle\left\vert D(s)\right\rangle$ where $D$ is a $\left\lbrace 0,1\right\rbrace$-valued function. Such an oracle can be efficiently implemented with the QRAM protocol (see e.g. https://arxiv.org/pdf/0708.1879.pdf). Then applying $\mathcal{D}$ to the even superposition over all computational basis states (efficiently preparable from the zero state of $n$ qubits via $n$ Hadamard gates), measuring the second register in the computational basis, and post-selecting for outcome 1, we obtain the state

\begin{aligned} \mathcal{N}\sum_{s:D(s)=1}\left\vert s\right\rangle \end{aligned}

where $\mathcal{N}$ is the normalization factor. This is a state of the form

\begin{aligned} \left\vert\psi\right\rangle=\sum_{s=0}^{M-1}\alpha(s)\left\vert s\right\rangle \end{aligned}
with $\alpha(s)\propto D(s)$, so now the QFT can be used to Fourier transform $D$.

If we assume that a constant fraction of the values of $s$ have $D(s)=1$, then we can prepare the state $\left\vert\psi\right\rangle$ with exponentially high probability in the number of tries.

Efficiently Extractable Data

Here I’ll show that the QFT can be used in an efficient procedure for estimating the period of a quantum state. Since this application is at the heart of Shor’s algorithm, it’s probably the most famous use of the QFT.
Suppose that the vector $\left\vert\psi\right\rangle=\sum_{s=0}^{N-1}\alpha(s)\left\vert s\right\rangle$ is periodic with period $p$, i.e. $\alpha(s)=\alpha(s+p)$ for all $s$. Suppose also that $p$ divides $M$. We have that $T^p\left\vert\psi\right\rangle=\left\vert\psi\right\rangle$ where $T\left\vert s\right\rangle=\left\vert s+1\right\rangle$ is the shift operator. Using the unitarity of the QFT, we then have
\begin{aligned} \left(U_\text{QFT}TU_\text{QFT}^\dagger\right)^pU_\text{QFT}\left\vert\psi\right\rangle=U_\text{QFT}\left\vert\psi\right\rangle. \end{aligned}
Expanding $U_\text{QFT}\left\vert\psi\right\rangle$ in the Fourier basis, this gives
\begin{aligned} \sum_{k=0}^{M-1}\hat{\alpha}(k)\hat{T}^p\left\vert k\right\rangle=\sum_{k=0}^{M-1}\hat{\alpha}(k)\left\vert k\right\rangle \end{aligned}
where the hat denotes change of basis into the Fourier basis. It is simple to verify that $\hat{T}\left\vert k\right\rangle=e^{2\pi ik/M}$, so that in order for this equation to hold, $\hat{\alpha}(k)$ must be zero unless $kp$ is a multiple of $M$ or, equivalently, $k$ is a multiple of $M/p$ (which we assumed was an integer). There are $p$ such values of $k$.

This analysis shows that if we apply the QFT to $\left\vert\psi\right\rangle$ and measure in the computational basis, we will obtain a value of $k$ such that $k=nM/p$. Suppose we prepare $J$ copies of $\left\vert\psi\right\rangle$ and apply the QFT to each one, then measure in the computational basis. We obtain values $k_1,\ldots,k_J$, with $k_i=n_iM/p$. If the gcd of the $n_i$ is one, then the gcd of the $k_i$ is $M/p$, and since $M$ is known, we obtain $p$. Of course, it’s possible that the $\hat{\alpha}(k)$ are exponentially small except for some $k$ a multiple of $M/p$, in which case we’ll underestimate $p$ with high probability unless $J$ is exponentially large, in which case the quantum speedup is lost. However, in this case, $\left\vert\psi\right\rangle$ is very close to a state with the period we estimated, so it’s not unreasonable to be satisfied with this performance.

On the other hand, suppose that all of the $p$ non-zero $\hat{\alpha}(k)$ have roughly the same magnitude. Then the probability that with $J$ samples we correctly find $p$ is the same as the probability that the gcd of $J$ integers drawn uniformly at random from $0,1,2,\ldots,p-1$ is one. It is not too hard to see that this probability is bounded exponentially (in $J$) close to one. If we didn’t do the classical post-processing of the outcomes and just looked for the smallest value of $k$ that appeared, we would not get this performance.

Failed Example

Combining these three parts (state preparation/data entry, transformation/data processing, and measurement/data extraction), we can try to build a quantum algorithm that gives with high probability a speedup over a classical computer for a simple problem. Suppose that we’re given a string of $2^n$ bits, stored either in a classical RAM or in a QRAM, and would like to determine the period of the data. Assume that a constant fraction of the bits are 1. Then with a constant expected number of calls to the QRAM, we can prepare the $n$-qubit state whose amplitudes encode the unknown bitstring. With $\mathcal{O}(n^2)$ elementary gates, we perform the QFT on this state. Then we make a single $n$-qubit measurement to obtain a value of $k$ present with non-zero amplitude in it’s Fourier transform. We need to repeat this procedure several times in order to give an estimate of the period. But how many?

Suppose that a malicious user designs a family of classical inputs $A_n$ and $B_n$ of lengths $2^{2n}$, where the $A_n$ have period $2^n$ and the $B_n$ are identical to the $A_n$ except that the first 1 in the second half of the string is changed to a 0, and the first 0 to a 1, so that they have period $2^{2n}$. Then the corresponding quantum states $\left\vert A_n\right\rangle$ and $\left\vert B_n\right\rangle$ are exponentially close in $n$, meaning that the error probability for distinguishing $\left\vert A_n\right\rangle$ and $\left\vert B_n\right\rangle$ with a single measurement is exponentially close to 1/2. Therefore, it is exponentially unlikely that, given state $\left\vert B_n\right\rangle$, we measure an odd value of $k$ after performing the QFT, as if it were more likely, the discrimination procedure that reports $A$ if an even $k$ is measured and $B$ if an odd $k$ is measured would have a lower error probability than is possible given the distance between the states. This means that given the inputs $B_n$, we need to repeat the basic QFT procedure above exponentially many times in order to have a large probability of obtaining an odd value of $k$ and accurately determining the period.

This counterexample tells us that, even for this very contrived problem, the QFT does not give a speedup over the classical algorithm, at least for the worst case. However, it’s worth pointing out that for some applications, it might be a feature that the quantum algorithm with sub-exponentially many runs of the QFT is insensitive to small deviations from perfect periodicity.

Scott Aaronson has written a paper about these kinds of issues in the context of quantum machine learning.