What was already known
Earlier general influence bounds could decay exponentially with the degree. Lovett and Zhang gave a route through fractional certificates that depended on a further conjectured inequality. Blanc, Docter, Strassle and Tan obtained the quantum simulation consequence for a fixed number of rounds of parallel queries.
This revision has no four-dimension assessment. Read the criteria.
AI involvement
PSI credits a non-public Anthropic model with the determinant argument, the inequality comparing pairs of inputs, the first complete proof and two improvements to the bound. David Turturean developed and ran the research system, scoped the problem and reviewed and edited the manuscript. The proof builds on Lovett and Zhang’s fractional-certificate approach and Reimer’s Butterfly Lemma.
Importance
This proves the general influence conjecture. By Aaronson and Ambainis’s reduction, a classical algorithm can approximate a quantum query algorithm’s acceptance probability on most uniformly random inputs. For fixed accuracy and exceptional fraction, the classical query count grows polynomially in the quantum query count.
Technical verification
Formal checking
PSI reports kernel replay and sandboxed comparison with a separate Mathlib-only statement.
- Checker
- Lean 4 kernel and Nanoda through Comparator
- Scope
- Unconditional influence bounds in Theorem 1.1 and Corollary 1.2, including the original conjecture in its 0/1 normalization
- Basis
- Reported by the linked checker
Correction and publication history
Blanc, Docter, Strassle and Tan explain the main steps of Turturean’s proof, including the determinant argument.
Read this published revisionHuffstutler, Miloschewsky and Podder give a self-contained derivation of a special case of Turturean’s certificate inequality.
Read this published revisionAdd the arXiv copy of the original paper without a research notification.
Read this published revisionNew unconditional proof of the general Aaronson–Ambainis conjecture, with central AI work and source-reported formal checks.
Read this published revision