Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
Technology

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."
This discussion has been archived. No new comments can be posted.

Quantum Computers Check Each Other's Work

Comments Filter:
  • by Anonymous Coward

    Reminds me of the Distributed Administration Network concept [metagovernment.org], where admins check each other.

  • by Dishwasha ( 125561 ) on Monday September 30, 2013 @04:42PM (#44995651)

    If a quantum computer makes a calculation in a forest and no one is around to verify it, does it solve the problem?

    • 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+.

    • by ebno-10db ( 1459097 ) on Monday September 30, 2013 @04:47PM (#44995683)

      No. For those Slashdotters unfamiliar with "forests" [wikipedia.org], an unoccupied one is, for these purposes, equivalent to /dev/null/.

    • by gl4ss ( 559668 )

      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

    • yes and no

    • by Nemyst ( 1383049 )
      In a purely philosophical sense, no observation was performed and therefore it is impossible to know what the answer would be without someone actually performing it.

      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.
    • by bdwebb ( 985489 )
      Its result is simultaneously all possible results for all possible sets of input data. It doesn't solve the problem...it solves all problems.
  • With the difficulty continuously rising, I'm predicting that the last bitcoins will be calculated on quantum computers.

    • That's what I use mine [wikipedia.org] for, but the 8MHz 68008 takes ages anyway, and the one time it found one the copy saved to the microdrive got corrupted and wouldn't load back.
    • Why would you do that? It'll become more practically to just use it to break the encryption, and steel the coins that already exist.
      • Re: (Score:2, Funny)

        by Anonymous Coward

        [...]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.

  • by zoffdino ( 848658 ) on Monday September 30, 2013 @04:52PM (#44995717)
    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.
    • 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.

    • 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

      • 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=

        • Um, so you are correct in that my statement wasn't quite correct- I should have said instead of " A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time" that " A class of problems is NP hard if being able to solve it in polynomial time allows one to solve all NP problems in polynomial time." But the person I was replying to is still wrong. Talking about being NP hard in one direction and not the other is just nonsense. I suppose if you wanted to real
          • by rjh ( 40933 )

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

            • 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

              • by rjh ( 40933 )

                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.

                • I fail to see why you are insisting on going out of your way to interpret everything people say in a way that maximizes the stupidity of their statements or to label people you apparently can't communicate with as being trolls.

                  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

                  • by rjh ( 40933 )

                    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

                    • 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

                    • by rjh ( 40933 )

                      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

                    • 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

    • by dido ( 9125 )

      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?

    • by Anonymous Coward

      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.

  • 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

    • by KritonK ( 949258 )
      Exactly. A quantum computer's eventual destiny is to design a computer whose merest operational parameters it is not worthy to calculate.
  • 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?

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

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

  • 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]

  • 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

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

Your own mileage may vary.

Working...