Quantum Algorithms
From oracle problems to exponential speedups -- the algorithms that define quantum advantage
2.1 The Deutsch-Jozsa Algorithm
The Deutsch-Jozsa algorithm was the first to demonstrate an exponential separation between quantum and deterministic classical computation for an oracle problem.
Problem Statement
Given a Boolean function $f: \{0,1\}^n \to \{0,1\}$ promised to be either:
- Constant: $f(x) = c$ for all $x$ (same output for every input)
- Balanced: $f(x) = 0$ for exactly half the inputs, $f(x) = 1$ for the other half
Determine which case holds. Classically, in the worst case, you need $2^{n-1} + 1$ queries. The quantum algorithm needs exactly one query.
The Algorithm
Starting from $|0\rangle^{\otimes n}|1\rangle$:
- Apply $H^{\otimes (n+1)}$: creates uniform superposition on first register, $|-\rangle$ on ancilla
- Apply oracle $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$
- Apply $H^{\otimes n}$ to first register
- Measure first register
After step 2, the phase kickback trick converts the oracle query into a phase:
$$\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle \otimes |-\rangle$$
After the final Hadamard, the amplitude of $|0\rangle^{\otimes n}$ is:
$$\langle 0^n | H^{\otimes n} \left(\frac{1}{\sqrt{2^n}} \sum_x (-1)^{f(x)}|x\rangle\right) = \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}$$
If $f$ is constant, this amplitude is $\pm 1$, so we measure $|0\rangle^{\otimes n}$ with certainty. If $f$ is balanced, the amplitude is 0, so we never measure $|0\rangle^{\otimes n}$.
2.2 Grover's Search Algorithm
Grover's algorithm (1996) provides a quadratic speedup for unstructured search, finding a marked item among $N$ unsorted elements in $O(\sqrt{N})$ queries instead of the classical $O(N)$.
Problem Setup
Given an oracle $O$ that marks the target state $|\omega\rangle$:
$$O|x\rangle = \begin{cases} -|x\rangle & \text{if } x = \omega \\ |x\rangle & \text{otherwise} \end{cases}$$
The Grover Iteration
Each Grover iteration (also called the Grover operator $G$) consists of two reflections:
- Oracle reflection: $O = I - 2|\omega\rangle\langle\omega|$ (phase flip on target)
- Diffusion operator: $D = 2|s\rangle\langle s| - I$ (reflection about the mean)
where $|s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle$ is the uniform superposition.
Geometrically, $G = DO$ is a rotation in the 2D plane spanned by $|\omega\rangle$ and $|s'\rangle$ (the superposition of non-target states). Each iteration rotates the state by angle $2\theta$ where:
$$\sin\theta = \frac{1}{\sqrt{N}}, \quad \text{so } \theta \approx \frac{1}{\sqrt{N}} \text{ for large } N$$
The optimal number of iterations is:
$$k^* = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor = O(\sqrt{N})$$
After $k^*$ iterations, the probability of measuring the target state is $\sin^2((2k^*+1)\theta) \approx 1$. This is provably optimal -- no quantum algorithm can do better than $\Omega(\sqrt{N})$ for unstructured search (Bennett et al., 1997).
Amplitude Amplification
Grover's algorithm generalizes to amplitude amplification: given any quantum algorithm$\mathcal{A}$ that produces a good state with probability $p$, we can boost the success probability to near 1 using $O(1/\sqrt{p})$ repetitions of $\mathcal{A}$.
2.3 Qiskit: Grover's Algorithm (3 Qubits)
Let us implement Grover's algorithm to search for the state $|101\rangle$ among 8 possibilities:
Click Run to execute the Python code
Code will be executed with Python 3 on the server
2.4 Quantum Fourier Transform
The Quantum Fourier Transform (QFT) is the quantum analogue of the discrete Fourier transform and a key subroutine in many quantum algorithms including Shor's. It maps:
$$\text{QFT}: |j\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle$$
The QFT on $n$ qubits can be implemented using $O(n^2)$ gates (compared to $O(n \cdot 2^n)$ for the classical FFT), giving an exponential speedup. The circuit uses Hadamard gates and controlled phase rotations:
$$R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}$$
The product representation of the QFT output reveals why it factorizes into single-qubit operations:
$$\text{QFT}|j_1 j_2 \cdots j_n\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{l=1}^{n} \left(|0\rangle + e^{2\pi i \cdot 0.j_{n-l+1}\cdots j_n}|1\rangle\right)$$
2.5 Quantum Phase Estimation (QPE)
Given a unitary $U$ and an eigenvector $|u\rangle$ with $U|u\rangle = e^{2\pi i\varphi}|u\rangle$, QPE estimates the phase $\varphi$ to $t$ bits of precision using $O(t)$ controlled-$U$ operations.
QPE Circuit Steps
- Initialize $t$ ancilla qubits in $|0\rangle$ and target in $|u\rangle$
- Apply Hadamards to all ancilla qubits
- Apply controlled-$U^{2^j}$ from ancilla qubit $j$ to the target register
- Apply inverse QFT to the ancilla register
- Measure the ancilla register to obtain $\tilde{\varphi} \approx 2^t \varphi$
After the controlled unitaries, the state of the ancilla register is:
$$\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i \varphi k} |k\rangle$$
The inverse QFT converts this to $|2^t \varphi\rangle$ when $\varphi$ is exactly representable in $t$ bits. For general $\varphi$, the probability of measuring the best $t$-bit approximation is at least $1 - \epsilon$ when using $t + \lceil\log(2 + 1/2\epsilon)\rceil$ bits.
2.6 Shor's Factoring Algorithm
Shor's algorithm (1994) factors an $n$-bit integer $N$ in time $O((\log N)^2 (\log \log N)(\log \log \log N))$, compared to the best known classical algorithm (General Number Field Sieve) at $O(e^{(\log N)^{1/3}(\log\log N)^{2/3}})$.
Reduction to Period Finding
The key insight is that factoring reduces to order finding: given a random $a < N$ with$\gcd(a, N) = 1$, find the smallest positive integer $r$ such that:
$$a^r \equiv 1 \pmod{N}$$
If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then at least one of $\gcd(a^{r/2} \pm 1, N)$ is a non-trivial factor of $N$. This succeeds with probability at least $1/2$ for a random choice of $a$.
Quantum Period Finding
- Prepare two registers: $|0\rangle^{\otimes 2n}|0\rangle^{\otimes n}$
- Apply QFT to first register: $\frac{1}{\sqrt{2^{2n}}}\sum_{x=0}^{2^{2n}-1}|x\rangle|0\rangle$
- Compute modular exponentiation: $|x\rangle|a^x \bmod N\rangle$
- Apply inverse QFT to first register
- Measure first register to get $s/r$ (via continued fractions)
Complexity Summary
Classical (GNFS):
$O\left(e^{1.9(\log N)^{1/3}(\log\log N)^{2/3}}\right)$
Quantum (Shor):
$O\left((\log N)^2 (\log\log N)(\log\log\log N)\right)$
For a 2048-bit RSA key, the classical approach is infeasible (estimated centuries of computation), while Shor's algorithm would need roughly 4000 logical qubits and millions of gates -- still beyond current hardware but a concrete future threat to public-key cryptography.
2.7 HHL Algorithm for Linear Systems
The Harrow-Hassidim-Lloyd (HHL) algorithm (2009) solves the linear system $A\vec{x} = \vec{b}$for a sparse, well-conditioned $N \times N$ Hermitian matrix $A$ in time:
$$O\left(\kappa^2 \frac{\log N}{\epsilon}\right)$$
where $\kappa$ is the condition number of $A$ and $\epsilon$ is the desired precision. Compare with the classical conjugate gradient method at $O(N\kappa\log(1/\epsilon))$ -- exponential speedup in $N$ when $\kappa = O(\text{poly}\log N)$.
Algorithm Outline
- Encode: Prepare $|b\rangle = \sum_i b_i |i\rangle$ in a quantum register
- QPE: Apply quantum phase estimation to extract eigenvalues $\lambda_j$ of $A$
- Eigenvalue inversion: Rotate an ancilla qubit conditioned on $|\lambda_j\rangle$ by angle $\arcsin(C/\lambda_j)$
- Un-compute: Reverse QPE to disentangle the eigenvalue register
- Post-select: Measure ancilla in $|1\rangle$ to obtain $|x\rangle \propto A^{-1}|b\rangle$
The state after eigenvalue inversion (before un-computation) is:
$$\sum_j \beta_j |\lambda_j\rangle |u_j\rangle \left(\frac{C}{\lambda_j}|1\rangle + \sqrt{1 - \frac{C^2}{\lambda_j^2}}|0\rangle\right)$$
Caveats
- - The output is a quantum state $|x\rangle$, not the classical vector $\vec{x}$
- - Reading all components of $\vec{x}$ requires $O(N)$ measurements, negating the speedup
- - Useful when only global properties of $\vec{x}$ are needed (e.g., expectation values)
- - Requires efficient quantum access to $A$ (e.g., sparse or structured)
- - The condition number $\kappa$ must be manageable; large $\kappa$ degrades performance
2.8 Quantum Complexity Classes
Quantum algorithms define a rich complexity-theoretic landscape:
- BQP (Bounded-error Quantum Polynomial time): problems solvable by a polynomial-time quantum computer with error $\leq 1/3$. Contains factoring and discrete log.
- QMA (Quantum Merlin-Arthur): the quantum analogue of NP. A quantum verifier checks a quantum proof. The Local Hamiltonian problem is QMA-complete.
- Known inclusions: $\text{P} \subseteq \text{BPP} \subseteq \text{BQP} \subseteq \text{PP} \subseteq \text{PSPACE}$
- Believed: $\text{NP} \not\subseteq \text{BQP}$ and $\text{BQP} \not\subseteq \text{NP}$(quantum computers probably cannot solve all NP problems efficiently, but can solve some problems outside NP efficiently).