Approximate average-case hardness for BosonSampling
Prove average-case approximate hardness for complex-Gaussian permanents, together with a robust reduction strong enough to rule out polynomial-time classical sampling within inverse-polynomial total-variation error for standard BosonSampling under standard wor
Problem statement
Prove average-case approximate hardness for complex-Gaussian permanents, together with a robust reduction strong enough to rule out polynomial-time classical sampling within inverse-polynomial total-variation error for standard BosonSampling under standard worst-case complexity assumptions.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Standard BosonSampling output probabilities involve squared permanents of interferometer submatrices; appropriate submatrices approach Gaussian matrices in the relevant hiding regime. The Aaronson–Arkhipov route to approximate-sampling hardness needs average-case approximate permanent hardness and anticoncentration, not merely worst-case hardness or exact probability evaluation.
July 2026 preprint: Koehler–Leung claim the full permanent anticoncentration conjecture via a complex-Gaussian small-ball estimate. This closes that ingredient at preprint level, but the approximate average-case hardness and sufficiently robust reduction remain unresolved. Exact-sampling consequences under noncollapse assumptions should not be substituted for this approximate target.
August 2026 preprints concern separate variants. Shou–Gorshkov–Galitski–Miller prove the Gaussian-BosonSampling hiding conjecture with equally squeezed inputs in the regime , where is the detected-photon number. Go–Jeong–Oh establish average-case hardness of probability estimation for threshold and parity BosonSampling in a linear-mode regime. Neither proves the stated approximate-sampling theorem for standard BosonSampling. Related: A13.
Source disclosures
Shou et al. report GPT-5.5 Thinking/Pro and GPT-5.6 Sol use for proof ideas, methods, checking and proofreading, and say they wrote the paper and checked every result and proof. Source
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
preprint: Claims the complex-Gaussian permanent anticoncentration conjecture; approximate average-case hardness is still missing. Evidence
preprint: Hiding theorem for Gaussian BosonSampling with equally squeezed inputs in the stated N = o(sqrt K) regime. Evidence
preprint: Average-case probability-estimation hardness for threshold/parity variants, not a general approximate-sampling theorem. Evidence
- [1]Aaronson & Arkhipov, 'The computational complexity of linear optics', Theory of Computing 9 (2013) link
- [2]Koehler & Leung, 'Anticoncentration of the Permanent in Ginibre Ensembles' (2026 preprint) link
- [3]Shou et al., 'Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes' (2026 preprint) link
- [4]Go, Jeong & Oh, 'Threshold and Parity BosonSampling in the Linear-Mode Regime' (2026 preprint) link
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.