Quantum query algorithms under various input distributions are equivalently simulated by classical ones
Distributional Variants of the Aaronson-Ambainis Conjecture
Computational Complexity
Summary
There is a big question in computer science about whether classical computers can simulate certain quantum algorithms efficiently on average. The authors study this question for different ways of picking inputs instead of just the usual random inputs. They show that if classical computers can simulate quantum ones well on the usual random inputs, then they can also do so for these other input types, and vice versa. This means these variants of the problem are all essentially the same question.
What this means in practice
- •For quantum algorithm designers: Determine whether quantum query speedups rely on structured input distributions by considering simulations under various distributions equivalently.
- •For complexity theorists: Use equivalences across input distributions to focus efforts on proving or disproving a single core simulation conjecture.
A theory result. No direct application yet.
Authors
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.