D-Wave Defies World of Critics With ‘First Quantum Cloud’
1–10 of 29 posts
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#2This 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.
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#3In 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.
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#4Scott Aaronson recently wrote an informative article about his trip to D-Wave: http://www.scottaaronson.com/blog/?p=954
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."
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#5The 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.
http://en.wikipedia.org/wiki/Permutation#Counting_sequences_...
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#6Scott Aaronson recently wrote an informative article about his trip to D-Wave: http://www.scottaaronson.com/blog/?p=954 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…
for folks in the Boston area, this meetup might be of interest:
http://www.meetup.com/Theoretical-Computer-Science-Problem-S...
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#7The 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…
Only using naive algorithms. You can get it down to 2^n time complexity by increasing the space complexity and applying dynamic programming techniques.
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Ex...
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#8> 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.
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#9The 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…
Only using naive algorithms. You can get it down to 2^n time complexity by increasing the space complexity and applying dynamic programming techniques. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Ex...
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 :-)
Re: D-Wave Defies World of Critics With ‘First Quantum Cloud’
#10PDF for the Google paper mentioned in the article: http://arxiv.org/pdf/0912.0779v1.pdf