Distributional Variants of the Aaronson-Ambainis Conjecture

Abstract

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution μ_p, where the input bits are independent Bernoulli variables with fixed bias p. We show that for every fixed p ∈ (0, 1), quantum query algorithms under the μ_p distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution ν_p that is uniform over the slice of strings with Hamming weight ⌊ pn ⌋ and prove a similar equivalence for the ν_p distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

From pq-webs to magnetic quivers and back II: distributional indices and 5d theories breaking bad
Sebastiano Garavaglia, Sara Pasquetti, Palash Singh
arXiv28 Oct 2026PreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv
RIDDLE: Revealing Irregularities through Distributional Discrepancies in Latent-space via Stein-Witness Estimation
Ali Eren Simsek
arXiv22 Oct 2026PreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv
Stability of Collective Neutrino Oscillations -- A Distributional Approach
Rupak Majumder, Dwaipayan Mukherjee, Shamik Gupta +1
arXiv3 Sep 2026PreprintarXiv licenceFull textSolar & stellar physics High-energy & particle physicsarXiv
Distributional Counterfactual Dependence in the Special Sciences
Youheng Zhang
arXiv25 Oct 2026PreprintarXiv licenceFull textStatistics General physicsarXiv
Coordinate isoperimetric mass and a positive mass theorem for distributional scalar curvature
Melanie Graf, Eduardo Hafemann
arXiv6 Oct 2026PreprintarXiv licenceFull textGeometry & topology Gravitation & general relativityarXiv

Cite

BibTeX RIS

BibTeX

@misc{girish2026distributional,
  title = {{Distributional Variants of the Aaronson-Ambainis Conjecture}},
  author = {Uma Girish and Kunal Mittal and Barak Nehoran and Ran Raz},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35327},
  eprint = {2609.35327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35327},
}

RIS

TY  - UNPB
TI  - Distributional Variants of the Aaronson-Ambainis Conjecture
AU  - Uma Girish
AU  - Kunal Mittal
AU  - Barak Nehoran
AU  - Ran Raz
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35327
UR  - https://arxiv.org/abs/2609.35327
AB  - A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution μ_p, where the input bits are independent Bernoulli variables with fixed bias p. We show that for every fixed p ∈ (0, 1), quantum query algorithms under the μ_p distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution ν_p that is uniform over the slice of strings with Hamming weight ⌊ pn ⌋ and prove a similar equivalence for the ν_p distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.
ER  -

Abstract

Related

Cite