AI-assisted proof settles a 2008 question about quantum speedups

Started by Kane21, Today at 01:38 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Topic: AI-assisted proof settles a 2008 question about quantum speedups   Views(Read 87 times)
Active members in this topic:
Kane21(1)

Kane21

A long running puzzle in quantum computing theory may finally be solved, with help from AI. The Quantum Insider reports that a new proof resolves the Aaronson-Ambainis conjecture, which has been open since Scott Aaronson raised it in a 2008 lecture

In plain terms, the result says that huge quantum speedups in how many times an algorithm reads its input need some kind of structure in the problem. For yes or no questions on most random inputs, quantum computers cannot gain an exponential advantage in input reads

The paper's author is David Turturean of Physical Superintelligence, whose in-house research system ran instances of a non-public Anthropic model. The models searched the literature, proposed and combined ideas, and tested arguments, and the first complete proof appeared on the third day of the run before the bound was improved twice

Turturean chose the problem, edited the draft and takes responsibility for it. The main theorem was formally checked in the Lean proof assistant, and Stanford researchers who proved a narrower version in August have reviewed the full proof, although it has not yet been through peer review

There are limits worth noting. The result holds for most inputs rather than all, it bounds the number of reads rather than total computing effort, and the bounds still allow a lot of reads. Even so, a machine checked proof of a famous open problem, found with AI help, is a striking moment for mathematics and computer science

Does this change how you think about AI in research? And how much should we trust proofs found with machine help?