QAOA for MaxCut¶

Category C4 · Module oracq.algorithms.optimization.variational · Stage V3

Overview¶

Given an undirected weighted graph \(G=(V,E)\), MaxCut asks for a partition of the vertices into two parts that maximizes the sum of the weights of the edges whose endpoints lie in different parts. QAOA starts from the uniform superposition and alternately applies cost evolution and mixer evolution, with the layer count and angles \((\gamma,\beta)\) chosen by a classical outer loop; the cost/mixer layering follows the original algorithm of Farhi et al. (arXiv:1411.4028, already cited under “Implementation basis” in the manual’s algorithm catalog). The cost operator takes the value

\[ C(z) = \sum_{(u,v,w)\in E} \frac{w}{2}\,(1 - z_u z_v), \]

on bit strings \(z\) — the sum of the weights of the cut edges; the mixer is the bitwise \(X\). This function generates the quantum circuit for fixed angles and reads out target to obtain a candidate bit string for a cut; it runs no classical optimizer.

Interface and input model¶

qaoa_maxcut(width, edges, gammas, betas)

API entry point: qaoa_maxcut

width: the number of vertices of the graph, also the target bit width, range 1..64.
edges: (u, v, weight) triples; u and v must lie in [0, width), the weights must be non-negative finite real numbers, and self-loops are rejected.
gammas / betas: the per-layer cost / mixer evolution angles; the two lists must be non-empty and of equal length, and the angles must be finite real numbers.

The graph’s edge list and the variational angles are both classical data parameterized directly, so the input model is CP. Returns an Operation whose only register is target (width bits), with no work bits. Module attributes:

Attribute	Meaning
`algorithm`	`"qaoa_maxcut"`
`layers`	the QAOA layer count, i.e. `len(gammas)`

Implementation notes¶

Initialization is the Hadamard uniform superposition over the whole target register. Each QAOA layer applies cost evolution first, then mixer evolution:

the cost layer applies an XOR–Rz(-gamma·weight)–XOR conjugation per edge, writing the phase onto the \(Z_u Z_v\) component; together with the global phase \(-\gamma w/2\), the single-edge gate is exactly \(e^{-i\gamma w(1-Z_uZ_v)/2}\); the per-edge ZZ gates commute with one another, and the whole layer implements \(e^{-i\gamma C}\).
the mixer layer applies rx(2·beta) to every qubit.

Register layout: vertex i corresponds to bit i of target. All parameters are validated at generation time (width cap, self-loops, negative weights, and inconsistent or empty gamma/beta lengths all raise ValidationError). Applicability boundary: only the circuit for the given angles is generated; angle initialization, expected-cut-value evaluation, and the outer optimization loop are organized by the caller; this module contains no classical optimizer.

Validation approach¶

Category C4 (heuristic/optimization semantics; acceptance criteria in ../../development/validation-plan.md §2: strictly better than the random baseline, and reaching the known optimum / theoretical fraction on small instances). Three layers of evidence:

Structure: construction and attribute assertions in tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests; the same family’s test_bad_inputs_fail_at_generation covers generation-time violations such as the self-loop edge (0, 0, 1).
Numerical: AlgorithmExpansionTests.test_qaoa_single_edge_optimal_layer — a single-layer QAOA with \(\gamma=\pi/2\) and \(\beta=\pi/8\) on the 2-vertex single-edge graph (weight 1.0), where the summed probability of the two optimal cut states |01> and |10> equals 1 (places = 10), i.e. the single layer already attains the optimal cut.
Binding: this module has no separate binding witness (the inputs are classical parameters, with no abstract oracle slots).

Known gaps and planned stages¶

Consistent with the variational.py row of validation-coverage.md: the strong witness for “reaching the optimal cut on small instances” is missing — currently there is only the analytically optimal layer for the single-edge graph, and a distribution-level cross-check against the exhaustively enumerated optimal cut value on multi-vertex graphs has not been done. Integration is planned for V3 (registering the new algorithm in the catalog + extending the real-backend cross-checks in tests/integration).

Numerical validation¶

Paper-grade numerical experiments are in tests/verification/verify_misc_algorithms.py (misc_algorithms group), all executed on real backends.

Experimental design: (a) the analytic anchor \(\gamma = \pi/2\), \(\beta = \pi/8\) of a single-layer QAOA on the single-edge graph (2 vertices, unit weight); (b) a single-layer QAOA on the 4-vertex cycle C4 (unit weights) — the angles are selected by a grid search over an exact numpy simulation (\(\gamma = 0.85\), \(\beta = 0.45\); the classical outer loop takes care of itself per the module contract), and the quantum distribution is cross-checked pointwise against the exact numpy simulation (diagonal cost phase + per-bit mixer \(e^{-i\beta X}\)); the optimal cuts are \(\lvert 0101\rangle\) and \(\lvert 1010\rangle\) (random baseline 2/16 = 0.125). Backend paths: full-amplitude cross-check on reference and originir-ext.

Key metrics:

Case	Scale	Path	Distribution TVD	Optimal-cut probability	Relative to random baseline
qaoa-single-edge-optimal	2 qubits, 1 layer	reference	—	1.0000 (analytic optimum)	—
qaoa-c4-distribution	4 qubits, 1 layer	reference + originir-ext	1.8e-16	0.5379	4.30×

Reproduce:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_misc_algorithms.py

Artifact: out/verification/misc_algorithms.json (all 24 cases pass; this page corresponds to the two qaoa-* cases).