Building the n-Qubit QFT Circuit

Hello! Welcome to the next lesson in our exploration of foundational quantum algorithms.

In our previous lesson, we completed our study of Grover's algorithm by deriving its quadratic speedup. We saw how the algorithm could be understood geometrically as a rotation in a 2D vector space, and that this rotation is constructed from two reflections implemented by the oracle and the diffusion operator. This analysis gave us the optimal number of iterations and the famous $O(\sqrt{N})$ query complexity.

Today, we shift our focus to another monumental tool in quantum computation: the Quantum Fourier Transform (QFT). The QFT is the quantum analogue of the classical Discrete Fourier Transform (DFT), a tool you are likely familiar with from your work in astrophysics for signal processing and solving differential equations. The QFT is the core component that unlocks the exponential speedup in many crucial quantum algorithms, most notably Shor's algorithm for factoring.

Our learning outcome for this lesson is to: Construct the quantum circuit for the n-qubit Quantum Fourier Transform using Hadamard and controlled-rotation gates. We will derive the circuit from first principles, understanding how the mathematical definition of the QFT can be translated into a sequence of elementary quantum gates.

1. The Quantum Fourier Transform: Definition

The QFT is a linear transformation that acts on the basis states of a quantum register. For an $n$-qubit register, the Hilbert space has dimension $N=2^n$. The QFT is defined by its action on any computational basis state $|j⟩$, where $j$ is an integer from $0$ to $N-1$:

This transformation takes a single basis state $|j⟩$ and maps it into a superposition of all $N$ basis states. The amplitude of each $|k⟩$ component is a complex phase, specifically a root of unity, determined by the input $j$ and the output index $k$. When applied to an arbitrary quantum state ${\sum }_j{x}_j|j⟩$, the QFT transforms the amplitudes $x_j$ into their discrete Fourier transform.

For a deeper look at the formal definition and its relation to the classical DFT, please review the first section of the following document.

2. The Key to an Efficient Circuit: The Product Representation

The definition above, while precise, does not immediately suggest an efficient quantum circuit. A direct implementation would require an exponentially large unitary matrix. The breakthrough comes from rewriting the QFT in a different form—a product representation.

This representation expresses the output state as a tensor product of single-qubit states, where the phase of each qubit depends on the bits of the input number $j$. Let's represent the input state $|j⟩$ using its binary representation $|j_1{j}_2\dots j_n⟩$, where $j=j_1{2}^{n-1}+j_2{2}^{n-2}+\cdots +j_n{2}^0$.

The QFT can be rewritten as:

Here, the notation $0.j_l{j}_{l+1}\dots j_m$ represents the binary fraction $\frac{j_l}{2}+\frac{j_{l+1}}{4}+\cdots +\frac{j_m}{2^{m-l+1}}$.

This product form is the crucial insight. It shows that the output is not an entangled mess but has a separable structure that we can build up qubit by qubit. The derivation of this form is an elegant piece of algebra.

3. Constructing the QFT Circuit

As you saw in the reading, the product representation allows us to construct the circuit. Let's break down the process.

The circuit produces the terms of the product representation in reverse order, starting with the term that depends only on $j_n$ and ending with the term that depends on all bits $j_1,\dots ,j_n$.

The circuit consists of two main components:

1. Hadamard and Controlled-Rotations: For each qubit $k$ (from 1 to $n$), we apply a Hadamard gate, followed by a series of controlled-rotation gates controlled by the subsequent qubits.
2. SWAP Gates: The initial sequence of gates produces the correct qubit states but in the wrong order ($q_n,q_{n-1},\dots ,q_1$). A final layer of SWAP gates is needed to reverse the qubit order.

The Gates

• Hadamard (H): Creates the initial $|0⟩+|1⟩$ superposition.
• Controlled-Rotation ($R_k$): This is a controlled-phase gate that applies a phase $e^{2\pi i/2^k}$ to the target qubit if the control qubit is $|1⟩$. Its matrix is: $$R_k=\left(\begin{array}{cc}1& 0\\ 0& e^{2\pi i/2^k}\end{array}\right)$$ A controlled-$R_k$ gate from qubit $c$ to qubit $t$ applies the $R_k$ transformation to $t$ only if $c$ is in state $|1⟩$.

The General Circuit Structure

The following video provides a clear visual explanation of the general $n$-qubit QFT circuit, including the final swap operations.

To summarize the structure shown in the video and the reading:

1. On qubit 1: Apply H, then a controlled-$R_2$ from qubit 2, a controlled-$R_3$ from qubit 3, ..., up to a controlled-$R_n$ from qubit $n$.
2. On qubit 2: Apply H, then a controlled-$R_2$ from qubit 3, a controlled-$R_3$ from qubit 4, ..., up to a controlled-$R_{n-1}$ from qubit $n$.
3. ...
4. On qubit $k$: Apply H, then controlled-$R_j$ gates from qubits $k+j-1$ for $j=2,\dots ,n-k+1$.
5. On qubit $n$: Apply H.
6. Final Swaps: Apply $\lfloor n/2\rfloor$ SWAP gates to reverse the qubit order: swap qubit 1 with $n$, 2 with $n-1$, and so on.

4. A Concrete Example: 3-Qubit QFT

Let's solidify this with a 3-qubit example. The input is $|j_1{j}_2{j}_3⟩$.

The circuit proceeds as follows:

1. Qubit 1: H gate. Then, a controlled-$R_2$ (also called an S gate) from qubit 2. Then, a controlled-$R_3$ (also called a T gate) from qubit 3.
2. Qubit 2: H gate. Then, a controlled-$R_2$ from qubit 3.
3. Qubit 3: H gate.
4. Swaps: Swap qubit 1 and qubit 3.

The video below walks through this 3-qubit example, showing how an input state is transformed step-by-step.

Conclusion

In this lesson, we have successfully constructed the circuit for the n-qubit Quantum Fourier Transform. We moved from the formal mathematical definition to an efficient circuit implementation by leveraging the powerful product representation of the QFT.

Key Takeaways:

• The QFT maps a computational basis state into a uniform superposition where the phases encode the value of the input state.
• The key to an efficient circuit is the product representation, which expresses the QFT output as a tensor product of single-qubit states.
• The circuit is constructed using a repeating pattern of Hadamard gates and controlled-rotation gates ($R_k$).
• The initial gate sequence produces the output qubits in reverse order, necessitating a final layer of SWAP gates.
• The complete circuit for an $n$-qubit QFT consists of $n$ Hadamard gates, $n(n-1)/2$ controlled-rotation gates, and $\lfloor n/2\rfloor$ SWAP gates.

We have now built the circuit. The next logical step is to analyze its efficiency. In our next lesson, we will analyze the gate complexity of the Quantum Fourier Transform circuit and contrast its computational cost with the classical Fast Fourier Transform. This will reveal the source of the exponential speedup that makes algorithms like Shor's possible.