The popular comparison — "quantum computers are exponentially faster than classical computers" — is wrong. Quantum computers are faster at a specific set of problems. For most computational tasks, quantum computers offer no advantage and are actually slower. Understanding the precise boundary between these regimes is essential for anyone building systems that might incorporate quantum computing.
The Right Framework: Computational Complexity
The field that rigorously characterizes what computers can and cannot compute efficiently is computational complexity theory. The relevant complexity classes:
P: Problems solvable in polynomial time on a classical deterministic computer. Sorting, shortest path, primality testing (since 2002), linear programming.
BPP: Problems solvable in polynomial time on a classical randomized computer with bounded error probability. Most practical randomized algorithms live here.
BQP: Problems solvable in polynomial time on a quantum computer with bounded error probability. This is the "quantum equivalent of BPP." BQP includes all of BPP (quantum computers can efficiently simulate classical randomized computation) and provably contains some problems outside BPP.
NP: Problems where solutions can be verified in polynomial time. TSP, SAT, protein folding (simplified models). Classical computers are believed to require exponential time to solve NP-hard problems in general.
The key relationships: We know P ⊆ BQP. We believe BQP ≠ NP (quantum computers do not solve NP-hard problems in general). The exact relationship between BQP and NP remains one of the central open questions in theoretical computer science.
What this means in practice: Quantum computers do not solve all hard problems. They solve specific problems in BQP that are believed to be outside BPP — the intersection of "hard for classical computers" and "tractable for quantum computers."
What Quantum Computers Are Faster At
Exponential speedup (proven):
Integer factorization — Shor's algorithm. Classical: sub-exponential O(exp(n^(1/3))). Quantum: polynomial O(n³). The problem underlying RSA security.
Discrete logarithm — Also Shor's algorithm variant. Breaks ECDSA.
Quantum simulation — Simulating quantum mechanical systems exactly. Classical: exponential in system size. Quantum: polynomial. Applications in chemistry, materials science, drug discovery.
Polynomial speedup (proven):
Unstructured search — Grover's algorithm. Classical: O(N). Quantum: O(√N). A quadratic, not exponential, speedup.
Collision finding — Finding two inputs with the same hash. Classical: O(N^(1/2)). Quantum: O(N^(1/3)). Relevant for hash function security.
Element distinctness — Determining if a list has duplicate elements. Classical: O(N log N). Quantum: O(N^(2/3)).
Potential speedup (active research, not proven):
Combinatorial optimization — QAOA may provide speedups over classical heuristics for specific problem classes. Not proven at scale.
Linear systems — HHL algorithm for sparse matrices. Exponential speedup in specific regimes, but significant caveats about data input/output.
Machine learning — Various proposals. Dequantization results show many proposed speedups are achievable classically. Active research area with no proven practical advantage yet.
What Quantum Computers Are NOT Faster At
This list is longer and more important for practical planning:
Sorting: No known quantum speedup. Classical O(N log N) lower bound applies to comparison-based sorting. Quantum computers cannot do better.
Graph traversal: BFS, DFS, Dijkstra's — no quantum speedup.
Database queries: Structured search in an indexed database is already O(1) or O(log N) classically. Grover's √N speedup does not improve on this.
Neural network training: No proven quantum speedup for gradient descent or backpropagation.
File I/O, network I/O: These are physical bottlenecks unaffected by computational model.
Most business logic: CRUD applications, web serving, data transformation — no quantum speedup.
NP-hard problems in general: Quantum computers do not solve TSP, SAT, or other NP-complete problems significantly faster than classical computers. Grover's gives a √N speedup, but this is not enough to escape exponential scaling.
The Memory Access Problem
A fundamental challenge for many proposed quantum speedups is the QRAM (Quantum Random Access Memory) assumption. Many QML and optimization algorithms assume quantum RAM: the ability to load N classical data points into a quantum superposition in O(log N) time.
No efficient physical implementation of QRAM exists today. Physical implementations require O(N) hardware components — eliminating the exponential speedup. This is not a temporary engineering limitation; it is a fundamental physical constraint.
Many exponential quantum speedups for ML and optimization are contingent on QRAM that may never exist at practical scale. Algorithms with proven speedups that do not rely on QRAM (Shor's, Grover's, quantum simulation) are on much firmer footing.
Practical Decision Framework
When should you consider quantum computing for a problem?
Yes, investigate quantum:
Your problem involves factoring or discrete logarithm (cryptography)
Your problem requires simulating quantum mechanical systems (chemistry, materials)
Your problem is an unstructured search over a database with no exploitable structure and N > 10¹²
Your problem is a combinatorial optimization over quantum-mechanical systems
No, do not expect quantum speedup:
Your problem is in P classically (sorting, shortest path, linear programming)
Your problem involves training neural networks on classical data
Your problem involves structured database queries
Your problem is NP-hard in general (quantum does not solve this)
Your problem requires QRAM for its claimed speedup
Monitor, not act:
Combinatorial optimization (QAOA claims)
Quantum machine learning on structured data
Financial modeling and Monte Carlo (some polynomial speedup claims)
The Practical Timeline
Application | Quantum speedup | Practical timeline |
|---|---|---|
Breaking RSA-2048 | Exponential | ~2033–2038 (fault-tolerant hardware) |
Quantum chemistry (drug discovery) | Exponential | ~2028–2033 |
Optimization heuristics (QAOA) | Unclear | ~2027–2032 |
General ML training | Not proven | Unknown / may not exist |
Sorting, search on structured data | None | Never |
The right mental model: quantum computing is a specialized accelerator for a specific class of problems, like how GPUs accelerate linear algebra. Most software does not need a GPU. Some software is transformatively better with one. The skill is knowing which is which.