AI confirms a long-suspected limit on quantum computers’ advantages - New Scientist

Quantum computers can’t significantly outperform standard computers for some calculationsmesh cube/Getty Images A decades-old, vastly influential conjecture about quantum computing has finally been proven – by AI. It confirms that a whole class of mathematical problems would not be more easily solved by quantum computers. In 1999, Scott Aaronson of The University of Texas at Austin got stuck on a question about when exactly quantum computers could excel over their conventional counterparts. At this time, researchers knew of at least one example of a problem where the quantum approach outshone all others: Shor’s algorithm for factoring numbers. But they suspected that this hinged on specific mathematical structure that underlies the factoring problem. Aaronson wondered whether quantum computers could also win in the opposite case, when the problem contained little to no structure and lots of randomness instead. In 2011, he and Andris Ambainis at the University of Latvia formally conjectured that in at least one case the answer was negative, but they could not prove it.