Physical Superintelligence says its AI proved an 18-year-old quantum computing conjecture

Physical Superintelligence says its AI research system has proved a quantum computing conjecture open since 2008—and published a formal proof that it says software accepted. The November 6 announcement offers a concrete artifact to examine, not just a breakthrough claim. But the paper had not been peer-reviewed as of Quantum Zeitgeist’s November 8 report.

The company, known as PSI, says its internal system ran instances of an unreleased Anthropic model on its own computing infrastructure. It produced a complete proof of the Aaronson-Ambainis conjecture on the third day of the run.

PSI then gave the system related open problems, and says it improved the result twice. Lean, a proof assistant that checks mathematical arguments step by step, accepted the original proof and the final version, according to the company. PSI published the paper and full formal proof on GitHub.

The conjecture takes its name from computer scientists Scott Aaronson and Andris Ambainis. Their paper, The Need for Structure in Quantum Speedups, was first posted in 2009, following work on the question around 2008.

The mathematical question starts with a long string of zeros and ones. Researchers count queries: the number of times an algorithm reads part of that input. An ordinary computer reads one bit per query. A quantum query can span many positions in superposition.

For yes-or-no questions on typical random inputs, the conjecture predicts that an ordinary computer can approximate the quantum algorithm’s answer without exponentially more queries. Its query count would instead grow as a fixed power of the quantum algorithm’s count—a polynomial gap.

The bridge is a mathematical expression called a polynomial. A 1998 result showed that a quantum algorithm’s probability of answering yes can be written this way. The expression’s degree, a measure of its complexity, is at most twice the number of quantum queries.

Think of that probability as a dial connected to switches representing the input bits. A switch’s influence measures how much flipping it changes the dial on average. The conjecture says that if the dial varies, at least one switch must have enough influence, with a bound tied to that variation and the polynomial’s degree.

1. Read the most influential input bit it has not yet examined.
2. Update the expression using that bit’s value, then choose the next influential bit.
3. Stop when the unread bits barely change the result, and use the remaining average as its prediction.

The distinction between random and structured inputs is essential. Shor’s factoring algorithm exploits hidden periodicity—a repeating mathematical pattern. Grover’s search algorithm needs no such structure, but offers a square-root saving rather than an exponential one.

Earlier general bounds weakened exponentially as the polynomial’s degree increased. They were too weak to rule out exponential quantum advantages. PSI says its theorem supplies the stronger bound, with an explicit power.