Quantum Algorithm

A step-by-step procedure for solving a problem using quantum computation, often providing speedup over classical algorithms.

A quantum algorithm is a procedure designed to run on a quantum computer. The best quantum algorithms exploit superposition, entanglement, and interference to solve problems faster than any known classical algorithm.

Anatomy of a Quantum Algorithm

Most quantum algorithms follow this pattern:

1. Initialize: Prepare qubits in |0⟩
2. Superpose: Create superposition (usually with Hadamards)
3. Compute: Apply problem-specific transformations
4. Interfere: Make correct answers constructive, wrong answers destructive
5. Measure: Extract the answer

The art is in step 4: designing interference patterns that amplify correct solutions.

Major Quantum Algorithms

Exponential Speedups

Algorithm	Problem	Speedup
Shor’s	Integer factoring	Exponential
HHL	Linear systems	Exponential*
Quantum simulation	Simulating quantum systems	Exponential

*With caveats about input/output

Polynomial Speedups

Algorithm	Problem	Speedup
Grover’s	Unstructured search	Quadratic
Quantum walks	Graph problems	Varies

Near-Term Algorithms

Algorithm	Application
VQE	Chemistry, materials
QAOA	Optimization
QML	Machine learning

What Makes Algorithms Quantum?

A quantum algorithm must use genuinely quantum resources:

Superposition: Process multiple states simultaneously
Entanglement: Create correlations impossible classically
Interference: Combine amplitudes to concentrate probability

Algorithms that don’t use these don’t provide quantum advantage.

Complexity Classes

Class	Description	Example Problems
BQP	Efficiently solvable by quantum computers	Factoring, simulation
QMA	Quantum analog of NP	Ground state energy

The Landscape

                    All Problems
                         │
          ┌──────────────┼──────────────┐
          │              │              │
    Classically     Quantum         Intractable
    Efficient      Advantage         for Both
    (P, BPP)        (BQP)              (?)
          │              │
    Sorting,       Factoring,
    Search         Simulation

Why So Few Algorithms?

Designing quantum algorithms is hard. We can’t just “quantize” classical algorithms. Each requires:

Finding structure in the problem
Designing interference to exploit that structure
Proving the speedup exists

New quantum algorithms are rare discoveries, celebrated by the community.

Quantum Jargon Decoder