A November 6 preprint by David Turturean gives a proof of the Aaronson–Ambainis conjecture, a result about what quantum algorithms can learn by querying their input. A subsequent exposition explains the argument with weaker numerical bounds to make the ideas easier to follow.
Turturean says the mathematical statements came from AI models, including instances of a non-public Anthropic model, run in a research system he built at Physical Superintelligence. The paper reports that its main results were checked in Lean and links the formal proof repository. Turturean reviewed and edited the written draft.
What an influential input looks like
Take a toy function that averages two bits with unequal weights: multiply the first by three quarters and the second by one quarter, then add them. Flipping the first bit always changes the result by 0.75, while flipping the second changes it by 0.25. The first bit has the stronger influence. This example illustrates a function where the important bit is easy to spot. The theorem guarantees an influential input for a much broader class of bounded, low-degree functions with enough variation.
The application to quantum computing concerns how many times an algorithm reads its input. The paper shows how a classical algorithm can approximate a quantum algorithm’s acceptance probability on most inputs with a polynomial number of queries in the quantum query count, for fixed error tolerances. The guarantee is about input access. Actual runtime also depends on the work an algorithm does between queries. A claim about a particular speedup still needs to specify the input structure and the resource being measured.
Abdessalam Alaoui
I'm Abdessalam Alaoui, founder of Musthave.AI. I write practical guides to AI models, tools, generative media.
