Solving puzzles has been Computer Scientists’ job from day one. From the days of Alan Turing, that’s what they’ve been doing. Figuring out the best possible way to solve a problem and verifying them. What if someone claimed to have the solution to a problem, but you didn’t have a way to verify the answer? What would you do? The answer is Quantum Mechanics.
This is where the Computer Scientists come in. In a new paper, they’ve claimed that Quantum Mechanics provides a way to verify the solution to an incredibly broad class of problems, including some that are impossible to solve in the first place. The practical effects might not be that obvious, but the theoretical effects have sent waves across the scientific community as it has implications in Physics, Mathematics, and of course Computer Science.
Computer Science has problems that are hard to solve but are easy to verify. Therefore, researchers classify problems according to how hard it is for a computer to verify the answer. When left to its own devices, a computer cannot do much to verify the solution. To overcome this problem, researchers have come up with some tricks. The “prover” or the computer/person that has to prove the answer is bombarded with questions by the entity trying to check the solution, the “verifier.”
This is known as interactive proof, and it can reveal additional information that can help researchers verify the results of problems that otherwise they wouldn’t be convinced of. An even more powerful technique involves two provers, and both would be peppered with questions. This technique resembles the police interrogation of two suspects. The suspects are isolated, and in different rooms, so they can’t coordinate together to trick an investigator. The new twist to this technique is that the two provers would be quantum entangled, making them behave in seemingly correlated ways. This class of problems is called Recursively Enumerable or RE problems.
Further Reading: