Can quantum computers solve optimization problems faster?
Not today, and for most problems possibly never in a way that matters. As of August 2026 there is no demonstrated quantum speedup on any real-world optimization workload: the provable speedups are mostly quadratic (Grover-type), which error-correction overheads largely cancel, and the heuristics — QAOA and quantum annealing — have not beaten well-tuned classical solvers.
Yes on paper — but mostly quadratic, which is the problem Grover search gives a proven quadratic reduction in the number of queries. But an error-corrected quantum operation is roughly ten orders of magnitude slower and more expensive than a classical one, so quadratic gains only pay off at problem sizes where both machines would run for months or years. The Google team's conclusion: quadratic speedups will not deliver quantum advantage on early fault-tolerant devices; look for quartic-or-better speedups instead. Those are rare in optimization.
Suggestive scaling evidence for one niche problem — not a practical win This JPMorgan–Argonne–Quantinuum result is the strongest published evidence for QAOA: on one specific, deliberately hard problem, the empirical scaling exponent beats branch-and-bound. The caveats matter — the evidence is simulation-led, the speedup is sub-quadratic to modest, fixed parameters may not generalize, and the projected crossover point sits far beyond any machine that exists. It is a real scientific result, not a capability you can buy.
Annealing advantage claims — every one has drawn classical counter-fire D-Wave has sold annealers for over a decade, and the pattern is consistent: an advantage claim appears, then classical teams (EPFL, Flatiron and others) reproduce or surpass the result with better classical algorithms. Note also the bait-and-switch risk in headlines: the strongest recent D-Wave result is a quantum <i>simulation</i> claim, routinely reported as if it were an <i>optimization</i> breakthrough. It is not one.
No — classical solvers remain the practical choice For a developer with a scheduling, routing or portfolio problem in 2026, the answer is unambiguous: use Gurobi, CPLEX, OR-Tools or a tuned heuristic. Independent benchmarking finds quantum and hybrid solvers competitive only when the problem already fits the machine's native QUBO format, and degrading once constraints, non-binary variables or higher-order terms appear — which is what real problems look like.
Why is a quadratic speedup not enough?
Grover's algorithm is real, proven mathematics: it finds a marked item among N possibilities in about √N steps by repeatedly amplifying the amplitude of the right answer through interference. For optimization, that translates to a quadratic speedup over brute force.
The catch is constant factors. A logical operation on an error-corrected quantum computer involves thousands of physical qubits and thousands of physical operations per step — roughly ten orders of magnitude costlier than a CPU instruction. A quadratic speedup only overcomes a 10^10 handicap at problem sizes where both computers would run for months. And you rarely race brute force anyway: real classical solvers exploit problem structure, and Grover cannot.
That is why serious quantum researchers say the search is for quartic-or-better speedups — and for optimization, almost none are known.
What about QAOA and quantum annealing?
Both are heuristics: no proven speedup, judged entirely on empirical results.
QAOA runs a shallow parameterized circuit and classically tunes its angles so that interference concentrates measurement probability on good solutions. On today's hardware, noise flattens exactly the interference pattern the algorithm depends on. The best evidence for it — the LABS scaling study above — comes mostly from classical simulation of ideal circuits, with only small error-detected hardware runs.
Quantum annealing takes a different route (analog evolution toward a ground state encoding the answer) and has the longest commercial track record. After a decade of D-Wave deployments, there is still no independently accepted demonstration of annealing beating the best classical solver on a problem anyone needed solved.
Compare what current gate-based machines can actually run at hardware/qpus and hardware/compare, or try a small QAOA circuit in the lab.
What would have to change for the answer to change?
Any one of these would move the verdict:
- A super-quadratic speedup for a problem people actually have. The theory community has looked hard; candidates are scarce and specialized.
- Much cheaper error correction. If logical operations got 100–1000x cheaper than surface-code projections (qLDPC codes are a live attempt), quadratic speedups start mattering at realistic sizes.
- Empirical scaling advantages surviving on hardware at scale. The LABS result run on real qubits at hundreds of variables, still beating the best classical solver, would be a genuine landmark.
Until then, the honest summary for developers: quantum optimization is a research program, not a tool. See also does quantum computing speed up machine learning?
Classifications follow the QPU137 editorial policy: every applied label carries a date, source, scale, and hardware, or it does not render. Found an error? Report it.