The Algorithm Landscape

Quantum computers excel at specific problems: factoring integers, searching unsorted databases, simulating quantum systems, and solving certain linear algebra problems. They do not speed up everyday tasks like word processing or video streaming.

The key quantum advantages are: exponential speedup for period-finding (Shor), quadratic speedup for search (Grover), and exponential speedup for quantum simulation.

• •Exponential: Shor's factoring, quantum simulation, hidden subgroup problems.
• •Quadratic: Grover's search, amplitude amplification.
• •No speedup: Most NP-complete problems, sorting, general optimization.

BQP (Bounded-error Quantum Polynomial time) is the class of decision problems solvable efficiently by quantum computers. It contains P and is contained in PSPACE.

BPP (Bounded-error Probabilistic Polynomial time) is the classical analog. We know P ⊆ BPP ⊆ BQP, but the exact relationship between BQP and NP is unknown — one of the most important open problems in quantum computing.

Current quantum computers have too few qubits and too much noise to run most quantum algorithms at useful scales. However, quantum advantage demonstrations — solving a problem faster than any classical computer — have been achieved for specific sampling problems.

The path to practical quantum advantage involves scaling up qubit counts, reducing error rates, and developing better algorithms and error correction.

• •2019: Google Sycamore: Demonstrated quantum supremacy on a random circuit sampling problem.
• •2023: IBM Heron: 133-qubit processor with improved error rates.
• •Near-term: NISQ-era algorithms aim for advantage before fault tolerance.