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.
I heard you like quantum computers so we put a quantum computers in your quantum computer so you can quantum computing while you're quantum computing
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
For an NP problem, if the QC gives you the answer you can verify the answer in polynomial time on an *ordinary* computer.
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. . . .
1st q. Comp answer: ...
24
2nd:
42
3rd:
33
all done here, we have a convergence!
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.
If a quantum computer finds the 'best' solution to a problem,
then a classic computer could verify that the answer is a solution,
but it could verify that the answer is the best one with out an exhaustive search.
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.
You needed a scientist to tell you that? I thought this was standard operating procedure for MBAs:
Problem: We need to solve problems we're not smart enough to understand.
Solution: Hire really smart person to solve problems.
New Problem: We cannot understand what the really smart person is saying so we can't verify that his solutions are correct.
Solution: Hire a project manager who is smarter than us but less smart than the really smart person to check his work and act as an interpreter.
New Problem: Project manager doesn't fully understand what either party is doing, so solutions are still unverified.
Solution: Hire a mid-level manager to manage the smart person team, set action items and verify deliverables.
New Problem: Mid-level manager determines that nothing is getting done but is powerless to do anything about it.
Solution: Develop quantum computer that can solve the problem in another dimension with a fake solution that becomes real when it crosses into our dimension.
New Problem: No one can verify the solutions produced by the quantum computer.
Solution: Develop another quantum computer that is smarter than us but less smart than the first quantum computer to check its work and act as an interpreter.
The spice must flow
Since the quantum particle can contain all states at once, then its just a matter of picking the one you want --kind of like the studies supporting the 'theory' of Manmade Global Warming. I guess the debate is now over about Quantum Computing and we can get back to doing other stuff.
Seriously is this all just hype by a bunch of bunko artists to get tards to fund their cushy living. This is all very algore
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 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.
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."
I don't think anyone here will argue otherwise. And we at least know that BQPPSPACE. So what is the problem here. Just check the result. It cannot be too hard.
The Twin 9000 computer indicates your HAL-9000 is faulty.