ComparisonQuantum Computing
Quantum optimization vs classical solvers: a fair way to compare them
For scheduling, routing and portfolio problems, quantum optimization should be compared with mature classical solvers on your own instances, measuring solution quality against end-to-end wall-clock time and cost, with repeated runs. On today's noisy hardware the classical baseline usually wins, so the useful question is whether a quantum or quantum-inspired method is worth a bounded prototype. This page compares the approaches and sets out a benchmarking protocol that avoids flattering either side.
On this page
Five optimization approaches side by side
Each column is a family of methods a team might put on the shortlist for a combinatorial problem such as vehicle routing, shift scheduling or asset allocation.
| Question | Exact MIP solvers | Heuristics and metaheuristics | Quantum-inspired algorithms | Quantum annealing | Gate-based variational (QAOA) |
|---|---|---|---|---|---|
| How the problem is expressed | Linear objective with integer and continuous variables and explicit constraints | Problem-specific moves, often directly on the business model | Usually a QUBO or Ising model solved on classical hardware | QUBO or Ising model with constraints turned into penalty terms | QUBO or Ising cost encoded as a parameterized circuit |
| What you get back | A solution with a proven optimality gap | Good solutions fast, with no optimality proof | Good solutions, no proof | A distribution of low-energy samples | Samples from a circuit tuned by a classical optimizer |
| Maturity today | Decades of engineering and commercial and open-source solvers | Mature and widely deployed in operations | Runs on CPUs and GPUs today | Available on specialized hardware with limited connectivity | Limited by noise and circuit depth on current devices |
| Main overhead | Model building and solve time on hard instances | Tuning and maintaining custom code | Reformulation into QUBO form | Penalty tuning and minor embedding onto hardware | Parameter optimization loops and repeated circuit runs |
| Where it is weaker | Very large or highly nonlinear instances within tight time limits | No guarantee of how far from optimal a solution is | Gains often shrink against tuned classical heuristics | Large problems need many physical qubits per variable | Current devices handle only small instances |
| Sensible role in a benchmark | The reference for quality and the gap | The practical baseline for speed | A control that separates the formulation from the hardware | A candidate if the problem maps naturally to QUBO | A research candidate tested mainly on simulators |
Cells summarize general characteristics, not measured results. The mapping of many NP-hard problems to Ising form is described by Lucas3; QAOA was introduced by Farhi, Goldstone and Gutmann2.
Why the classical baseline is harder to beat than vendor demos suggest
Mixed-integer programming solvers have been refined for decades, and the MIPLIB library exists precisely as a standard test set for comparing them6. Around them sit decomposition methods, local search, tabu search and simulated annealing, many already embedded in planning software your team may own. Any quantum result has to clear that whole field, not a textbook greedy algorithm.
Two rows of the table decide most comparisons. The first is formulation cost. Annealers and QAOA need a quadratic unconstrained binary model, so capacity limits, time windows and precedence rules become penalty terms whose weights must be tuned, and integer variables expand into many binary ones. On annealing hardware, each logical variable may then need a chain of physical qubits to fit the device's connectivity, a step known as minor embedding4. The model that reaches the hardware can be much larger than the business problem.
The second is what counts as time. A fair clock starts when the business data arrives and stops when a feasible, validated schedule is ready. That includes QUBO construction, embedding, queueing for a shared device, repeated sampling and repairing infeasible samples. Rønnow and colleagues showed how definitions of speedup can create or hide an apparent advantage, and found no evidence of speedup on the annealer they tested5.
A benchmarking protocol that is fair to both sides
Fix the decision and acceptance criteria
Write down which business decision the benchmark informs, the time budget a real planner would accept and the quality threshold that would justify a pilot. Agree these before any run.
Assemble a representative instance set
Use real historical instances at production sizes, smaller cut-downs that fit current quantum hardware, and public instances for calibration. Record which instances each method can and cannot attempt.
Tune the strongest classical baseline
Run a commercial or open-source MIP solver and a tuned heuristic with the same time budget. Give the classical side the engineering effort you give the quantum side.
Formulate and validate the QUBO
Build the quadratic model, tune penalty weights and check on small instances that its optimum matches the original problem's optimum. Report the variable and interaction counts after formulation and after embedding.
Run each method repeatedly
Quantum and stochastic methods return different answers each run, so repeat runs, report distributions rather than best cases and measure time to reach a target quality with a stated probability.
Report end-to-end time, cost and noise sensitivity
Compare wall-clock time from data to validated solution, the cost per solve at expected volumes, and how results degrade under hardware noise or simulator noise models.
A delivery-routing problem benchmarked across approaches
Stop, watch or prototype: reading the benchmark
- If
Classical methods meet the time and quality targets on production-sized instances
ThenStop the quantum track for this problem and record the instance sizes and gap at which you would re-test.
There is no business gap for any new method to close.
- If
Classical methods miss targets on large instances, and a quantum-inspired solver closes part of the gap
ThenPursue the quantum-inspired option on classical hardware first, and keep the QUBO formulation ready for hardware re-tests.
It captures the formulation benefit without hardware queueing, noise or access cost.
- If
Quantum runs match the classical baseline on small instances but cannot reach realistic sizes
ThenWatch: re-run the same protocol when hardware qubit counts, connectivity or error rates change materially.
A fixed protocol makes future results comparable instead of anecdotal.
- If
A quantum method beats tuned classical methods on end-to-end time or quality at a size that matters
ThenPrototype a bounded hybrid workflow with independent replication of the result before any production commitment.
Claims of advantage are contested and should survive a second, independent run.
Questions and answers
Has quantum optimization beaten classical solvers on a real business problem?
Published claims of quantum advantage in optimization are disputed, and results on benchmark instances do not transfer automatically to business problems with many side constraints. ColdAI does not promise quantum advantage1. The defensible position for any team is to test on its own instances against tuned classical methods, using the protocol on this page, and treat any positive result as needing independent replication.
How large an optimization problem can today's quantum hardware handle?
It depends less on the headline qubit count than on what survives formulation and noise. Penalty terms and binary encodings enlarge the model, embedding can consume several physical qubits per variable, and circuit depth is limited by errors. AWS notes that no universal fault-tolerant quantum computer exists yet8. In practice, test the largest instance you can run after formulation, then compare it with your production size.
Do we need our own quantum hardware to run an optimization benchmark?
No. Simulators and cloud-accessible quantum hardware are enough for screening and prototyping. Amazon Braket, for example, offers managed circuit simulators and on-demand access to several types of quantum computers without upfront commitment8. Owning hardware only makes sense for organizations doing hardware research.
Which optimization problems are worth screening for quantum methods at all?
Problems that are binary or naturally quadratic, such as selection, assignment and some portfolio formulations, map most directly. Problems with many hard constraints, long time horizons or mostly continuous variables usually suffer large formulation overhead. Screening should also require that the current classical solution is falling short of a business target; otherwise there is nothing to improve.
Sources
- Quantum Computing: prepare for quantum on two fronts — ColdAI
- A Quantum Approximate Optimization Algorithm — Edward Farhi, Jeffrey Goldstone and Sam Gutmann (arXiv) · checked 10 October 2026
- Ising formulations of many NP problems — Andrew Lucas (arXiv) · checked 10 October 2026
- Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem — Vicky Choi (arXiv) · checked 10 October 2026
- Defining and detecting quantum speedup — Rønnow et al., Science (arXiv preprint) · checked 10 October 2026
- MIPLIB: the Mixed Integer Programming Library — Zuse Institute Berlin · checked 10 October 2026
- A quantum-inspired classical algorithm for recommendation systems — Ewin Tang (arXiv) · checked 10 October 2026
- What is Amazon Braket? — Amazon Web Services · checked 10 October 2026
- Qiskit — IBM · checked 10 October 2026
- Cirq — Google Quantum AI · checked 10 October 2026