4 ms·
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 o
by 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 agoQuantum 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 agoQuantum 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.