arxiv: 2605.01620 · v1 · submitted 2026-05-02 · 🪐 quant-ph

Recognition: unknown

Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA

Evan Camilleri , Andr\'e Xuereb , Tony J. G. Apollaro , Mirko Consiglio

Authors on Pith no claims yet

Pith reviewed 2026-05-09 13:59 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantumoptimizationalgorithmapproximatea-qaoahypergraphsma-qaoaparameterization

0 comments

The pith

kA-QAOA matches MA-QAOA approximation ratios on 3-uniform hypergraphs while using significantly fewer function evaluations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

QAOA solves combinatorial problems by alternating quantum operations controlled by adjustable angles. Standard versions use one or many angles per term, trading off solution quality against the difficulty of tuning those angles classically. The new kA-QAOA groups all terms that involve exactly k variables and assigns them the same angles. This structured sharing is natural for hypergraph problems where interactions involve three or more parties, such as certain satisfiability or resource-allocation tasks. The authors test the approach on two families of 3-uniform hypergraphs: cyclic sign-alternating instances and random-coefficient instances. They report that the grouped-angle version reaches approximation ratios close to those of the fully flexible multi-angle QAOA while requiring substantially fewer evaluations of the cost function during classical optimization, thereby lowering the total number of quantum circuit runs needed.

Core claim

Our results demonstrate that kA-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.

Load-bearing premise

That grouping parameters strictly by k-body interaction order remains effective and near-optimal for hypergraph problems beyond the two specific 3-uniform families benchmarked in the abstract.

Figures

Figures reproduced from arXiv: 2605.01620 by Andr\'e Xuereb, Evan Camilleri, Mirko Consiglio, Tony J. G. Apollaro.

**Figure 1.** Figure 1: kA-QAOA four-qubit quantum circuit for Eq. (5) with p = 1 layers having parameterized angles γ1 for Rzi (blue) gates, γ2 for Rzizj (green) gates, γ3 for Rzizj zk (yellow) gates, as well as β1, β2, β3, and β4 for Rxi (red) gates. directly attributed to its handling of k-body terms rather than graph-specific artifacts. Second, the random coefficient hypergraphs with Ji ∈ {−1, +1, 0} offer a contrasting sce… view at source ↗

**Figure 2.** Figure 2: 5-vertex 3-uniform cyclic hypergraph representation. Each node is represented by a yellow circle with a number i inside it. The hyperedges are represented by areas, denoted by ei , which encapsulate the nodes they link. For example, hyperedge e1 links nodes 1, 2, and 3. Next, we transform the problem to a spin problem C(z) = 1 8 " − nX−k i=0 (−1)iσ z i ! − 2(n mod 2)σ z 1 + nX−k i=0 (−1)iσ z i σ z i+2! + 2… view at source ↗

**Figure 3.** Figure 3: a showcases the average and standard deviation of normalized magic M˜ 2 as a function of the number of layers whilst Fig. 3b shows the average and standard deviation of the AR and Fig. 3c the nfev for SA-QAOA, kA-QAOA and MA-QAOA from one to five layers. Magic is normalized on a per-hypergraph basis by dividing each Rényi entropy value M2 by the maximum entropy observed within that specific hypergraph. … view at source ↗

**Figure 4.** Figure 4: Approximation Ratio for 3-uniform cyclic sign-alternating hypergraphs with view at source ↗

**Figure 5.** Figure 5: Fidelity for 3-uniform cyclic sign-alternating hypergraphs with view at source ↗

**Figure 6.** Figure 6: Number of function evaluations for 3-uniform cyclic sign-alternating hypergraphs with view at source ↗

**Figure 7.** Figure 7: Comparison of approximation ratio, fidelity, and number of function evaluations for random coefficient view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

kA-QAOA groups angles by interaction order but the benchmarks stay inside 3-uniform hypergraphs where that grouping collapses to something close to single-angle QAOA.

read the letter

The paper introduces kA-QAOA, which groups the variational parameters in QAOA by the interaction order k of the hyperedges. On two 3-uniform hypergraph problems it reports approximation ratios similar to the multi-angle version but with substantially lower classical optimization cost. This parameterization is a reasonable attempt to balance flexibility and tractability. For problems where interactions come in different body orders, assigning angles by k rather than by individual term or all together could cut the number of parameters without losing too much expressivity. The authors correctly note that hypergraph problems appear in SAT and multi-party constraints, so the setting is relevant. The main limitation is the choice of benchmarks. Both the cyclic sign-alternating family and the random-coefficient family are strictly 3-uniform. In a 3-uniform hypergraph every cost term has the same k, so the grouping collapses to one angle per symmetry class at most. That makes the scheme close to standard single-angle QAOA, and any reduction in function evaluations might simply follow from having fewer independent parameters due to symmetry. The stress test is right that mixed-order hypergraphs would be needed to show the grouping actually delivers the advertised middle ground. The abstract gives no numbers on the actual function evaluation counts, no error bars, and no description of the classical optimizer used. This makes it hard to judge how robust the significantly fewer claim is. The underlying math for the parameterization itself looks clean and does not introduce obvious inconsistencies. This kind of work is useful for the QAOA community focused on hypergraph optimization. It deserves peer review because it puts forward a concrete, easy-to-implement variant with initial empirical results. Referees should push for broader test cases and clearer reporting of the optimization statistics, but the core idea is worth evaluating.

Referee Report

2 major / 2 minor

Summary. The paper introduces kA-QAOA, a QAOA parameterization that groups variational angles by the k-body interaction order of hypergraph cost terms. It positions this as an intermediate scheme between single-angle (SA-QAOA) and multi-angle (MA-QAOA) variants, and reports numerical benchmarks on two 3-uniform hypergraph families (cyclic sign-alternating and random-coefficient) claiming that kA-QAOA matches MA-QAOA approximation ratios while using far fewer classical function evaluations.

Significance. If the performance trade-off is substantiated on appropriate instances, the structured parameterization could reduce classical optimization overhead for QAOA on hypergraph problems arising in SAT and resource allocation, while the non-stabilizerness analysis (implied by the title) might provide additional theoretical grounding for the ansatz choice.

major comments (2)

[Abstract] Abstract: The two benchmark classes are both strictly 3-uniform. Consequently every cost term has identical interaction order, so the k-body grouping collapses to a single angle (or one per symmetry class), rendering kA-QAOA formally identical to SA-QAOA on these instances. The reported reduction in function evaluations therefore cannot be attributed to the structured grouping; it is consistent with symmetry alone. This directly undermines the central claim that kA-QAOA supplies a middle ground for hypergraphs in general.
[Numerical Experiments] Numerical Experiments (or equivalent results section): No benchmarks are presented on hypergraphs containing mixed interaction orders (e.g., 2-body plus 3-body terms). The paper's own motivation emphasizes that multi-body interactions arise naturally in applications, yet the experiments never probe the regime in which the k-grouping is supposed to deliver its advertised advantage over both SA-QAOA and MA-QAOA.

minor comments (2)

[Abstract] The title references non-stabilizerness, but the abstract and claimed results focus exclusively on approximation ratios and function evaluations. A brief statement clarifying whether non-stabilizerness is used to motivate or analyze the parameterization would improve clarity.
[Abstract] The abstract states that kA-QAOA requires 'significantly fewer function evaluations' without reporting error bars, number of independent runs, or statistical tests. Adding these details would strengthen the empirical comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, acknowledging where clarification and additional results are warranted.

read point-by-point responses

Referee: [Abstract] Abstract: The two benchmark classes are both strictly 3-uniform. Consequently every cost term has identical interaction order, so the k-body grouping collapses to a single angle (or one per symmetry class), rendering kA-QAOA formally identical to SA-QAOA on these instances. The reported reduction in function evaluations therefore cannot be attributed to the structured grouping; it is consistent with symmetry alone. This directly undermines the central claim that kA-QAOA supplies a middle ground for hypergraphs in general.

Authors: We agree that on strictly 3-uniform hypergraphs the k-interaction grouping reduces to a single parameter group (or per symmetry class), rendering kA-QAOA equivalent to SA-QAOA in parameterization structure. The reduction in function evaluations relative to MA-QAOA therefore stems from the smaller number of variational parameters rather than from a distinct grouping effect in these uniform instances. We will revise the abstract and introduction to clarify that the current benchmarks validate performance on uniform hypergraphs (where kA-QAOA coincides with SA-QAOA yet still matches MA-QAOA approximation ratios with fewer evaluations), while emphasizing that the middle-ground advantage is designed for and will be demonstrated on mixed-order hypergraphs. revision: yes
Referee: [Numerical Experiments] Numerical Experiments (or equivalent results section): No benchmarks are presented on hypergraphs containing mixed interaction orders (e.g., 2-body plus 3-body terms). The paper's own motivation emphasizes that multi-body interactions arise naturally in applications, yet the experiments never probe the regime in which the k-grouping is supposed to deliver its advertised advantage over both SA-QAOA and MA-QAOA.

Authors: We acknowledge that the presented numerical experiments are restricted to 3-uniform hypergraphs and do not include mixed-order instances, even though the motivation section highlights applications involving mixed multi-body terms. This limits the direct demonstration of kA-QAOA's advantage in the regime where the structured grouping is most distinct. In the revised manuscript we will add benchmarks on hypergraphs containing mixed interaction orders (e.g., combinations of 2-body and 3-body terms) to explicitly show the performance trade-off of kA-QAOA relative to both SA-QAOA and MA-QAOA in the intended setting. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical benchmarks on explicit hypergraph instances

full rationale

The paper proposes kA-QAOA as a grouping of variational angles by interaction order k and reports numerical approximation ratios and function-evaluation counts on two families of 3-uniform hypergraphs. These outcomes are obtained by direct simulation against SA-QAOA, MA-QAOA and AA-QAOA baselines; no derivation, uniqueness theorem, or fitted-parameter renaming is invoked that would make the reported trade-off tautological by construction. The central claim therefore remains an independent empirical observation rather than a self-referential reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No new axioms, free parameters, or invented entities are introduced in the abstract; the work extends the existing QAOA framework with a structured grouping choice for angles.

pith-pipeline@v0.9.0 · 5548 in / 1067 out tokens · 41041 ms · 2026-05-09T13:59:28.870071+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 8 canonical work pages · 1 internal anchor

[1]

2025301 UM MinED

metrics. The AR is the figure of merit that measures algorithm efficiency in approximation algorithms, it is defined as AR= Cmin Copt ,(8) whereC min is the minimum attained value of the cost function, andC opt is the true optimal value of the cost function (typically computed classically via brute force). Another figure of merit one can consider is the f...
[2]

Ezratty, Understanding quantum technologies 2025 (2025), arXiv:2111.15352 [quant-ph]

O. Ezratty, Understanding quantum technologies 2025 (2025), arXiv:2111.15352 [quant-ph]

work page arXiv 2025
[3]

R. T. Toledo,Industrial Applications of Combinatorial Optimization(Springer, Boston, MA, 1999)

1999
[4]

Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014), review article, Section: In- terdisciplinary Physics

A. Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014), review article, Section: In- terdisciplinary Physics

2014
[5]

Yarkoni, E

S. Yarkoni, E. Raponi, T. Bäck, and S. Schmitt, Quan- tum annealing for industry applications: introduction and review, Reports on Progress in Physics85, 104001 (2022)

2022
[6]

Wang, J.-H

P.-H. Wang, J.-H. Chen, Y.-Y. Yang, C. Lee, and Y. J. Tseng, Recent advances in quantum computing for drug discovery and development, IEEE Nanotechnology Mag- azine17, 26 (2023)

2023
[7]

Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

2018
[8]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2014
[9]

Amico, R

L. Amico, R. Fazio, A. Osterloh, and V. Vedral, Entan- glement in many-body systems, Rev. Mod. Phys.80, 517 (2008)

2008
[10]

Eisert, M

J. Eisert, M. Cramer, and M. B. Plenio, Colloquium: Area laws for the entanglement entropy, Rev. Mod. Phys. 82, 277 (2010)

2010
[11]

Preskill, Quantum computing and the entanglement frontier, arXiv preprint arXiv:1203.5813 (2012)

J. Preskill, Quantum computing and the entanglement frontier (2012), arXiv:1203.5813 [quant-ph]

work page arXiv 2012
[12]

Aaronson and D

S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A70, 052328 (2004)

2004
[13]

S.BravyiandA.Kitaev,Universalquantumcomputation with ideal clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005)

2005
[14]

Feige, J

U. Feige, J. H. Kim, and E. Ofek, Witnesses for non- satisfiability of dense random 3cnf formulas, in2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06)(2006) pp. 497–508

2006
[15]

Heydaribeni, X

N. Heydaribeni, X. Zhan, R. Zhang, T. Eliassi-Rad, and F. Koushanfar, Distributed constrained combinato- rial optimization leveraging hypergraph neural networks (2024), arXiv:2311.09375 [math.OC]

work page arXiv 2024
[16]

Singh, N

R. Singh, N. Boškov, A. Gudal, and M. A. Khan, A ranking framework for network resource allocation and scheduling via hypergraphs (2025), arXiv:2506.01571 [cs.DS]

work page arXiv 2025
[17]

arXiv preprint, 1901.04405 , year=

N. Dattani, Quadratization in discrete optimization and quantum annealing, arXiv preprint arXiv:1901.04405 (2019)

work page arXiv 1901
[18]

Guruswami and R

V. Guruswami and R. Saket, On the inapproximabil- ity of vertex cover on k-partite k-uniform hypergraphs, inAutomata, Languages and Programming, edited by S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010) pp. 360–371

2010
[19]

Giovagnoli, An introduction to the quantum approx- imate optimization algorithm (2025), arXiv:2511.18377 [quant-ph]

A. Giovagnoli, An introduction to the quantum approx- imate optimization algorithm (2025), arXiv:2511.18377 [quant-ph]

work page arXiv 2025
[20]

Cerezo, A

M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shal- low parametrized quantum circuits, Nature Communica- tions12, 1791 (2021)

2021
[21]

Herrman, P

R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, Multi-angle quantum approximate opti- mization algorithm, Scientific Reports12, 6781 (2022)

2022
[22]

J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Bab- bush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications9, 4812 (2018)

2018
[23]

Larocca, S

M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Bia- monte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren plateaus in variational quantum computing, Nature Reviews Physics7, 174 (2025)

2025
[24]

Bharti, A

K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Noisy intermediate-scale quantum algorithms, Rev. Mod. Phys.94, 015004 (2022)

2022
[25]

K. Shi, R. Herrman, R. Shaydulin, S. Chakrabarti, M. Pistoia, and J. Larson, Multiangle qaoa does not al- ways need all its angles, in2022 IEEE/ACM 7th Sympo- sium on Edge Computing (SEC)(2022) pp. 414–419

2022
[26]

Stein, F

J. Stein, F. Chamanian, M. Zorn, J. Nüßlein, S. Zielinski, M. Kölle, and C. Linnhoff-Popien, Evidence that pubo outperforms qubo when solving continuous optimization problems with the qaoa, inProceedings of the Compan- ion Conference on Genetic and Evolutionary Computa- tion, GECCO ’23 Companion (Association for Comput- ing Machinery, New York, NY, USA, 2...

2023
[27]

Leone, S

L. Leone, S. F. E. Oliviero, and A. Hamma, Stabilizer rényi entropy, Phys. Rev. Lett.128, 050402 (2022)

2022
[28]

Gross, S

D. Gross, S. Nezami, and M. Walter, Schur–weyl duality for the clifford group with applications: Property test- ing, a robust hudson theorem, and de finetti represen- tations, Communications in Mathematical Physics385, 1325 (2021)

2021
[29]

Haug and L

T. Haug and L. Piroli, Stabilizer entropies and nonstabi- lizerness monotones, Quantum7, 1092 (2023)

2023
[30]

Capecci, G

C. Capecci, G. C. Santra, A. Bottarelli, E. Tirrito, and P. Hauke, Role of nonstabilizerness in quantum optimiza- tion (2025), arXiv:2505.17185 [quant-ph]

work page arXiv 2025
[31]

Garey and D

M. Garey and D. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness, Mathemati- cal Sciences Series (W. H. Freeman, 1979)

1979
[32]

Nocedal and S

J. Nocedal and S. J. Wright,Numerical Optimization, 2nd ed., Springer Series in Operations Research and Fi- nancial Engineering (Springer, New York, NY, 2006)

2006
[33]

M. J. D. Powell, An efficient method for finding the minimum of a function of several variables with- out calculating derivatives, The Computer Journal7, 155 (1964), https://academic.oup.com/comjnl/article- pdf/7/2/155/959784/070155.pdf

1964
[34]

Virtanen, R

P. Virtanen, R. Gommers, T. E. Oliphant, M. Haber- land, T. Reddy, D. Cournapeau, E. Burovski, P. Pe- terson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Po- lat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henri...

2020
[35]

S. H. Sack and M. Serbyn, Quantum annealing initializa- tionofthequantumapproximateoptimizationalgorithm, Quantum5, 491 (2021)

2021
[36]

transition probability

A. Uhlmann, The “transition probability” in the state space of a∗-algebra, Rep. Math. Phys.9, 273 (1976)

1976