A quantum strategy could verify the solutions to unsolvable problems — in theory
Computer scientists’ daydreams have revealed the power of quantum mechanics. Imagine meeting omniscient beings who claim to have the solution to a complex problem that no computer could ever solve. You’d probably be at a loss to check the answer. But now, computer scientists report that quantum mechanics provides a way to quickly verify the solutions to an incredibly broad class of problems, including some that are impossible to solve in the first place. Although the result doesn’t have obvious practical applications, its theoretical ramifications have had a ripple effect, answering unsolved questions in physics and mathematics, scientists report in a paper posted January 13 at arXiv.org. “It has so many implications for all these areas. It’s a huge deal no matter how you look at it,” says theoretical computer scientist Scott Aaronson of the University of Texas at Austin, who was not involved with the new study. In computer science, some problems are difficult to solve but have solutions that are easy to check....