Key Quantum Computing Algorithms

Why This Matters

Quantum computing algorithms sit at one of the most important intersections of physics and computation in this course. You're being tested not just on what these algorithms do, but on how they exploit quantum mechanical principles to achieve computational advantages that classical machines can't match. The three key principles at play: superposition, interference, and entanglement.

These algorithms connect directly to core concepts like unitary evolution, measurement, and quantum state manipulation. When you study Shor's algorithm, you're really studying the Quantum Fourier Transform. When you analyze Grover's algorithm, you're watching constructive and destructive interference do the heavy lifting. Don't just memorize what each algorithm solves. Know which quantum principle gives it power and why classical computers can't replicate that advantage.

---

Foundational Algorithms: Proving Quantum Advantage

These algorithms were designed to demonstrate that quantum computers can fundamentally outperform classical machines for specific problems. They exploit quantum parallelism and interference to solve problems with provably fewer operations than any classical approach.

Deutsch-Jozsa Algorithm

This was the first proof of quantum speedup. The problem: determine whether a black-box function is constant (same output for all inputs) or balanced (outputs 0 for half the inputs and 1 for the other half). Classically, you'd need up to $2^{n-1} + 1$ queries in the worst case. The quantum algorithm does it in exactly one query.

• Quantum parallelism lets the algorithm evaluate the function on all inputs simultaneously by preparing a superposition of all $2^n$ input states
• Interference between computational paths cancels out wrong answers, leaving only the correct classification after a single measurement

Simon's Algorithm

Simon's algorithm finds a hidden period (a secret bitstring $s$ such that $f(x) = f(y)$ if and only if $x \oplus y = 0$ or $x \oplus y = s$). It achieves an exponential speedup, requiring $O(n)$ quantum queries versus $O(2^{n/2})$ classically.

• Served as the direct precursor to Shor's algorithm, establishing the template for using quantum mechanics to solve period-finding problems
• Falls within the hidden subgroup problem framework, which captures a broad class of problems where quantum computers excel at detecting mathematical structure

---

Cryptographic Impact Algorithms

These algorithms have direct implications for information security and represent the most famous applications of quantum computing. They use the Quantum Fourier Transform to efficiently extract periodic information from quantum states.

Shor's Algorithm

Shor's algorithm factors integers in polynomial time, running in $O((\log N)^3)$. This directly threatens RSA encryption, which relies on the assumption that factoring large numbers is computationally intractable.

The core strategy converts factoring into a period-finding problem:

1. Choose a random integer $a < N$ and compute $\gcd(a, N)$. If this isn't 1, you've already found a factor.
2. Use quantum parallelism to evaluate $f(x) = a^x \mod N$ for all $x$ simultaneously in superposition.
3. Apply the Quantum Fourier Transform to extract the period $r$ of this function. The QFT converts the periodicity in the amplitudes into a sharp frequency peak that measurement can reveal.
4. Use the period $r$ classically to compute factors of $N$ via $\gcd(a^{r/2} \pm 1, N)$.

The quantum advantage comes from step 2 and 3: classical computers have no efficient way to extract the period from an exponentially large set of function values.

Quantum Fourier Transform

The QFT transforms quantum amplitudes into frequency space using only $O(n^2)$ gates, compared to $O(n \cdot 2^n)$ for the classical discrete Fourier transform applied to all $2^n$ amplitudes. It's the core subroutine in Shor's algorithm, phase estimation, and many other quantum algorithms.

The key: superposition allows the transform to act on all $2^n$ basis states simultaneously through a sequence of Hadamard gates and controlled phase rotations. Each qubit picks up phases conditioned on the states of other qubits, building up the Fourier coefficients in the amplitudes.

Quantum Phase Estimation

QPE extracts eigenvalues of unitary operators. Given a unitary $U$ and one of its eigenstates $|\psi\rangle$ with $U|\psi\rangle = e^{2\pi i\phi}|\psi\rangle$, QPE estimates the phase $\phi$ to precision $\epsilon$ using $O(1/\epsilon)$ controlled-$U$ operations.

• It works by applying controlled powers of $U$ (i.e., $U^{2^k}$) to encode the phase into ancilla qubits, then applying the inverse QFT to convert that phase information into a binary representation you can measure
• This is a gateway algorithm: it appears as a subroutine in HHL (for eigenvalue inversion), quantum chemistry simulations, and anywhere you need spectral information about a quantum operator

---

Search and Optimization Algorithms

These algorithms address problems where you're searching for solutions in large spaces. They use amplitude amplification, which means constructive interference on correct answers and destructive interference on wrong ones, to boost the probability of measuring a solution.

Grover's Algorithm

Grover's algorithm provides a quadratic speedup for unstructured search: it finds a marked item among $N$ possibilities in $O(\sqrt{N})$ queries, compared to $O(N)$ classically.

The mechanism is amplitude amplification through repeated application of two operations:

1. Oracle query: Flip the sign of the amplitude on the marked (target) state.
2. Grover diffusion operator: Reflect all amplitudes about their mean, which boosts the marked state's amplitude while suppressing the rest.

After roughly $\frac{\pi}{4}\sqrt{N}$ iterations, the marked state's amplitude is close to 1, and measurement yields the answer with high probability. This speedup is provably optimal: no quantum algorithm can do unstructured search faster than $O(\sqrt{N})$.

Quantum Walks

Quantum walks are the quantum analogue of classical random walks, using superposition to explore graph structures.

• The spreading behavior differs fundamentally: a quantum walk spreads linearly with time ($\propto t$), while a classical random walk spreads as $\sqrt{t}$
• For search on structured problems like spatial search on graphs and element distinctness, quantum walks achieve Grover-like speedups while naturally incorporating the problem's geometry

Quantum Approximate Optimization Algorithm (QAOA)

QAOA is a hybrid quantum-classical approach for combinatorial optimization problems (like MaxCut or satisfiability). The problem's constraints are encoded in a cost Hamiltonian $H_C$.

• The quantum circuit alternates between two operations: cost evolution $e^{-i\gamma H_C}$ and mixing evolution $e^{-i\beta H_M}$, where $H_M$ is typically a sum of single-qubit $X$ operators
• The parameters $\gamma$ and $\beta$ are optimized by a classical optimizer that receives measurement results from the quantum circuit and adjusts parameters to minimize the cost function
• Designed specifically for noisy intermediate-scale quantum (NISQ) devices with limited qubit counts and imperfect gates, making it one of the most practically relevant near-term algorithms

---

Quantum Simulation and Chemistry Algorithms

These algorithms tackle problems where quantum systems simulate other quantum systems, which was Feynman's original vision for quantum computing. They leverage the natural correspondence between qubit evolution and physical quantum dynamics.

Variational Quantum Eigensolver (VQE)

VQE finds ground state energies of quantum systems (especially molecules) by minimizing the energy expectation value:

$\langle\psi(\theta)|H|\psi(\theta)\rangle$

1. A parameterized quantum circuit (the ansatz) prepares a trial wavefunction $|\psi(\theta)\rangle$ on the quantum processor.
2. Measurements estimate the energy expectation value for the current parameters.
3. A classical optimizer updates the parameters $\theta$ to lower the energy.
4. Repeat until convergence. By the variational principle, the minimum energy found is an upper bound on the true ground state energy.

The main application is quantum chemistry: simulating molecular ground states relevant to drug discovery and materials science. Like QAOA, VQE is designed for NISQ hardware because the quantum circuits can be kept relatively shallow.

HHL Algorithm

The HHL algorithm solves linear systems $Ax = b$ with an exponential speedup, running in $O(\log N)$ time versus $O(N)$ classically. But this comes with important caveats.

• It uses phase estimation to decompose $|b\rangle$ in the eigenbasis of $A$, then inverts the eigenvalues (rotating ancilla qubits conditioned on each eigenvalue), effectively preparing $|x\rangle \propto A^{-1}|b\rangle$
• The critical readout limitation: if you need the full classical solution vector $x$, extracting all $N$ components destroys the exponential speedup. HHL is useful when you need global properties of $x$ (like an expectation value) rather than every individual entry
• The matrix $A$ must also be sparse and well-conditioned for the speedup to hold

---

Quick Reference Table

---

Self-Check Questions

1. Both Shor's algorithm and Simon's algorithm exploit period-finding. What quantum subroutine enables this in Shor's algorithm, and why can't classical computers efficiently replicate it?

2. Compare Grover's algorithm and quantum walks: what quantum mechanical principle do both exploit for speedup, and how does the type of problem they solve differ?

3. Why are VQE and QAOA called "hybrid" algorithms? What role does classical computation play, and why is this design choice important for current quantum hardware?

4. If an FRQ asks you to explain why Shor's algorithm threatens RSA encryption, what three quantum concepts must your answer include?

5. Quantum Phase Estimation appears as a subroutine in multiple algorithms on this list. Identify two that use it and explain what information QPE extracts in each case.