Key Quantum Computing Algorithms

Why This Matters

Quantum computing algorithms represent one of the most profound intersections of physics and computation you'll encounter in this course. You're being tested not just on what these algorithms do, but on how they exploit quantum mechanical principles—superposition, interference, and entanglement—to achieve computational advantages impossible with classical machines. Understanding these algorithms demonstrates your grasp of quantum mechanics as a practical tool, not just an abstract theory.

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 seeing constructive and destructive interference in action. 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 primarily 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

• First proof of quantum speedup—determines whether a function is constant or balanced using just one quantum query versus up to $2^{n-1} + 1$ classical queries
• Quantum parallelism allows the algorithm to evaluate the function on all inputs simultaneously through superposition
• Interference between computational paths cancels out wrong answers, leaving only the correct classification

Simon's Algorithm

• Exponential speedup for finding hidden periodicities—requires $O(n)$ quantum queries versus $O(2^{n/2})$ classical queries
• Precursor to Shor's algorithm, establishing the template for period-finding problems using quantum mechanics
• Hidden subgroup problem framework demonstrates how 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

• Factors integers in polynomial time $O((\log N)^3)$—threatens RSA encryption, which relies on factoring being computationally hard
• Quantum Fourier Transform extracts the period of modular exponentiation, converting a number theory problem into a frequency analysis problem
• Quantum parallelism evaluates $f(x) = a^x \mod N$ for all $x$ simultaneously, then interference reveals the period

Quantum Fourier Transform

• Transforms quantum amplitudes into frequency space using $O(n^2)$ gates versus $O(n \cdot 2^n)$ classical operations
• Core subroutine in Shor's algorithm, phase estimation, and many other quantum algorithms—understand this, and you understand quantum speedup
• Exploits superposition to perform the transform on all $2^n$ basis states simultaneously through controlled phase rotations

Quantum Phase Estimation

• Extracts eigenvalues of unitary operators with precision $\epsilon$ using $O(1/\epsilon)$ controlled operations
• Combines controlled-U gates with the inverse Quantum Fourier Transform to encode phase information in measurable qubits
• Gateway algorithm for quantum chemistry, linear algebra, and simulation—appears as a subroutine in HHL, VQE applications, and more

---

Search and Optimization Algorithms

These algorithms address problems where you're searching for solutions in large spaces. They use amplitude amplification—constructive interference on correct answers, destructive interference on wrong ones—to boost success probability.

Grover's Algorithm

• Quadratic speedup for unstructured search—finds a marked item in $O(\sqrt{N})$ queries versus $O(N)$ classically
• Amplitude amplification through repeated application of the Grover diffusion operator rotates the state toward the solution
• Optimal bound—proven that no quantum algorithm can search faster than $O(\sqrt{N})$, making Grover's speedup the best possible

Quantum Walks

• Quantum analogue of random walks—exploits superposition to explore graph structures faster than classical random walks
• Spreading behavior differs fundamentally: quantum walks spread linearly with time versus classical $\sqrt{t}$ diffusion
• Search applications achieve Grover-like speedups on structured problems like spatial search and element distinctness

Quantum Approximate Optimization Algorithm (QAOA)

• Hybrid quantum-classical approach for combinatorial optimization—encodes problem constraints in a cost Hamiltonian $H_C$
• Alternating operators apply cost evolution $e^{-i\gamma H_C}$ and mixing evolution $e^{-i\beta H_M}$ with classically optimized parameters
• Near-term practical algorithm—designed for noisy intermediate-scale quantum (NISQ) devices with limited qubit counts

---

Quantum Simulation and Chemistry Algorithms

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

Variational Quantum Eigensolver (VQE)

• Finds ground state energies by minimizing $\langle\psi(\theta)|H|\psi(\theta)\rangle$ through classical optimization of quantum circuit parameters
• Ansatz circuits prepare trial wavefunctions; measurements estimate energy expectation values
• Quantum chemistry applications—simulating molecular ground states for drug discovery and materials science

HHL Algorithm

• Exponential speedup for solving linear systems $Ax = b$—runs in $O(\log N)$ time versus $O(N)$ classically, with important caveats
• Encodes solution in quantum amplitudes using phase estimation to invert eigenvalues: $|x\rangle \propto A^{-1}|b\rangle$
• Readout limitation—extracting full classical solution eliminates speedup; useful when you need properties of $x$, not $x$ itself

---

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 algorithms that use it and explain what information QPE extracts in each case.