Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA

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 quantum approximate optimization algorithm (MA-QAOA) and automorphic-angle quantum approximate optimization algorithm (AA-QAOA), each presents distinct trade-offs between expressiveness and classical optimization complexity. In this work, we introduce the $k$-interaction-angle quantum approximate optimization algorithm ($k$A-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 $k$A-QAOA against standard single-angle quantum approximate optimization algorithm (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 $k$A-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.

The paper asks whether grouping QAOA parameters by interaction order can balance solution quality against classical optimization cost for hypergraph optimization, and how this parameterization affects nonstabilizerness. It introduces $k$-interaction-angle QAOA ($k$A-QAOA): cost-Hamiltonian terms of equal Pauli weight share an angle, while each qubit retains an independent mixer angle. For costs containing one-, two-, and three-body terms, this gives $n+3$ parameters per layer. Numerical benchmarks compare this scheme with single-angle, multi-angle, and automorphism-based QAOA. Tests cover sign-alternating cyclic three-body problems on $4$–$15$ vertices at depths $p=1,2,3$, and 44 random-coefficient, 12-vertex instances at depths up to five. Results average over four initialization strategies and two classical optimizers. On the structured instances, $k$A-QAOA reports better depth-one performance than the alternatives; on random-coefficient instances, it reaches multi-angle approximation ratios around $p=3$, with fewer objective-function evaluations. A separate study uses 70 nondegenerate, 12-vertex instances, Powell optimization, and trotterized-annealing initialization to evaluate second stabilizer Rényi entropy. Both $k$A-QAOA and multi-angle QAOA approach optimal solutions by depth five, with a lower average normalized magic barrier for $k$A-QAOA. Its average approximation ratio is slightly lower, a stated trade-off. Magic is normalized separately for each instance against the maximum observed across depths and parameterizations. Extensions to other optimization classes and integration with hardware-native multiqubit gates are left for future work.