Finally, a Problem That 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. Twenty-five years later, it’s been all but solved. In a paper posted online at the end of May, computer scientists Ran Raz, former Visiting Professor in the School of Mathematics, and Avishay Tal, former Member in the School, provide strong evidence that quantum computers possess a computing capacity beyond anything classical computers could ever achieve.