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

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. 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. 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. For one, theoretical computer scientists already knew that quantum computers can solve any problems that classical computers can. But Raz and Tal’s paper demonstrates that quantum and classical computers really are a category apart—that even in a world where classical computers succeed beyond all realistic dreams, quantum computers would still stand beyond them.