Skip to content

Distributional Variants of the Aaronson-Ambainis Conjecture

Sep 2026 · arXiv.org · Vol abs/2609.35327 · 1 citation · 19 references
Physics Computer Science

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 $\mu_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 $\mu_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $\nu_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $\nu_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.

View source

Similar papers

Preprint Nov 2026

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $\delta$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<\epsilon<1$, a deterministic algorithm computes $f$ correctly on at least a $1-\epsilon$ fraction of its doma...

Thomas Huffstutler, David Miloschewsky, Supartha Podder · 0 citations
Preprint Nov 2026

Proof of the Aaronson-Ambainis Conjecture: An Exposition

We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated clas...

Guy Blanc, Jordan Docter, Carmen Strassle et al. · 0 citations
Preprint Nov 2026

A proof of the Aaronson-Ambainis conjecture

Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathr...

David Turturean · 1 citation
Oct 2026

Unconditional Quantum PAC Learning Advantage in the Large Error Regime

We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $\lambda(n) = n^{-\omega(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $...

I. C. Oliveira · 0 citations
Preprint Oct 2026

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we sho...

Keshav Bhateja, Mehdi Esmaili, A. Mantri · 0 citations
Preprint Oct 2026

Distributional Quantum Query Complexity

This work gives distributional joint computation lower bounds for the composition, direct sum, and direct product problems, and introduces some new tools for handling quantum query lower bounds, including a new ``Shaltiel-free''measure of quantum query complexity, which characterizes the composition behavior of distrib...

S. Ben-David, M. H. Ebtehaj · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.