"Verification Problem" for Quantum Computers
In his book, Labyrinths of Reason , William Poundstone talks of the “Oracle of the Maze”, an oracle who can answer any question immediately. Even if he is a true oracle, convincing others isn’t easy. Why? “Answer a question that no one else possibly could, and he is accused of fabricating; answer a question whose answer is known or knowable, and he is accused of cheating.” So is there no way out for the oracle? Aha, there is: “a difficult question whose answer, once stated, can be verified easily ”. The solution to an insanely big and twisted maze is an example, ergo, the name Poundstone gave: Oracle of the Maze. This topic is of practical relevance (no, not maze solving; checking if an oracle is really an oracle) in… quantum computing, writes Erica Klarreich: “Once a quantum computer can perform computations a classical computer can’t, how will we know if it has done them correctly?” See the parallel with the Oracle of the Maze? Is there “any ironclad guarantee that i...