Preprint explains a proof limiting quantum query advantages on most inputs

Quantum algorithms can sometimes solve problems with far fewer input queries than classical algorithms. But how much does that advantage depend on special structure in the inputs? A preprint by Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan explains a recent proof of the Aaronson–Ambainis conjecture, a mathematical statement that helps make this question precise.

The article is an exposition of a proof attributed to David Turturean, rather than a report of a computing experiment. It is available as an arXiv preprint; the authors say it is not intended for conference or journal publication. Its claims should be understood in that publication context, not presented as independently established by peer review.

The setting is the query model. An algorithm receives access to an input string and requests information about its bits. Researchers count those requests, rather than all the computational work involved. A quantum algorithm can query in superposition, whereas a classical algorithm accesses bits classically.

The conjecture concerns polynomials that take binary strings as inputs and always produce numbers between zero and one. Their degree, d, limits how many input variables can occur together in a polynomial term. Their variance measures how much their outputs fluctuate around the average, with all binary strings equally likely.

A variable’s influence is the average squared change in the output when that bit is flipped. The conjecture says that a low-degree bounded polynomial with appreciable variance cannot spread its dependence so thinly that every bit has negligible influence: some bit must have influence bounded below by a polynomial expression in variance and inverse degree.

The exposition proves a specific bound: maximum influence is at least a universal positive constant times Var(p)^8/d^12. It reports a stronger bound from the original proof, proportional to Var(p)^(5/2)/d^6. The authors deliberately sacrifice sharper exponents to emphasize the argument’s structure.

The proof connects four main ingredients. First comes a certificate–influence inequality. A certificate describes information sufficient to establish an output. A fractional certificate instead assigns nonnegative weights to bits: for any alternative input, the weights on differing bits must cover the change in output. Its cost is the total weight. An existing result supplies certificates costing at most a constant times d squared for bounded degree-d polynomials.

The new inequality connects certificate costs to an influential variable for functions whose outputs are zero or one. Crucially, it uses averages of reciprocal costs on both output classes. Looking only at the most expensive certificates would not suffice for the reduction used here.

Second, a weighted all-pairs inequality relates influences to the overlap between fractional certificates for inputs with opposite outputs. Third, a routing lemma establishes the geometric control needed for that inequality. Binary strings form the vertices of a high-dimensional cube, with an edge joining strings differing in one bit. The lemma selects points within specified regions while controlling coordinate-by-coordinate disagreements through influences.

Fourth, an antipodal routing lemma handles strings that are opposite corners of a cube. Its proof uses determinants—signed sums associated with square matrices—to encode possible permutations of vertices. A matrix identity preserves certain minimal polynomial terms when geometric constraints are imposed, establishing the required routing.

To return from binary-valued functions to the original polynomial, the authors threshold its output: values above a chosen cutoff become one, and the rest zero. Averaging over thresholds near the mean transfers the influence guarantee back to the polynomial.

The quantum consequence follows because a t-query quantum algorithm’s acceptance probability is a polynomial of degree at most 2t. A classical simulator can query influential bits successively until that probability becomes nearly constant. For any positive error tolerance ε and exceptional fraction δ, the resulting query bound is polynomial in t, 1/ε and 1/δ, with additive error at most ε on at least a 1−δ fraction of uniformly distributed inputs.

These qualifications matter. The guarantee is not for every input, does not cover arbitrary input distributions, and bounds queries rather than total running time. It concerns decision problems; the paper notes that an analogous search-problem statement is false.

The result also makes unconditional a previously conditional implication connecting random-oracle separations to a separation between classical and quantum promise-problem classes. It does not resolve whether efficient classical and quantum computation have equal power.

According to the authors, Turturean discovered the proof using a Physical Superintelligence research system together with a non-public Anthropic model. They used public Anthropic models while preparing the exposition. That account describes the proof’s provenance, not an independent test of its correctness.