5 ms·

What's the deal with this Dwave device?? Is it the real thing? According to wikipedia there is a "history of controversy." [1] Can anyone here provide more de

by nissimk 13y ago

What's the deal with this Dwave device?? Is it the real thing? According to wikipedia there is a "history of controversy." [1] Can anyone here provide more details? http://en.wikipedia.org/wiki/D-Wave_Systems#History_of_controversy http://en.wikipedia.org/wiki/D-Wave_Systems#History_of_contr...

Zweihander 13y ago
From a recent HN post: http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-computer-usc/ http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-... It looks like it's the real thing in terms of being able to do a lot of useful quantum calculations that can't be done as easily with classical computers. It's not the full deal in terms of being able to do everything a 'true' quantum computer should be able to do - sounds like it might be able to help the NSA out with their data problem though.
izend 13y ago
The Dwave device is definitely real, it is a specific type of quantum computer which is called adiabatic quantum computer and can be used to efficiently solve optimization problems [1]. Some people believe the Dwave device shouldn't be labeled as a "Quantum Computer" because the general community typically uses the Quantum Computer label for a device which could compute NP-Complete problems in linear time instead of exponential time, the Dwave device cannot do this. [1] https://en.wikipedia.org/wiki/Optimization_problem https://en.wikipedia.org/wiki/Optimization_problem
- arjunnarayan 13y ago
  Quantum computing is not known to allow you to compute NP hard problems in linear (or polynomial) time. Specifically, the relationship between BQP and NP is open, but widely believed to be not equal (just as the general community's priors are biased towards P \neq NP). Here's a hint as to why: http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality If you are interested in what exactly the D-Wave computer is doing, http://www.scottaaronson.com/blog/?p=1400 http://www.scottaaronson.com/blog/?p=1400 is a good source.
- gizmo686 13y ago
  Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. However there is an exponentially small chance that when we make the measurement we will see the currect answer instead of no result (or simmiliar). Effectively, we need to repeat the computation an exponential amount of times to arrive at the answer. There is a genneral algorithm that could solve many (all?) NP-Complete problems in the square root of the time it takes classical algorithms, but that is still exponential.

by nissimk 13y ago

Zweihander 13y ago

From a recent HN post: http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-computer-usc/ http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-... It looks like it's the real thing in terms of being able to do a lot of useful quantum calculations that can't be done as easily with classical computers. It's not the full deal in terms of being able to do everything a 'true' quantum computer should be able to do - sounds like it might be able to help the NSA out with their data problem though.

izend 13y ago

The Dwave device is definitely real, it is a specific type of quantum computer which is called adiabatic quantum computer and can be used to efficiently solve optimization problems [1]. Some people believe the Dwave device shouldn't be labeled as a "Quantum Computer" because the general community typically uses the Quantum Computer label for a device which could compute NP-Complete problems in linear time instead of exponential time, the Dwave device cannot do this. [1] https://en.wikipedia.org/wiki/Optimization_problem https://en.wikipedia.org/wiki/Optimization_problem

arjunnarayan 13y ago
Quantum computing is not known to allow you to compute NP hard problems in linear (or polynomial) time. Specifically, the relationship between BQP and NP is open, but widely believed to be not equal (just as the general community's priors are biased towards P \neq NP). Here's a hint as to why: http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality If you are interested in what exactly the D-Wave computer is doing, http://www.scottaaronson.com/blog/?p=1400 http://www.scottaaronson.com/blog/?p=1400 is a good source.
gizmo686 13y ago
Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. However there is an exponentially small chance that when we make the measurement we will see the currect answer instead of no result (or simmiliar). Effectively, we need to repeat the computation an exponential amount of times to arrive at the answer. There is a genneral algorithm that could solve many (all?) NP-Complete problems in the square root of the time it takes classical algorithms, but that is still exponential.