ADAPT-QAOA Algorithm

A variant of QAOA that, like ADAPT-VQE, grows its mixer adaptively — picking the operator with the largest gradient at each layer instead of a fixed mixer. Understand first why it does this, then see how qalgora-Q expresses the whole loop in a few lines of code.

The problem it solves — a fixed mixer is too rigid

Standard QAOA alternates two kinds of operator: the cost Hamiltonian HC that encodes the problem, and a mixing operator that drives transitions between states — the latter usually fixed to a transverse field Σ Xi on every qubit. That fixed mixer treats every problem, and every layer, identically; it pays no attention to which direction the current state most needs to be stirred. The result is that reaching a good solution often demands many layers — and depth is exactly the scarcest resource on shallow, near-term hardware.

Intuition — pick the best way to stir at every layer

ADAPT-QAOA stops fixing the mixer and instead chooses it adaptively, layer by layer. Prepare a pool of candidate mixing operators, and whenever a new layer is to be added, ask the same old question: which operator drives the energy down fastest? The gradient answers it. Pick the largest-gradient operator as this layer's mixer, re-optimize all the angles, then move on to the next layer. This way the stirring at each layer is tailored to the current state, and a good solution is usually reached in far fewer layers.

The math — measuring mixer gradients with a commutator

The criterion is the same as in ADAPT-VQE: in the current state, the gradient of the energy with respect to the angle of a candidate mixer Aj, once it is switched in, is given by the expectation of its commutator with the cost Hamiltonian

gj = −i⟨ [HC, Aj] ⟩.

The −i makes the gradient real-valued: for Hermitian HC and Aj the commutator is anti-Hermitian, so −i[HC, Aj] is Hermitian and its expectation is real.

The derivative is taken on the current optimized state |ψp⟩ at the candidate mixer parameter β=0:

gj = d/dβ ⟨ψp| e(iβ Aj) HC e(−iβ Aj) |ψp⟩|β=0 = −i⟨ψp|[HC, Aj]|ψp⟩

so the operator actually measured is the Hermitian −i[HC, Aj], not the non-Hermitian product HC·Aj.

The operator with the largest absolute gradient is the stirring direction that currently pushes the energy down hardest — so it is chosen as this layer's mixer. The only difference is what the criterion is used for: ADAPT-VQE uses it to grow a chemistry ansatz, while ADAPT-QAOA uses it to select QAOA's mixer one layer at a time.

How it works — the layer-by-layer iteration

1. Start from the uniform superposition and a given cost Hamiltonian HC.
2. For each operator Aj in the pool, measure the gradient −i⟨[HC, Aj]⟩.
3. Add the highest-gradient operator to the circuit as the next mixer layer.
4. Re-optimize all angles, then return to step 2 to grow the next layer.

The initial state is not always the uniform superposition: constrained problems need a feasible reference state and a constraint-preserving mixer pool. And on re-optimization, all γl and βl are optimized together.

Honest limits

• Per-layer screening costs measurements. Each new layer requires measuring the gradient of every candidate in the pool — this is precisely the price paid in exchange for shallower circuits.
• It is still greedy. Each layer takes only the locally steepest direction; there is no guarantee of the globally optimal layer ordering or the minimum total number of layers.
• The mixer pool design is critical. If the pool contains no suitable operator, adaptivity cannot conjure a good mixer; if the pool is too large, the screening cost climbs.
• Re-optimization grows more expensive with depth. Every added layer means re-optimizing all existing angles together, so each later round costs progressively more.

Seeing it in code

Read this code against the explanation above. pool collects the candidate mixers — both single-qubit spin.x(i) and the two-qubit spin.y(i) * spin.y(j) acting along the graph's edges. Each pass of the loop first computes the gradients grads for every operator in the pool (the −i⟨[HC, Aj]⟩ values), uses max(..., key=lambda k: abs(grads[k])) to select the operator with the largest absolute gradient and append it as a new layer, then calls reoptimize(...) to re-optimize all the angles. One pass, one layer — exactly matching the iteration above. Note that commutator(cost, a) builds the actual commutator [HC, Aj], and the measured operator is the Hermitian −i[HC, Aj], not the non-Hermitian product HC·Aj.

import qalgora
from qalgora import spin

cost = build_maxcut_cost(graph)
pool = [spin.x(i) for i in range(n)] + \
       [spin.y(i) * spin.y(j) for i, j in edges]

def commutator(h, a):
    return h * a - a * h          # [H_C, A_j] = H_C·A_j − A_j·H_C

layers = []
for _ in range(depth):
    # g_j = -i<[H_C, A_j]> — measure the Hermitian observable -i[H_C, A_j]
    grads = [(-1j * qalgora.observe(commutator_kernel,
                                    commutator(cost, a), params).expectation()).real
             for a in pool]
    layers.append(pool[max(range(len(pool)), key=lambda k: abs(grads[k]))])
    params = reoptimize(cost, layers)