Is the quantum Fourier transform exponentially faster than a classical transform, and is this why it can make difficult problems solvable by a quantum computer?

/ / Published in Quantum Information, EITC/QI/QIF Quantum Information Fundamentals, Quantum Fourier Transform, Properties of Quantum Fourier Transform

The quantum Fourier transform (QFT) occupies a central role in quantum information theory and quantum computing. Its design and implementation have profound implications for the efficiency of quantum algorithms, notably in problems where classical approaches are believed to be inefficient. To address whether the QFT is exponentially faster than its classical counterpart and whether this underpins the quantum advantage in solving certain computationally hard problems, it is essential to examine both the mathematical structure and computational complexity of the QFT and contrast these with the best known classical algorithms.

## The Classical Discrete Fourier Transform (DFT)

The classical discrete Fourier transform (DFT) is a mathematical operation mapping a vector of complex numbers to another vector of the same dimension, representing the frequency components of the original vector. The DFT of an N-dimensional vector x = (x_0, x_1, ..., x_{N-1}) is given by:

    \[ \tilde{x}_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}, \quad k = 0, 1, ..., N-1 \]

The naive implementation of the DFT requires O(N^2) time because each output element involves a sum over all N input elements, and there are N outputs.

However, the fast Fourier transform (FFT), a classical algorithm, reduces this complexity to O(N \log N) by recursively breaking down the DFT into smaller DFTs. The FFT is one of the most celebrated algorithms in computational science, underpinning applications from signal processing to numerical analysis.

## The Quantum Fourier Transform (QFT): Definition and Circuit Complexity

The quantum Fourier transform is the quantum analogue of the classical DFT, acting on quantum states. For an n-qubit system, where N = 2^n, the QFT is the linear operator defined by:

    \[ |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N} |k\rangle \]

for x in 0, 1, ..., N-1.

The implementation of the QFT as a quantum circuit is particularly efficient. It can be decomposed into a sequence of Hadamard gates and controlled phase shift gates. The depth and size of the circuit are both O(n^2), i.e., O((\log N)^2), where n is the number of qubits and N = 2^n is the dimension of the Hilbert space.

Detailed Circuit Description

For an n-qubit register, the QFT circuit typically consists of:

1. A Hadamard gate on the most significant qubit.
2. Controlled phase shifts between the most significant qubit and each less significant qubit, with phase e^{2\pi i/2^k} for the kth control.
3. Recursion on the remaining n-1 qubits.
4. A final reversal of the order of the qubits (swap gates).

The total gate count for an exact QFT is O(n^2). However, if a small error is tolerable (which is often sufficient for quantum algorithms), it is possible to approximate the QFT with accuracy \epsilon using only O(n \log n + \log n \log(1/\epsilon)) gates, further reducing the resource requirements.

Computational Complexity Comparison

– Classical FFT: O(N \log N) = O(2^n n)
– Quantum QFT: O(n^2) gates

Translating these complexities into the same units, the QFT operates in O(\log^2 N) quantum gates, whereas the FFT requires O(N \log N) classical operations. This is an exponential improvement in the number of basic operations required, at least relative to the input size measured in bits (n = \log N).

## Is the QFT Alone Exponentially Faster?

While the QFT can be implemented exponentially faster than the classical FFT when measuring resources by the number of basic quantum gates versus classical operations, it is important to analyze what this means for practical computation. The exponential speedup refers to the internal circuit complexity: the QFT maps an entire superposition of N amplitudes using only O(n^2) gates. However, quantum measurement collapses the quantum state to a single outcome, restricting the direct extraction of all output amplitudes.

If one is interested in computing all N output amplitudes of a QFT, this would not be faster on a quantum computer because only a single measurement outcome can be observed per run, and reconstructing the full spectrum would require exponentially many repetitions. Therefore, the exponential speedup is not in the computation of *all* output values, but in the transformation of quantum information within a quantum algorithm.

## The Role of QFT in Quantum Algorithms

The QFT is a key subroutine in several quantum algorithms that provide exponential or superpolynomial speedups over the best known classical algorithms. The most prominent example is Shor's algorithm for integer factorization.

Shor's Algorithm

Shor's algorithm uses the QFT to find the period of a function (period finding), which is then used to factor large integers. The algorithm proceeds as follows:

1. Prepare a uniform superposition over N states.
2. Compute a function f(x) = a^x \mod N in superposition.
3. Measure the second register, collapsing the state to a superposition of inputs that all map to the measured output.
4. Apply the QFT to the first register, which transforms the periodic structure into a superposition where measurement yields information about the period.
5. Use the measured result and classical post-processing (continued fractions) to recover the period and factor the integer.

The QFT is exponentially faster than the classical FFT in terms of the number of basic operations for the transformation. This efficiency is *important* for the polynomial-time performance of Shor's algorithm.

Hidden Subgroup Problems

The quantum Fourier transform is also central to the class of hidden subgroup problems (HSP), where the goal is to determine a hidden subgroup H of a group G given a function that is constant on the cosets of H and distinct on different cosets. Many problems of significant interest, such as discrete logarithms and certain graph isomorphism problems, can be cast in this form. The QFT enables the extraction of subgroup structure from quantum states, allowing for efficient solutions where classical algorithms are infeasible.

## Limitations and Misconceptions

It is important to recognize the subtleties in the statement that QFT is exponentially faster than classical FFT:

– Efficient Transformation, Not Efficient Sampling: The QFT efficiently transforms the quantum state, but a quantum computer cannot output the entire transformed state. Measurement yields a sample from the probability distribution defined by the squared amplitudes. For many applications, this is sufficient, as the quantum algorithm is designed to make the probability of measuring a useful answer high.
– Classical Output Reconstruction: If the goal is to compute and output all N Fourier coefficients classically, the QFT does not help; only a quantum sample can be obtained per run. As such, QFT's exponential efficiency is useful within quantum algorithms, not for direct classical computation of all transform values.
– Not All Problems: The QFT itself does not make all classically hard problems tractable. Its utility is specific to problem classes where quantum coherence and interference, in conjunction with the QFT, enable extraction of global properties (such as period) efficiently.

## Example: Order-Finding and Periodicity

Consider the problem of period finding, which underpins Shor's algorithm:

Suppose one is given a function f: \mathbb{Z}_N \to S that is periodic with period r, i.e., f(x) = f(x + r) for all x. The goal is to determine r.

Classically, finding r requires O(\sqrt{N}) evaluations of f in the worst case (for general functions). Quantumly, the process involves:

1. Preparing a uniform superposition \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle.
2. Computing f(x) in superposition: \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x)\rangle.
3. Measuring the second register yields a value y, entangling the first register to the subset of x with f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. Applying the QFT transforms this into a superposition sharply peaked at multiples of N/r. Measuring yields k such that k/N approximates a rational number with denominator r.
5. Classical post-processing allows recovery of r.

Here, the exponential efficiency of the QFT is critical: the transformation from periodicity in the time domain to peaks in the frequency domain is accomplished with polynomially many quantum gates, while a classical search would require exponential time in the number of input bits.

## Approximate Quantum Fourier Transform

In practical applications, especially as the number of qubits increases, it is often sufficient to use an approximate QFT. By omitting controlled-phase gates with very small angles, the QFT can be implemented with significantly fewer gates while maintaining high fidelity. This is particularly useful for NISQ (Noisy Intermediate-Scale Quantum) devices, where reducing gate count helps to mitigate the effects of noise and decoherence.

## Further Implications

The impact of the QFT extends beyond the specific algorithms already mentioned. In quantum phase estimation, a fundamental subroutine for algorithms solving problems such as eigenvalue estimation for Hamiltonians, the QFT is again a key element. The algorithm employs the QFT to extract phase information encoded in the amplitudes of a quantum state, enabling the estimation of eigenvalues exponentially faster than classical counterparts can achieve for certain problems.

Additionally, the QFT is fundamentally linked to the structure of quantum information processing, underlying the ability of quantum algorithms to exploit global properties and symmetries that are inaccessible to classical computation. This is particularly evident in quantum chemistry and simulation algorithms, where the QFT is used to switch between position and momentum representations efficiently.

## Concluding Remarks

The quantum Fourier transform is exponentially more efficient than the classical fast Fourier transform in terms of the number of quantum gates required relative to the input size expressed in qubits. This efficiency, however, is meaningful within the context of quantum algorithms, where the QFT enables the extraction of global periodic properties from quantum states using a number of steps polynomial in the number of qubits. While the QFT does not allow for the efficient computation of all output amplitudes as a classical list, its role within quantum algorithms is to efficiently manipulate and reveal structure in quantum information, leading to exponential or superpolynomial quantum speedups in problems such as factoring and hidden subgroup identification.

Other recent questions and answers regarding EITC/QI/QIF Quantum Information Fundamentals:

View more questions and answers in EITC/QI/QIF Quantum Information Fundamentals

More questions and answers:

Tagged under: , , , , ,