Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA

Camilleri, Xuereb, Apollaro, Consiglio (University of Malta) · arXiv:2605.01620 · submitted 2026-05-05 · 13 pages · score 8/10

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising candidate for demonstrating quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) devices. While various QAOA parameterization schemes exist, ranging from the original single-angle approach to the more expressive multi-angle (MA-QAOA) and automorphic-angle (AA-QAOA), each presents distinct trade-offs between expressiveness and classical optimization complexity. In this work, we introduce the k-interaction-angle QAOA (kA-QAOA), a parameterization scheme that groups cost function terms by their k-body interaction order, providing a natural middle ground between parameter efficiency and solution quality. This approach is particularly well-suited for combinatorial optimization problems defined on hypergraphs, where multi-body interactions naturally arise in applications such as Boolean satisfiability and resource allocation with multi-party constraints. We benchmark kA-QAOA against standard SA-QAOA, MA-QAOA, and AA-QAOA on two problem classes: 3-uniform cyclic sign-alternating hypergraphs and random coefficient hypergraphs. Our results demonstrate that kA-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.

Executive summary

The paper introduces a new QAOA parameterization (kA-QAOA) that interpolates between the parameter-frugal single-angle and the expressive multi-angle scheme by giving each interaction order (1-body, 2-body, 3-body, …) its own angle. On 3-uniform cyclic hypergraph PUBOs and random-coefficient hypergraphs of 12 vertices, kA-QAOA matches MA-QAOA's approximation ratio while using substantially fewer function evaluations and traversing a lower magic ("nonstabilizerness") barrier during optimization. For Yuan, this is a methodological cousin of Y1's iterative warm-started QAOA: both papers attack the QAOA parameter-optimization bottleneck by injecting structure into the parameter space, just with different mechanisms (Y1's warm-start measurement vs kA's interaction-order grouping).

Main contribution

The kA-QAOA parameterization assigns one γ angle per k-body interaction order in the cost Hamiltonian. For a 4-qubit example with cost C(z) = σ₀σ₁σ₂ − σ₀σ₁ − σ₀σ₂ + σ₀ − σ₁σ₂σ₃ + σ₁σ₃ + σ₂σ₃ − σ₃, the circuit uses one γ₁ for all single-Z rotations, one γ₂ for all two-Z (RZZ) rotations, and one γ₃ for all three-Z (RZZZ) rotations — three γ angles instead of MA-QAOA's eight. The mixer is left fully multi-angle (one β per qubit). This is hypergraph-natural because higher-order interactions are organic to PUBOs, JSSP, SAT, etc., and aligns with emerging hardware platforms (trapped ions, neutral atoms) that natively support multi-qubit gates. The benchmarks are systematic: 3-uniform cyclic sign-alternating hypergraphs (computationally hard, structured) over n ∈ [4, 15], k=3, p ∈ {1, 2, 3}; random-coefficient hypergraphs with J_i ∈ {−1, 0, +1}, n=12, p ∈ [1, 5]. The paper additionally tracks the magic barrier — the transient buildup of stabilizer Rényi entropy (SRE, M₂) during optimization — and shows kA-QAOA traverses a lower barrier than MA-QAOA while reaching comparable AR.

Key definitions and protocol

kA-QAOA cost layer: for cost Hamiltonian Σ J_S ∏_i∈S σ^z_i, all terms with |S|=k share a single γ_k; mixer remains MA (one β per qubit).
Approximation ratio: AR = C_min / C_opt; fidelity F = |⟨ϕ|ψ⟩|²; nfev tracks total objective-function evaluations.
Stabilizer Rényi entropy (Leone 2022): M_α = (1−α)⁻¹ log₂(Σ_{P∈𝒫_n} |⟨ψ|P|ψ⟩|^2α / Dⁿ); zero iff the state is a stabilizer state. The paper uses M₂.
3-uniform cyclic sign-alternating PUBO: C(x) = Σ_i (−1)ⁱ ∏_j=0..k−1 x_i+j with x_i+n=x_i; for n not divisible by 2, an extra σ₀σ₁ term emerges in the spin form.
Optimizers: BFGS (quasi-Newton with finite-difference Hessian) and Powell (1-D line searches).
Initialization: 1/p, R(0, 1/p), R(0, 2π/p), and TQA_0.75 (Sack 2021's Trotterized quantum annealing init with Δt=0.75).

Detailed walkthrough

Section II frames the parameter-expressivity trade-off in QAOA: SA-QAOA (Farhi 2014) has 2p parameters; MA-QAOA (Herrman 2022) gives every gate its own angle and is much more expressive but requires more iterations and is more prone to barren plateaus; AA-QAOA (Shi 2022) groups by graph automorphism — collapsing to MA when no symmetry exists. kA-QAOA is positioned as a middle ground that always works (no symmetry needed) and reflects the natural structure of higher-order interactions.

Section III lays out the optimization protocol. BFGS and Powell are tested with four initialization strategies. Section IV (Results) is where the empirical claims live. For 3-uniform cyclic sign-alternating hypergraphs at p=1, kA-QAOA already beats AA and MA on both AR and fidelity, and at p=2 AA and MA catch up while SA still lags at p=3. The notable finding: kA-QAOA's nfev to reach optimum is substantially lower than MA's — meaning the savings come not from fewer parameters per se but from a smoother optimization landscape that converges faster.

For 12-vertex random-coefficient hypergraphs (J_i ∈ {−1, 0, +1}), kA-QAOA reaches MA's AR at p=3, well above SA, with consistently lower nfev. AA-QAOA isn't tested here because few graphs have non-trivial automorphisms.

The magic-barrier analysis (Sect. IV-C) is the most interesting contribution. Following Capecci 2025, the paper computes M₂ at every optimization step on 70 random 12-vertex hypergraphs (J_i ∈ [−10, 10]) at depths up to p=5, with degenerate ground states excluded. All three QAOA variants exhibit a magic barrier — magic rises from zero (the |+⟩^⊗n stabilizer initial state), peaks mid-optimization, then decreases as the algorithm zeroes in on a low-magic ground state. kA-QAOA's barrier peak is lower than MA-QAOA's at comparable AR. The authors interpret this as kA-QAOA selectively consuming non-stabilizer resources only where they're functionally needed — by the problem's interaction-order topology — while MA-QAOA over-parameterizes and burns excess magic. The trade-off: kA's average AR is slightly below MA's, but the resource savings (fewer parameters, lower nfev, lower magic) likely outweigh the small AR gap on NISQ.

Section V (Conclusion) suggests kA-QAOA is well-suited to scheduling (JSSP) and SAT-style PUBOs because both have natural k-body structure. The authors flag emerging multi-qubit-gate hardware (Mølmer–Sørensen, Rydberg) as a future direction where kA's hardware-native operator decomposition pays off.

Figures

Figure 1. 5-vertex 3-uniform cyclic hypergraph representation. Each yellow circle is a vertex; each enclosed area is a hyperedge connecting three vertices. For example, e₁ links 1, 2, 3.

Figure 2. Average normalized magic M̃₂ vs number of layers (1 to 5) with standard deviation, averaged over 70 random 12-vertex hypergraphs. All three variants exhibit a magic barrier; kA-QAOA's barrier height is consistently lower than MA-QAOA's.

AR comparison — Figure 3. Average approximation ratio (AR) with standard deviation across p ∈ [1, 5] for SA-QAOA, kA-QAOA, MA-QAOA. kA and MA converge to a solution after 5 layers; SA does not.

nfev comparison — Figure 4. Average number of function evaluations (nfev) with standard deviation. kA-QAOA's nfev is substantially below MA-QAOA's at all depths, despite achieving similar AR.

3-uniform cyclic AR p=1 — Figure 5. Approximation Ratio for 3-uniform cyclic sign-alternating hypergraphs at p=1, comparing SA, AA, MA, and kA-QAOA across n ∈ [4, 15]. kA-QAOA already outperforms both AA and MA at single-layer depth.

3-uniform cyclic AR p=2 — Figure 6. Approximation Ratio for 3-uniform cyclic hypergraphs at p=2. AA and MA catch up to kA's p=1 performance, while SA still lags substantially.

3-uniform cyclic AR p=3 — Figure 7. Approximation Ratio for 3-uniform cyclic hypergraphs at p=3 across n ∈ [4, 15]. SA-QAOA still does not reach the AR of kA, AA, or MA at this depth.

Random-coefficient AR — Figure 8. Approximation Ratio for 12-vertex random-coefficient hypergraphs (J_i ∈ {−1, 0, +1}) across p ∈ [1, 5]. kA-QAOA reaches MA-QAOA's AR at p=3 and consistently outperforms SA-QAOA.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1 (warm-started iterative QAOA): Strongest method overlap. Both papers attack the same root problem — QAOA's parameter-optimization bottleneck — by injecting structure into the parameter space. Y1's iterative measurement-based warm-start improves the 3-regular MaxCut approximation ratio and DGMVP scaling; kA-QAOA's interaction-order grouping reduces nfev with comparable AR. The two are complementary: kA reduces parameter count, Y1 provides better initial parameter values for whatever count is used. A natural extension is to apply Y1's warm-start procedure to kA-QAOA on hypergraph PUBOs.
Y2 (quasi-binary portfolio QAOA): Both papers reduce the QAOA parameter footprint — Y2 by re-encoding (~2log₂(U−L+1) qubits per variable) and using a constraint-preserving mixer; this paper by aggregating angles by interaction order. The kA scheme could in principle be applied to Y2's quasi-binary cost Hamiltonian as an additional optimization, especially for higher-order PUBO cost functions arising in portfolio with risk constraints.
Y3 (QAOA DGMVP): Y3's layerwise optimization is itself a parameter-structure choice (initialize each new layer's parameters from the previous one). kA-QAOA is orthogonal — same layer count, fewer parameters per layer. Plausibly composable.
Y4 (Grover + ADMM cardinality-constrained BO): Tangential method. Y4 is Grover-based, not QAOA, so kA-QAOA's parameter-grouping doesn't transfer directly; however the magic-barrier framework (SRE M₂) could be applied to Y4's Grover circuits to compare resource consumption.
Y5 (GW SDP via Gibbs / Pauli sparsity): Marginal — both touch Pauli structure but in very different ways (Y5 uses Pauli sparsity for Gibbs-state preparation; this paper uses SRE in the Pauli basis for measuring magic).
Y6 (PBR test on Heron2): No direct overlap.

Recommended action for Yuan

Cite kA-QAOA in any future Y1 follow-up as a complementary parameter-reduction strategy for warm-started iterative QAOA. The combination ("kA + Y1 warm-start") is a natural quick-paper.
Implement kA-QAOA on Y2's portfolio benchmark. Y2's CVaR-QAOA portfolio benchmark would be a clean test of whether interaction-order grouping helps when the cost is dominated by 2-body covariance terms with sparse 1-body returns. Likely modest AR savings but lower nfev and smaller barren-plateau risk.
Adopt the SRE / magic-barrier diagnostic. Tracking M₂ through optimization is a useful additional figure of merit for any QAOA-style paper Yuan writes — it's a signal of whether the algorithm is over-using non-Clifford resources, complementary to AR and fidelity.