Key Quantum Algorithms

Why This Matters

Quantum algorithms aren't just theoretical curiosities—they're the reason quantum computing matters at all. When you study these algorithms, you're learning why quantum computers can outperform classical machines and which problems they're actually good at solving. The core concepts you'll be tested on include quantum parallelism, interference and amplitude amplification, the quantum Fourier transform, and hybrid quantum-classical approaches. These principles appear repeatedly across different algorithms, so understanding the underlying mechanisms will serve you far better than memorizing individual steps.

Don't just memorize what each algorithm does—know how it achieves its speedup and what class of problems it addresses. Can you explain why Grover's algorithm offers only a quadratic speedup while Shor's achieves exponential? Do you understand why hybrid algorithms like VQE exist when we have "pure" quantum algorithms? These comparative questions are exactly what separates surface-level knowledge from exam-ready understanding. You've got this—let's break it down by concept.

---

Foundational Algorithms: Proving Quantum Advantage

These algorithms were designed primarily to demonstrate that quantum computers can fundamentally outperform classical ones. They exploit superposition and interference to extract global properties of functions with fewer queries than any classical approach could achieve.

Deutsch-Jozsa Algorithm

• Determines if a function is constant or balanced using just one quantum query—a problem that classically requires up to $2^{n-1} + 1$ evaluations in the worst case
• Quantum parallelism allows the algorithm to evaluate all possible inputs simultaneously through superposition
• Historical significance as the first algorithm to prove quantum speedup, even though the problem itself has limited practical applications

Simon's Algorithm

• Finds a hidden period in a function with only $O(n)$ quantum queries versus $O(2^{n/2})$ classical queries—an exponential speedup
• Introduced the period-finding framework that directly inspired Shor's algorithm and modern quantum cryptanalysis
• Black-box model demonstrates how quantum algorithms can extract hidden structure from functions without examining every input

---

The Quantum Fourier Transform Family

The quantum Fourier transform is the engine behind many of quantum computing's most powerful algorithms. It converts quantum states from the computational basis to the frequency domain, revealing periodic structures that would be exponentially hard to detect classically.

Quantum Fourier Transform

• Transforms quantum states into frequency domain in $O(n \log n)$ time versus $O(n \cdot 2^n)$ for the classical Fast Fourier Transform on the same problem size
• Core subroutine in Shor's algorithm, phase estimation, and the HHL algorithm—understanding QFT means understanding a huge chunk of quantum algorithms
• Cannot directly output results because measurement collapses the state; its power comes from enabling interference patterns that subsequent operations exploit

Quantum Phase Estimation

• Extracts eigenvalues of unitary operators by encoding phase information into a quantum register, then applying inverse QFT to read it out
• Precision scales with register size—using $n$ qubits gives eigenvalue estimates accurate to $2^{-n}$
• Critical building block for Shor's algorithm, HHL, and quantum simulation; if an exam asks about quantum subroutines, this is your go-to example

---

Cryptography and Number Theory

These algorithms target problems with direct implications for security and encryption. They leverage quantum parallelism and the QFT to find hidden mathematical structures exponentially faster than classical methods.

Shor's Factoring Algorithm

• Factors integers in polynomial time $O((\log N)^3)$, threatening RSA encryption which relies on factoring being computationally infeasible
• Reduces factoring to period-finding using modular exponentiation, then applies quantum phase estimation to find the period efficiently
• Most famous quantum algorithm and the primary driver of post-quantum cryptography research; if you remember one algorithm's implications, make it this one

HHL Algorithm for Linear Systems

• Solves linear systems $Ax = b$ exponentially faster than classical methods under specific conditions (sparse matrices, efficient state preparation)
• Combines phase estimation with controlled rotations to encode the solution in a quantum state's amplitudes
• Caveats matter for exams—the speedup only holds when you don't need to read out the full solution vector; practical applications require careful problem formulation

---

Search and Optimization

These algorithms tackle problems where you're searching for solutions in large spaces. Grover's algorithm uses amplitude amplification—a technique that constructively interferes "good" answers while destructively interfering "bad" ones.

Grover's Search Algorithm

• Quadratic speedup for unstructured search—finds a marked item in $O(\sqrt{N})$ queries versus $O(N)$ classically
• Amplitude amplification iteratively boosts the probability of measuring the correct answer through carefully designed interference
• Provably optimal for black-box search; no quantum algorithm can do better, which is why the speedup is "only" quadratic rather than exponential

Quantum Walk Algorithms

• Quantum analogues of random walks that spread across graphs quadratically faster due to interference effects
• Faster mixing and hitting times enable speedups in graph traversal, element distinctness, and certain search problems
• Two main types—discrete-time (using coin operators) and continuous-time (governed by graph Hamiltonians); both can achieve Grover-like speedups for structured problems

---

Hybrid Quantum-Classical Algorithms

Designed for near-term quantum devices with limited qubits and high error rates, these algorithms split the work between quantum and classical processors. The quantum computer evaluates a parameterized circuit, while a classical optimizer adjusts parameters to improve the solution.

Variational Quantum Eigensolver (VQE)

• Finds ground state energies of quantum systems using the variational principle: the measured energy is always ≥ the true ground state energy
• Parameterized quantum circuits (ansätze) generate trial wavefunctions; classical optimization tunes parameters to minimize energy
• Primary application in quantum chemistry—simulating molecular ground states for drug discovery and materials science

Quantum Approximate Optimization Algorithm (QAOA)

• Tackles combinatorial optimization problems like Max-Cut by alternating between problem-specific and mixing Hamiltonians
• Depth parameter $p$ controls solution quality—higher $p$ means better approximations but deeper circuits
• NP-hard problems are the target; while QAOA doesn't guarantee optimal solutions, it may find good approximations faster than classical heuristics

---

Quick Reference Table

---

Self-Check Questions

1. Both Shor's algorithm and Simon's algorithm achieve exponential speedup—what shared technique enables this, and how do their target problems differ?

2. Why does Grover's algorithm achieve only quadratic speedup while Shor's achieves exponential? What does this tell you about the role of problem structure in quantum advantage?

3. Identify two algorithms that use quantum phase estimation as a subroutine. What does phase estimation provide that makes it so widely useful?

4. Compare VQE and QAOA: What type of problem does each address, and why are both considered "near-term" algorithms suitable for current quantum hardware?

5. If asked to explain why quantum computers threaten RSA encryption but only weaken (not break) AES encryption, which two algorithms would you reference and what speedup does each provide?