Rand-SEMI-QAOA: Finite-Budget Depth-One MaxCut Ensembles on Compressed Quantum Registers

AI summary

Overview

Research area: Quantum combinatorial optimization — specifically shallow (depth-one) quantum approximate optimization for MaxCut on compressed, noncommuting qubit encodings.

Technical level: Advanced. The paper assumes familiarity with QAOA, quantum random access codes/optimization (QRAO), stabilizer states, mutually unbiased bases (MUBs), and Pauli decoding; the framing and statistics are also aimed at readers who care about resource accounting.

Scope (one sentence): The paper defines and empirically evaluates Rand-SEMI-QAOA, a finite-budget ensemble method that draws product-X stabilizer-MUB state–mixer labels uniformly without replacement, optimizes each depth-one candidate independently on a (3,1)-QRAC relaxed Hamiltonian, and reports decoded best-of-set MaxCut approximation ratios on a 2,400-graph cohort of random connected 3-regular graphs with n ∈ {18, 20, 22}.

What This Paper Is About

Standard QAOA at shallow depth has limited expressivity, and its reported numbers are hard to compare across methods because different pipelines spend very different resources. This paper asks how much decoded MaxCut quality can be extracted from one cost–mixer alternation per candidate when the search effort is moved into a finite catalog of candidate state–mixer pairs on a compressed QRAO register, rather than into circuit depth or into a classically computed instance-specific warm start.

The goal is to build such an ensemble from a principled, algebraically controlled catalog (a stabilizer MUB system), to justify restricting it to the product-X family, and to report performance with the candidate budget and optimizer spelled out explicitly — without claiming quantum advantage.

Key Contributions

1. The SEMI-QAOA framework and its randomized selector. SEMI-QAOA restricts candidate state–mixer pairs to the product-X stabilizer-MUB family {(Z^v|+⟩^⊗r, B_{0,v}) : v ∈ 𝔽₂^r}; Rand-SEMI-QAOA samples a subset of labels uniformly without replacement under a declared budget schedule K(r), with |S_r| = min{K(r), 2^r}. Candidate count and per-candidate angle optimization are stated as resources separate from depth p.

2. Complete-cohort depth-one decoded ratios under matched budgets. On the full cohort of 2,400 random connected 3-regular graphs (800 each at n = 18, 20, 22), the capped matched-cardinality schedule reaches graph-mean decoded best-of-set ratio 0.9421 [0.9406, 0.9435] and the K = r² schedule reaches 0.9319 [0.9304, 0.9334] at p = 1, alongside a structured cross-family selector Ξ₁₂₃ at 0.9439 [0.9424, 0.9453] and a single |+⟩^⊗r QRAO baseline at 0.7108 [0.7072, 0.7143].

3. Discovery and control evidence for the product-family restriction. An exhaustive campaign over all noncomputational MUB families, a zero-angle (no-QAOA) dynamical control, and exact finite-population best-of-K order-statistic curves support the restriction rather than assuming it.

4. One-layer theory. An exact gauge identity shows product-family labels generate the orbit of the QRAO Hamiltonian under an r-dimensional sign-gauge group; deterministic syndrome analysis proves branchwise dephasing for typical entangled families; and an anisotropic Gaussian (polymer-expansion) surrogate controls the coherent label-averaged response on the scale β = b/r. The theory explicitly does not order independently optimized decoded maxima.

Main Findings

• Product-X family ranks first almost everywhere in the exhaustive scan. Across the 20 validated (r, p) family-mean aggregations, the product family is first in 18. At r = 5, 6, 7 it is first at every tested depth including p = 5; across its 18 leading cells the paired product-minus-nonproduct margin ranges from 0.0134 to 0.0861.

• Two exceptions, both at the smallest register. At r = 4, basis 5 leads at p = 4 and p = 5, with the product family second by margins of −0.0051 and −0.0101. At r = 4 and p = 2, 3, 4, 5 the descriptive intervals cross zero, so no ordering is inferred in those cells.

• The strongest nonproduct family is not fixed. It changes among bases 2, 3, 5, 10, and 66 across the campaign; equal family cardinality and a common optimizer rule out candidate count as the explanation for the family means.

• Depth-one ensemble performance on the complete cohort. Matched-budget Rand-SEMI-QAOA: 0.9421; r²-budget: 0.9319; Ξ₁₂₃: 0.9439; single-state baseline: 0.7108. Intervals are 95% graph-bootstrap intervals; every candidate in the first three rows receives the same 33 × 65 angle grid and three L-BFGS-B local starts before best-of-K selection on decoded score.

• Register compression is modest. QRAC packings use r = 6, …, 9 relaxed qubits for n = 18, 20, 22, with graph-weighted means E[r/n] = 0.3876 (range 1/3 to 4/9) and E[n/r] = 2.594. The paper states this is compression of the noncommuting Hamiltonian, not a claim about total circuit or optimization cost.

• Candidate budgets are polynomial. Over the complete p = 1 cohort (r = 6, 7, 8, 9), K = 64–232 for matched-budget Rand-SEMI-QAOA, K = 36–81 for the r² arm, and K = 112–232 for Ξ₁₂₃, versus the 2^r product family and 4^r noncomputational MUB catalog. Because arms overlap, the executed campaign optimized 112, 184, 302, or 414 distinct candidate states at these sizes plus one baseline, at a mean physical campaign count of 275.27 candidate state–mixer optimizations per graph including the baseline.

• Depth persistence, with a caveat. Matched-budget Rand-SEMI-QAOA rises from 0.9421 at p = 1 to 0.9942 at p = 5; the r² arm from 0.9319 to 0.9829; Ξ₁₂₃ from 0.9439 to 0.9934. These p > 1 results are experimental — the mechanism theory is one-layer only — and all are best-of-set statistics.

• Censored scale tail. At the 65 completed n = 34 scans, matched and r² schedules are 0.9147 and 0.9026; Ξ₁₂₃ falls from 0.9036 at n = 32 to 0.8946 at n = 34. The n ≥ 28 tail is runtime-censored: shorter-register tasks finish first and the completed graphs do not reproduce the intended register-size mixture, so these points are not unbiased population estimates.

• Equal-cardinality selector comparison. At r = 8, matched-budget Rand-SEMI-QAOA trails Ξ₁₂₃ by 0.0020; at r = 9, 10, 11, 12 it leads by 0.0115, 0.0065, 0.0217, and 0.0190 respectively, with paired bootstrap intervals above zero. Since only one subset seed exists per r, this is conditional on those frozen pools.

• The lift comes from the cost–mixer evolution, not from the raw states. In the zero-angle control (72 graphs spanning nine (n, r) cells, eight graphs per cell), the mean product-family ratio is 0.4090 before QAOA — below the 0.5640 random-cut anchor — and 0.7623 after one optimized layer. At K = 64, the exact expected best-of-K ratio is 0.602 before QAOA and 0.923 after.

• Explicitly excluded data. A finite-field power-table recurrence that omitted modular reduction affected r = 8 only; family 1 (j = 0) is algebraically immune, but 248 of the 256 noncomputational r = 8 bases change. Historical r = 8 nonproduct ranks and brightness maps are excluded and no corrected exhaustive rerun exists; post-fix product-family scale data at r ≥ 8 remain valid.

• No advantage claimed. The authors state they do not claim quantum advantage, lower total computation, or superiority to Goemans–Williamson or modern classical MaxCut solvers, and that results are finite-size and resource-explicit.

Methodology in Plain English

MaxCut asks how to split a graph's vertices into two groups so that as many edges as possible cross between them. Standard QAOA solves this on one qubit per vertex. This paper instead uses quantum random access codes to pack up to three vertices onto a single qubit, which shrinks the register at the cost of turning the problem into a noncommuting Hamiltonian — a "relaxed" objective whose energy is no longer the same as the number of cut edges. Because there is no computational-basis encoding left, the starting state and mixer must be chosen as part of the ansatz design.

For that design the authors borrow a well-known structure from quantum information: the complete mutually unbiased basis system of an r-qubit register, built here from a Galois-field construction. This gives a finite, algebraically controlled catalog of state–mixer pairs — d = 2^r noncomputational families, 4^r states in total. They ran an exhaustive discovery campaign (100 graphs per (n, p) cell for n ∈ {10, 12, 14, 16, 18} and p = 1, …, 5, totalling 20,308,480 state evaluations and 2,500 baseline evaluations, with 9,822,720 validated rows after exclusions) to ask which family wins on average — and found the simplest one: the product-X family, which requires only Z sign flips on |+⟩^⊗r and a matched signed-X mixer, with no S or CZ gates.

The deployed method, Rand-SEMI-QAOA, then keeps only that family and samples a limited number of its labels. Each sampled label gets its own independent classical angle optimization (a 33 × 65 grid plus three L-BFGS-B local starts), is decoded into a concrete cut by deterministic Pauli-sign rounding, and the best decoded cut across the set is kept. Two budget schedules are compared: K = min{r², 2^r} and a "matched" schedule sized to the cross-family selector Ξ₁₂₃. Controls include a zero-angle run (candidate states decoded before any QAOA layers), an exact combinatorial formula for the expected best-of-K over uniformly drawn labels without replacement, and graph-bootstrap intervals with the graph as the inferential unit.

Why This Matters

Impact on research. The paper's main methodological point is about accounting: a "depth-one" headline can hide an arbitrarily large ensemble, per-candidate optimizer, and decoding step. By reporting candidate counts, executed union sizes, angle-grid budgets, and order-statistic controls, it gives a template for comparing shallow quantum pipelines without conflating expected energies, measured bitstrings, rounded correlations, and best-of-set decoded ratios — the paper's own Table 1 makes that non-interchangeability explicit. The exact product-label gauge identity (labels = orbit of the Hamiltonian under an r-dimensional sign-gauge group) is a clean structural result that reframes "which state to prepare" as "which gauge of the Hamiltonian to optimize."

Real-world applications (contextual — the paper reports no application studies):

• Logistics and supply-chain partitioning, where cut-type objectives appear in routing and clustering decisions.
• Network design and VLSI placement, where graph partitioning is a standard subproblem.
• Portfolio diversification and risk-factor partitioning in quantitative finance, often modeled as MaxCut-like graph problems.
• Materials and lattice-model studies, where Ising/spin-glass formulations share the same mathematical structure.

Industry relevance. The paper is deliberately resource-explicit, which matters to practitioners deciding whether a hybrid quantum–classical pipeline is worth deploying: it reports polynomial candidate counts (K = 64–232 at the studied registers) against exponentially larger catalogs, and it does not claim a time-to-solution or total-resource win. Its negative controls (0.4090 before QAOA versus 0.7623 after) show how much of a shallow "gain" can come from decoding rather than from the quantum circuit — a check that industrial benchmarking efforts can reuse.

Future Directions

• Selector-seed variability. All statistics are conditional on disclosed frozen selector pools; only one subset seed exists per r. Repeating the study over many random selector draws would turn the reported best-of-set numbers into an estimate with selector variability attached.

• A corrected r = 8 exhaustive rerun. Because the finite-field defect changed 248 of the 256 noncomputational r = 8 bases and no corrected rerun exists, the family-ranking evidence stops at r = 7. Rebuilding the r = 8 catalog and rerunning the all-family scan would test whether the product-family lead persists.

• Theory past one layer and past energy. The syndrome-dephasing and anisotropic Gaussian results are p = 1 and relaxed-energy only, and the paper states the theory does not order independently optimized decoded maxima. Extending it to decoded-ratio ordering, or to p > 1, is the obvious open theoretical gap behind the observed 0.9942 at p = 5.

• Honest total-cost comparison. The paper explicitly declines to compare against Goemans–Williamson or modern classical MaxCut solvers, and its n ≥ 28 tail is runtime-censored. A pre-registered comparison on total resource cost (candidates × angle optimization + decoding) with an uncensored large-n cohort is the natural next experiment.

Target Audience

Researchers working on shallow variational quantum optimization and QRAO/QRAC-based relaxations; quantum-information theorists interested in stabilizer MUB constructions and gauge/orbit structure; and benchmarking-minded readers in academia or industry who need to interpret "depth-one" performance claims with the ensemble and optimizer costs made explicit. Readers seeking an introduction to QAOA, or a direct quantum-versus-classical performance verdict, will not find either here — the authors state plainly that no advantage is established.

Authors’ abstract

We introduce Rand-SEMI-QAOA, a finite-budget QRAO--QAOA ensemble for MaxCut based on a $(3,1)$-QRAC relaxation. The method samples labels uniformly without replacement from the product-$X$ family of an implemented Galois stabilizer mutually unbiased basis (MUB) system. Each selected state--mixer pair is optimized independently for relaxed QRAO energy and then evaluated by deterministic Pauli-sign decoding. Exhaustive scans of the implemented noncomputational MUB catalog place the product-$X$ family first in 18 of 20 validated family-mean cells and in every tested cell for $r=5,6,7$. On a complete cohort of $2{,}400$ random connected 3-regular MaxCut instances with $n\in\{18,20,22\}$, the capped matched-cardinality schedule attains a graph-mean decoded best-of-set approximation ratio of $0.9421$ with one QAOA layer, while the $K=r^2$ schedule attains $0.9319$. These statistics are conditional on the disclosed frozen selector pools and do not estimate variability over selector seeds. An exact gauge identity shows that product-family labels generate the orbit of the QRAO Hamiltonian under an $r$-dimensional sign-gauge group. For common angles and relaxed energy, deterministic syndrome analysis proves branchwise dephasing, while an anisotropic Gaussian surrogate controls the coherent label-averaged response on the scale $β=b/r$. The theory does not order independently optimized decoded maxima. The results are finite-size and resource-explicit and do not establish quantum advantage.