Quantum Computers Check Each Other's Work 77
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."
Sorta like... Who polices the police? (Score:1)
Reminds me of the Distributed Administration Network concept [metagovernment.org], where admins check each other.
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
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."
Age old question (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?
Re: (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+.
Re:Age old question (Score:4, Funny)
No. For those Slashdotters unfamiliar with "forests" [wikipedia.org], an unoccupied one is, for these purposes, equivalent to /dev/null/.
Re: (Score:2)
if researches drum up publicity around quantum computing without actually furthering the research and publish it just for fun and publicity is it then actually an article on quantum computing or article on quantum computing dudes who want publicity?
I mean, they even admit that the idea has no practical effect at all now and is a "well duh" kind of thing. in other words even they sort of know that they just wasted bits on cyberspace talking about their "fun thought experiment". even dwave is more useful than
Re: (Score:3)
yes and no
Re: (Score:2)
Obviously in practical terms the "observation" would be done by a classical part of the computer, but it's a lot more fun to think about this with a philosophical perspective.
Re: (Score:2)
Bitcoins (Score:2)
With the difficulty continuously rising, I'm predicting that the last bitcoins will be calculated on quantum computers.
Re: (Score:2)
Re: (Score:1)
That's one sexy machine.
Should get 1 BTC / week just for the looks of that beauty.
Re: (Score:2)
Re: (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: (Score:3)
"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.
Re:Actually... (Score:4, Informative)
Re: (Score:1)
I think your summary is right. Skimming the article
http://arxiv.org/abs/1309.0005 [arxiv.org]
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.
Re: (Score:1)
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.
Re: (Score:2)
Re: (Score:2)
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.
Re:Actually... (Score:5, 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.
Re: (Score:1)
you should review the definition of NP [wikipedia.org]
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.
Re: (Score:2)
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 f
Re: (Score:1)
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.
BQP might include problems outside NP (Score:1)
Re: (Score:2)
It might, but it is strongly believed that the decision problems in BQP are also in NP and, in particular, that quantum computers can't solve NP-hard decision problems "efficiently". Interestingly, there is some evidence that this may not be true of problems which are not decision problems. If that's true, then BQP sits in a very interesting space indeed.
As an aside, there is a small but growing set of problems which are known to be in BQP and in NP, but believed not to be outside P and not NP-hard. Interes
Answer: use a classical computer (Score:5, Insightful)
Re: (Score:2, Informative)
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 man
Re: (Score:2)
Yes, this is the standard approach in theory. Ie, P-time to set up a problem to be solved, non deterministic machine computes an answer, then P-time to verify and serialize the results.
What the classical computer can not do though is verify that the solution is an optimal solution, and I think this is what the quantum computers would check each other for.
Re: (Score:2)
Many problems are NP-hard in one direction, but not the other way around.
This statement is at best confused, and is essentially wrong. A class of problem is in NP if when the answer is yes, they have a polynomial length proofs that can be checked in polynomial time. A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time. It does not make sense to talk about being NP-hard in any direction. What you are talking about are problems like factoring but not because they are NP hard, but because they are likely intermediate in dif
No, it's quite correct. (Score:2)
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=
Re: (Score:2)
Re: (Score:2)
No, even then your characterization of NP-Hard is incorrect.
"A class of problems is NP-Hard if being able to solve it in polynomial time..."
If you can solve it in polynomial time, then it's in P. Even under your revised definition, you're implicitly arguing that P=NP, because that's the only way you can solve an NP-Hard problem in polynomial time. (And even then, you would only be able to solve the NP-Complete subset of NP-Hard.)
Re: (Score:2)
If you can solve it in polynomial time, then it's in P. Even under your revised definition, you're implicitly arguing that P=NP, because that's the only way you can solve an NP-Hard problem in polynomial time. (And even then, you would only be able to solve the NP-Complete subset of NP-Hard.)
What? No. Notice I didn't say anything about how you could solve the NP hard problem. If one has an oracle that can solve the problem then that's fine for this purpose phrasing things in terms of oracles is a pretty standard approach. Also, I fail to see the point of your parenthetical remark since no one has claimed that being able to solve some NP hard problem lets you solve all NP hard problems. That would just be stupid given that the standard version of the halting problem is NP-hard and obviously not
Re: (Score:2)
At this point I'm pretty sure you're trolling. The Halting Problem is UNDECIDABLE -- it exists in a complexity class considerably beyond what is normally thought of as 'NP-Hard'.
And if you don't understand my parenthetical remark, well... that should be taken as a sign that your computational theory is seriously lacking. The meaning is quite clear to someone who has a proper understanding of what complexity class NP-Hard is about.
Goodbye, troll.
Re: (Score:2)
The Halting Problem is UNDECIDABLE -- it exists in a complexity class considerably beyond what is normally thought of as 'NP-Hard'.
One is completely capable of talking about undecidable problems being NP-hard or not. In fact, one neat thing is that one can have a problem that is equivalent to the Halting problem in the computability sense that is not NP-hard, even though the Halting problem itself is NP-hard. Thi
Re: (Score:2)
No. The Halting Problem belongs to class UNDECIDABLE, not class NP-Hard. I admire your attempt at rationalizing it, but Alan Turing proved this to the world's satisfaction. If you wish to prove the Halting Problem does not belong to UNDECIDABLE then you're going to have an uphill road to hoe. If you still believe the Halting Problem belongs to NP-Hard, I would suggest you begin by correcting its Wikipedia article [wikipedia.org].)
Your argument involving an oracle that solves the Halting Problem is absurd because you're
Re: (Score:2)
No. The Halting Problem belongs to class UNDECIDABLE, not class NP-Hard. I admire your attempt at rationalizing it, but Alan Turing proved this to the world's satisfaction. If you wish to prove the Halting Problem does not belong to UNDECIDABLE then you're going to have an uphill road to hoe.
Yes, the Hatlting problem is undecidable. That doesn't stop it from being NP-hard also. This isn't that complicated: nothing in the standard definition of NP-hard assumes we are talking about a decidable language.
Your argument involving an oracle that solves the Halting Problem is absurd because you're assuming the existence of hypercomputation -- and if such an oracle could exist, then we would simultaneously have P=NP and P != NP. Martin Davis [wikipedia.org] has gone so far as to declare hypercomputation both "a myth" and "a nonexistent discipline." Those are strong words coming from one of the brightest lights in the field of computational theory and computational complexity.
It's a bedrock principle of logic that if you start from a false proposition anything can be proven. You assume the existence of an oracle that can solve the Halting Problem. This is a false proposition. Anything can be proven once you make oracular assumptions.
Assuming one has an oracle is not the same thing as assuming one has a Turing machine that does something. That's in fact part of the entire point of why we speak about oracles instead of assuming one has a Turing machine that does stuff. So if it turns out that one doesn't have such a Turing mach
Re: (Score:2)
Yes, the Halting problem is undecidable. That doesn't stop it from being NP-hard also.
Saying that it exists somewhere in NP-Hard may be technically true, in that NP-Hard encompasses all classes NP-Complete and harder (and UNDECIDABLE is definitely harder). But I don't know of a single reputable computer scientist who would characterize the Halting Problem as NP-Hard, in the same way that I don't know of a single one who would characterize 3SAT as being in EXPTIME. As my advisor once quipped, "That idea
Re: (Score:2)
Saying that it exists somewhere in NP-Hard may be technically true, in that NP-Hard encompasses all classes NP-Complete and harder (and UNDECIDABLE is definitely harder).
So part of the neat thing is that this isn't actually true. There are undecidable languages that are *not* NP-hard. Consider for example some computable listing of Turing machines. Now consider the language L that accepts iff L is a string of n 1s where n=Ackermann(m) for some m such that the mth Turing machine halts on the blank tape. This language is undecidable and is also not NP-hard. That is, if you have an oracle L, then one can show that P = NP if and only P^L = NP^L. And one can do some even strang
Re: (Score:3)
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?
Re: (Score:1)
The problem is that the quantum annealing result is almost always wrong - you need to run it thousands or millions of times to settle on a score you can verify. The balance between classical verification and the generating of slightly bad results is a fine line.
Answer: 42 Question: ? (Score:2)
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 [wikipedia.org] vs. Earth
Re: (Score:1)
Comp Sci 101 (Score:2)
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).
Re: (Score:2)
Verifying that a particular answer is correct is often far less complicated...
Often, but not always. I'm going to go out on a limb and assume that Dr. Stefanie Barz knows this, and is working on this technique for those cases were this doesn't apply.
What this means (Score:2)
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.uwa [uwaterloo.ca]
Use Qunit4 (Score:1)
would this actually be an issue? (Score:1)
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
Just a test suite (Score:2)
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
pfff. (Score:2)
Re: (Score:2)