...an optical Pachinko machine
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) 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.
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).
"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.
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).
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.
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?
> 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.
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.
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.
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.
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?
"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.
Pretty sure this concept was first thought up by Douglas Adams... 'bistromathics'
"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."
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.