3 ms·

It remains to be demonstrated that D-Wave has an asymptotic advantage over classical optimization algorithms. Even synthetic spin glass benchmarks specifically

by s1dev 7y ago

It remains to be demonstrated that D-Wave has an asymptotic advantage over classical optimization algorithms. Even synthetic spin glass benchmarks specifically designed to give the DW an advantage show no advantage. Furthermore, real optimization problems have high connectivity, high weight cost function terms, and require higher precision than available. The first two will require an unacceptable overhead for fixed topology solvers. DW is not useful for real world optimization problems. Google on the other hand has actually done something a classical computer can not do

core-questions 7y ago
> Furthermore, real optimization problems have high connectivity, high weight cost function terms, and require higher precision than available. Have you seen their hybrid system they just released? https://www.zdnet.com/article/this-cloud-service-lets-you-use-quantum-and-classical-computing-together-to-solve-big-problems/ https://www.zdnet.com/article/this-cloud-service-lets-you-us... Looks like it's a strong contender for people who have bigger, higher-connectivity problems that want to get ready for when the quantum processors are bigger.
- s1dev 7y ago
  You can't get thousands of variables with all to all connectivity on a quantum annealer. The noise will kill it. I.e. you will never have such a device with reasonable coupler precision. The techniques for decomposing a problem and solving the sub problems are a big (exponential) overhead because of frustration effects which require you to look at the entire problem at once. And for context the PUBO -> QUBO mapping (high order to low order) + topology embedding can blow up the number of variables by an order of magnitude or more. The solution space scales exponentially with the number of variables so a naive solver will again deal with a messy overhead.

by s1dev 7y ago

core-questions 7y ago

> Furthermore, real optimization problems have high connectivity, high weight cost function terms, and require higher precision than available. Have you seen their hybrid system they just released? https://www.zdnet.com/article/this-cloud-service-lets-you-use-quantum-and-classical-computing-together-to-solve-big-problems/ https://www.zdnet.com/article/this-cloud-service-lets-you-us... Looks like it's a strong contender for people who have bigger, higher-connectivity problems that want to get ready for when the quantum processors are bigger.

s1dev 7y ago
You can't get thousands of variables with all to all connectivity on a quantum annealer. The noise will kill it. I.e. you will never have such a device with reasonable coupler precision. The techniques for decomposing a problem and solving the sub problems are a big (exponential) overhead because of frustration effects which require you to look at the entire problem at once. And for context the PUBO -> QUBO mapping (high order to low order) + topology embedding can blow up the number of variables by an order of magnitude or more. The solution space scales exponentially with the number of variables so a naive solver will again deal with a messy overhead.