Ganesh Swami

As a British Columbian, D-wave’s story in the Economist makes me happy. This single story might have done more for the province than all the marketing the government has been trying to do. But today, I came across this note to the Economist by Umesh Vazirani:

Sir,

Your article “Orion’s belter” regarding D-Wave’s demonstration of a “practical quantum computer”, sets a new standard for sloppy science journalism. Most egregious is your assertion that quantum computers can solve NP-complete problems in “one shot” by exploring exponentially many solutions at once. This mistaken view was put to rest in the infancy of quantum computation over a decade ago when it was established that the axioms of quantum physics severely restrict the type of information accessible during a measurement. For unstructured search problems like the NP-complete problems this means that there is no exponential speed up but rather at most a quadratic speed up.

Your assertions about D-Wave are equally specious. A 16 qubit quantum computer has smaller processing power than a cell phone and hardly represents a practical breakthrough. Any claims about D-Wave’s accomplishments must therefore rest on their ability to increase the number of qubits by a couple of orders of magnitude while maintaining the fragile quantum states of the qubits. Unfortunately D-Wave, by their own admission, have not tested whether the qubits in their current implementation are in a coherent quantum state. So it is quite a stretch to assert that they have a working quantum computer let alone one that potentially scales. An even bleaker picture emerges when one more closely examines their algorithmic approach. Their claimed speedup over classical algorithms appears to be based on a misunderstanding of a paper my colleagues van Dam, Mosca and I wrote on “The power of adiabatic quantum computing”. That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave’s “quantum computer” even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone.

Yours sincerely,
Umesh Vazirani
Roger A. Strauch Professor of Computer Science
Director, Berkeley Quantum Computing Center

(via Scott Aaronson)

Possibly related:

• No related posts

This entry was posted on Saturday, February 17th, 2007 at 11:58 pm and is filed under Computing, Physics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.