QFT vs. FFT: A Complexity Analysis

Hello! Let's continue our journey into foundational quantum algorithms.

In our last lesson, we successfully constructed the quantum circuit for the $n$-qubit Quantum Fourier Transform. We saw how the mathematical definition could be translated into a practical circuit using a sequence of Hadamard gates, controlled-rotations, and a final layer of SWAP gates.

Today, we will analyze the efficiency of that circuit. This is a critical step, as the QFT's power lies not just in what it does, but in how efficiently it does it. Our goal is to analyze the gate complexity of the Quantum Fourier Transform circuit and contrast its computational cost with the classical Fast Fourier Transform. This analysis will reveal the exponential quantum advantage that underpins algorithms like Shor's.

To align with your interest in cutting-edge research, we will also go beyond the standard textbook analysis and explore how complexity is measured in the context of fault-tolerant quantum computing, using a recent research paper on the topic.

1. Analyzing the QFT Circuit's Gate Complexity

Let's begin by counting the elementary gates in the $n$-qubit QFT circuit we constructed in the previous lesson. The total number of gates will give us a measure of the computational resources required, which we can then analyze asymptotically.

The circuit has three types of gates:

1. Hadamard gates: One is applied to each of the $n$ qubits.
2. Controlled-Rotation gates: The first qubit receives $n-1$ controlled rotations. The second receives $n-2$, and so on, down to the $(n-1)$-th qubit, which receives one. The last qubit receives none.
3. SWAP gates: To reverse the order of the qubits at the end, we need to swap qubit 1 with $n$, 2 with $n-1$, etc. This requires $\lfloor n/2\rfloor$ SWAP gates.

The following video provides a clear walkthrough of this gate counting process and derives the asymptotic complexity.

As the video explains, the total number of Hadamard and controlled-rotation gates is the sum of an arithmetic series:

$$\text{Number of H and C-ROT gates}=n+(n-1)+(n-2)+\cdots +1=\frac{n(n+1)}{2}$$

The number of SWAP gates is $\lfloor n/2\rfloor$.

Therefore, the total gate count is $\frac{n(n+1)}{2}+\lfloor n/2\rfloor$.

For large $n$, the dominant term is $\frac{n^2}{2}$. In big-O notation, we say the gate complexity of the QFT is $O(n^2)$. This means the number of gates grows quadratically with the number of qubits, $n$.

It's worth noting that each SWAP gate can be decomposed into three CNOT gates. This would change the constant factor but not the overall quadratic scaling, as the number of CNOTs would be $3\lfloor n/2\rfloor$, which is still $O(n)$.

2. The Classical Benchmark: DFT and FFT

To appreciate the QFT's efficiency, we must compare it to its classical counterparts: the Discrete Fourier Transform (DFT) and its optimized version, the Fast Fourier Transform (FFT). You've likely used FFT libraries extensively in your astrophysics work for tasks like analyzing time-series data from celestial objects or solving PDEs in simulations.

Let's formalize their complexity. We'll consider transforming a vector of $N$ complex numbers.

To summarize the key points from the reading:

• Discrete Fourier Transform (DFT): The straightforward implementation involves a matrix-vector multiplication. For a vector of size $N$, this requires $O(N^2)$ arithmetic operations.
• Fast Fourier Transform (FFT): This is not a different transform, but a highly efficient algorithm to compute the DFT. The most common version, the Cooley-Tukey algorithm, uses a divide-and-conquer approach. By recursively breaking down a transform of size $N$ into smaller transforms, it reduces the computational cost to $O(N\log N)$.

3. The Exponential Quantum Speedup

Now we can make the comparison. At first glance, comparing QFT's $O(n^2)$ complexity with FFT's $O(N\log N)$ might seem confusing. The key is to relate the number of qubits, $n$, to the size of the data vector, $N$.

An $n$-qubit register can represent $N=2^n$ basis states. This means the QFT acts on a Hilbert space of dimension $N$, analogous to the classical DFT acting on a vector of size $N$. The number of qubits $n$ is therefore related to $N$ by $n={\log }_{2}N$.

Let's re-express all complexities in terms of $N$:

Algorithm	Complexity (in its native variable)	Complexity (in terms of N)
Classical DFT	$O(N^2)$	$O(N^2)$
Classical FFT	$O(N\log N)$	$O(N\log N)$
Quantum FT	$O(n^2)$	$O((\log N{)}^2)$

The comparison is now stark. The QFT's complexity scales polynomially with the logarithm of the problem size $N$, while the best classical algorithm scales nearly linearly with N itself. This is an exponential speedup.

A Critical Caveat

There is a crucial subtlety here. The QFT transforms a quantum state $|\psi ⟩={\sum }_{j=0}^{N-1}{x}_j|j⟩$ into another quantum state $|\tilde{\psi }⟩={\sum }_{k=0}^{N-1}{\tilde{x}}_k|k⟩$, where $\{{\tilde{x}}_k\}$ is the DFT of $\{x_j\}$. The exponential speedup refers to the creation of the state $|\tilde{\psi }⟩$.

However, we cannot directly access all the $N$ amplitudes ${\tilde{x}}_k$. A measurement on the final state would yield only one outcome $k$ with probability $|{\tilde{x}}_k{|}^2$. To reconstruct the full Fourier spectrum with high precision would require preparing and measuring the state many times, erasing the exponential advantage.

This is why the QFT is not a universal replacement for the classical FFT. Its power is realized in algorithms where the structure of the problem allows us to extract the information we need from just a few measurements of the output state. Period-finding, the core of Shor's algorithm, is the canonical example.

4. A Deeper Dive: Complexity in Fault-Tolerant Quantum Computing

For a researcher like yourself, it's important to know that the simple $O(n^2)$ gate count is just the beginning of the story. On future fault-tolerant quantum computers, not all gates are created equal.

The standard universal gate set is Clifford+T. Clifford gates are relatively "easy" to implement fault-tolerantly, while the T-gate is "expensive," requiring a costly procedure called magic state distillation. Therefore, a more practical measure of complexity for large algorithms is the T-count (total number of T gates) and T-depth (number of sequential layers of T gates).

The controlled-rotation gates $R_k$ in the QFT circuit are not Clifford gates and must be decomposed into Clifford and T gates. Rotations by very small angles require a large number of T gates. This has motivated the development of the Approximate Quantum Fourier Transform (AQFT), where small-angle rotations are simply omitted, trading some accuracy for a significant reduction in T-count.

The following research paper is a great example of modern work in this area. It presents new circuit designs to reduce the T-count and T-depth of the AQFT.

As you read, note a few key ideas:

• The cost of the exact QFT in terms of T-gates is high, scaling as $O(n^2\log n)$.
• The AQFT, by removing rotations with angles smaller than a threshold, reduces this cost. The complexity of state-of-the-art AQFT circuits scales as $O(n\log (n/\epsilon ))$, where $\epsilon$ is the approximation error.
• This paper's contribution is to reduce the constant factors in this scaling, for instance, halving the T-count from $\sim 8n\log (n/\epsilon )$ to $\sim 4n\log (n/\epsilon )$.

This shift from a pure gate count $O(n^2)$ to a resource-aware T-count $O(n\log (n/\epsilon ))$ is a perfect illustration of the evolution from theoretical algorithm design to practical, hardware-aware circuit optimization. It shows that "complexity" is a nuanced concept that depends heavily on the underlying computational model and hardware constraints.

Conclusion

In this lesson, we have thoroughly analyzed the computational cost of the Quantum Fourier Transform and placed it in context.

Key Takeaways:

• The standard QFT circuit has a gate complexity of $O(n^2)$, where $n$ is the number of qubits.
• The best classical algorithm, the FFT, has a complexity of $O(N\log N)$, where $N$ is the number of data points.
• By relating $n=\log N$, we see that the QFT's complexity of $O((\log N{)}^2)$ is exponentially better than the FFT's.
• This speedup is conditional; it applies to the creation of the Fourier-transformed quantum state, and its utility depends on being able to extract the desired information with a few measurements.
• In the context of fault-tolerant quantum computing, the relevant complexity metrics are T-count and T-depth. This leads to the use of Approximate QFT (AQFT), whose complexity scales with both the number of qubits $n$ and the allowed error $\epsilon$, typically as $O(n\log (n/\epsilon ))$.

We now have a powerful and efficient tool in our arsenal. In our next lesson, we will put it to work by implementing the quantum phase estimation algorithm, which uses the inverse QFT to find the eigenvalue of a unitary operator. This algorithm is the engine that drives Shor's algorithm and has numerous other applications.