Quantum Computers Check Each Other's Work

← Back to Stories (view on slashdot.org)

Quantum Computers Check Each Other's Work

Posted by samzenpus on Monday September 30, 2013 @08:32AM from the steel-sharpens-steel dept.

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."

11 of 77 comments (clear)

Min score:

Reason:

Sort:

Age old question by Dishwasha · 2013-09-30 08:42 · Score: 5, Funny

If a quantum computer makes a calculation in a forest and no one is around to verify it, does it solve the problem?
1. Re:Age old question by sexconker · 2013-09-30 08:46 · Score: 2
  
  If a quantum computer makes a calculation in a forest and no one is around to verify it, does it solve the problem?
  No, but Google will push it out as a staggered update anyway and silently tweak it for 2 years before pulling the whole thing and telling people to use the new Quantum tab on Google+.
2. Re:Age old question by ebno-10db · 2013-09-30 08:47 · Score: 3, Funny
  
  No. For those Slashdotters unfamiliar with "forests", an unoccupied one is, for these purposes, equivalent to /dev/null/.
3. Re:Age old question by Khashishi · 2013-09-30 09:52 · Score: 2
  
  yes and no
Answer: use a classical computer by zoffdino · 2013-09-30 08:52 · Score: 5, Insightful

Many problems are NP-hard in one direction, but not the other way around. Use a quantum computer to find a solution, then use a classical computer/supercomputer to verify its results. Case in point: brute-forcing a hash function is hard, but computing the hash from a known value is easy; factoring large integers are hard, but multiplying two numbers are easily done.
1. Re:Answer: use a classical computer by Anonymous Coward · 2013-09-30 11:16 · Score: 2, Informative
  
  Many problems are NP-hard, and thus can be verified on a conventional computer.
  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.
2. Re:Answer: use a classical computer by dido · 2013-09-30 13:42 · Score: 2
  
  Not all problems tractable on a quantum computer are so easily amenable to such verification. For example, the original problem that motivated the quantum computer, that of the simulation of quantum processes, is a case in point. All known algorithms for doing that on classical computers take exponential time. How do you verify the results of a complex simulation thus done on a quantum computer?
  
  --
  Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
Re:Actually... by Sarten-X · 2013-09-30 08:56 · Score: 2

"In polynomial time" does not necessarily mean "quickly". Perhaps the verification will only take a century, rather than fifty millenia... I'd still prefer to not wait around for it.

--
You do not have a moral or legal right to do absolutely anything you want.
Re:Actually... by green+is+the+enemy · 2013-09-30 09:23 · Score: 4, Informative

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.
Re:Bitcoins by Anonymous Coward · 2013-09-30 09:26 · Score: 2, Funny

[...]steel the coins that already exist.
Foreman: What exactly are you dipping in that vat of steel?
Worker: My cellphone.
Foreman: Why the hell would you cover your phone in molten steel?
Worker: Well, someone on Slashdot said that I should break the bitcoin encryption and then steel them.
Foreman: You know they're just ones and zeroes, right?
Worker: Yes, that's why I'm coating my entire phone.
Re:Actually... by dgatwood · 2013-09-30 09:59 · Score: 4, Insightful

The thing is, most of those problems that take a thousand years to verify aren't generally interesting except perhaps in some esoteric field of study.
The interesting uses of QC, IMO involve things like cracking RSA, where the time required to verify a solution is trivial, but the time required to produce a solution is enormous.

--
Check out my sci-fi/humor trilogy at PatriotsBooks.