What quantum computers cannot do

You have watched a quantum computer factor numbers in polynomial time and search a haystack in a square root of the usual steps. It is tempting to extrapolate: throw any hard problem at it and it melts. This lesson is the hype filter. It draws the ceiling in numbers, and the ceiling is a lot lower than the headlines suggest.

Put a number on it

Before the algebra, feel the sizes. The ledger below compares the best known classical and quantum operation counts for three problems, on a log scale. Slide the problem size up and watch which quantum bars shrink to nothing and which stay stubbornly tall. Only one of the three collapses.

Why halving the exponent is not enough

Grover's algorithm gives a quadratic speedup: it turns $N$ queries into about $\sqrt{N}$. For an unstructured search over $N=2^n$ candidates that means

so a 100-bit search drops from $2^{100}$ to $2^{50}$. That is an enormous factor - and $2^{50}$ is still about a thousand trillion operations, for the small case. Double the problem to 200 bits and the quantum cost is $2^{100}$, back where the classical version started. An exponential with a halved exponent grows just as relentlessly; it only buys you a constant factor in the exponent, never a change of kind.^[1] And this is not a matter of finding a cleverer quantum algorithm later: for genuinely unstructured search, $\sqrt{N}$ is provably the best any quantum computer can do.^[3]

So the NP-complete problems, the ones that would reshape logistics, cryptography, and biology overnight, stay hard. Grover shaves their brute force from $2^n$ to $2^{n/2}$, and no general-purpose exponential quantum speedup for them is known or expected - consistent with the conjecture that NP-complete problems lie outside BQP. The classical picture of that wall is in the P versus NP lesson.

import math

def costs(n_bits):
    classical = 2 ** n_bits          # brute force over 2^n candidates
    grover = 2 ** (n_bits / 2)       # quantum: square root of that
    return classical, grover

for n in (50, 100, 200):
    c, g = costs(n)
    print(f"n={n}: classical 2^{n} = {c:.0e}, quantum 2^{n//2} = {g:.0e}")

# n=200 quantum cost 2^100 is where the n=200 classical run STARTED at n=100.
# Halving the exponent is a discount, not an escape from exponential growth.

Check yourself