QUBO and Portfolio Optimization

Markowitz handed us a beautiful machine. Feed it expected returns and a covariance matrix, turn the crank, and out comes the portfolio with the least risk for a target return. For the continuous version of that problem — “hold any fraction of each asset” — the machine is genuinely solved: it is a convex quadratic program, and we can crack it in polynomial time before lunch.

Then a portfolio manager walks in and says: “Lovely. But I want to hold exactly 8 names, never a position smaller than 2%, and only in round lots of 100 shares.” And the beautiful convex machine seizes up. Those innocent-sounding requests turn a polynomial-time problem into a combinatorial one — the kind that, in the worst case, is NP-hard.

This lesson is about that phase change, and the bet quantum computing makes on it. We will recast the discrete portfolio problem as a QUBO (Quadratic Unconstrained Binary Optimization), see how a quantum annealer (D-Wave) and QAOA (gate model) attack a QUBO, and — crucially — keep a clear head about whether any of it currently beats a good classical solver. Spoiler from the start: the math is real and elegant; the advantage is, as of today, mostly aspirational.

Why continuous portfolios are easy and discrete ones are hard

Analogy. The continuous problem is rolling a marble into the bottom of a smooth bowl: wherever you start, gravity slides you to the single lowest point. The discrete problem is finding the lowest valley across a vast mountain range while only being allowed to stand on a finite set of peaks. There is no slope to follow — you must, in principle, check combinations.

Definition — continuous mean–variance. With weights $w \in \mathbb{R}^n$, expected returns $\mu$, covariance $\Sigma$, and risk-aversion $q$, Markowitz minimizes

$\min_{w}\; q\, w^{\top}\Sigma\,w \;-\; \mu^{\top} w \quad\text{s.t.}\quad \sum_i w_i = 1.$

Because $\Sigma$ is positive semidefinite, the objective is convex and the constraint is linear. Convex quadratic programs are solvable in polynomial time (interior-point methods). This is the “easy” world.

Where it breaks. Real mandates add constraints that are not convex:

• Cardinality: hold exactly (or at most) $k$ of the $n$ names.
• Minimum lot / position sizes: a holding is either $0$ or at least some floor (e.g. at least 2% or at least 100 shares) — a “semi-continuous” variable.
• Buy-in thresholds / round lots: weights must land on a discrete grid.

Each of these introduces a yes/no decision per asset. With $n$ assets there are up to $2^n$ on/off combinations, and the feasible region is no longer a single convex blob — it is a scatter of disconnected islands. Branch-and-bound can prune, but the worst case is exponential. This combinatorial core is exactly what QAOA and quantum annealing claim to attack.

Worked example — the explosion. Pick the best 5 names out of 30 by brute force: $\binom{30}{5} = 142{,}506$ portfolios — trivial. Now best 15 out of 100: $\binom{100}{15} \approx 2.5 \times 10^{17}$. At a billion evaluations per second that is roughly 8 years of compute for one rebalance. The continuous version of the same 100-asset problem solves in milliseconds. The discreteness, not the size, is the enemy.

When to use it

Stay in the continuous convex world whenever you legitimately can — if the only “discrete” constraint is soft (a preference, not a hard rule), encode it as a penalty in a convex solver and move on. Reach for combinatorial machinery (and only then consider quantum) when the discreteness is a hard, binding business constraint: a fixed name count, a regulatory lot size, a minimum ticket that can’t be fractioned.

QUBO: minimize x-transpose Q x over binary x

Analogy. A QUBO is a set of light switches (one per asset, each on or off) wired together so that every pair of switches has a reward or penalty for being on together, and each switch has its own solo reward for being on. You are hunting for the switch configuration with the lowest total “energy.” That is the whole model — pairs plus singles, nothing else.

Definition. A QUBO is

$\min_{x \in \{0,1\}^n}\; x^{\top} Q\, x \;=\; \min_{x}\; \sum_{i} Q_{ii}\, x_i \;+\; \sum_{i < j} Q_{ij}\, x_i x_j,$

where $Q$ is an $n \times n$ matrix and we used $x_i^2 = x_i$ to merge linear terms into the diagonal. “Unconstrained” means there are no separate equality/inequality constraints — every preference and rule must be baked into $Q$, usually as a quadratic penalty.

Mapping mean–variance + cardinality onto a QUBO. Let $x_i = 1$ if we hold asset $i$ (equal-weight the chosen names for simplicity). We want three things:

1. Reward expected return — a linear term $-\mu_i x_i$ (negative because we minimize). Fold it into the diagonal: it lowers $Q_{ii}$.
2. Penalize risk — a quadratic term $q\,\sigma_{ij} x_i x_j$ from the covariance. On-diagonal it adds variance; off-diagonal it adds covariance.
3. Enforce the cardinality “choose exactly $k$” with a penalty $\lambda\big(\sum_i x_i - k\big)^2$ for a large weight $\lambda$. This is zero when exactly $k$ switches are on and strictly positive otherwise.

Expanding the penalty is the key trick:

$\lambda\Big(\textstyle\sum_i x_i - k\Big)^2 = \lambda\Big(\sum_i x_i^2 + 2\!\!\sum_{i<j}\! x_i x_j - 2k\!\sum_i x_i + k^2\Big),$

and using $x_i^2 = x_i$ this contributes $\lambda(1 - 2k)$ to each diagonal $Q_{ii}$ and $2\lambda$ to each off-diagonal pair $Q_{ij}$ (the $\lambda k^2$ is a constant offset that does not change which $x$ is best).

Worked example — a 3-asset QUBO. Three assets, choose exactly $k = 2$. Take risk-aversion $q = 1$, penalty $\lambda = 5$, and these (toy) numbers:

Pairwise covariances: $\sigma_{AB}=0.01,\ \sigma_{AC}=0.00,\ \sigma_{BC}=0.005$.

Build $Q$ term by term. Diagonal $Q_{ii} = -\mu_i + q\,\sigma_{ii} + \lambda(1 - 2k)$. With $k=2$, $\lambda(1-2k) = 5(1-4) = -15$:

• $Q_{AA} = -0.10 + 0.04 - 15 = -15.06$
• $Q_{BB} = -0.08 + 0.02 - 15 = -15.06$
• $Q_{CC} = -0.06 + 0.01 - 15 = -15.05$

Off-diagonal $Q_{ij} = 2q\,\sigma_{ij} + 2\lambda$. With $2\lambda = 10$:

• $Q_{AB} = 2(0.01) + 10 = 10.02$
• $Q_{AC} = 2(0.00) + 10 = 10.00$
• $Q_{BC} = 2(0.005) + 10 = 10.01$

Now evaluate the energy $E(x) = x^{\top} Q x$ for two candidate selections (the $\lambda k^2 = 20$ constant is the same for every $x$, so we drop it and compare relative energies). Energy = sum of diagonal entries of chosen assets + the off-diagonal term of each chosen pair.

Candidate 1 — pick A and B ($x = (1,1,0)$), which meets the constraint (2 names):

$E_{AB} = Q_{AA} + Q_{BB} + Q_{AB} = -15.06 - 15.06 + 10.02 = -20.10.$

Candidate 2 — pick A only ($x = (1,0,0)$), which violates the constraint (1 name):

$E_{A} = Q_{AA} = -15.06.$

The valid two-name portfolio has the lower (better) energy, $-20.10 \le -15.06$ — the penalty did its job: under-filling leaves a big chunk of the $-15$ diagonal rewards unclaimed. For completeness, the three valid pairs:

The optimum here is A + C at $-20.11$ — it grabs the two best return/risk diagonals while paying the lowest pairwise penalty (their covariance is zero). Notice how close the valid energies are: real QUBOs have a rugged landscape where the best and second-best differ by a hair, which is exactly what makes the search hard.

When to use it

Reach for a QUBO formulation when your problem is natively about on/off decisions with pairwise interactions — asset in-or-out, edge in-or-out, bit set-or-not — and when your constraints can be written as quadratic penalties. If your variables are genuinely continuous (fractional weights), forcing them into QUBO via binary expansion (one bit per 0.1% of weight) bloats the variable count and is usually a step backward.

The Ising equivalence

A QUBO over $x_i \in \{0,1\}$ and an Ising model over spins $s_i \in \{-1,+1\}$ are the same optimization in different clothing. Substitute $x_i = (1 + s_i)/2$ and any QUBO becomes an Ising Hamiltonian

$H(s) = \sum_{i<j} J_{ij}\, s_i s_j \;+\; \sum_i h_i\, s_i \;+\; \text{const},$

where $J_{ij}$ are coupling strengths and $h_i$ are local fields, both linear functions of the original $Q$. This single line matters because quantum annealers minimize Ising energies natively — the hardware is a programmable spin glass. So “solve my portfolio QUBO” becomes “set these couplers and fields, then let the physics relax to the ground state.” Keep the equivalence in your pocket; the rest of the lesson uses QUBO and Ising interchangeably.

Quantum annealing: the adiabatic descent

Analogy. Annealing is named after metallurgy for a reason. Heat a metal until its atoms jiggle freely, then cool it slowly: the atoms settle into a low-energy, well-ordered crystal. Cool it fast (quench it) and they freeze into a messy, high-energy glass. Quantum annealing does the same trick on a problem’s energy landscape — it “cools” a quantum system slowly enough that it slides into the lowest valley (the optimum) rather than getting stuck in a local dent.

Definition — adiabatic / quantum annealing. The machine prepares the ground state of a simple driver Hamiltonian $H_0$ (one whose lowest-energy state is easy and known — a uniform superposition of all configurations). It then slowly interpolates to the problem Hamiltonian $H_P$ that encodes your Ising model:

$H(t) = \Big(1 - \tfrac{t}{T}\Big) H_0 \;+\; \tfrac{t}{T}\, H_P, \qquad 0 \le t \le T.$

By the adiabatic theorem, if the total time $T$ is long compared to $1/g_{\min}^2$ — where $g_{\min}$ is the smallest energy gap between the ground state and the first excited state along the way — the system stays in the ground state, and at $t = T$ a measurement returns the optimum of $H_P$. That gap is the catch: for hard problems it can shrink exponentially, demanding an exponentially long anneal.

Play with the island above before reading on. Notice three things the physics buys you: the search accepts occasional uphill moves while hot (so it doesn’t get trapped in the first dip), those uphill jumps shrink as temperature falls (so it eventually commits), and the constraint chip can flicker red mid-search — a QUBO doesn’t forbid invalid states, it just makes them expensive, so the annealer wanders through them on its way down.

Worked example — why “slowly enough” can be ruinous. Suppose the minimum gap on a particular problem is $g_{\min} = 0.01$ (energy units). The adiabatic condition demands roughly $T \gtrsim 1/g_{\min}^2 = 1/(0.01)^2 = 10{,}000$ time units. Halve the gap to $0.005$ and the required time quadruples to $40{,}000$. For genuinely hard instances the gap closes exponentially in problem size, so the “guaranteed” anneal time blows up exponentially — which is precisely why real D-Wave anneals are short and repeated and treated as a heuristic, not a guarantee.

When to use it

Quantum annealing is worth a pilot when your problem is natively Ising-shaped, sparse (so embedding overhead stays manageable), and you are content with a good heuristic answer rather than a certified optimum. Treat it as you would simulated annealing or tabu search: run it many times, keep the best sample, and always benchmark against a strong classical solver on the same instance before claiming any benefit.

QAOA: the gate-model variational cousin

Analogy. If annealing is a marble cooling into a valley, QAOA is a relay race between two coaches. One coach (the problem Hamiltonian) nudges the team toward low-cost configurations; the other (the mixer) shakes things up so the team explores. They alternate for $p$ rounds, and a classical optimizer outside the race tunes how long each coach gets the baton (the angles) to make the final lineup as low-cost as possible.

Definition — QAOA. The Quantum Approximate Optimization Algorithm prepares a state by alternating $p$ layers of a problem unitary $e^{-i\gamma_\ell H_P}$ (encoding your Ising cost) and a mixer unitary $e^{-i\beta_\ell H_M}$ (typically transverse-field spin flips):

$|\boldsymbol{\gamma},\boldsymbol{\beta}\rangle = \prod_{\ell=1}^{p} e^{-i\beta_\ell H_M}\, e^{-i\gamma_\ell H_P}\, |+\rangle^{\otimes n}.$

A classical optimizer adjusts the $2p$ angles $(\boldsymbol{\gamma},\boldsymbol{\beta})$ to minimize the measured expected energy $\langle H_P \rangle$. It is a quantum–classical loop: the quantum chip evaluates the cost of a parameter setting, the classical optimizer proposes the next setting. As $p \to \infty$ the layers can mimic the slow adiabatic sweep, so QAOA can in principle reach the optimum.

Worked example — the cost of depth. At depth $p$ you must optimize $2p$ angles. For a modest $p = 5$ that is 10 parameters — and each evaluation means running the circuit and sampling it thousands of times to estimate $\langle H_P \rangle$ to acceptable precision. Say 5,000 shots per evaluation and 200 optimizer steps: that is $10 \times 200 \times 5{,}000 = 10{,}000{,}000$ circuit executions for one problem, on hardware where each multi-qubit gate injects noise. Deeper $p$ means deeper circuits, more noise accumulation, and a higher-dimensional angle landscape to search.

When to use it

Today, QAOA is primarily a research and learning tool, not a production portfolio optimizer. Use it to understand variational quantum algorithms, to benchmark small instances, and to track the field — but do not stake a rebalance on it expecting it to beat branch-and-bound or simulated annealing. If you are running QAOA in anger, keep $p$ shallow, warm-start the angles from known good values or the adiabatic schedule, and (again) always benchmark classically on the identical instance.

The sober verdict

Time for the unglamorous truth. Classical combinatorial optimization is very good. Commercial mixed-integer programming (MIP) solvers using branch-and-bound and cutting-planes routinely crack cardinality-constrained portfolios with hundreds of assets to certified optimality, and metaheuristics like simulated annealing and tabu search deliver excellent near-optimal solutions fast when exactness isn’t required. Quantum annealing and QAOA are scientifically fascinating and may one day help on instances with especially nasty discrete structure — but as of today, no clear, reproducible advantage over these classical methods has been demonstrated on realistic portfolio problems.

The disciplined posture is the same one this whole course preaches about machine learning: benchmark honestly, beware the hype, and let the classical baseline have the first and last word. If a vendor demos a quantum portfolio win, ask whether they ran the same instance through a tuned classical solver — the answer is usually that they didn’t, or that the classical solver also won.

When to use it

Default to classical: a MIP solver when you need a certified optimum and the instance is tractable, simulated annealing or tabu when you need fast, good-enough answers on large QUBOs. Consider quantum annealing only for sparse, genuinely hard discrete instances and only as a benchmarked pilot. Treat QAOA as a research instrument. In every case, the rule is identical: run the classical baseline on the same instance, and believe the numbers over the narrative.

Recap

You watched a beautiful convex machine seize up the moment a portfolio manager asked for a fixed name count, a minimum lot, or a round-share grid — the convexity cliff that turns polynomial-time mean–variance into a combinatorial, NP-hard search. You recast that search as a QUBO (minimize $x^\top Q x$ over binary $x$), folding return into the diagonal, risk into the quadratic term, and the cardinality rule into a $\lambda(\sum x_i - k)^2$ penalty. You saw the one-line Ising equivalence that lets annealing hardware minimize it natively, the adiabatic descent of quantum annealing (and its gap-and-embedding caveats), and the variational QAOA loop (and its barren plateaus). And you ended where an expert should: classical solvers are strong, quantum advantage on real portfolios is not yet demonstrated, and the honest move is always to benchmark.