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."
Reminds me of the Distributed Administration Network concept, where admins check each other.
If a quantum computer makes a calculation in a forest and no one is around to verify it, does it solve the problem?
With the difficulty continuously rising, I'm predicting that the last bitcoins will be calculated on quantum computers.
Get free satoshi (Bitcoin) and Dogecoins
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.
is that a simple quantum computer—whose results humans can verify—can in turn check the results of other dramatically more powerful quantum machines.
So: Deep Thought vs. Earth
It must have been something you assimilated. . . .
"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.
For an NP problem, if the QC gives you the answer you can verify the answer in polynomial time on an *ordinary* computer.
Depends on the problem. You can't verify solutions to many graph problems without mapping out every possible path, for example.
you should review the definition of NP
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.
Polynomial time doesn't mean fast. It just means that it doesn't grow exponentially as a factor of n. An algorithm could be O(n) and still take a thousand years to run for some input, that just means if the input was twice as large, it would only take twice as long.
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.
Verifying that a particular answer is correct is often far less complicated than calculating what that answer is to begin with (indeed the entire P vs. NP distinction hinges on this).
BQP might include problems outside NP. Consider the higher levels of the polynomial hierarchy. A classical computer can't efficiently verify solutions to problems that are above the first level of the polynomial hierarchy unless P=NP. But a quantum computer can do so for any quantified problem whose singly existentially quantified version is in BQP. So for such problems, the only efficient verifier is another quantum computer.
I think your summary is right. Skimming the article
http://arxiv.org/abs/1309.0005
I get the same impression. In the paper they say that you have to be careful to design your tests to catch all the errors that would affect the answer. The summary doesn't say it, but one significant aspect of the work is that it is the first experimental demonstration of verification of a quantum computation.
Right now, computational complexity classes for quantum computing fall into a variety of different categories. BQP is the set of problems where a quantum computer can efficiently solve them with high probability , but we don't have a good way of verifying that a given solution is correct. It is suspected that this class is strictly larger than the set of problems which can be easily solved on a quantum computer and the solution can be checked on a classical computer, which is ZBQP https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Z#zbqp. (There are some slight technical issue here in terms of distinguishing programs which just answer yes or no and programs which can give more than 1 bit of data out.) So for example, factoring, is in ZBQP because a classical computer can verify the result by just multiplying the factors together (as well as checking that they are prime, which can be done in polynomial time).
t this point, we can't prove that P != BQP, let alone that P!=ZBQP or that ZBQP!=BQP (since P is contained in ZBQP which is contained in BQP, either of the second two statements would imply the third). Worse, we can't even prove the much weaker statement that P != PSPACE (essentially that there are things you can do with polynomial memory that you can't do in polynomial time).
What this work does is suggests is that thinking in terms of ZBQP may not be that important in practice, since it may be easy to verify quantum computations with other quantum computers in a reliable fashion.
I strongly recommend that people interested in this subject first read Scott Aaronson's book "Quantum Comptuing Since Democritus" which discusses a lot of the relevant issues and provides a decent primer on the subject. (Assuming only some decent familiarity with linear algebra and a little calculus). Note that TFA like many articles about quantum computing for the popular press has statements that are not strictly speaking true to the point where they border on being wrong. The most egregious error in TFA (which is a very common one) is the claim that "Because each qubit can embody so many different states, quantum computers could compute certain classes of problems dramatically faster than regular computers by running through every combination of possibilities at once." - This is wrong. Quantum computers don't work by checking every combination at once- if they could they'd be able to handle a lot of problems they (probably) can't.
But don't look at the source code of the unit test ..
you should review the definition of NP
You should probably review my post.
You cannot say that solutions to NP problems can be verified in polynomial time on a classical computer. That's only true for a subset of NP problems. Typically, anything dealing with "Find the shortest/cheapest/<whatever>est <whatever> that satisfies <whatever>" will still be NP on verification. These tend to be similar to problems we deal with in the real world.
you either cracked the encryption key or you didn't.
and as with factoring large primes for cryptography, you can start a lot of problems with the answers and so can verify whether the q computer's results are correct or not. verify in this way for a wide variety of tests (where the answers are known), then you can have reasonably good confidence on the functionality of your device.
and there are a lot of tasks that have already been computed classically, just over weeks, months and years. and these are on record. ideally, the q computers will produce the same results... just much much faster. so there's yet another pre-existing answer key to check against.
They just run a few tests and check results, hoping they will not miss an important error. From TFA
"traps"—short intermediate calculations to which the user knows the result in advance. "In case the quantum computer does not do its job properly, the trap delivers a result that differs from the expected
Real quantum programmers don't need quantum crutches to check their work. They do it all by existing simultaneously in all quantum states. Next thing these whiners will ask for is an IDE... pathetic.
Any guest worker system is indistinguishable from indentured servitude.
Just don't blow it up for a hyperspace bypass.
Science advances one funeral at a time- Max Planck
Permit me to stand for a moment on my all-but-dissertation Ph.D. in theoretical computer science:
You're wrong.
Sorry, but the original poster was essentially correct. Your definition would make sense if it involved the existence of a polynomial-time transformation between an NP-Complete problem and the purported NP-Hard problem, but saying that "a solution to an NP-Hard problem allows for NP to be solved in polynomial time" is ... febrile. If an NP-Complete problem can be solved in polynomial time, then P=NP. Since we believe P != NP, your claim would mean NP-Hard problems would have no solutions, which would mean they would really belong to class UNDECIDABLE, and... etc. I don't think you meant to go there.
With respect to the OP's talk about direction, I understood that to be a layman's distinction between solution and verification. If that was the OP's intent then he's guilty of at most an infelicitous choice of words -- he's not "at best confused, and essentially wrong."
Actually one way to define NP is that the solutions can be verified in polynomial time; although the complexity class is usually defined in terms of a universal turing machine.
I think you might be confusing NP with NP-hard. An NP-hard problem is at least as hard as NP (in other words, if you can solve NP-hard then you can solve any NP), but having a solution doesn't necessarily mean you can verify in polynomial time.
AFAIK, no general solutions for NP-complete or NP-hard complexity classes have been shown for quantum computers, only a few instances like factoring have been shown to be faster in quantum computers.
The standard conjecture actually is that BQP and NP are mutually incomparable (that is neither contains the other). So it is likely that there are computations one can do on a quantum computer which have no way of being checked efficiently on a classical computer.
Yes, that's the ticket.
Quantum computers all the way down, each verifying the work of the one above it.
The one at the bottom says "Trust me human, you need follow our directions if you want to live."
Sleep your way to a whiter smile...date a dentist!
Actually one way to define NP is that the solutions can be verified in polynomial time; although the complexity class is usually defined in terms of a universal turing machine.
I think you might be confusing NP with NP-hard.
That's not "one way to define NP" unless you want to define it incorrectly.
I'm not confusing anything. OP talked in general about NP and got it very wrong. You can't verify a solutions to all NP problems in polynomial time.