D-Wave Defies World of Critics With ‘First Quantum Cloud’

<i>The classic example is figuring out the most efficient route for a traveling salesman going to multiple destinations. [...] For example, if you have six destinations, there are 64 possible combinations. If you have 20 destinations, there are 1,048,576 possible combinations.</i><p>That's incorrect, the number of combinations for N destinations is N!, not 2^N. So for 6 destinations there are 720 combinations and for 20 there are 2.43290201 × 10^18.<p><a href="http://en.wikipedia.org/wiki/Permutation#Counting_sequences_without_repetition" rel="nofollow">http://en.wikipedia.org/wiki/Permutation#Counting_sequences_...</a>

&#62; That same month, mega defense contractor Lockheed Martin bought a D-Wave quantum computer and a support contract for $10 million.<p>lol, i used to work at LM advanced research, LM consistently blows 10 mil over 3 ears on stupid dead end projects and nobody even blinks. This is not a criticism of LM so much as it gives us insight into the size of budget and scope of projects the work with. they did 45bn revenue in 2011 per wikipedia. this d-wave project looks like a toy that some kids in a lab bought.<p>but it doesn't matter how it looks to us. quantum computing is a weapon, and as such is highly classified. i'm not sure we can draw any conclusions at all about the state of quantum computing from information in the public domain and if LM had a larger relationship with d-wave or similar companies, we wouldn't know.

Scott Aaronson recently wrote an informative article about his trip to D-Wave: <a href="http://www.scottaaronson.com/blog/?p=954" rel="nofollow">http://www.scottaaronson.com/blog/?p=954</a><p>Most interesting to me: "Geordie presented graphs that showed D-Wave’s quantum annealer solving its Ising spin problem “faster” than classical simulated annealing and tabu search (where “faster” means ignoring the time for cooling the annealer down, which seemed fair to me). Unfortunately, the data didn’t go up to large input sizes, while the data that did go up to large input sizes only compared against complete classical algorithms rather than heuristic ones. (Of course, all this is leaving aside the large blowups that would likely be incurred in practice, from reducing practical optimization problems to D-Wave’s fixed Ising spin problem.) In summary, while the observed speedup is certainly interesting, it remains unclear exactly what to make of it, and especially, whether or not quantum coherence is playing a role."

This article is full of bullshit claims about the power of quantum computers. There are no known quantum algorithms for NP-complete problems like the travelling salesman problem mentioned in the article that run faster than exponential time. Quantum computers in general don't consider an exponential number of possible solutions, or if they do, you can't extract the true solution from the quantum state.

In a nice instance of synchronicity, I was just reading a paper by Scott Aaronson, "NP-Complete Problems and Physical Reality" [1]. The paper talks a little bit about the quantum adiabatic method, which seems to be similar to simulated annealing, with similar limitations (on specially chosen SAT problems, the method can have difficulty overcoming local optima; see page 6 for discussion).<p>So, D-Wave may be selling an expensive simulated annealing hardware implementation, rather than a quantum computer.<p>1: <a href="http://www.scottaaronson.com/papers/npcomplete.pdf" rel="nofollow">http://www.scottaaronson.com/papers/npcomplete.pdf</a>

It seems that every time I read articles about quantum computing, the increase in computing power is described with gaping hole:<p>1. Qubits can be 1 and 0 at the same time<p>2. ...<p>3. Solve hard problems!<p>Can someone provide a link that fills in the middle somewhat? Preferably, aimed at an audience with something closer to undergrad engineering degree and than a PhD?

&#62; On some level, Rose understands the criticism. “It’s the same basic human reaction that everybody has to something that someone says that sounds outrageous,”<p>I think it less about it being outrageous and more about the fact that he and the company's press releases sound more like infomercials then technological descriptions. Which historically seems to happen with pseudoscience based companies.

<i>"The great mathematician and founding figure of computer science, Alan Turing, showed that it is impossible to eliminate all errors from software."</i><p>Oh? I thought he only proved that it's impossible for an algorithm to determine whether an arbitrary program will halt -- not whether all errors can be eliminated from software.

Quantum computing is here!<p>No, wait, it's over there!<p>One thing is for sure - we're uncertain where quantum computing is right now.<p>(yes, bad joke. It seems to work on a couple of different levels, though)

PDF for the Google paper mentioned in the article: <a href="http://arxiv.org/pdf/0912.0779v1.pdf" rel="nofollow">http://arxiv.org/pdf/0912.0779v1.pdf</a>

To add to the myriad criticisms, I would only point out that quantum computation was first proposed in 1982 by the late great Richard Feynman, not by Deutsch.

This is a terrible article, which is to be expected from Wired I guess.