A shorter proposed proof of a limit on quantum query advantages

What the result says

The paper studies Boolean functions: rules that turn an input string of bits into a single output bit. A partial Boolean function specifies an answer only for certain valid inputs. Those inputs form its domain; its density, δ, is the fraction of all possible bit strings that are valid.

In the query model, an algorithm learns about an input by accessing its bits. Quantum query complexity, written Q(f), measures the number of input queries needed by a quantum algorithm. This model counts information access, rather than the complete running time of a program.

The authors claim that, for any permitted error fraction ε between zero and one, a deterministic classical algorithm can agree with the function on at least a 1 − ε fraction of its valid inputs using

O(Q(f)^6 / (εδ)^2) queries.

The big-O notation hides a constant factor. The accuracy guarantee counts valid inputs equally: it is not a promise of correctness on every valid input, nor a guarantee for every possible input distribution. The classical algorithm itself need not use randomness; the allowed error comes from the subset of inputs on which its answer can be wrong.

Domain density matters substantially. A smaller δ makes the bound weaker, as does demanding a smaller error fraction. For fixed density and accuracy, however, the classical query bound is polynomial in the quantum query complexity.

Turning a partial rule into a complete one

The central device is a completion. This assigns outputs to every bit string, including those for which the original problem gives no answer. Here, the authors also allow the completed function to disagree with the original on a small fraction of its domain.

That reframes the goal: construct a function defined everywhere that is easy to compute classically and preserves almost all the required answers. The resulting algorithm does not need to test whether its input belongs to the preserved subset.

The proof first works with the classical adversary measure, CAdv(f). Its definition assigns nonnegative weights to input coordinates, with constraints ensuring that inputs requiring opposite outputs have enough weight on coordinates where they differ. The paper then uses an existing bound, CAdv(f) = O(Q(f)^2), to obtain the sixth-power quantum-query result.

The authors construct an initial completion with controlled total influence. For a Boolean function, a coordinate’s influence is the probability that flipping that bit changes the output, when inputs are uniformly distributed. Total influence adds these probabilities across all coordinates.

They also control fractional certificates at the original valid inputs. These are weighted guarantees: any input with the opposite output must differ on coordinates carrying at least a specified total weight.

How the algorithm makes progress

After some bits have been queried, the remaining possible inputs form a subcube—all strings consistent with the answers already received. A certificate inequality identifies an influential unqueried coordinate whenever both required outputs still occur among valid inputs in that subcube.

Querying that coordinate decreases the expected remaining total influence. Tracking this decrease bounds how much uncertainty can remain after a given number of queries. At the stopping point, the algorithm outputs whichever answer is more frequent among the valid inputs still consistent with its observations. The analysis bounds the total fraction of mistaken answers.

The authors credit David Turturean’s earlier preprint with supplying the missing certificate inequality. They use a special case and provide a self-contained proof involving weighted counting and a polynomial matrix determinant. Their disclosure also describes earlier exploratory work assisted by ChatGPT; it says those efforts had not supplied the missing ingredient.

A second claim—and the limits

An appendix derives the bounded-polynomial influence conjecture. For a polynomial bounded between zero and one on bit strings, with degree d and positive variance v, the authors prove that some coordinate has influence at least a constant times v^12/d^12. Here, influence means the average squared change caused by flipping that coordinate.

These are mathematical proof claims, not hardware experiments or performance benchmarks. The query bound does not establish an equally efficient end-to-end classical implementation or eliminate quantum advantages in other settings. Version 1 was posted to arXiv on November 9, 2026. It is a preprint, and the supplied evidence does not establish independent verification or peer-reviewed acceptance.