Quantum annealing vs QAOA: two ways to solve the same QUBO, and how to choose
Quantum annealing and QAOA both minimise a QUBO or Ising cost by steering a transverse-field state toward the problem's low-energy states. Annealing does it as one continuous evolution on dedicated analog hardware such as D-Wave's; QAOA does it with layers of gates whose angles a classical optimiser tunes, on gate-based quantum computers or simulators. We ran one 14-asset QUBO through QAOA on a noiseless simulator and through classical simulated annealing, the baseline any annealer has to beat; no annealing hardware ran. Neither quantum method has shown a general advantage over classical solvers so far, and QAOA cannot run on a D-Wave annealer.
Updated
Quantum annealing and QAOA side by side
| Aspect | Quantum annealing | QAOA |
|---|---|---|
| Hardware | A dedicated analog machine (D-Wave): qubits whose couplings are set to the problem | Any gate-based quantum computer, or a classical simulator |
| How it searches | One slow, continuous change from a transverse field to the problem's Ising energy[1] | p alternating layers of cost and mixer gates, with 2p angles tuned in a classical loop[3] |
| What you tune | Annealing time and schedule, chain strength, the number of reads | Depth p, the optimiser and its budget, the initial angles, the number of shots |
| Connectivity | Fixed sparse graph, up to 15[6] couplers per qubit on Pegasus; denser problems need chains of physical qubits | Routing with SWAP gates on the chip's coupling map; quality fell on problems that did not match it[8] |
| Constraints | Penalties in the QUBO, and analog precision limits how large they can be | Penalties, or a mixer that keeps the constraint, such as the XY mixer for a fixed count[5] |
| Problem size today | Fully connected problems of at most 128[7] variables on a D-Wave Advantage1.1; sparse ones far larger | A few dozen qubits on an exact simulator; noisy hardware beyond that |
| In eigenkit | Not supported: no annealer, no D-Wave connection, no simulated annealing | QAOA on any QUBO or Ising model; see the QAOA page |
How the two methods are related
Both come from the same physics. A quantum annealer starts in the ground state of a transverse field, the equal superposition of all bitstrings, and turns the problem's energy on slowly; if the change is slow compared with the smallest energy gap on the way, the state ends in the problem's ground state[2]. QAOA starts from the same state and applies the same two Hamiltonians, but as discrete layers whose lengths are free parameters[3]. With many layers and small steps it can imitate an annealing schedule.
With optimised angles it can also do what annealing cannot. Zhou and colleagues found that QAOA learns non-adiabatic mechanisms that get around the small gaps on hard instances where adiabatic annealing fails[4]. That is a statement about ideal, simulated QAOA. On hardware, QAOA pays for every layer in gate errors, while an annealer pays in heat, noise and limited coupling precision, so neither ideal survives contact with a device intact.
The practical difference is the machine. An annealer is one kind of special-purpose hardware, sold as a cloud service, and runs nothing but annealing. QAOA is a program for general-purpose gate-based machines, which is why it runs on simulators and why it cannot run on a D-Wave system. How annealers sit beside superconducting, trapped-ion and neutral-atom gate machines is on the qubit types comparison.
Worked example: one QUBO, QAOA and simulated annealing
Pick 7 of 14 assets, written as one penalty QUBO with eigenkit. QAOA at on eigenkit's noiseless simulator, 1,024 shots; simulated annealing with dwave-samplers on a CPU, 1,000 sweeps and 100 reads. Mean of five seeds. No quantum annealer ran.
| Solver and penalty | P(optimum) per sample | Samples that break the constraint | Wall-clock |
|---|---|---|---|
| QAOA, provable penalty | 0.030% | 2.8% | 48 s |
| QAOA, tuned penalty | 0.101% | 37.5% | 63 s |
| Simulated annealing, provable penalty | 0.2% | 0.0% | 0.014 s |
| Simulated annealing, tuned penalty | 18.6% | 1.4% | 0.016 s |
| dimod reference sampler, default schedule | 0.0% | 72.0% | 3.6 s |
Run qaoa-portfolio-selection of 2026-11-03, mean and spread over 5 seeds, on Synthetic one-factor model of annualised returns and covariances, one instance per size (seed 100 + n). The provable penalty keeps the optimum feasible without knowing it; the tuned one was set from the brute-force answer and is not available on a real problem. A uniformly random valid portfolio is optimal with a chance of 1 in 3,432. Exhaustive search solves this instance exactly in milliseconds.
What the example shows about the two approaches
The penalty decides the outcome for both. With the provable penalty QAOA learned to hold seven assets but not which seven are best: its chance of the optimum matches a random pick among the 3,432 valid portfolios. Simulated annealing with the same penalty also stalled, for a different reason: moving between valid portfolios takes two bit flips, and the single flip in between breaks the constraint and climbs the penalty barrier. With a weaker, tuned penalty, simulated annealing found the optimum in a large share of reads in milliseconds, while QAOA's chance of the optimum stayed far lower after about 63 s of angle optimisation.
A real annealer would face the same formulation problem in a harder form, because it rescales every coefficient into a fixed analog range: a large penalty squeezes the objective's differences toward the hardware's precision, which a 2022 benchmark put at about 5 bits[7] for the couplings of a D-Wave Advantage1.1. We did not test this on hardware. The QUBO and Ising guide covers how to choose penalty weights.
On speed-ups, the record is thin for both. A study of a D-Wave Two on random spin glasses found no evidence of quantum speed-up[9], and one estimate puts a QAOA speed-up for MaxCut out of reach until several hundreds of qubits[10] are available. How annealers compare with simulated annealing and simulated bifurcation across published benchmarks is on the three-way comparison page.
What would change this comparison
On the QAOA side, the penalty is the first thing to change. A mixer that keeps the asset count fixed never leaves the valid portfolios, so there is no penalty to drown the objective[5], and it can be tested on a simulator before any hardware. With optimised angles, simulated QAOA has also found ways past the small energy gaps that stop adiabatic annealing[4]; whether that survives on a device depends on gate errors staying low enough for the depth it needs.
On the annealing side, our example says nothing yet, because no annealer ran. What would decide it is whether a dense penalty QUBO survives the hardware: the chains of physical qubits each variable needs on a sparse graph, and the coupling precision above. A sparser formulation, or hardware with finer couplings, would change what an annealer can show. The test is the same QUBO on the annealer and on tuned simulated annealing, with the same time budget.
For both, size is the last condition. At 14 variables exhaustive search takes milliseconds, so neither method can pay off; one estimate puts a QAOA speed-up for MaxCut at several hundreds of qubits[10] or more.
Choosing between them
Whichever you pick, write the QUBO once and solve it classically first, so you know what a quantum result has to beat.
Set the classical bar
Run an exact solver if the problem is small or a mixed-integer solver if it is not (see QAOA vs MILP), and simulated annealing on the same QUBO with a tuned schedule.
Pick quantum annealing to test large, sparse problems on hardware today
An annealer holds far more variables than any gate-based device runs QAOA on, and returns many samples per call. Check how many physical qubits the embedding uses and whether the coefficients survive the analog precision.
Pick QAOA for gate-based research and constraint-preserving mixers
QAOA runs on simulators, so you can study depth, angles and mixers exactly before touching hardware, and on any gate-based QPU afterwards. Report sampled shots, not the simulator's exact state.
Compare on the same instances and the same budget
Measure the time to reach a target cost, the share of samples that are optimal and the share that break constraints, for every solver including the classical ones.
Run it on a real QPU with EigenOrbit RouterThe QAOA side of the comparison: the circuit of your QUBO on a gate-based QPU, sampled for shots. Annealers are a different machine and are not part of it.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).
Questions
What is the difference between quantum annealing and QAOA?
Both minimise the same kind of cost, a QUBO or Ising model. Quantum annealing does it with one continuous physical evolution on a dedicated analog machine, such as a D-Wave annealer. QAOA does it with alternating layers of quantum gates whose angles a classical optimiser tunes, on a gate-based quantum computer or a simulator.
Can QAOA run on a D-Wave quantum annealer?
No. D-Wave annealers are not gate-based machines: they run annealing schedules, not circuits. QAOA needs a gate-based quantum computer or a simulator. The same QUBO can be sent to both, which is what makes them comparable.
Is QAOA a discretised version of quantum annealing?
It can be. With many layers and small angles, QAOA imitates a discretised annealing schedule. With optimised angles at low depth it can also use mechanisms that are not adiabatic at all, which on some hard instances let simulated QAOA get past small energy gaps where annealing fails.
Which is better for optimization, quantum annealing or QAOA?
Neither has shown a general advantage over classical solvers, so the better choice depends on what you want to test. Annealers hold larger problems today, especially sparse ones. QAOA runs on general-purpose gate-based machines and simulators and allows constraint-preserving mixers. In our worked example, classical simulated annealing did far better than QAOA on the same QUBO; no quantum annealer ran.
Does either quantum annealing or QAOA have a proven speed-up?
No. Benchmarks of annealers have found no general speed-up over classical heuristics, and studies of QAOA estimate that a speed-up on problems such as MaxCut needs hundreds of qubits or more. The positive results so far are limited to particular problem families and, for QAOA, to noiseless simulation.
Do I need quantum hardware to compare them?
For QAOA, no: a simulator runs it exactly on small problems, as in the example on this page. For quantum annealing, yes, because only annealing hardware does it; classical simulated annealing is the baseline to compare it against, not a substitute.
Sources
- T. Kadowaki, H. Nishimori. Quantum annealing in the transverse Ising model. Physical Review E 58, 5355, 1998. arXiv:cond-mat/9804280.
- E. Farhi, J. Goldstone, S. Gutmann, M. Sipser. Quantum computation by adiabatic evolution. arXiv preprint, 2000. arXiv:quant-ph/0001106.
- E. Farhi, J. Goldstone, S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. arXiv:1411.4028.
- L. Zhou, S.-T. Wang, S. Choi, H. Pichler, M. D. Lukin. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Physical Review X 10, 021067, 2020. arXiv:1812.01041.
- S. Hadfield, Z. Wang, B. O'Gorman, E. G. Rieffel, D. Venturelli, R. Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12, 34, 2019. arXiv:1709.03489.
- K. Boothby, P. Bunyk, J. Raymond, A. Roy. Next-generation topology of D-Wave quantum processors. arXiv preprint, 2020. arXiv:2003.00133.
- M. Kowalsky, T. Albash, I. Hen, D. A. Lidar. 3-regular 3-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quantum Science and Technology 7, 025008, 2022. arXiv:2103.08464.
- M. P. Harrigan, K. J. Sung, M. Neeley, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics 17, 332–336, 2021. arXiv:2004.04197.
- T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, M. Troyer. Defining and detecting quantum speedup. Science 345, 420, 2014. arXiv:1401.2910.
- G. G. Guerreschi, A. Y. Matsuura. QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Scientific Reports 9, 6903, 2019. arXiv:1812.07589.
Run it yourself with eigenkit
eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.
$ pip install eigenkit