New research has exploded the space of problems that quantum computers can efficiently verify, simultaneously knocking down milestone problems in quantum physics and math. By Mordechai Rorvig.
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.
The authors show that quantum computers can rapidly verify the solution to what is known as the halting problem. What allows this remarkable feat is quantum entanglement: each quantum computer contains subatomic particles that are entangled with particles in the other computer.
Entanglement offers a profound communication resource for the two quantum computers. In separate work from 2019, two of the new study’s coauthors, Anand Natarajan and John Wright, showed that entanglement allowed rapid verification of the solution of one class of enormously long problems, called NEEXP problems. To learn more follow the link for truly fascinating reading!
[Read More]