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.
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.
Only using naive algorithms. You can get it down to 2^n time complexity by increasing the space complexity and applying dynamic programming techniques.
Just like the article I didn't say anything about space or time complexity, only about the number of combinations (permutations) of visiting N destinations. That number is constant regardless of how sophisticated your algorithm is :-)
I always find it funny when 2^n is viewed as 'good news'. I realize it's better than the other options, but it still feels like a doctor saying great news you've got cancer!
> That same month, mega defense contractor Lockheed Martin bought a D-Wave quantum computer and a support contract for $10 million.
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.
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.
I have spoken to a guy who was at one point closely involved with the D-wave people. He suggested that the actual story with the Lockheed purchase was that LM sells an awful lot of gear to Canada, and as part of the contract they are expected to buy some number of million worth of Canadian tech in return. The D-wave purchase was one of these obligated purchases.
Just a comment given in unofficial conversation, take it how you will.
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.
There seems to be a general misunderstanding of what quantum computers are capable of in the public mind, or at least that slice of it that is even aware of quantum computers' existence. I was just reading Hominids by Robert J Sawyer and it involves a quantum computer. He describes how it 'checks every possible answer simultaneously' to find the prime factors of a number instantaneously...which of course is not how Shor's algorithm actually works.
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).
So, D-Wave may be selling an expensive simulated annealing hardware implementation, rather than a quantum computer.
> 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,”
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.
It seems that every time I read articles about quantum computing, the increase in computing power is described with gaping hole:
1. Qubits can be 1 and 0 at the same time
2. ...
3. Solve hard problems!
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?
"The great mathematician and founding figure of computer science, Alan Turing, showed that it is impossible to eliminate all errors from software."
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.
Indeed, it was the Curry–Howard correspondence which led to the realisation that software could be proven correct: a function's type can be seen as a proposition, the function itself a proof of that proposition.
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.
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.
http://en.wikipedia.org/wiki/Permutation#Counting_sequences_...