Quantum Computers vs P vs NP: What Can They Actually Solve?

Chapter 1 — Classical complexity in one page

Recall from the flagship: P = deterministic polynomial time; NP = polynomial-time verifiable; NP-complete = hardest in NP via polynomial reductions; worst-case, asymptotic, decision-problem framing throughout. Quantum computing changes the machine model underneath those definitions — so every classical theorem must be re-asked, not assumed. This chapter's only job is to stop the reader importing classical intuitions into a model where information behaves differently.

Chapter 2 — Quantum computing foundations

A qubit is a two-level quantum system whose state is a unit vector α|0⟩ + β|1⟩ with |α|² + |β|² = 1; measurement yields 0 or 1 with those probabilities and destroys the superposition. Gates are unitary (reversible) transformations; circuits compose them; entanglement correlates multi-qubit states beyond any product of individual states. ESTABLISHED: these are physical facts with a precise linear-algebra model — and the model, not the mystique, is what algorithm designers exploit [2].

Chapter 3 — The complexity class BQP

FORMAL DEFINITION: BQP is the class of decision problems solvable by a uniform family of polynomial-size quantum circuits with error probability at most 1/3 (amplifiable toward 0 by repetition). ESTABLISHED relationships: P ⊆ BQP and BQP ⊆ PSPACE. OPEN: BQP versus NP in both directions — NP ⊄ BQP is widely believed, unproved; BQP ⊄ NP likewise. Anyone drawing you a tidy nested diagram of these classes without “unknown” labels is selling something.

Chapter 4 — Grover's algorithm

ESTABLISHED THEOREM (Grover, 1996; optimality by Bennett–Bernstein–Brassard–Vazirani): searching an unstructured space of N items takes Θ(√N) quantum queries versus Θ(N) classical. The mechanism is amplitude amplification: rotate the state vector toward the marked item by angle 2θ per iteration, succeeding with probability sin²((2m+1)θ). Quadratic is real and useful — and it turns 2^n into 2^(n/2), which is still exponential. The lab below computes the exact idealised probabilities; executing the same maths on your laptop confers zero quantum speedup, a distinction this article will keep making until it sticks.

import math
def grover_success(N, m):
    theta = math.asin(math.sqrt(1 / N))
    return math.sin((2 * m + 1) * theta) ** 2

print([round(grover_success(16, m), 3) for m in range(4)])
# [0.062, 0.473, 0.908, 0.961] (executed) - overshooting reduces success: timing matters

Chapter 5 — Shor's algorithm and factoring

ESTABLISHED THEOREM (Shor, 1994): integer factorization and discrete logarithms are in BQP — polynomial-time on a fault-tolerant quantum computer, via period-finding and the quantum Fourier transform. The caveat is load-bearing: no existing machine is anywhere near the fault-tolerant scale RSA-2048 requires (millions of physical qubits under current error-correction estimates, which themselves evolve). “In BQP” is a theorem about a model; “broken in practice” is an engineering forecast. Both matter; only one has happened.

Chapter 6 — Quantum computing and NP-complete problems

Apply Grover generically to SAT: √2^n = 2^(n/2) — exponential. Structured quantum approaches to SAT, TSP and friends are active research with no worst-case polynomial result, and oracle separations show any relativizing technique cannot give one cheaply. Quantum heuristics may help average instances (classical heuristics do too); a heuristic that wins benchmarks is not a complexity result — the exact confusion Chapter 14 of the flagship catalogues. What would change the picture: a polynomial-time quantum algorithm for an NP-complete problem (proving NP ⊆ BQP) — a breakthrough nobody has produced.

Chapter 7 — Quantum security implications

RSA and elliptic-curve cryptography fall to Shor on a future fault-tolerant machine; symmetric crypto mostly needs longer keys against Grover. NIST has standardized post-quantum algorithms and publishes migration guidance [1] — the rational response is inventory, agility and staged migration (“harvest now, decrypt later” makes delay itself a risk), not panic and not complacency. No claim is made here about any vendor's current hardware; check NIST and primary sources for the present tense, always.

Chapter 8 — Research frontiers

OPEN fronts: quantum query complexity separations, optimization algorithms with provable advantage, fault tolerance thresholds in practice, and classical simulation limits that keep redrawing the “quantum advantage” line. Conclusion: quantum algorithms establish real, specific speedups (factoring: exponential-class; search: quadratic), establish nothing that resolves P vs NP, and leave BQP vs NP as one of the great open questions. Explore the probabilities below — then state, out loud, which parts were mathematics and which were hardware. Only one of them ran on your machine.