From VICE, February 11:
New research has exploded the space of problems that quantum computers can efficiently verify, simultaneously knocking down milestone problems in quantum physics and math.
If today's computers had dreams and ambitions, there would be some problems that they wouldn’t even dream about solving. Some problems would take far too much time or memory, running on for nearly forever. But in an exciting new result, a team of computer scientists have shown how in theory quantum computers should be able to rapidly verify that a practically infinite problem was solved.
Quantum computers were not supposed to be able to do this. One prominent computer scientist and professor at the University of Texas at Austin, Scott Aaronson, called the discovery one of the biggest theoretical “surprises so far in this century”.
The new result, still awaiting peer review, comes from the abstract realm of theoretical computer science, where computers are examined through mathematical models and proofs. In this field, scientists can describe epic computers of unlimited power with scribbled definitions on paper.
“You’re not studying these [computers] in order to build anything,” said Thomas Vidick, one coauthor of the study and professor at the California Institute of Technology. Rather, the researchers theorize about quantum computers to understand the complexity of problems that they could solve. “Problems that are so hard that you are setting aside how much time it takes to solve them, and instead focusing on different ways to verify their solution.”
The authors show that quantum computers can rapidly verify the solution to what is known as the halting problem. (In mathematical terms, this can be stated as MIP* = RE.) The halting problem is the problem of determining whether a running program ever comes to a stop. The program must be finite in length, say, 100 lines of code long.
Alan Turing discovered that the halting problem was uncomputable in 1936, when he devised his breakthrough mathematical model of a computer, now known as a Turing machine. In this case, uncomputability means that there is no clever algorithm for solving the halting problem. If a computer simply watched a program run for an arbitrarily long time, then it could eventually determine if a program finally stops. But this strategy doesn’t count as computable, because useful computations must finish in a predictable time, whether that’s one day, or one year, or one billion years....
....MUCH MORE
