Quantum Algorithms I: Quantum Fourier Transform and Shor's Algorithm

The quantum Fourier transform (QFT) stands as the cornerstone of quantum speedup in number-theoretic problems, enabling algorithms that are exponentially faster than any known classical counterpart. At its core, the QFT maps a quantum state $|x\rangle$ in the computational basis to its quantum analog of the discrete Fourier transform, but does so in a way that exploits quantum superposition and entanglement to achieve a gate complexity of $O(n^2)$ on $n$ qubits — in contrast to the classical fast Fourier transform (FFT) which requires $O(n \cdot 2^n)$ operations to transform a vector of $2^n$ components. This exponential compression of circuit depth is not magic; it arises from the fact that the quantum computer manipulates all $2^n$ amplitudes simultaneously through interference, whereas the classical computer must access and process each component sequentially.

The discrete Fourier transform (DFT) of a complex vector $(x_0, x_1, \ldots, x_{N-1})$ of length $N = 2^n$ produces the vector $(y_0, y_1, \ldots, y_{N-1})$ where $y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega_N^{jk}$ and $\omega_N = e^{2\pi i / N}$ is the primitive $N$-th root of unity. The QFT performs this transformation on the amplitudes of a quantum state: if the input is $|\psi\rangle = \sum_{j=0}^{N-1} x_j |j\rangle$, the output is $\sum_{k=0}^{N-1} y_k |k\rangle$ where the $y_k$ are exactly the DFT coefficients. The QFT circuit achieves this using only $n(n+1)/2$ Hadamard and controlled-phase gates — polynomial in $n$, versus the exponential number of arithmetic operations required classically.

Phase estimation is the algorithmic primitive that transforms the QFT from a mathematical curiosity into a computational weapon. Given a unitary operator $U$ and one of its eigenstates $|u\rangle$ with eigenvalue $e^{2\pi i \varphi}$, phase estimation determines $\varphi$ to $t$ bits of precision using $t$ ancilla qubits and $O(t^2)$ gates. This is the subroutine at the heart of Shor's algorithm, the HHL algorithm for linear systems, and quantum simulation of molecular Hamiltonians. The elegance of phase estimation is that it converts a continuous eigenvalue — the phase $\varphi$ — into a discretely readable integer via the QFT, allowing quantum measurement to extract classical information about a continuous quantum property.

Shor's algorithm, published by Peter Shor in 1994, was the watershed moment that convinced the scientific community that quantum computers could solve problems intractable for classical computers. The algorithm factors an integer $N$ in $O((\log N)^3)$ quantum gate operations — polynomial in the number of digits — versus the best known classical algorithm (the general number field sieve) which runs in $\exp(O((\log N)^{1/3} (\log \log N)^{2/3}))$, a sub-exponential but still superpolynomial time. For a 2048-bit RSA modulus, a classical computer would need longer than the age of the universe, while a fault-tolerant quantum computer would require hours to days.

The key insight of Shor's algorithm is that factoring reduces to period-finding. If we define $f(x) = a^x mod N$ for a randomly chosen integer $a$ coprime to $N$, this function is periodic with some period $r$ (called the order of $a$ modulo $N$). If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ yields a nontrivial factor of $N$ with high probability. The quantum period-finding step, which uses the QFT to extract $r$ from a superposition of function evaluations, is where the exponential speedup occurs. The classical post-processing using continued fractions is efficient and runs in $O((\log N)^2)$ time.

The hidden subgroup problem (HSP) provides the unifying algebraic framework for understanding when quantum algorithms beat classical ones. The QFT-based algorithms — Shor's, Deutsch-Jozsa, Simon's — all solve instances of the HSP over abelian groups. The problem asks: given a function $f: G \to S$ that is constant on cosets of a hidden subgroup $H \leq G$ and distinct on different cosets, find $H$. For $G = \mathbb{Z}_N$, this is exactly period-finding. Quantum computers solve the abelian HSP exponentially faster than any classical algorithm; the non-abelian case (which would crack graph isomorphism) remains open and is one of the great open problems in quantum complexity theory.

The threat to cryptography is concrete and quantified. RSA-2048 encryption, used to secure the majority of internet traffic, relies on the difficulty of factoring a 2048-bit semiprime. Running Shor's algorithm on RSA-2048 would require approximately 4,000 logical qubits and $O(10^{10})$ fault-tolerant gate operations. Given realistic error rates of physical qubits (around $10^{-3}$ per gate), achieving 4,000 logical qubits requires roughly 4 million physical qubits with surface code error correction. Current state-of-the-art machines have thousands of physical qubits with insufficient fidelity. The timeline to cryptographically relevant quantum computers is estimated at 10–20 years, but the "harvest now, decrypt later" threat — where adversaries collect encrypted data today to decrypt once quantum computers arrive — makes post-quantum cryptography (lattice-based, hash-based, code-based) an urgent priority.

Beyond cryptography, quantum simulation is the application where quantum advantage is clearest and most near-term. Simulating the quantum mechanics of a molecule with $n$ electrons requires a Hilbert space of dimension $2^n$ — classically intractable for $n \gtrsim 50$. The Jordan-Wigner mapping transforms fermionic creation and annihilation operators $\hat{a}_j^\dagger, \hat{a}_j$ into Pauli strings of length $O(n)$, allowing the molecular Hamiltonian to be represented as a sum of $O(n^4)$ Pauli terms acting on $n$ qubits. This allows quantum computers to simulate chemical reactions, find ground-state energies of catalysts, and design new materials with applications from drug discovery to battery technology — all in polynomial quantum resources versus exponential classical resources.