QAOA in practice: how to write a real problem for it, what to compare it with and how to read the results
QAOA, the quantum approximate optimization algorithm, is a gate-based heuristic for problems written as a QUBO or Ising model: a circuit proposes bitstrings and a classical optimiser tunes its angles. On a real problem the hard parts are the constraints, which the standard mixer does not respect, and the comparison, which exact classical solvers win at every size a simulator can reach. We ran it on a 14-asset portfolio selection on a noiseless simulator: with a safe penalty, QAOA learned to keep the constraint but picked the best portfolio about as often as a random valid choice. The rules below come from that run, and they apply to any constrained QAOA test you run yourself.
Updated
At a glance
- What it is
- A variational circuit, or ansatz, of p alternating cost and mixer layers, with 2p angles tuned by a classical optimiser[1]
- Input
- A QUBO or Ising model: one qubit per binary variable, plus slack qubits for every inequality constraint
- Proven guarantee
- At on 3-regular MaxCut, a cut of at least 0.6924[1] times the optimum; quality improves as p grows
- Where a speed-up might start
- MaxCut needs several hundreds of qubits[4] before QAOA could beat classical solvers, by one simulation-based estimate
- Our 14-asset run, safe penalty, p = 5
- Probability of the optimal portfolio per shot 0.030%, about the rate of a random pick among the 3,432 feasible portfolios
- In eigenkit
- QUBO and Ising classes, exact brute_force(), and QAOA with the standard X mixer only: no constraint-preserving mixer, no warm start
What the eigenkit docs cover, and what this page adds
The mechanics are in the eigenkit docs: the cost Hamiltonian, the p-layer loop and the optimiser are in QAOA: how it works, and the MaxCut example shows how depth raises the approximation ratio on a six-node graph. MaxCut is the friendly case: every bitstring is a valid answer, so the circuit only has to rank them.
Real problems carry constraints: pick exactly K assets, assign every job once, stay under a budget. QAOA with the standard mixer has no notion of a constraint, so the constraint goes into the cost as a penalty, and the penalty changes what QAOA learns. This page follows one such problem end to end, a K-of-N portfolio selection that we ran at 6 to 14 assets against exact and classical solvers, and turns what went wrong into rules for writing, comparing and reporting a QAOA run.
Writing a constrained problem for QAOA
The general QUBO recipe is in the QUBO and Ising guide. These are the points where QAOA adds its own trouble.
Count the qubits before anything else
One qubit per binary decision. An equality such as needs no extra qubits; an inequality such as a budget cap needs slack bits, about of its range, and each one doubles the state the simulator holds. eigenkit's exact simulator holds all amplitudes, so problems stay at a few dozen variables.
Decide how the constraint is enforced
There are two ways. A penalty in the cost works with any mixer. A constraint-preserving mixer, such as the XY mixer that swaps a 1 and a 0 and so keeps the Hamming weight fixed, never leaves the feasible set[2]. eigenkit has only the transverse-field X mixer, so on eigenkit the penalty is the only option.
Choose the penalty weight without knowing the answer
A weight that provably keeps the optimum feasible follows from a bound: flipping one bit changes the objective by at most for the portfolio, so a weight at least that large means no infeasible bitstring undercuts the best feasible one. That safe weight is also large, and it is the setting a real run would use.
Scale the coefficients
QAOA's angles act on the energies, so divide the QUBO by its largest coefficient. This does not move the optimum. It shows the problem: after scaling, the penalty terms are of order one and the differences between feasible portfolios are small fractions of that, which a few layers cannot resolve.
Check the formulation exactly before running QAOA
On up to about 20 variables, QUBO.brute_force() returns the exact minimum. If it is not the constrained optimum you get from enumerating feasible answers, the penalty is too weak, and no solver will fix it. The docs' check-the-answer step does the same for MaxCut.
Consider a better start instead of more depth
Warm-starting QAOA from the solution of a continuous relaxation lets it inherit the relaxation's guarantee, and the authors found it most useful at low depth[3]. eigenkit does not implement it; you would write the initial state yourself.
An 8-asset selection in eigenkit: QAOA's state against a random feasible pick
import itertools
import numpy as np
from eigenkit.optimization import QAOA, QUBO
rng = np.random.default_rng(108) # the same 8 assets
beta = rng.uniform(0.5, 1.5, 8)
sigma = 0.18**2 * np.outer(beta, beta) + np.diag(rng.uniform(0.10, 0.30, 8) ** 2)
mu = 0.02 + 0.06 * beta + rng.normal(0.0, 0.02, 8)
q, k, n = 0.5, 4, 8
off = np.abs(sigma).sum(axis=1) - np.diag(sigma)
a = np.max(np.abs(mu) + q * (np.diag(sigma) + 2 * off)) # provable penalty
Q = q * sigma - np.diag(mu) + a * (np.ones((n, n)) - 2 * k * np.eye(n))
scale = np.abs(Q).max()
qubo = QUBO(Q / scale, constant=a * k * k / scale)
best, _ = qubo.brute_force()
bits = np.array(list(itertools.product((0, 1), repeat=n))) # index order of probabilities
optimum = int("".join(map(str, best)), 2)
feasible = bits.sum(axis=1) == k
result = QAOA(layers=3, random_state=0).solve(qubo)
p = result.probabilities
print(f"{p[optimum]:.4f} vs {1 / feasible.sum():.4f}") # 0.0133 vs 0.0143 P(optimum) vs a random feasible pick
print(f"{p[~feasible].sum():.3f}") # 0.039 mass on portfolios that break the constraint
shots = np.random.default_rng(0).choice(len(p), size=1024, p=p)
print(int((shots == optimum).sum())) # 17 optimal portfolios among 1,024 shots
print(result.best_bitstring == best) # False the decoder's pick is not the optimum hereThe instance comes from the same one-factor generator as the experiment below, with the provable penalty. At the probability of the optimum is about the 1 in 70 of a uniformly random 4-of-8 portfolio, although under 4% of the state breaks the constraint. Seventeen of 1,024 shots are optimal, which is what a device would return. On this seed the decoded best_bitstring is not the optimum either; on larger instances it often is, for a reason explained below.
The 14-asset run: QAOA learns the constraint, not the objective
Pick 7 of 14 assets to minimise risk minus return, on synthetic returns and covariances. QAOA on eigenkit's noiseless simulator, mean of five seeds. The closeness column puts the expected objective of the feasible part between the worst feasible portfolio (0%) and the optimum (100%).
| Sampler | P(optimum) per shot | Shots that break the constraint | Closeness to optimum, feasible part |
|---|---|---|---|
| Uniformly random bitstring | 0.006% | 79.1% | 56% |
| QAOA p = 5, provable penalty | 0.030% | 2.8% | 57% |
| QAOA p = 5, penalty tuned with the answer | 0.101% | 37.5% | 67% |
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). With the provable penalty, the probability of the optimum rises from 0.016% at to the value above at , and five layers push the infeasible share far below the random level; but inside the feasible set the state is as good as a random pick: the same probability of the optimum as choosing uniformly among the 3,432 feasible portfolios, and the same closeness. This held at every size from 6 to 14 assets. A penalty tuned by brute force does better on the objective and lets over a third of the shots break the constraint; it is not available on a real problem. Each solve took about 48 s, mostly angle optimisation.
Reading a QAOA result honestly
Report sampled shots, not the decoded answer. eigenkit's best_bitstring scores the 64 most probable bitstrings of the exact final state and keeps the best (the top_k default, see guarantees and limits). A device cannot read those 64 most probable states; it returns shots. In our run, with the provable penalty at 14 assets, best_bitstring was the optimum in 80% of seeds, while 1,024 shots from the same state contained it in 20%. On a small problem the decoder scores every bitstring, so it is always optimal and says nothing about QAOA.
Compare with a uniformly random feasible answer, not only with a random bitstring. A random bitstring wastes most of its shots on infeasible answers, so beating it can mean only that QAOA learned the penalty. The useful baseline is a uniform pick among feasible answers: if QAOA's probability of the optimum matches it, the circuit has learned nothing about the objective.
Do not quote an approximation ratio over the penalised energy. Infeasible bitstrings carry large penalty energies, so the ratio normalised over all QUBO energies came out close to 1 for every safe-penalty run, including the ones no better than random among feasible portfolios. Report the probability of the optimum per shot, the share of infeasible shots and the objective of the feasible part.
Time the whole solve. The figure that matters is the wall-clock of the angle optimisation plus the shots, and it has to be set against the exact solver's time on the same instance. The QAOA vs MILP comparison does that for this problem.
What to compare a QAOA run against
Run these on the same instance before reading anything into QAOA's numbers. All of them are free and run in milliseconds at the sizes a simulator reaches.
| Baseline | What it tells you | Where it comes from |
|---|---|---|
| Enumeration or QUBO.brute_force() | The exact optimum and whether the penalty is strong enough | eigenkit, or a loop over the feasible answers |
| Mixed-integer solver on the constrained model | A proven optimum without any penalty, at sizes far beyond enumeration | HiGHS, Gurobi, CPLEX, OR-Tools; see QAOA vs MILP |
| Greedy or a simple local search | How hard the instance is: in our run greedy selection was optimal on most sizes | A few lines of code |
| Simulated annealing on the same QUBO | A heuristic with the same input and the same penalty problem | dwave-samplers or your own; see quantum annealing vs QAOA |
| Uniform random feasible answer | Whether QAOA learned the objective or only the constraint | 1 divided by the number of feasible answers |
What would change this result
Our run tested one combination: the standard X mixer, a safe penalty, random initial angles and up to five layers on a noiseless simulator. Each of those is a lever, and the run points to the first two. A constraint-preserving mixer such as the XY mixer never leaves the feasible set, so there is no penalty to drown the objective[2]. A warm start from a continuous relaxation gives QAOA a starting point that already knows something about the objective[3]. Neither is in eigenkit; both are tests worth running on the same instance, with the same baselines as the table above.
Size and problem class are the next lever. At 14 variables an exact solver is free, so no heuristic can pay off; the evidence above points to hundreds of qubits on MaxCut[4], or to problem families that exact solvers find hard, such as LABS[6]. The last is hardware. Those sizes run only on a device, where every layer adds gate errors and problems that do not match the chip's connectivity need extra gates[5]. The question a run has to answer is whether its sampled shots still beat the uniform feasible pick once noise is in.
Run it on a real QPU with EigenOrbit RouterThe QAOA circuit of your QUBO, run on a gate-based QPU, where shots are all you get back.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).
Questions
What is QAOA in simple terms?
QAOA is a quantum algorithm for optimisation problems over bitstrings. A circuit starts from an equal superposition of all bitstrings and applies alternating layers: one that rewards low-cost bitstrings and one that mixes them. A classical optimiser tunes the angles of the layers so that measuring the circuit gives low-cost bitstrings more often.
How do you handle constraints in QAOA?
Either as a penalty term in the cost, which is zero when the constraint holds, or with a mixer that never leaves the feasible set, such as the XY mixer for a fixed number of selected items. eigenkit has only the standard X mixer, so constraints go in as penalties. A penalty large enough to be safe can dominate the cost and leave QAOA unable to rank the feasible answers.
Is QAOA better than classical optimisation?
Not at any problem size tested so far. Exact solvers settle the problems a simulator can hold in milliseconds, and simulated annealing on the same QUBO did far better than QAOA in our portfolio run. The one published positive result is a better empirical scaling on one problem family in noiseless simulation, not a faster solve. Constraint-preserving mixers, warm starts and larger instances on hardware are the open tests.
How many layers p should I use in QAOA?
Start at p = 1 to 3 and increase while the results improve. Each layer adds two angles and makes the classical optimisation slower, and on hardware each layer adds noise. In our portfolio run, going from one to five layers mostly removed infeasible answers; it did not make the optimum more likely than a random feasible pick.
How many qubits does QAOA need?
One per binary variable of the QUBO. An equality constraint adds none, an inequality adds slack qubits for its range, and integer variables need several bits each. Exact simulation holds all 2 to the n amplitudes, so it is practical up to a few dozen qubits.
Can I run QAOA on real quantum hardware with eigenkit?
Yes, through the hardware providers eigenkit supports, which return shot counts that QAOA reads as estimated probabilities, with a gradient-free optimiser such as COBYLA or SPSA. Expect noise to lower the probability of good answers compared with the exact simulator.
Sources
- E. Farhi, J. Goldstone, S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. arXiv:1411.4028.
- 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.
- D. J. Egger, J. Mareček, S. Woerner. Warm-starting quantum optimization. Quantum 5, 479, 2021. arXiv:2009.10095.
- 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.
- 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.
- R. Shaydulin, C. Li, S. Chakrabarti, et al. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances 10, eadm6761, 2024. arXiv:2308.02342.
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