PSI says a non-public Anthropic model proved the Aaronson-Ambainis conjecture, open since 2008

A proof checker accepted it on the third day of the run, seven years after the last claimed proof was retracted.

By Think Facility · November 6, 2026 · Anthropic AI research

On November 6, 2026, Physical Superintelligence (PSI) said it had a proof of the Aaronson-Ambainis conjecture, a question about quantum computers that had been open since 2008. The company posted the news on X at 9:05 am Eastern and put the write-up on its own site.

The proof came from a research system PSI built in-house, running instances of an Anthropic model that isn't public. PSI says the system had a complete proof during the third day of the run, and Lean accepted it.

Who: Physical Superintelligence (PSI)
Model: A non-public Anthropic model
Open since: 2008
Proof found: During the third day of the run
Checked by: Lean, a proof assistant

PSI's own post is short, and it's where the claim was first made in public.

Physical Superintelligence@psipbcNov 6, 9:05 am ET

Today Physical Superintelligence PBC is announcing a proof of the Aaronson-Ambainis conjecture, one of the central open problems in quantum complexity, with major implications for quantum computing speedup. https://t.co/sAewkKdSOu Thread 👇

View the post on X

What the conjecture says

Scott Aaronson and Andris Ambainis wanted to know whether a quantum computer can be exponentially faster than an ordinary one on a random input, one with no hidden pattern in it. Shor's 1994 factoring algorithm gets its speed from exactly that kind of pattern. Aaronson wrote in 2019 that around 2008 he noticed the answer would follow from a statement about polynomials.

That statement is about influence. Take a low-degree polynomial whose value always stays between 0 and 1 and isn't constant: some single bit has to move it by a real amount. PSI proves a floor of (v/d) to the seventh power, where v is how much the value varies and d is the degree.

Here's why that matters. With the conjecture proved, an ordinary computer can predict a quantum computer's yes-or-no answer on most strings by reading only a few more bits. The extra cost grows like a fixed power of the number of quantum looks, not exponentially. So the quantum machine can't save exponentially many looks "unless the string has a rare pattern," in PSI's words.

Who checked it

PSI credits David Turturean, a member of its technical staff, with building the system and running it on the problem. He then had the model package the results into a first draft of the paper, reviewed it, and is responsible for its correctness. Jim Halverson, an adviser, audited the proof. Phiala Shanahan, another adviser, commented on the Lean formalization.

The public repository puts it more plainly: "The proof, the paper and the formalization were produced by AI models." It says the Lean files have no placeholder and no added axiom, and that two independent implementations of the Lean kernel re-checked them.

In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford had settled a special case: no exponential speedup on random inputs for quantum algorithms that read their input in a fixed number of parallel rounds. PSI says the four have been reading the full proof and are writing a shorter exposition for experts. They wrote to PSI:

This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups.

From A proof of the Aaronson-Ambainis conjecture · PSI

The last claimed proof didn't hold

This conjecture has been "proved" before. On November 17, 2019, Aaronson blogged that Nathan Keller and Ohad Klein said they had a proof. He later added an update at the top: they'd retracted their preprint over what looked like "a fatal flaw in Lemma 5.3," which Paata Ivanishvili found.

That flaw was caught by a person reading the paper. PSI's proof has already been through a machine check, and the repository says a reader only has to read one Lean definition, PrintedConjecture, to confirm the theorem states the conjecture as Aaronson and Ambainis printed it. That's the part people still have to do by eye.

The announcement lands seven weeks after Aaronson wrote, on September 15, 2026, that he'd been told AI companies "are now sitting on solutions to some very major problems" (we covered that post). PSI's page doesn't say when the run took place, and it doesn't name the Anthropic model.

What it means for encryption

The quantum computers most people worry about are the ones that could break today's encryption. NIST, the US standards agency, released its first three post-quantum encryption standards on August 13, 2024. On October 27, 2026 it published a road map for switching to them: federal high-value systems have to move by 2030 for key establishment and 2031 for digital signatures, under Executive Order 14412, with 2035 the target for federal systems overall.

PSI's theorem is about inputs with no hidden pattern. Its own page puts Shor's algorithm on the other side of that line, as a speedup that relies on structure. So nothing in the write-up touches the case for switching, and NIST's reason for hurrying, which it calls "harvest now, decrypt later", is about data collected today and read once the hardware exists.

Where the result does land is in quantum computing research itself. (My reading: it tells anyone hunting for exponential quantum speedups that random, unstructured inputs won't give them one.) The Stanford group's shorter exposition is still being written, and PSI didn't give a date for it.