QFT's Role in Period Finding

1. The State of Affairs: A Periodic Superposition

Let's quickly recall the state of our quantum computer just before the QFT steps in. The full period-finding routine works as follows:

1. Prepare Superposition: We start with two registers of qubits. The first, or "input" register, is put into an equal superposition of all possible numbers it can hold, from $|0⟩$ to $|N-1⟩$, where $N=2^n$.
2. Apply the Function: We apply a complex unitary gate, $U_f$, that calculates $f(x)=a^x(\mathrm{mod}N)$. This entangles the input register with a second "output" register, creating a state that is a superposition of all |x, f(x)> pairs.
3. Measure the Output: We measure the second (output) register. This measurement yields some random value, let's call it $y_0$.

Because of how measurement works, the first register instantly collapses. It is no longer a superposition of all possible inputs. Instead, it becomes a superposition of only the inputs $x$ that could have produced the output $y_0$. Since $f(x)$ is periodic with period $r$, this means the first register is now in a state like:

where $x_0$ is the first input that gives the result $y_0$, and $M$ is the number of terms in the sum.

The information we need, the period r, is now encoded in the physical state of the qubits. But we have a problem: if we simply measure this register, we'll get one of the values ($x_0$, $x_0+r$, etc.) at random. This doesn't directly tell us what r is. We need a way to "see" the periodic structure of the state itself.

The following video explains this setup and highlights why we are stuck at this point without a new tool.

As the video concludes, we need a tool that can analyze a state with this periodic, "linearly shifted" structure and extract the period. That tool is the Quantum Fourier Transform.

2. The Quantum Fourier Transform: A "Rhythm Detector"

In your electrical engineering studies, you know the classical Fourier Transform is used to decompose a signal from the time domain into its constituent frequencies. It tells you "what frequencies are in this signal, and how strong are they?"

The Quantum Fourier Transform does something conceptually analogous for a quantum state. It transforms a state from the computational basis (states like |0>, |1>, etc.) into the Fourier basis, which is a basis of states defined by their phase.

For a deeper intuition, watch this explanation from the Qiskit team.

The QFT is essentially a phase-encoding machine. It takes a number represented in the computational basis and maps it onto a superposition of states where the original number is encoded in the phases of the qubits.

Now, how does this help us find the period r? Let's use an analogy.

As the article beautifully explains, the QFT acts as a "rhythm detector." Our periodic state $|\psi ⟩=|x_0⟩+|x_0+r⟩+\dots$ is like a complex jumble of sounds. The QFT performs an analysis on this state. Through quantum interference:

• The amplitudes corresponding to "frequencies" (or periods) that don't match our r will cancel each other out.
• The amplitudes corresponding to the correct "frequency" (which is related to 1/r) will constructively interfere and be amplified.

3. How QFT Reveals the Period

Let's put this all together. The quantum period-finding routine looks like this:

1. Preparation: Create the periodic superposition state $|\psi ⟩=\frac{1}{\sqrt{M}}{\sum }_k|x_0+kr⟩$ in the first register.
2. Transformation: Apply the Inverse Quantum Fourier Transform (IQFT) to this register. The IQFT is simply the QFT run in reverse. It transforms from the Fourier (phase) basis back to the computational basis.
3. Measurement: Measure the first register.

The magic is in what happens after the IQFT. Because our state $|\psi ⟩$ was periodic with period r, the IQFT transforms it into a new state where the measurement outcome is highly likely to be an integer multiple of $\frac{N}{r}$, where $N=2^n$ is the size of our register.

So, when we measure, we get a value m such that:

for some integer k.

Let's formalize this with the help of a lecture slide that introduces the concept of phase estimation.

Once we measure m, we have the equation $\frac{m}{N}\approx \frac{k}{r}$. Since we know m and N, we can use a classical algorithm called the continued fractions algorithm to find the fraction $\frac{k}{r}$ and from it, the period r. We won't delve into the classical continued fractions algorithm, but the key is that once we have m, the rest is straightforward classical post-processing.

Conclusion

In this lesson, we've uncovered the pivotal role of the Quantum Fourier Transform in Shor's algorithm. You saw that it's not just abstract mathematics, but a practical tool for extracting hidden periodic information from a quantum state.

Key Takeaways:

• After preparing the quantum system, the period r is encoded in a periodic superposition of states in an input register.
• Directly measuring this state is not useful, as it just returns a random term from the superposition.
• The Quantum Fourier Transform (QFT) is a tool that transforms a state from the computational basis to a phase-encoded "Fourier" basis. It acts like a "rhythm detector."
• In the period-finding routine, an Inverse QFT is applied to the periodic state. This causes constructive interference for states related to the period r.
• A final measurement then yields a value m that is approximately a multiple of $N/r$, from which the period r can be classically determined.

Preview of the Next Lesson:

We now understand what the QFT does conceptually and why it's essential for period-finding. But how is this powerful transform actually built? In our next lesson, we will get practical and implement the QFT circuit for a small number of qubits in Qiskit, constructing it from the basic Hadamard and controlled-rotation gates you've already seen.