back to article Boffins build a 2D 'quantum walk' that's not a computer, but could still blow them away

Do you want to know what a quantum walk is? The reason we ask is that that’s what a group of Chinese researchers have demonstrated, and it’s being hailed as a big thing in the development of quantum computing. The “quantum walk” doesn’t deliver a general purpose quantum computer. Instead it delivers a a quantum simulator which …

  1. Anonymous Coward
    Anonymous Coward

    Sounds like...

    ...an optical Pachinko machine

  2. Lee D Silver badge

    1) These things really need to be renamed. A random walk should really be called a Wander. A quantum random walk should be a Quander.

    2) The way I understand it, quantum physics / collapsing waveforms is really about finding out what universe you happen to be in. In all the myriad possibilities of possibilities, there's only one that you're actually in. But once you find out what one you're in, the answer reveals itself across the universe (hence you can take entangled photons, send them across the galaxy, and as soon as someone "reveals" what one of them is, the other one is automatically determined... you didn't make it do anything, you just discovered which particular universe you were in at that point).

    3) Though this can help towards quantum computing, it's really just a speed-up of traditional computing. It looks short-lived and relatively limited in terms of applications.

    1. Gordon 10 Silver badge
      Joke

      Does that make a problem solvable by a Quantum Computer a Quandary?

    2. Destroy All Monsters Silver badge
      Headmaster

      quantum physics / collapsing waveforms is really about finding out what universe you happen to be in.

      Absolutely not. There is only one universe, crazy idea slingers, lazy cranks and publicity hounds notwithstanding. It's just that information is "soft" (it's just partially constrained) for small systems that one does not have much information about (note that "small distance" has nothing to do with it; separation could be in time, too for example).

      1. Brewster's Angle Grinder Silver badge

        "There is only one universe..."

        The pedant in me says that's true by definition. But we're talking about QM, not string theory and eternal inflation. And, hate it though you may, Many Worlds is as (in)valid as any other interpretation.

        These days I view it as naive, and unlikely to produce an insight that solves the problem (and, on that basis, probably false). But we can't dismiss it because we find it aesthetically unattractive. Many Worlds has the same order of complexity as any other interpretation of QM and can fully explain the facts.

        1. Lee D Silver badge

          Correction: You can only ever perceive one universe. Which, are far as 99.9999999999% of things are concerned makes almost no difference to you.

          However, explaining quantum physics to laymen is much easier when you can explain it as "There are a billion possible positions/answers... only one of them is right... when you discover which one is right, that one is right instantaneously throughout the entire universe for that measurement/question".

          Rather than magically-faster-than-light stuff, it makes a much better analogy to say "By measuring, you find out what universe you were in all along from an infinity of possibilities".

          Like anything in maths (and quantum physics, like relativity, is someone doing the maths, going "Oh, that can't be right, that would mean that..." and then 100 years later realising that's exactly what happens in the real world) - all the explanations can be correct simultaneously, so they are all equivalent, and choosing one arranged in a particular way that makes a particular calculation / explanation easier is part and parcel of making a breakthrough in understanding. (I refer you to how Fermat's Last Theorem was proven - by joining two entirely different areas of mathematics with a particular equivalence that meant an unsolveable problem became solveable).

    3. Evil Auditor Silver badge
      Alien

      as soon as someone "reveals" what one of them is, the other one is automatically determined

      Are you saying that we may be what we are just because some wrinkly E.T. in a remote galaxy looked at some entangled photons?

  3. amanfromMars 1 Silver badge
    Pint

    Are you serious? ....

    predicting the behaviour of randomly-grown .... neural network systems

    Really? Good luck with that. But it is good to hear of such Stealthy Quantum Communications Progress and with China leading too in an Exotic and Erotically Derived Confection. Nice one.

    1. defiler Silver badge

      Re: Are you serious? ....

      Have I just cracked the code?

      I posit that amanfromMars1 jots down his/her post, and then substitutes each word with the last synonym listed in the thesaurus, burying the meaning.

      Do I get a prize?

      1. imanidiot Silver badge

        Re: Are you serious? ....

        No, but these gentlemen in friendly white coats have a soft new jacket for you. With extra long sleeves.

      2. 2+2=5 Silver badge
        Joke

        Re: Are you serious? ....

        > Do I get a prize?

        No, you get an award winning.

  4. Destroy All Monsters Silver badge
    Headmaster

    In the quantum world, superposition (the property of quanta that they may exist in a superposition of multiple states at once until the waveform is collapsed)

    Actually, it's the property of SYSTEMS to exist in a "superposition" (a complex-valued probability distribution aka "the wavefunction") until the waveform is collapsed enough information has been extracted from the system so that superposition is no longer apparent.

    1. Anonymous Coward
      Anonymous Coward

      The trick is getting it to collapse into the right one.

      In this case, it sounds like they're building a machine to solve the travelling salesman problem. The trouble is, all solutions to the travelling salesman are valid solutions. What we want is the "best" one - i.e. the one with the lowest cost, across all solutions. Plus: we don't just want to know what the lowest cost is; we want to know what route it took to generate that lowest cost.

      If not: then what sort of problem *is* this machine designed to solve?

      1. Akko
        Joke

        The problem of how to get research grant money?

        1. amanfromMars 1 Silver badge

          10 Billion starts and buys one. .... [for those with a Need to Know]:-)

          The problem of how to get research grant money? ... Akko

          Design and Create a Variant Almighty Weapons System is one sure fire way to be practically drowning in folding.

          1. jonathan keith Silver badge

            Re: 10 Billion starts and buys one. .... [for those with a Need to Know]:-)

            Ah! So quantum computing is what will finally deliver us a Lazy Gun.

            1. aeonturnip
              Thumb Up

              Re: 10 Billion starts and buys one. .... [for those with a Need to Know]:-)

              Have an upvote for your Iain M Banks reference, sir.

      2. Atomic Duetto

        42

        Forty two...

      3. Crisp

        What sort of problem *is* this machine designed to solve?

        Optimisation of fuel tankers. A machine like this would be able to simulate the movement of all tankers over all routes between depots and find the lowest cost solution in terms of either time or fuel consumed.

        1. Anonymous Coward
          Anonymous Coward

          Re: What sort of problem *is* this machine designed to solve?

          > Optimisation of fuel tankers. A machine like this would be able to simulate the movement of all tankers over all routes between depots and find the lowest cost solution in terms of either time or fuel consumed.

          That's the travelling salesman problem.

          But how does a quantum computer compare all possible outcomes and collapse to the "best" one? That's not the same as collapsing to the right answer when all the others are wrong.

          1. Crisp

            Re: How does a quantum computer compare all possible outcomes and collapse to the "best" one?

            In much the same way as computing the ground state of an atom.

            In this instance with the tankers, you're computing all possible solutions and picking the lowest energy solution. For that is the best solution.

          2. Baldrickk Silver badge

            Re: What sort of problem *is* this machine designed to solve?

            That's the travelling salesman problem.

            Well, the travelling salesman is one circuit visiting all nodes, the problem described (tankers) is multiple circuits collectively visiting all nodes with a bit of knapsack thrown in (limited load)

            Sounds a little harder to solve, though segmentation would help.

            1. GIRZiM

              Re: What sort of problem *is* this machine designed to solve?

              the problem described (tankers) is multiple circuits collectively visiting all nodes

              And solvable with simulated annealing a la Rumelhart/McClelland/PDP- no need to solve for NPC.

              1. Michael Wojcik Silver badge

                Re: What sort of problem *is* this machine designed to solve?

                And solvable with simulated annealing a la Rumelhart/McClelland/PDP

                Yeah. And if your problem is too large and rough for simulated annealing to give you a good-enough answer in reasonable time, you can always step up to quantum annealing a la D-Wave. I'm not a D-Wave trufan, but there are certainly applications where annealing is more suitable than trying to go with more exotic approaches, and it's not inconceivable that some real-world examples would be outside the envelope of practical conventional simulated annealing (though that envelope grows quickly) but within the QA one.

                In any case, offhand I don't think I've seen anything that claims QW helps with TSP variants like this. Unless something's been proven since I last checked, NP-Complete isn't in BQP, so while quantum algorithms may provide poly-time speedups in some cases, they don't change the complexity class.

      4. Michael Wojcik Silver badge

        Re: What sort of problem *is* this machine designed to solve?

        what sort of problem *is* this machine designed to solve?

        Yeah, it's pretty hard to find out what a quantum-walk machine might do. Unless, I guess, you have access to some sort of world-wide linked-up-thing of information, say.

        Or, if you want to Sticki with the Wiki, like 99% of the web-using populace, try this.

        Quantum-walk algorithms that are strictly faster than classical-computer algorithms have been known since at least 2002. (Hey, I think I know one of the authors of that one. Cool.)

        That 2002 paper talks about oracular problems: You have a function that's a black box - you can't find out anything about it, but you can provide inputs and observe outputs. The problem is to determine some property of that function with as few input-output exchanges as possible. Quantum walk can do that strictly faster than any conventional algorithm (where "faster" is in terms of complexity, not wall clock time, since obviously we haven't specified how fast a QW or conventional computer we're talking about).

        Later papers mostly seem to be about various kinds of search problems, set and group problems, graph problems - that sort of thing.

        Some of these are just polynomial improvements. For the triangle problem, for example, conventional can do it in O(N1.4), while QW apparently gets that down to O(N1.297), according to the Always-Reliable source. Obviously you need a fairly big graph before that makes much of a difference,1 even assuming your QW is as fast as your conventional machine (and no, it won't be). But for some other problems QW might be useful in practice.

        Seriously, I am amazed at the lengths people will go to say "I couldn't be bothered to look this up, but I sure will spend some time letting you know that!".

        1Well, if my back-o'-the-envelope scratchings are right, it actually saves you about 25% of the queries for a million-node graph. So if your QW machine is really close in speed to your conventional one, it might be worthwhile. But then I'm not sure why you're trying to solve the Triangle Problem in the first place. What do you have against triangles, huh?

  5. Nimby
    WTF?

    Could still blow them away?

    "and potentially be able to beat the computational power of classical computers in the near future"

    This hypegasm is so couched that all I keep reading are all of the hedgewords, dancing, and distancing from actual reality that the whole article should just be deleted from El Reg.

  6. mstreet
    Angel

    Tis sounds like a rip off...

    Pretty sure this concept was first thought up by Douglas Adams... 'bistromathics'

    From HGTTG:

    "Bistromathics itself is simply a revolutionary new way of understanding the behavior of numbers. Just as Einstein observed that space was not an absolute but depended on the observer's movement in space, and that time was not an absolute, but depended on the observer's movement in time, so it is now realized that numbers are not absolute, but depend on the observer's movement in restaurants."

    1. GIRZiM

      Re: Tis sounds like a rip off...

      Indeed.

      Think about it: if quantum computing were ever going to happen in this universe, it would already have happened - just ask the Lutece 'twins'. Fortunately, it won't have and I, therefore, needn't trouble myself with the Future Semiconditionally Modified Subinverted Plagal Past Subjunctive Intentional tense or becoming my own father.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Biting the hand that feeds IT © 1998–2020