5 min read
On this page

Quantum Algorithms

Deutsch-Jozsa Algorithm

Problem: Given a function f: {0,1}^n -> {0,1} promised to be either constant or balanced, determine which with certainty.

Classical: Requires 2^{n-1} + 1 queries (worst case). Quantum: 1 query.

Circuit:

  1. Prepare |0>^n |1>, apply H^{n+1}
  2. Query oracle U_f: |x>|y> -> |x>|y XOR f(x)>
  3. Apply H^n to the first n qubits
  4. Measure first n qubits: all zeros iff f is constant

Mechanism: Phase kickback converts f(x) into phase (-1)^{f(x)}, then Hadamard interference distinguishes constant from balanced. This was the first algorithm demonstrating exponential quantum speedup (albeit for a contrived promise problem).

Bernstein-Vazirani Algorithm

Problem: Given oracle for f(x) = s . x (mod 2) for unknown s in {0,1}^n, find s.

Classical: n queries needed. Quantum: 1 query.

Circuit: Identical structure to Deutsch-Jozsa. Measurement yields s directly. The phase pattern (-1)^{s.x} across all x, after Hadamard, constructively interferes exactly at |s>.

Simon's Algorithm

Problem: Given f: {0,1}^n -> {0,1}^n with promise f(x) = f(y) iff x XOR y in {0, s}, find s.

Classical: Omega(2^{n/2}) queries (birthday bound). Quantum: O(n) queries.

Algorithm:

  1. Apply H^n to |0>^n, query oracle, measure second register
  2. First register collapses to uniform superposition over {x, x XOR s} for some x
  3. Apply H^n to first register, measure -- yields a random y satisfying y . s = 0
  4. Repeat O(n) times to collect n-1 linearly independent equations, solve for s

Simon's algorithm provided the conceptual template for Shor's algorithm. It gives an exponential speedup for a structured problem, bridging query complexity and algebraic structure.

Grover's Algorithm

Problem: Unstructured search -- find x* such that f(x*) = 1 among N = 2^n items.

Classical: O(N) queries. Quantum: O(sqrt(N)) queries. Provably optimal (BBBV lower bound).

Amplitude Amplification

Grover's algorithm is a special case of amplitude amplification:

  1. Initialize |psi> = H^n|0> (uniform superposition)
  2. Repeat R ~ (pi/4)*sqrt(N) times: a. Oracle: O|x> = (-1)^{f(x)}|x> (phase flip marked items) b. Diffusion: D = 2|psi><psi| - I (reflection about mean)
  3. Measure to obtain x* with probability close to 1

Geometric interpretation: Grover iteration is a rotation by angle 2*arcsin(1/sqrt(N)) in the 2D plane spanned by the marked and unmarked states. After ~(pi/4)*sqrt(N) rotations, the state aligns with the marked subspace.

Generalizations: Multiple marked items (k items -> O(sqrt(N/k)) queries), unknown number of solutions (quantum counting), amplitude amplification for arbitrary initial states (amplify any state with nonzero overlap with target).

Shor's Algorithm

Problem: Factor integer N in polynomial time. Classical best: sub-exponential (GNFS). Quantum: O((log N)^3) with quantum FFT.

Reduction to Period Finding

  1. Choose random a < N with gcd(a, N) = 1
  2. Find the order r of a modulo N: smallest r such that a^r = 1 (mod N)
  3. If r is even and a^{r/2} != -1 (mod N), then gcd(a^{r/2} +/- 1, N) yields nontrivial factors
  4. This reduction succeeds with probability >= 1/2; repeat if needed

Quantum Fourier Transform (QFT)

The n-qubit QFT maps |j> -> (1/sqrt(2^n)) sum_{k=0}^{2^n-1} e^{2piijk/2^n} |k>.

Implementation uses O(n^2) gates: Hadamards and controlled-R_k rotations (where R_k = diag(1, e^{2pii/2^k})). The QFT can be approximately implemented with O(n log n) gates by truncating small rotations.

Period Finding Circuit

  1. Prepare two registers: |0>^{2n} |0>^n (use 2n qubits for precision)
  2. Apply H^{2n} to first register
  3. Compute modular exponentiation: |x>|0> -> |x>|a^x mod N>
  4. Apply QFT^{-1} to first register
  5. Measure first register, obtain s/r approximation
  6. Use continued fractions to extract r from s/r

The modular exponentiation is the computationally expensive step, requiring O(n^3) elementary gates via repeated squaring.

Quantum Phase Estimation (QPE)

Problem: Given unitary U and eigenstate |u> with U|u> = e^{2pii*phi}|u>, estimate phi.

Circuit:

  1. t ancilla qubits initialized to |0>, target register in |u>
  2. Apply H to each ancilla
  3. Apply controlled-U^{2^j} from ancilla j to target, for j = 0, ..., t-1
  4. Apply QFT^{-1} to ancilla register
  5. Measure ancillas to obtain t-bit approximation of phi

Precision: t qubits give phi to t bits with success probability >= 1 - 1/(2(2^t - 2)). QPE is a subroutine in Shor's algorithm, HHL, quantum simulation, and quantum chemistry.

HHL Algorithm

Problem: Solve linear system Ax = b, where A is an N x N Hermitian matrix.

Approach: Given |b>, produce |x> proportional to A^{-1}|b>.

  1. Encode |b> into a quantum state
  2. Use QPE to decompose |b> in the eigenbasis of A: sum_j beta_j |lambda_j>|u_j>
  3. Perform controlled rotation to encode 1/lambda_j into an ancilla
  4. Uncompute QPE, measure ancilla
  5. Remaining state is proportional to sum_j (beta_j / lambda_j) |u_j> = |x>

Complexity: O(log(N) * s^2 * kappa^2 / epsilon) where s is sparsity, kappa is condition number, epsilon is precision. Exponential speedup in N over classical methods, but with caveats: requires efficient state preparation of |b>, the output is a quantum state (reading all components costs O(N)), and the dependence on kappa can negate the speedup.

Variational Quantum Eigensolver (VQE)

A hybrid quantum-classical algorithm for finding ground state energies, designed for near-term (NISQ) devices.

  1. Parameterize a trial state |psi(theta)> using a variational ansatz (hardware-efficient or chemically-inspired circuit)
  2. Measure expectation value E(theta) = <psi(theta)|H|psi(theta)> by decomposing H into weighted sum of Pauli strings
  3. Classical optimizer updates theta to minimize E(theta)
  4. Iterate until convergence

The variational principle guarantees E(theta) >= E_0 (ground state energy). Challenges include barren plateaus (exponentially vanishing gradients for deep random circuits), local minima, measurement noise, and ansatz expressibility.

QAOA (Quantum Approximate Optimization Algorithm)

Targets combinatorial optimization problems. For a cost function C encoded as a diagonal Hamiltonian H_C:

  1. Define mixing Hamiltonian H_B = sum_i X_i
  2. Prepare initial state |+>^n
  3. Apply p layers of: e^{-igamma_jH_C} followed by e^{-ibeta_jH_B}
  4. Measure in computational basis
  5. Classically optimize angles (gamma_1,...,gamma_p, beta_1,...,beta_p) to maximize

At p -> infinity, QAOA converges to the adiabatic algorithm and finds the exact optimum. For finite p, it provides approximation guarantees for certain problems (e.g., MaxCut on 3-regular graphs at p=1 achieves ratio >= 0.6924). QAOA can be viewed as a Trotterized version of quantum annealing.