Portfolio optimisation: QAOA against the provable optimum

The problem

Minimise x'Sx - lambda*mu'x over binary x with exactly k assets selected, where S is the covariance matrix and mu the vector of expected excess returns. The binary selection is what makes this NP-hard in general: the continuous version has a closed-form solution and needs no quantum computer, or indeed any solver.

Instances come from a seeded single-factor market model, so every asset loads on a common factor plus idiosyncratic noise, which reproduces the correlation structure real equity covariance has rather than an unrealistic random matrix. Seed 20260902, lambda = 1.0.

The classical baseline

Exhaustive enumeration of every k-subset. This is deliberately the strongest possible baseline rather than a heuristic: it returns the provable optimum, so the quantum method is measured against the best answer that exists. It also yields the full distribution of feasible portfolios, which lets us score the quantum result on a scale that stays meaningful when the optimum sits near zero.

The quantum method

QAOA at depth p = 1, 2 and 3, with the cardinality constraint imposed as a quadratic penalty, run on our exact statevector engine at 512 shots. Variational parameters were optimised by COBYLA with three restarts of 150 iterations each. Every circuit evaluation inside that loop is counted below, because the optimiser is the real cost of a variational algorithm and a benchmark that reports only the final circuit understates it by two orders of magnitude.

What the numbers say

QAOA found the provable optimum in 6 of 12 runs, and in every single run it returned a portfolio in the top 2 percent of all feasible portfolios. As a heuristic it works.

It is also roughly a thousand times slower. At N = 16 exhaustive enumeration returns the proven optimum in 0.06 seconds. QAOA takes 15 to 38 seconds and between 85 and 153 circuit evaluations to reach an answer that is sometimes optimal and sometimes 10 percent of the way toward the worst portfolio available.

And it cannot prove anything. This is the distinction that matters most for a mandate. Enumeration returns the optimum and a proof that nothing better exists. QAOA returns a good portfolio with no certificate of optimality, so a risk committee asking "is this the best allocation available" gets an answer from one method and a shrug from the other.

Depth did not reliably help. Higher p contains lower p as a special case, so p = 3 scoring worse than p = 2 at N = 12 and N = 14 is the classical optimiser failing to converge in a larger parameter space, not a property of the algorithm. That fragility is itself a finding: QAOA quality here is governed by parameter optimisation rather than by circuit depth.

Where the classical method stops

The interesting question is not who wins at N = 16, because classical wins decisively. It is how far enumeration goes before it becomes impossible.

Estimated at 10 million subset evaluations per second.

The honest caveat, and it is a large one

Enumeration dying around N = 50 does not mean quantum computing has an opening at N = 50. No desk enumerates. Production practice is mixed-integer quadratic programming with branch and bound, which prunes the search tree and handles universes in the hundreds or thousands routinely, returning either the optimum or a bound on how far from it you are.

We use enumeration here precisely because it proves optimality at sizes we can also run on a quantum engine, which makes the comparison exact. The real classical frontier sits far beyond it. Any argument that quantum computing is about to become useful for portfolio construction has to beat Gurobi or CPLEX at N in the hundreds, not enumeration at N = 50.

Meanwhile the quantum side has its own ceiling. QAOA at N = 50 needs 50 qubits, which is past exact statevector simulation, and hardware at that width today carries error rates that would swamp the objective differences we are resolving here at the fifth decimal place.

What would have to change

For this to become a real decision rather than an experiment, three things need to happen together: hardware wide enough for the universe you actually trade, error rates low enough that the objective function survives the circuit, and a parameter optimisation strategy that does not degrade as the problem grows. None of the three is close today, and the third is a software problem that could be solved before the hardware arrives.

The number to watch is not qubit count. It is two-qubit gate fidelity, because that is what determines whether a deep enough QAOA circuit returns signal or noise. On that measure the field has moved: the best reported two-qubit fidelity is now 99.99 percent, and 96 logical qubits have been demonstrated from 448 physical ones.

Even so, more qubits alone do not produce a win here, and this is the part worth being clear about. The 2029 roadmaps target hundreds of logical qubits, which would allow QAOA on a few hundred assets. A few hundred assets is a size mixed-integer solvers handle comfortably today. Unlike chemistry, where the classical cost grows exponentially and hardware progress eventually crosses it, portfolio optimisation has a classical method that scales with the problem. The quantum side has to overtake a moving target rather than a stationary one.