Quantum Computing Algorithms
Quantum Computing Algorithms
Quantum computers exploit superposition and entanglement to solve certain problems dramatically faster than any classical computer. Two of the most celebrated algorithms are Grover's search and the Quantum Fourier Transform (the backbone of Shor's factoring algorithm).
Grover's Search Algorithm
To find one marked item in an unsorted database of $N$ items, a classical computer needs $O(N/2)$ queries on average. Grover's algorithm needs only $O(\sqrt{N})$ queries — a quadratic speedup.
Starting with the uniform superposition, each iteration ("oracle + diffusion") rotates the amplitude toward the target state by angle $2\theta$ where $\sin\theta = 1/\sqrt{N}$:
$$P(\text{success after }k\text{ iterations}) = \sin^2\!\bigl((2k+1)\theta\bigr)$$
The optimal number of iterations is $k^* = \lfloor\frac{\pi}{4\theta}\rfloor \approx \frac{\pi}{4}\sqrt{N}$.
Quantum Fourier Transform
The QFT maps computational basis states to Fourier-transformed states:
$$\text{QFT}|x\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i \cdot xk/N} |k\rangle$$
Unlike the classical FFT which takes $O(N\log N)$ operations, the QFT acts on an $n$-qubit register with only $O(n^2)$ gates — exponentially faster. It is the key subroutine in Shor's factoring algorithm.
Quantum Speedup Comparison
The power of quantum algorithms becomes clear when comparing their scaling to classical algorithms for large $N$:
| Algorithm | Problem | Complexity |
|---|---|---|
| Brute force | Search / trial division | $O(N)$ |
| FFT | Discrete Fourier transform | $O(N\log N)$ |
| Grover | Unstructured search | $O(\sqrt{N})$ |
| Shor | Integer factoring | $O((\log N)^3)$ |