Method

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 p=1p = 1 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.

  1. Count the qubits before anything else

    One qubit per binary decision. An equality such as ∑ixi=K\sum_i x_i = K needs no extra qubits; an inequality such as a budget cap needs slack bits, about log⁡2\log_2 of its range, and each one doubles the state the simulator holds. eigenkit's exact simulator holds all 2n2^{n} amplitudes, so problems stay at a few dozen variables.

  2. Decide how the constraint is enforced

    There are two ways. A penalty A(∑ixi−K)2A(\sum_i x_i - K)^2 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.

  3. 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 ∣μi∣+q(Σii+2∑j∣Σij∣)|\mu_i| + q(\Sigma_{ii} + 2\sum_j |\Sigma_{ij}|) 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.

  4. 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.

  5. 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.

  6. 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 here

The instance comes from the same one-factor generator as the experiment below, with the provable penalty. At p=3p = 3 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%).

SamplerP(optimum) per shotShots that break the constraintCloseness to optimum, feasible part
Uniformly random bitstring0.006%79.1%56%
QAOA p = 5, provable penalty0.030%2.8%57%
QAOA p = 5, penalty tuned with the answer0.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 p=1p = 1 to the value above at p=5p = 5, 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 p=5p = 5 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.

BaselineWhat it tells youWhere it comes from
Enumeration or QUBO.brute_force()The exact optimum and whether the penalty is strong enougheigenkit, or a loop over the feasible answers
Mixed-integer solver on the constrained modelA proven optimum without any penalty, at sizes far beyond enumerationHiGHS, Gurobi, CPLEX, OR-Tools; see QAOA vs MILP
Greedy or a simple local searchHow hard the instance is: in our run greedy selection was optimal on most sizesA few lines of code
Simulated annealing on the same QUBOA heuristic with the same input and the same penalty problemdwave-samplers or your own; see quantum annealing vs QAOA
Uniform random feasible answerWhether QAOA learned the objective or only the constraint1 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

  1. E. Farhi, J. Goldstone, S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. arXiv:1411.4028.
  2. 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.
  3. D. J. Egger, J. Mareček, S. Woerner. Warm-starting quantum optimization. Quantum 5, 479, 2021. arXiv:2009.10095.
  4. 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.
  5. 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.
  6. 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