Slashdot Mirror
Currently Quantum Computers Might Be Where Rockets Were At the Time of Goddard
schwit1 writes: If quantum computing is at the Goddard level that would be a good thing for quantum computing. This means that the major fundamental breakthrough that would put them over the top was in hand and merely a lot of investment, engineering and scaling was needed. The goal of being able to solve NP-hard or NP-Complete problems with quantum computers is similar to being able to travel to the moon, mars or deeper into space with rockets. Conventional flight could not achieve those goals because of the lack of atmosphere in space. Current computing seems like they are very limited in being able to tackle NP-hard and NP Complete problems. Although clever work in advanced mathematics and approximations can give answers that are close on a case by case basis.
Stripping off the D-Wave Quantum nonsense:
http://phys.org/news/2014-06-independent-group-d-wave-quantum-speedup.html
"(Phys.org) —An independent research team with members affiliated with several universities in the U.S. and Switzerland has concluded that the D-Wave Two computer shows no signs of quantum speedup"
-----
It does a calculation known as 'constrained minimization'. so for a function f(x1,x2,x3....) where x1 has limits on acceptable values (constraints), x2 has limits, x2,...and so on, calculate a minimum value of f(x1,x2,x3...) and say at what x1,x2,x3,.... those values occur.
In theory you could brute force this with noise (which would randomly change x1, x2 and x3, x4..., trying all possible values and filtering for ones that are within the constraints. D Wave claim to do it in quantum way, i.e. all possible values simultaneously being tested by the magic of Quantum Annealing. However their kit doesn't show that, and the results it generates under tests are often wrong, indicating all possible values have not been tested.
So we have a problem here. It behaves like a noisy system being used to brute force a calculation, and like that system it generates wrong results because noise is random and spread across time, and you cannot know if you've given it enough time to get the optimal solution. And since we can run classical techniques for constrained minimization, we can find *better* solutions, and this prove it has not actually done the task!
It also means it cannot possibly be doing Quantum Annealing because it has not tested all solutions. No amount of money will turn a brute force noise machine into a Quantum computer.
"Currently Quantum Computers Might Be Where Rockets Were At the Time of Goddard"
Designed on totally incorrect physics?
https://en.wikipedia.org/wiki/...
The true revolutionaries of rocket propulsion all have German last names.
Quantum computers cannot solve NP-Hard or NP-Complete problems -- at least, no faster than a classical computer. This is one of the most basic results in the field, and the author keeps on making hash of it.
No, in fact the basic result in the field is that it isn't known if quantum computers can solve NP-Hard or NP-Complete problems more efficiently than a classical computer.
From a accessible article (http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf):
"The question thus remains unanswered: Is there an efficient quantum algorithm to solve NP-complete problems? Despite much trying, no such algorithm has been found—though not surprisingly, computer scientists cannot prove that it does not exist."