arXiv:2609.35327
Distributional Variants of the Aaronson-Ambainis Conjecture
Uma Girish, Kunal Mittal, Barak Nehoran, Ran Raz
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 \in (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 $\lfloor pn \rfloor$ 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.
AI Summary
The paper asks whether the conjectured polynomial classical simulation of quantum query algorithms under uniformly random inputs depends essentially on the uniform distribution. It studies biased product measures $\mu_{n,p}$ and uniform Hamming-slice measures $\nu_{n,p}$, supported on strings of weight $\lfloor pn\rfloor$. For every fixed $p,q\in(0,1)$, it proves equivalence between polynomial-overhead classical simulation under $\mu_{n,p}$, under $\nu_{n,q}$, and under the uniform measure. Simulation means approximating a $T$-query quantum algorithm’s acceptance probability in average absolute error $\epsilon$ using $\operatorname{poly}(T,1/\epsilon)$ classical queries, independently of input length. It also proves equivalence of the corresponding Aaronson–Ambainis influence conjectures: bounded degree-$d$ polynomials with variance $v$ have a coordinate of influence at least $(v/d)^{O(1)}$. The reductions between product measures compose the input with small Boolean gadgets that approximate a target bias. Product-to-slice reductions use a coupling with conditional coordinate-disagreement probability at most $4/\sqrt{an}$, where $a=\min(p,1-p)$, together with quantum hybrid bounds. For the polynomial statements, Markov’s inequality for polynomial derivatives yields variance and influence discrepancies at most $48d^2/\sqrt n$; small input lengths are handled separately. Neither original conjecture is resolved. Algorithms are nonuniform and computationally unbounded apart from queries. Biases must remain bounded away from zero and one for the stated broader distribution-family extensions. Slice polynomials are bounded on the entire cube, and coordinate influence uses values outside the slice, rather than the intrinsic swap-influence.
ChatGPT assisted in developing the remaining proofs and refining the exposition. The tools materially affected all the technical results in this paper.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.