pith. sign in

arxiv: 2605.22758 · v1 · pith:VKHTRJG7new · submitted 2026-05-21 · 🪐 quant-ph · cs.CC

A sharp interaction-degree threshold for simulating QAOA

Ralfs \=Aboli\c{n}\v{s} , Andris Ambainis This is my paper

Pith reviewed 2026-05-22 05:28 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords QAOAclassical simulationinteraction degreesampling hardnesspolynomial hierarchyquantum optimizationdepth-1 QAOA
0
0 comments X

The pith

Classical sampling from depth-1 QAOA becomes hard precisely at interaction degree 3 and would collapse the polynomial hierarchy.

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

The paper shows a sharp threshold separating easy and hard regimes for classically simulating QAOA when the cost function has limited interaction degree. At degree 3, even approximate sampling from the output distribution of depth-1 QAOA is hard enough that it would collapse the polynomial hierarchy to its third level. At degree 2, exact sampling from depth-p QAOA becomes possible in polynomial time as long as the depth p grows only logarithmically with the number of qubits. The separation holds even though the hard degree-3 instances are easy to optimize classically, so the sampling hardness stands alone.

Core claim

There is a sharp interaction-degree threshold for the classical simulation of QAOA with 2-local cost functions. At degree 3, classical sampling from depth-1 QAOA with small multiplicative error would collapse the polynomial hierarchy to its third level. At degree 2, exact classical sampling from depth-p QAOA on n qubits runs in time n to the O(1) whenever p equals O(log n). The hard degree-3 instances have trivially optimizable cost functions.

What carries the argument

A hardness reduction from a known hard sampling problem to the QAOA output distribution on specific 3-local cost functions.

If this is right

  • Degree-3 QAOA sampling is classically intractable under standard complexity assumptions.
  • Degree-2 QAOA remains classically simulable for logarithmic depth.
  • Sampling hardness for these instances does not imply a quantum optimization advantage.
  • The interaction degree of the cost function is the parameter that controls the classical simulability threshold.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Interaction degree may serve as a practical knob for designing variational circuits that separate sampling from optimization hardness.
  • Similar degree thresholds could appear in other variational quantum algorithms beyond QAOA.
  • The result invites constructions of explicit degree-3 cost functions that realize the hard sampling distributions.

Load-bearing premise

There exist particular 3-local cost functions whose QAOA output distributions at depth 1 encode a hard sampling problem.

What would settle it

An efficient classical algorithm that samples from depth-1 QAOA on those degree-3 instances to within small multiplicative error would show the polynomial hierarchy does not collapse.

Figures

Figures reproduced from arXiv: 2605.22758 by Andris Ambainis, Ralfs \=Aboli\c{n}\v{s}.

Figure 1
Figure 1. Figure 1: Degree reduction for three diagonal operators on a sin￾gle wire. Moreover, the reduction preserves the post-selected output distribution exactly. Proof. The inclusion PostQAOAdeg≤3 1 ⊆ PostBQP is immediate. For the reverse, we will show that decomposing over G and applying our coupling to each Hadamard converts an arbitrary PostBQP circuit into depth-1 QAOA, and then bound the interaction degree. For F = e… view at source ↗
read the original abstract

We identify a sharp interaction-degree threshold for the classical simulation of QAOA with $2$-local cost functions. At degree $3$, classical sampling from depth-$1$ QAOA with small multiplicative error would collapse the polynomial hierarchy to its third level. At degree $2$, exact classical sampling from depth-$p$ QAOA on $n$ qubits runs in time $n^{O(1)}$ whenever $p = O(\log n)$. The hard degree-$3$ instances have trivially optimizable cost functions, so sampling hardness does not by itself imply a quantum optimization advantage.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript establishes a sharp threshold at interaction degree 3 for classical simulation of QAOA with 2-local cost functions. For degree-3 instances, multiplicative-error sampling from depth-1 QAOA is shown to be #P-hard via an explicit reduction, implying collapse of the polynomial hierarchy to the third level. For degree-2 instances, exact sampling from depth-p QAOA is polynomial-time when p = O(log n), using an MPS/tensor-network contraction whose bond dimension scales as 2^{O(p)} on treewidth-2 graphs. The hardness constructions use cost functions that are trivially optimizable, so the sampling result does not claim an optimization advantage.

Significance. If the central claims hold, the work supplies a clean complexity separation governed by interaction degree, with an efficient classical algorithm on one side and a conditional hardness result on the other. The use of standard PH-collapse arguments and the explicit treewidth-based simulation are strengths; the note that the hard instances are trivially optimizable prevents over-interpretation as evidence for quantum optimization advantage. The result is likely to influence discussions of when QAOA can exhibit quantum advantage and of the role of graph structure in variational quantum algorithms.

major comments (2)
  1. [§3.2] §3.2, the reduction paragraph: the claim that QAOA amplitudes on the chosen 3-regular graphs encode a #P-hard quantity is load-bearing for the PH-collapse statement; the manuscript should exhibit the explicit mapping from the hard counting instance to the QAOA output distribution (including the precise form of the 2-local terms) so that the multiplicative-error sampling hardness can be verified directly.
  2. [§4.1] §4.1, Eq. (8): the runtime analysis states that sequential contraction and sampling on the treewidth-2 MPS yields n^{O(1)} time for p = O(log n); a short calculation showing that the per-step contraction cost remains polynomial when the bond dimension is 2^{O(log n)} would make the polynomial-time claim fully explicit.
minor comments (2)
  1. [Figure 1] The caption of Figure 1 could explicitly label the interaction graphs as degree-2 versus degree-3 to match the text discussion of treewidth.
  2. [§4] A reference to the standard result on efficient sampling from low-treewidth tensor networks (e.g., the contraction algorithm of Markov & Shi) would help readers place the degree-2 algorithm in context.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The suggestions improve clarity, and we have revised the paper accordingly to address both major points.

read point-by-point responses

  1. Referee: [§3.2] §3.2, the reduction paragraph: the claim that QAOA amplitudes on the chosen 3-regular graphs encode a #P-hard quantity is load-bearing for the PH-collapse statement; the manuscript should exhibit the explicit mapping from the hard counting instance to the QAOA output distribution (including the precise form of the 2-local terms) so that the multiplicative-error sampling hardness can be verified directly.

    Authors: We agree that greater explicitness strengthens verifiability. In the revised manuscript we have expanded §3.2 with a dedicated paragraph that spells out the reduction: we start from the #P-complete problem of counting independent sets on 3-regular graphs and map each edge of the input graph to a 2-local term of the form (1−Z_u Z_v)/2 in the QAOA cost Hamiltonian. The depth-1 QAOA amplitudes on the resulting 3-regular interaction graph then satisfy that multiplicative-error sampling of the output distribution recovers the independent-set count up to a known polynomial factor, yielding the desired #P-hardness. The construction is now fully self-contained and can be checked directly. revision: yes

  2. Referee: [§4.1] §4.1, Eq. (8): the runtime analysis states that sequential contraction and sampling on the treewidth-2 MPS yields n^{O(1)} time for p = O(log n); a short calculation showing that the per-step contraction cost remains polynomial when the bond dimension is 2^{O(log n)} would make the polynomial-time claim fully explicit.

    Authors: We thank the referee for this observation. We have inserted a short paragraph immediately after Eq. (8) that supplies the missing calculation. The MPS bond dimension satisfies D=2^{O(p)}. On a treewidth-2 graph each sequential contraction step multiplies matrices of size at most D×D and therefore costs O(D^3) arithmetic operations. With O(n) steps the total runtime is O(n D^3). Substituting p=O(log n) gives D=n^{O(1)}, so the overall time remains n^{O(1)}, confirming that exact sampling is polynomial-time. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via external complexity results

full rationale

The paper's central claims rest on standard tensor-network contraction for degree-2 graphs (using treewidth-2 structure to bound bond dimension as 2^{O(p)}) and an explicit reduction from #P-hard sampling problems for degree-3 instances. These steps invoke established results in complexity theory and graphical models rather than any self-referential fitting, ansatz smuggling, or load-bearing self-citation. The hardness argument is parameterized by specific 3-local cost functions whose QAOA amplitudes encode the hard quantity, but this encoding is constructed externally and does not reduce to the paper's own inputs by definition. No equation or premise collapses to a prior result from the same authors in a way that forces the threshold.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result depends on standard complexity-theoretic assumptions about the polynomial hierarchy and on the existence of particular 3-local cost functions that encode hard sampling instances; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The polynomial hierarchy does not collapse to its third level
    The hardness statement is conditional on this standard assumption; if the hierarchy collapses the implication is vacuously true.

pith-pipeline@v0.9.0 · 5622 in / 1216 out tokens · 44058 ms · 2026-05-22T05:28:48.253432+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [1]

    A Quantum Approximate Optimization Algorithm

    A quantum approximate optimization algorithm , author=. arXiv preprint arXiv:1411.4028 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    Quantum supremacy through the quantum approx- imate optimization algorithm

    Quantum supremacy through the quantum approximate optimization algorithm , author=. arXiv preprint arXiv:1602.07674 , year=

    work page arXiv

  3. [3]

    Karp , title =

    Richard M. Karp , title =. Complexity of Computer Computations , editor =. 1972 , pages =

    work page 1972

  4. [4]

    Garey and David S

    Michael R. Garey and David S. Johnson , title =. 1979 , address =

    work page 1979

  5. [5]

    SIAM Journal on Computing , volume=

    Simulating quantum computation by contracting tensor networks , author=. SIAM Journal on Computing , volume=. 2008 , publisher=

    work page 2008

  6. [6]

    1984 , publisher=

    Tovey, Craig A , journal=. 1984 , publisher=

    work page 1984

  7. [7]

    2022 , publisher=

    Introduction to algorithms , author=. 2022 , publisher=

    work page 2022

  8. [8]

    Theoretical Computer Science , volume=

    A partial k-arboretum of graphs with bounded treewidth , author=. Theoretical Computer Science , volume=. 1998 , publisher=

    work page 1998

  9. [9]

    Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=

    Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy , author=. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=. 2011 , publisher=

    work page 2011

  10. [10]

    Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=

    Quantum computing, postselection, and probabilistic polynomial-time , author=. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , volume=. 2005 , publisher=

    work page 2005

  11. [11]

    A simple proof that

    Aharonov, Dorit , journal=. A simple proof that

    work page

  12. [12]

    SIAM Journal on Computing , volume=

    Threshold computation and cryptographic security , author=. SIAM Journal on Computing , volume=. 1997 , publisher=

    work page 1997

  13. [13]

    Physical Review Letters , volume=

    Average-case complexity versus approximate simulation of commuting quantum computations , author=. Physical Review Letters , volume=. 2016 , publisher=

    work page 2016