A sharp interaction-degree threshold for simulating QAOA

Ralfs Āboliņš, Andris Ambainis · arXiv:2605.22758 · new submission, 2026-05-22 · score 9/10

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.

Executive summary

Āboliņš and Ambainis pin down a structural threshold for QAOA classical simulability: with 2-local cost functions, interaction-degree 3 already inherits Farhi–Harrow's PostQAOA = PostBQP sampling hardness (with a clean preprocessing trick to bound the interaction graph), while interaction-degree 2 is fully classically tractable in time n^O(1) for p = O(log n) via the Markov–Shi tensor-network contraction. This is the QAOA analogue of the 2-SAT / 3-SAT dichotomy. Crucially for Yuan's work on QAOA portfolio optimisation (Y2, Y3): the hard degree-3 instances built here have a trivially optimizable cost function — so even where sampling is hard, the optimisation problem on that instance class is easy. This sharpens the dividing line between "QAOA can do something classically hard" and "QAOA can outperform classical optimisers on this cost function".

Main contribution

The paper proves two complementary results bracketing 2-local QAOA. First (Theorem 3.1): a polynomial-time compilation that takes an arbitrary PostBQP circuit, decomposes it over {H, T^†, CZ}, and replaces every intermediate Hadamard with a diagonal coupling to an auxiliary qubit while inserting H² separators between consecutive diagonal gates, ending with the invariant that each wire carries at most one diagonal gate between Hadamards. The compiled circuit is genuine depth-1 QAOA (single phase layer e^−iπC/4 followed by a mixer ẽ⊗n) of interaction degree at most 3, and Proposition 4.5 shows the cost function C can be made monotone with maximum at the all-ones string. Second (Theorem 4.2): for interaction-degree-2 graphs the interaction graph decomposes into paths and cycles, each of cut width O(p); Markov–Shi then computes any marginal in time (np)^O(1) · exp(O(p)), and Corollary 4.3 promotes this to exact chain-rule sampling.

Key theorems / lemmas / algorithms

Definition 2.1 (interaction graph / degree): graph on [n] with an edge {j,k} whenever some 2-local term depends on both variables; interaction degree = max vertex degree.
Definition 2.4 (PostQAOA_p^deg≤d): languages decided with bounded error by post-selected depth-p QAOA of interaction degree at most d.
Proposition 3.1 (gadget identity): the diagonal two-qubit coupling W needed to substitute a Hadamard followed by single-qubit gate F is uniquely determined (up to global phase) by w_ab = λ(−1)^ab/r_b, and unitarity forces |r₀| = |r₁|.
Theorem 3.2 (degree-3 hardness): PostQAOA₁^deg≤3 = PostBQP, with the compilation preserving the post-selected output distribution exactly.
Corollary 3.3: PostIQP^deg≤3 = PP (drop in F=H, W=CZ).
Corollary 3.4 (PH collapse): multiplicative-error c < √2 classical sampling of depth-1 degree-3 QAOA ⇒ PH ⊆ Δ₃.
Proposition 3.6 (trivial optimum): the cost function in Thm 3.2 can be made monotone with maximum at x = 1ⁿ, so the hard sampling instances are easy to optimise.
Theorem 4.2 (degree-2 tractability): any marginal Pr[Z_S = z_S] of depth-p degree-2 QAOA on n qubits is computable in time (np)^O(1) · exp(O(p)).
Corollary 4.3: exact classical sampling in n^O(1) time whenever p = O(log n).

Detailed walkthrough

Setting. The setup (Section 2) is standard QAOA: a 2-local cost C = Σ C_i, the depth-p state |γ,β⟩ = ∏_k e^−iβ_kB e^−iγ_kC |+⟩^⊗n, and measurement in the computational basis. The interaction graph (Def 2.1) is the natural graph on [n] of variables that share a term. The degree of this graph is the structural parameter the paper varies. The post-selected complexity class PostQAOA_p^deg≤d (Def 2.4) is the standard "designated output qubit + post-selection register" tool used by Aaronson, Bremner–Jozsa–Shepherd and Farhi–Harrow.

The hardness side (Section 3). Prior work (Farhi–Harrow 2016) already proved PostQAOA₁ = PostBQP without any degree restriction. The contribution here is to bound the interaction degree by 3 without losing the equality. The construction has two ingredients:

(i) Coupling gadget (Prop 3.1). Suppose we want to replace a Hadamard on wire j by a diagonal coupling W to an auxiliary qubit a (prepared in |+⟩), followed by some single-qubit gate F on j and post-selection of j on |0⟩. The composite map V from j to a has entries V_ab = w_abr_b/√2 with w_ab = ⟨a,b|W|a,b⟩ and r_b = ⟨0|F|b⟩. Requiring V = λH (so that a inherits the logical wire as if a Hadamard had been applied) uniquely determines w_ab = λ(−1)^ab/r_b. Unitarity of W (entries on the unit circle) forces |r₀| = |r₁|. The Bremner–Jozsa–Shepherd choice (F = H, W = CZ) and the Farhi–Harrow choice (F = ẽ = e^−iπX/4, W = diag(1,i,1,−i)) are both recovered as special cases (Remark 3.2).

(ii) Degree-3 preprocessing. A naive substitution of every intermediate Hadamard explodes the interaction degree, because every consecutive diagonal gate on the same wire wants to share that wire's auxiliary. The trick (Fig 1a in the LaTeX) is to insert identities I = H² between consecutive diagonal gates, then absorb the boundary Hadamards into the |+⟩ preparation at the start and the ẽ mixer layer at the end. The invariant after preprocessing: every wire begins in |+⟩, ends with a single ẽ, and has at most one diagonal gate between consecutive Hadamards. Substituting each remaining intermediate Hadamard by the gadget gives a depth-1 QAOA circuit (one big diagonal phase layer of phases that are 8th roots of unity, then a uniform ẽ mixer with β = π/4) whose interaction degree is bounded by 2 + 1 = 3: each qubit is touched by at most 2 gadget couplings (incoming + outgoing) plus at most 1 original 2-local gate.

(iii) Polynomial-hierarchy collapse (Cor 3.4). Standard PostBQP amplification gives a circuit whose acceptance probability is in [0, ε] or [1−ε, 1]. A multiplicative-error c sampler approximates both the numerator and denominator of the post-selected acceptance probability to within factor c, hence the ratio to within c². For c < √2 and small ε this distinguishes yes- from no-instances, so PP ⊆ PostBPP ⊆ Δ₃, hence PH ⊆ Δ₃ by Toda.

(iv) The optimization caveat (Prop 3.6). Because W = e^−iπC_W/4 with C_W = 6|01⟩⟨01| + 2|11⟩⟨11|, and because diagonal phases depend only on the cost mod 8, one can shift coefficients by multiples of 8 to make every entry of every 2-local term nonnegative — giving a monotone cost function maximised at the all-ones string. So the "hard" QAOA instance has a cost function whose optimum is obvious by inspection. This is the paper's most pointed disclaimer: sampling hardness ≠ optimisation advantage. The authors leave open whether instance families exist where both are hard.

The tractability side (Section 4). Markov–Shi (Proposition 4.1, cited from their 2008 paper) gives T^O(1) exp(O(r)) simulation for a circuit of size T and cut width r. The authors observe that any graph of maximum degree 2 decomposes into paths, cycles, and isolated vertices. On a path with the natural left-to-right ordering, each edge {i,i+1} only crosses cut i, so the interaction-graph cut width is 1; multiplied by p phase layers, the QAOA circuit cut width is p. On a cycle, only the wrap-around edge {1,k} crosses every cut, raising the cut width to 2p. Mixer gates are single-qubit so contribute nothing. Markov–Shi then gives (np)^O(1) exp(O(p)) per component, additive across components (Theorem 4.2). Corollary 4.3 turns this into exact sampling via the chain rule: at step t, two marginal queries give Pr[z₁…z_t-1,Z_t = 0] and Pr[z₁…z_t-1,Z_t = 1], and z_t is drawn from the conditional. For p = O(log n), exp(O(p)) = n^O(1), so we get classical polynomial-time exact sampling.

Discussion (Section 5). The threshold mirrors the 2-SAT/3-SAT line in classical complexity (Karp 1972; Tovey 1984: SAT with each variable in ≤ 3 clauses is NP-complete, ≤ 2 clauses is P). Open questions explicitly listed: (a) extending degree-3 hardness from multiplicative to additive error (would need an anticoncentration bound for 2-local cost functions on degree-3 graphs, which the IQP machinery from Bremner–Montanaro–Shepherd does not directly transfer because IQP anticoncentration uses complete interaction graphs); (b) whether the exp(p) factor in degree-2 simulation can be improved; (c) whether QAOA instance families exist where both sampling and optimisation are classically hard.

Figures

No external figures extracted — the paper's only diagrams are inline TikZ/yquant quantum-circuit schematics (Figure 1: degree-reduction substitution on a single wire), which render at LaTeX compile time and have no standalone image file in the e-print source.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography. (The bibliography is short — 12 entries — and references only foundational QAOA / IQP / complexity work: Farhi–Goldstone–Gutmann, Farhi–Harrow, Bremner–Jozsa–Shepherd, Bremner–Montanaro–Shepherd, Aaronson, Aharonov, Markov–Shi, Tovey, Karp, Garey–Johnson, Han–Hemaspaandra–Thierauf, Cormen et al., Bodlaender.)

Overlap with Y1–Y6

Y1 (warm-started iterative QAOA) — method overlap. Y1 designs new QAOA initialisation/iteration schemes to improve the approximation ratio; this paper provides the complementary structural perspective — what classical complexity prevents QAOA from being efficiently simulated, and which graph structures already admit polynomial-time classical simulation. Direct relevance: any new QAOA variant aimed at quantum advantage on degree-2 graphs is dead on arrival (this paper makes that explicit); on degree-3 graphs there is sampling hardness but, as Prop 3.6 emphasises, no optimisation advantage on the constructed hard family.
Y2 (quasi-binary portfolio QAOA) — scope + method overlap. Y2 applies a hard-mixer QAOA-like ansatz to portfolio optimisation. Portfolio Hamiltonians (mean-variance with cardinality constraints) generically yield a dense interaction graph — degree ≫ 3 — so the paper's hard regime is the relevant one. The "sampling hardness ≠ optimisation advantage" disclaimer is directly relevant: it argues that QAOA papers should make optimisation-side benchmarks the load-bearing claim, not sampling-side complexity arguments.
Y3 (QAOA DGMVP, QST 2026) — scope + conclusion overlap. Y3's main empirical conclusion is that thermal-relaxation noise precludes quantum advantage for QAOA on DGMVP portfolios. This paper provides an orthogonal, complexity-theoretic precondition: if the interaction graph were degree-2 (which it is not, for typical portfolio instances), QAOA would already be classically simulable for p = O(log n). The two together give an outer bracket on QAOA portfolio prospects — degree-2 is classically easy, degree ≥ 3 has sampling hardness but no automatic optimisation advantage, and Y3 shows the noise barrier dominates in practice.
Y4 (Grover + ADMM, cardinality-constrained BO) — weak link. Different method family (Grover/amplitude amplification, not QAOA). The 2-local cost structure is unrelated to Grover's oracle-query model. Not a direct overlap.
Y5 (GW via Gibbs states + Pauli sparsity) — weak link. Y5 is about SDP relaxations and Gibbs-state preparation, not about variational depth-p ansatz simulation. The "Pauli sparsity"/"low-degree interaction" analogy is superficial.
Y6 (PBR Heron2 test) — no overlap. Foundations, not optimisation.

Recommended action for Yuan

Cite in next QAOA paper. This is a clean, citeable structural result that strengthens the framing of any QAOA paper that claims an optimisation advantage. Specifically: when Y2-style or Y3-style follow-ups argue for quantum advantage on portfolio/QUBO instances, citing Prop 3.6 sharpens the message — sampling-side hardness arguments are not enough; the paper must benchmark optimisation quality on instances that escape the degree-2 tractability regime.
Read alongside Farhi–Harrow 2016. The whole paper is a 6-page sharpening of that result; reading the two together is the fastest way to internalise where the "sampling hardness" frontier for QAOA currently sits.
Optional: probe portfolio interaction degrees. For Y3's DGMVP instances and Y2's portfolios, it is worth checking which interaction-degree regime the constructed Hamiltonians actually fall into. If degree-2 components dominate after sparsification, the classical-simulability conclusion bites; if not, the sampling-hardness regime applies and the burden shifts to the optimisation-side benchmark.