Can quantum computers solve optimization problems faster?
Not today, and for most problems maybe never in a way that matters. As of August 2026, no quantum speedup has been shown on any real-world optimization job. The proven speedups are mostly quadratic (Grover-type), and the huge cost of error correction mostly cancels them out. The rule-of-thumb methods, QAOA and quantum annealing, have not beaten well-tuned ordinary solvers.
Yes on paper — but mostly quadratic, which is the problem Grover search gives a proven quadratic cut in the number of queries: the work shrinks to its square root. But an error-corrected quantum operation is roughly ten orders of magnitude slower and more costly than an ordinary 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 error-corrected machines. Look for quartic-or-better speedups instead. Those are rare in optimization.
Suggestive scaling evidence for one niche problem — not a practical win This result from JPMorgan, Argonne and Quantinuum is the strongest published evidence for QAOA. On one specific, deliberately hard problem, its measured scaling beats branch-and-bound, a standard exact method. The caveats matter. The evidence comes mainly from simulation. The speedup is modest (sub-quadratic). Fixed settings may not carry over to other problems. 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 repeats. An advantage claim appears. Then classical teams (EPFL, Flatiron and others) match or beat the result with better ordinary algorithms. Also watch for a switch in headlines. The strongest recent D-Wave result is a quantum <i>simulation</i> claim, often reported as if it were an <i>optimization</i> breakthrough. It is not one.
No — classical solvers remain the practical choice Say you are a developer with a scheduling, routing or portfolio problem in 2026. The answer is clear: use Gurobi, CPLEX, OR-Tools or a tuned heuristic. Independent tests find quantum and hybrid solvers competitive only when the problem already fits the machine's native QUBO format. They fall behind once constraints, non-binary variables or higher-order terms appear. That is what real problems look like.
Why is a quadratic speedup not enough?
Why care? Optimization means finding the best choice among a huge number of options. Think of planning delivery routes, work schedules or an investment mix. Companies spend real money on these problems. So a quantum speedup here would matter.
Grover's algorithm is real, proven math. It finds one marked item among N options in about √N steps. It does this by boosting the amplitude of the right answer through interference, over and over. An amplitude is a number that says how strongly the machine leans toward an answer. For optimization, this gives a quadratic speedup over brute force, which means trying every option. Quadratic means the work shrinks to its square root. A million tries become about a thousand.
The catch is the cost of each step. One logical step on an error-corrected quantum computer uses thousands of physical qubits and thousands of physical operations. That makes it roughly ten orders of magnitude (10^10 times) costlier than one instruction on a normal processor.
Work the numbers with a toy handicap first. Say each quantum step costs 1,000 ordinary steps. Brute force on N = 1,000,000 options takes 1,000,000 steps. Grover takes √1,000,000 = 1,000 quantum steps. Those cost 1,000 × 1,000 = 1,000,000 ordinary steps. That is a tie. Only bigger problems favour the quantum machine. Now use the real handicap of 10^10. The tie moves to where √N = 10^10, so N = 10^20. A quadratic speedup only beats that handicap at problem sizes where both computers would run for months.
And you rarely race brute force anyway. Real solvers use the problem's structure to skip most options. It is like solving a maze by ruling out dead ends instead of walking every path. Grover cannot use structure.
That is why serious quantum researchers say the search is for quartic-or-better speedups. Quartic means the work shrinks to its fourth root: a trillion (10^12) tries would become about a thousand. For optimization, almost none are known.
What about QAOA and quantum annealing?
Both are heuristics: rule-of-thumb methods with no proven speedup. They are judged only on how they do in practice.
QAOA, the quantum approximate optimization algorithm, runs a short circuit with adjustable angles. A normal computer tunes the angles so that interference piles up the chances of measuring good solutions. On today's hardware, noise flattens exactly the interference pattern the method depends on. It is like trying to hear a tune through heavy static. The best evidence for QAOA is the LABS scaling study above. It comes mostly from normal-computer simulation of perfect circuits, with only small error-detected hardware runs.
Quantum annealing takes a different route. The machine slowly changes its settings so that it settles into a lowest-energy state, and that state encodes the answer. Picture a ball rolling over a bumpy landscape and settling in the deepest dip. Unlike a real ball, the machine follows quantum rules. Even so, it can end up in a dip that is not the deepest. Annealing is analog, not gate-based. It has the longest commercial track record. After a decade of D-Wave machines, there is still no independently accepted case of annealing beating the best ordinary 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 change the verdict:
- A better-than-quadratic speedup for a problem people actually have. Theorists have looked hard. Candidates are rare and specialized.
- Much cheaper error correction. Suppose logical operations got 100–1000x cheaper than surface-code forecasts. (qLDPC codes are one live attempt.) Then quadratic speedups would start to matter at realistic sizes.
- Scaling advantages that hold up on real hardware at scale. Imagine the LABS result run on real qubits with hundreds of variables, still beating the best ordinary solver. That would be a true 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.