p=1 QAOA MaxCut ansatz on a 4-cycle, referencing arXiv:2608.06212

Primitive

A depth-one (p=1) QAOA MaxCut ansatz on the 4-vertex cycle graph C4, edges 0-1, 1-2, 2-3, 3-0.

Three layers on four qubits: a Hadamard on each qubit for the uniform superposition over all 16 bitstrings; a cost layer applying one cx - rz(2y) - cx sandwich per edge, phasing on that edge's ZZ parity; and a transverse-field mixer of rx(2b) on every qubit. Twenty gates, with y = 3pi/8 and b = pi/8 - a depth-one optimum for this graph, not the only such pair.

What the paper's abstract says

Bach, Safro and Maciejewski (2026) propose a hybrid strategy in which quantum information enhances leading classical heuristics rather than replacing them. Per the abstract, a warm start built from local correlators obtained from QAOA initializes the Burer-Monteiro rank-two relaxation. Against a random multi-start baseline, that quantum-informed initialization is reported to give a significant head start - high-quality solutions in very few iterations - on two problem classes: random Erdos-Renyi graphs at 10% edge density, and fully-connected Sherrington-Kirkpatrick spin glasses, at n = 500 and n = 1000 qubits. The abstract adds that given enough iterations the random baseline often eventually catches up and slightly outperforms the warm-start strategy on average, framing the two as an exploitation/exploration tradeoff.

What this card is, and is not

This is a deterministic, fixed-seed simulator run on Provenova of a textbook QAOA ansatz, inspired by and referencing arXiv:2608.06212. It is not a reproduction of that paper's results: not its ER or SK instances, not its n = 500 / 1000 scale, and no hardware is involved. The p = 1 depth and the 4-cycle are our own choices, not sizes given in the abstract. This card prepares an ansatz state only; it does not compute the local correlators the paper's method extracts from its own far larger instances. The authors are not involved in this card and do not endorse it.

Ideal behaviour

The exact statevector places 17/64 on each of the maximum-cut strings 0101 and 1010, 5/64 on each of 0011, 0110, 1001 and 1100, and 1/64 on each remaining string - an expected cut of 3 against a maximum of 4. A finite-shot run should concentrate on 0101 and 1010 near that proportion; sampling variation and the backend's small noise tail put some counts elsewhere, so treat these as approximate, not exact, frequencies.