quant-ph digest — 2026-05-23
Scored against Yuan's research programme (Y1–Y6):
- Y1 — arXiv:2502.09704 — iterative warm-started QAOA
- Y2 — arXiv:2304.06915 — quasi-binary portfolio QAOA
- Y3 — arXiv:2410.16265 — QAOA DGMVP portfolio (QST 2026)
- Y4 — arXiv:2603.14744 — Grover + ADMM cardinality-constrained BO
- Y5 — arXiv:2510.08292 — GW speed-ups via Gibbs states + Pauli sparsity
- Y6 — arXiv:2510.11213 — PBR test on IBM Heron2
Source
arXiv listing: https://arxiv.org/list/quant-ph/new (54 new + 14 cross = 68 entries)
Coverage: all 68 entries scored. 4 relevant (score ≥ 1); 64 SKIP (score 0, omitted).
Scoring rubric
0–10 on method/scope/conclusion overlap — max wins. HIGH 8–10 · MED 5–7 · LOW 1–4 · SKIP 0.
Highly relevant (score 8–10) — 1 paper
A sharp interaction-degree threshold for simulating QAOA
- Authors: Ralfs Āboliņš, Andris Ambainis
- arXiv: 2605.22758
- Category: new submission — Quantum Physics (quant-ph); Computational Complexity (cs.CC)
- Score: 9/10 (HIGH)
- Overlaps with: Y1, Y2, Y3 — method (QAOA classical-simulation complexity, post-selected hardness), scope (2-local cost / Ising / portfolio-style Hamiltonians), conclusion (sampling hardness does not imply quantum optimisation advantage)
- Why it matters: sharpens the boundary between classically simulable and classically hard QAOA regimes (degree-2 = polynomial; degree-3 = PostBQP-complete), and explicitly flags that the hard family has a trivially-optimisable cost function — a direct caveat for any QAOA optimisation-advantage claim.
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 nO(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.
Moderately relevant (score 5–7) — 0 papers
None today.
Tangential (score 1–4) — 3 papers
- 2605.22770 · score 3/10 · Adiabatic Quantum Phase Estimation — adiabatic protocol for QPE; shares the adiabatic-evolution backbone with the QAOA/quantum-annealing family, but neither method nor scope is a real match.
- 2605.22551 · score 2/10 · Joint Unitarity and a Single Definite Outcome in a Quantum Measurement — measurement-problem foundations; tangentially adjacent to PBR/Y6 territory (what a single definite outcome means operationally), but no PBR test or ontic/epistemic content.
- 2605.22264 · score 2/10 · Statistical Interpretation of the Procedures Measurement of Physical Quantities — algebraic/probability synthesis of measurement foundations; PBR-foundations adjacent but no direct overlap with Y6's experimental Heron2 test.
Summary table
| Score | arXiv ID | Short title | Overlaps | arXiv |
|---|---|---|---|---|
| 9 | 2605.22758 | Sharp interaction-degree threshold for simulating QAOA | Y1, Y2, Y3 (method + conclusion) | link |
| 3 | 2605.22770 | Adiabatic Quantum Phase Estimation | Y1 (adiabatic backbone, weak) | link |
| 2 | 2605.22551 | Joint Unitarity and a Single Definite Outcome | Y6 (measurement foundations) | link |
| 2 | 2605.22264 | Statistical Interpretation of Measurement Procedures | Y6 (foundations) | link |