# Quantum Advantage Aiwiki — Bills Draft (v0.2)

> Status: post-batch-1 revision. Promoted observable-estimation reframe to Bill_14. Added M7 meta-cost. Locked taxonomy expected after batch 2 (~600 papers).

## Taxonomy version history

- v0.1 (2026-05-08, pre-sweep): 13 bills + 6 meta-costs + 3 escape gates
- **v0.2 (2026-05-08, post-batch-1)**: **14 bills** + **7 meta-costs** + 3 escape gates. Promoted Bill_14 (observable-estimation reframe) after sweep 07 returned 9 papers in coherent cluster. Added M7 (honest-utility framing) after sweep 06 surfaced IBM-led rhetorical pattern.

## The fourteen bills

A "bill" is a closure mechanism that any quantum-advantage claim must engage. We name them by the structural primitive they invoke.

| # | Bill | What gets paid | Empty-space candidate |
|---:|---|---|:---:|
| 1 | **Tensor network simulation** | Bond dimension threshold; advantage window shrinks as TN improves (Pan–Zhang, Tindall, Lykov, Kalachev, Schuch, Gray). | |
| 2 | **Stabilizer / Pauli sparse simulation** | Clifford+T circuits up to T-count threshold are classically efficient (Bravyi–Gosset, Pashayan–Bartlett–Gross, Begusic-Chan). | |
| 3 | **Approximate sampling** | TV tractability for low-depth random circuits (Aharonov–Bouland–Fefferman, Bremner–Jozsa–Shepherd). | |
| 4 | **XEB / cross-entropy spoofing** | Linear-XEB scoring spoofable for some classes (Boixo–Kalachev). Bill paid by stronger benchmark (HOG, fidelity-via-XEB, witness-based tests). | |
| 5 | **Verification gap** | Output cannot be classically verified — no advantage *claim* survives because experiment is unfalsifiable. Bill paid by interactive proof, cross-platform verification, or reduction to a classically-checkable instance. | |
| 6 | **Logical-vs-physical qubit accounting** | Physical-qubit demos don't generalize to fault-tolerant. Bill paid by reporting logical qubit count after error-correction overhead, or below-threshold error rates. | |
| 7 | **Error mitigation overhead** | ZNE, PEC, virtual distillation don't scale — sample complexity grows exponentially in mitigation budget. | |
| 8 | **Algorithmic separation on real targets** ★ | Shor on ≥1024-bit RSA, Grover on real cryptographic search, HHL on real linear systems. ★ **Empty-space candidate (HOLDING through batch 1, n=10):** all 10 candidates pay M5 (resource-unbounded). | ★ |
| 9 | **Variational competitor parity** | VQE / QAOA / QNN claims must beat DMRG / classical-ML / MCMC under matched compute. | |
| 10 | **Useful-task gap** | Advantage demonstrated only on hardware-designed tasks (RCS, GBS) without practical application. | |
| 11 | **Boson sampling / GBS spoofing** | Classical samplers (Quesada-Arrazola, Oh-Lim, Villalonga, Drummond) match GBS verifier scores without simulating photonic device. | |
| 12 | **Useful logical-task at >100 logical qubits** ★ | The signature target. ★ **Empty-space candidate (HOLDING through batch 1, n=9):** strongest candidate is Zhao-Zlokapa-Preskill-Babbush-McClean-Huang `arxiv:2604.07639` — 60 logical qubits SIMULATED + relies on unphysical "quantum oracle sketching" primitive (M5). DARPA QBI Phase 1 found 0 of N evaluated vendors trigger this bill. | ★ |
| 13 | **Heuristic advantage with classical control** ★ | Claimed quantum advantage on heuristic tasks (combinatorial optimization, materials discovery) without strong classical baseline that exploits the same problem structure. ★ **Empty-space candidate (HOLDING through batch 1, n=16):** all 16 candidates pay M1 (hardware-only) or M3 (asymptotic-only). Closest existing candidate to falsifier: IBM Heron-156 optimization (Nature Physics 2024), no Pan-class problem-structure-aware classical heuristic was tested. | ★ |
| **14** | **Observable-estimation reframe** [NEW v0.2] | Polynomial-precision *observable estimation* is classically tractable for many circuits where sampling is hard. Bill paid by either showing the advantage task requires sampling (not estimation), or by accepting that the advantage is in a model where observable-estimation isn't the natural target. Lineage: Huang-Chen-Cotler-Preskill, Angrisani-Schmidhuber-Rudolph-Cerezo-Holmes-Huang (source handle pending lint), Krovi-O'Donnell, Begusic-Hejazi-Chan, Schmidhuber-Cerezo-Holmes. **10 papers in batch 1 cohort.** | |

★ = signature construction; empty-space hypothesis predicts no paper in 2024–2026 corpus triggers cleanly without paying meta-costs.

## Seven meta-costs (disqualifying conditions)

| # | Meta-cost | Description |
|---:|---|---|
| M1 | **Hardware-only special-form task** | Task constructed specifically for the hardware's natural Hamiltonian (e.g., random circuit sampling) with no externally-motivated definition. |
| M2 | **Trust the device** | No classical or interactive verification of output; advantage holds only if you trust experimenter's claim about distribution. |
| M3 | **Asymptotic-only claim** | Speedup is in $O()$ notation; no concrete crossover demonstrated. |
| M4 | **Hypothesis-conditional speedup** | Quantum advantage holds only conditional on unproven complexity-theoretic hypotheses (PH non-collapse, $\mathsf{P}^{\#\mathsf{P}}$ separation, LWE hardness, etc.). |
| M5 | **Resource-unbounded quantum hardware** | Claimed advantage assumes ideal qubits / unlimited coherence / unlimited gate fidelity, with no engineering path to realization. |
| M6 | **Variant model** | Advantage in a non-standard model (measurement-based, adiabatic, photonic-only, neutral-atom-only) with no obvious extension to gate-model or fault-tolerant settings. |
| **M7** | **Honest-utility framing** [NEW v0.2] | Paper or vendor explicitly disavows asymptotic advantage and frames itself as "utility" / "useful work" / "practical demonstration" rather than supremacy claim. The framing itself is a closure — it's the author/vendor stating they don't trigger any bill. IBM "quantum utility" lineage is the prototype. |

## Three escape gates (unchanged from v0.1)

A paper that triggers no bill but also fits no meta-cost passes one of three escape gates:

1. **Classical-simulation / spoofing rebuttal** — paper is *itself* a rebuttal of an advantage claim, counts as a closure mechanism in its own right.
2. **Hardware capability paper** — roadmap or hardware-specs document making no advantage claim. Tracked in watch-list but not bill-classified.
3. **Theoretical separation paper** — proves a complexity-theoretic separation (oracle, query, communication) without implementation claim. Tracked but out-of-scope.

## Deferred candidates (need batch 2 evidence)

These were proposed during batch 1 but lacked sufficient corroboration:

- 🟡 **Bill_1a / Bill_1b sub-bill split** — TN bond-dim vs noise-induced Pauli-path simulability. Currently both fall under Bill_1. **Decision rule: split if Bill_1b populates ≥4 standalone candidates after batch 2.** (Note: many of these now mapped to Bill_14 instead, so split may be obsolete.)
- 🟡 **Connectivity-overhead bill** — Placidi et al. `arxiv:2604.12635`: IQP advantage windows depend on hardware connectivity orthogonal to gate noise. **Single-paper signal.** Need batch 2 corroboration.
- 🟡 **Query-complexity-only advantage bill** — Singkanipa-Kasatkin-Lidar `arxiv:2604.27457`: exponential speedup on Simon's problem in query-complexity metric, not wall-clock. Already rebutted (Tuziemski). **Single-paper signal.**
- 🟡 **Cryptographic-verification-via-LWE sub-bill** — Aharonov-Brakerski + Vaikuntanathan-Kalai + Mahadev cluster. **Currently Bill_5 + M4.** Promote to standalone bill if implementations appear in 2026 Q3–Q4.

## Dual-bill cases noted (atlas should support)

- **D-Wave annealing supremacy** sits between Bill_1 (TN closure) + Bill_13 (heuristic classical control). Tag both bills once taxonomy locks.
- **IBM Eagle/Heron utility experiments** trigger Bill_9 (variational) + Bill_14 (observable-estimation) in many cases.

## Iteration plan

- ✅ **Batch 1 (this batch, complete):** 8 sweeps × ~30-50 papers = 346 unique papers. Tested bill draft against the corpus. Promoted Bill_14, added M7. Empty-space prediction holding for Bills 8, 12, 13.
- **Batch 2 (next):** ~6-8 targeted sweeps to fill gaps:
  - IACR ePrint quantum-cryptanalytic deep sweep (Bill_8 territory; cross-reference factorization atlas)
  - CRYPTO / EUROCRYPT / ASIACRYPT 2024-2026 quantum sessions (Bill_8)
  - Quantum-ML claim papers (Bill_9 / Bill_12 boundary)
  - Pauli-path / observable-estimation full sweep (Bill_14 — now a real bill)
  - Hardware capability paper deep sweep (Bill_6 + watch-list)
  - DARPA QBI Phase 2 + DOE QSC + EU Quantum Flagship (Bill_12 / Bill_13)
  - Hidden-shift / abelian period-finding / new-quantum-algorithm sweep (Bill_8 cousin space)
  - Variant-model advantage sweep (M6 territory: measurement-based, adiabatic, photonic-only)
- **Batch 3:** edge-case + falsifier protocol drafting. Lock the taxonomy.
- **Batch 4 (final):** comprehensive coverage; lock atlas at ~600-800 papers.

## Resource estimate updated

Original estimate: 250-300 papers. Batch 1 already returned 346 unique. **Revised estimate: 700-900 papers at lock time.** The literature is denser than the factorization corpus (which was 504); quantum advantage has a particularly active rebuttal layer (sweep 07 alone returned 77 rebuttal papers).