Aaronson–Ambainis influential-variable conjecture

Here $x^{\oplus i}$ flips the $i$th sign. The conjecture is an exact analytic statement, independent of implementation costs. Aaronson–Ambainis show it would imply that a $T$-query quantum algorithm's acceptance probability can be approximated within additive $\varepsilon$ on a $1-\delta$ fraction of uniformly random Boolean inputs using $\operatorname{poly}(T,1/\varepsilon,1/\delta)$ classical queries.

The full influential-variable conjecture remains open. Its simulation consequence concerns acceptance probabilities on most inputs; it is not a worst-case simulation theorem for every promise problem, nor a theorem that a classical algorithm samples the full quantum output distribution.

August 2026 preprints, moved here from A16: Blanc–Docter–Strassle–Tan prove an analogous acceptance-probability simulation for $t$ queries in $d$ parallel query rounds, with $t^{O(d^2)}$ classical queries at fixed approximation and failure parameters. Liu–Mutreja independently establish constant-round and limited-adaptivity simulation results with different quantitative bounds. Constantly many oracle-query rounds are thus a positive restricted case; physical gate depth, unrestricted adaptive queries and sampling advantage are separate notions.

A16 retains the input/output/data-access comparison methods and the historical record; it is not counted as a second conjecture. Related: A1, A16.

Source disclosures

Blanc et al. report ChatGPT 5.4 use for literature search, note transcription, proof checking and copyediting; this is an author disclosure, not independent verification of the workflow. Source

Liu–Mutreja report that conversations with ChatGPT 5.5 Pro helped prove their constant-depth version and assisted with a main theorem's proof. Source

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

preprint: Bounded-round acceptance-probability simulation on most uniform inputs, with t^{O(d^2)} classical queries at fixed error parameters. Evidence

preprint: Independent simulation results for constant-round and limited-adaptivity quantum query algorithms; sampling is a different target. Evidence