Comparison

QAOA vs MILP: when an exact classical solver beats a quantum heuristic

A mixed-integer solver (MILP) returns a proven optimum, or a bound on how far its best answer can be from one; QAOA returns samples that may contain a good answer, with no certificate. We ran both on the same 14-asset selection problem, QAOA on a noiseless simulator: the MILP proved the optimum in milliseconds, while QAOA needed close to a minute of angle optimisation and its shots often missed the optimum. On every problem a simulator or today's hardware can hold, the exact solver is faster and certain. The open question is larger instances, where an exact solver's gap stays open, and that is a test you can run on your own problems.

Updated

QAOA and MILP side by side

AspectMixed-integer solver (MILP, MIQP)QAOA
What it returnsThe best answer found, with a proven lower bound; the gap between them closes to zero at optimalityA distribution of bitstrings to sample; the best sample has no certificate
ConstraintsStated as constraints, kept exactlyPenalties in the cost, unless a constraint-preserving mixer is built[4]
InputLinear constraints, integer and continuous variables, a linear or convex quadratic objectiveA QUBO or Ising model: binary variables only, at most pairwise terms
GuaranteeExact, given enough time; worst-case time grows exponentiallyApproximation bounds only for special cases, such as 0.6924[1] of the optimum at p=1p = 1 on 3-regular MaxCut
Size todayLarge industrial models; how large depends on their structureA few dozen qubits on an exact simulator; noisy hardware beyond that
ToolsHiGHS (free, in SciPy), CBC, SCIP, OR-Tools, Gurobi, CPLEXeigenkit and other quantum SDKs, on simulators or QPUs

How each method finds an answer

A MILP solver runs branch-and-bound. It relaxes the integer variables to continuous ones and solves the easy linear program, which gives a bound no integer answer can beat. It then branches on a fractional variable, solves the two halves, and discards every branch whose bound is worse than the best integer answer found so far. Cutting planes tighten the relaxation and heuristics find good answers early. When the best answer meets the best bound, the solver has a proof of optimality; if it is stopped early, the remaining gap says how far from optimal the answer can be.

QAOA does none of this. It turns the problem into a cost Hamiltonian, prepares a state with p alternating cost and mixer layers, and tunes 2p angles so that measuring the state gives low-cost bitstrings more often[1]. It never sees a bound, so it cannot say how good its best sample is. The QAOA page covers how to write a constrained problem for it and how to read its output.

A quadratic objective such as portfolio risk has two classical routes: a solver that handles convex quadratic objectives directly (MIQP), or a linearisation. For binary variables the product xixjx_i x_j can be replaced by a new variable yy with three linear constraints, y≤xiy \le x_i, y≤xjy \le x_j and y≥xi+xj−1y \ge x_i + x_j - 1, which is what the sample below does.

The 14-asset selection as an exact MILP, with SciPy's HiGHS

import itertools
import numpy as np
from scipy.optimize import Bounds, LinearConstraint, milp

rng = np.random.default_rng(114)                  # 14 assets, one-factor model
beta = rng.uniform(0.5, 1.5, 14)
sigma = 0.18**2 * np.outer(beta, beta) + np.diag(rng.uniform(0.10, 0.30, 14) ** 2)
mu = 0.02 + 0.06 * beta + rng.normal(0.0, 0.02, 14)
q, k, n = 0.5, 7, 14

pairs = list(itertools.combinations(range(n), 2))  # y_p stands for x_i * x_j
m = n + len(pairs)
c = np.r_[q * np.diag(sigma) - mu, [2 * q * sigma[i, j] for i, j in pairs]]

rows, lo, hi = [], [], []
def add(coeffs, l, h):
    row = np.zeros(m)
    for col, v in coeffs.items():
        row[col] = v
    rows.append(row); lo.append(l); hi.append(h)

for p, (i, j) in enumerate(pairs):                # McCormick: y = x_i x_j for bits
    add({n + p: 1, i: -1}, -np.inf, 0)            # y <= x_i
    add({n + p: 1, j: -1}, -np.inf, 0)            # y <= x_j
    add({i: 1, j: 1, n + p: -1}, -np.inf, 1)      # y >= x_i + x_j - 1
add({i: 1 for i in range(n)}, k, k)               # exactly k assets: a constraint, not a penalty

res = milp(c, constraints=LinearConstraint(np.array(rows), lo, hi),
           integrality=np.r_[np.ones(n), np.zeros(len(pairs))], bounds=Bounds(0, 1))
print(res.status, res.mip_gap)                    # 0 0.0  status 0: proven optimal, gap closed
print(np.round(res.x[:n]).astype(int), round(res.fun, 5))  # [0 1 1 0 0 0 1 0 0 1 1 1 0 1] 0.03551

f = lambda x: q * x @ sigma @ x - mu @ x          # check: all C(14, 7) = 3,432 portfolios
best = min((np.isin(range(n), s).astype(int) for s in itertools.combinations(range(n), k)), key=f)
print(best, round(f(best), 5))                    # the same portfolio, 0.03551

The constraint of exactly 7 assets stays a constraint, with no penalty to tune. The linearised model has 14 binary and 91 continuous variables. HiGHS proves the optimum (status 0, gap 0), and enumerating all 3,432 portfolios confirms it.

The same instance, every method

Pick 7 of 14 assets, synthetic data, mean of five seeds where a method is random. QAOA ran at p=5p = 5 on eigenkit's noiseless simulator, and was read from 1,024 sampled shots, as a device would return.

MethodWall-clock per solveShare of seeds that found the optimum
Enumeration of the valid portfolios0.012 salways, exact
eigenkit QUBO.brute_force()0.039 salways, exact
MILP (HiGHS), linearised0.066 salways, proven
QAOA, provable penalty48 s20%
QAOA, penalty tuned with the answer63 s60%

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). QAOA's time is almost all classical angle optimisation on the simulator. With the provable penalty its probability of the optimum per shot was 0.030%, the same as a random pick among the valid portfolios. The tuned penalty needed the exact answer to set, so it is not an option on a real problem.

Why the exact solver wins, and where that might stop

At the sizes in our run the exact answer is cheap by any method, so the comparison only shows whether QAOA finds it. With a penalty a real run could use, its 1,024 shots contained the optimum in a minority of seeds. That is not specific to portfolios. Every problem an exact simulator can hold has at most a few dozen binary variables, and a modern MILP solver proves optimality at that size in milliseconds to seconds. On hardware, noise lowers QAOA's chance of a good sample further.

Where could a heuristic like QAOA matter? Only on instances where an exact solver's gap stays open for hours. One estimate for MaxCut puts a QAOA speed-up out of reach until several hundreds of qubits[2] are available. The best evidence in QAOA's favour is a better empirical scaling than branch-and-bound solvers on the LABS problem, from noiseless simulations of up to 40 qubits[3]. That is one problem family, chosen because exact solvers find it hard, and a scaling trend in simulation, not a faster solve on hardware.

Three things would have to change for the verdict to move, and each can be tested. The formulation: in our run the penalty held QAOA back, and a mixer that keeps the asset count fixed removes the penalty altogether[4]; eigenkit does not have one, so we did not test it. The instance: the comparison only means something where the MILP, run with a time limit, still reports an open gap, and those instances are far larger than our 14 assets. The hardware: at that size QAOA no longer fits on an exact simulator, so the circuit has to run on a device whose errors leave enough of the signal to beat the solver's best answer.

Where the exact solver's gap does stay open, the practical alternatives are classical heuristics first: local search, simulated annealing and quantum-inspired Ising machines take the same QUBO and return good answers fast. The comparison of quantum annealing and QAOA shows how simulated annealing did on our instance. A fair QAOA test on such an instance uses the MILP's bound as the yardstick: it says how far QAOA's best sample is from optimal, even when nobody knows the optimum.

Choosing between them

  1. Write the problem with its constraints first

    Formulate it as a mixed-integer model before thinking of a QUBO. If the constraints are hard (they must hold), the MILP keeps them exactly and the QUBO only penalises breaking them.

  2. Run a MILP solver with a time limit

    If the gap closes, you have the proven optimum and there is nothing for a heuristic to add. HiGHS is free and ships with SciPy.

  3. If the gap stays open, try classical heuristics

    Give local search, simulated annealing or an Ising machine the same time budget, and use the MILP's bound to judge how good their answers are.

  4. Test QAOA as research, on the same instance

    Use the same formulation, report the share of shots that are optimal and that break constraints, and set its full wall-clock against the MILP's. The MILP's bound tells you how far QAOA's best sample is from optimal.

Run it on a real QPU with EigenOrbit RouterThe QAOA circuit of the same selection QUBO on a real QPU, sampled for shots, to set what a device returns against the MILP's proven optimum.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).

Questions

Is QAOA faster than MILP?

Not on any problem tested so far. On the sizes a simulator or current hardware can run, a MILP solver proves the optimum in milliseconds to seconds, while QAOA spends most of its time tuning angles and gives no proof. In our 14-asset run the MILP was faster by orders of magnitude and always optimal. Whether that holds on instances where the MILP's gap stays open is the open question; the best evidence so far is a scaling trend in simulation on one problem family.

What is the difference between QAOA and integer programming?

Integer programming solves problems with integer variables and explicit constraints, using relaxations and branch-and-bound, and can prove an answer optimal. QAOA is a quantum heuristic for binary problems without constraints, a QUBO, so constraints have to be added as penalties, and it returns samples with no proof of quality.

When should I use a quantum optimizer instead of Gurobi or CPLEX?

Today, for research and learning, not for production. If a classical solver closes the gap within your time limit, a quantum heuristic cannot add anything. If it does not, compare classical heuristics first. Test QAOA on the same instances and report its results honestly against the solver's bound.

Can QAOA handle constraints like a MILP?

Not directly. With the standard mixer, constraints become penalty terms in the cost, and a penalty large enough to keep answers valid can swamp the objective. Constraint-preserving mixers keep some constraints exactly, such as a fixed number of selected items, but they are harder to build and eigenkit does not have them.

Does QAOA give the optimal solution?

Not with any guarantee. It produces a distribution over bitstrings, and the best sample may or may not be optimal. Only an exact method, such as enumeration on a small problem or a MILP solver, can tell you whether it is.

Sources

  1. E. Farhi, J. Goldstone, S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. arXiv:1411.4028.
  2. 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.
  3. 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.
  4. 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.

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