Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve

Kevin Hartnett in Quanta:

Early on in the study of quantum computers, computer scientists posed a question whose answer, they knew, would reveal something deep about the power of these futuristic machines. Twenty-five years later, it’s been all but solved. In a paper posted online at the end of May, computer scientists Ran Raz and Avishay Tal provide strong evidence that quantum computers possess a computing capacity beyond anything classical computers could ever achieve.

Raz, a professor at Princeton University and the Weizmann Institute of Science, and Tal, a postdoctoral fellow at Stanford University, define a specific kind of computational problem. They prove, with a certain caveat, that quantum computers could handle the problem efficiently while traditional computers would bog down forever trying to solve it. Computer scientists have been looking for such a problem since 1993, when they first defined a class of problems known as “BQP,” which encompasses all problems that quantum computers can solve.

Since then, computer scientists have hoped to contrast BQP with a class of problems known as “PH,” which encompasses all the problems workable by any possible classical computer — even unfathomably advanced ones engineered by some future civilization. Making that contrast depended on finding a problem that could be proven to be in BQP but not in PH. And now, Raz and Tal have done it.

More here.