Slashdot Mirror
Quantum Computers Check Each Other's Work
sciencehabit writes "Quantum computers can solve problems far too complex for normal computers, at least in theory. That's why research teams around the globe have strived to build them for decades. But this extraordinary power raises a troubling question: How will we know whether a quantum computer's results are true if there is no way to check them? The answer, scientists now reveal, is that a simple quantum computer—whose results humans can verify—can in turn check the results of other dramatically more powerful quantum machines."
It does not seem like their method truly verifies the solution. It only checks that the quantum computer is functioning correctly for specific problems with known solutions. By inserting these problems in many places in the quantum algorithm, they verify that the quantum computer was working correctly for the entire duration of the computation. Maybe that grants enough confidence in the solution... I don't know.
Erm... NP-hard does not imply "in NP". In fact, NP-complete are exactly the problems that are NP-hard and also inside NP.
That said, by "Many problems are NP-hard in one direction, but not the other way around.", it sounds like zoffdino was describing exactly that (NP-complete problems). In which case, he misses the point: some interesting problems are not in NP, thus can't be verified (fast) in a classical computer. There are many applications for solving problems of this kind; for example it would be a huge help in understanding high-temperature superconductivity.