Opening Quantum Computing To the Public 191
director_mr writes "Tom's Hardware is running a story with an interesting description of a 28-qubit quantum computer that was developed by D-Wave Systems. They intend to open up use of their quantum computer to the public. It is particularly good at pattern recognition, it operates at 10 milliKelvin, and it is shielded to limit electromagnetic interference to one nanotesla in three dimensions across the whole chip. Could this be the first successful commercial quantum computer?"
Re:But does it work? (Score:5, Informative)
Re:Was I the only one? (Score:2, Informative)
Re:What does this mean for encryption? (Score:5, Informative)
No, their device is *NOT* a universal quantum computer. So far as I know, no reputable quantum physicist not in their employ has been allowed to examine what they actually do. Examples of performing calculations impractical on a classical computer are not available as far as I know.
They are something of a joke among the QC people I know. While people acknowledge that their device may be possible of doing some interesting things, everything they do is acting like they have something to hide.
Re:How does it work? (Score:4, Informative)
Can someone post a link that describes the benefits of a quantum architecture and how software can be written to take advantage of them?
And by "benefits", I don't mean hype.
http://en.wikipedia.org/wiki/Shor%27s_algorithm [wikipedia.org]
^The big one.
Re:How does it work? (Score:5, Informative)
The wikipedia article is not bad, though it is fairly technical.
A very small number of algorithms are known for universal quantum computers (which the D-wave device does not claim to be) that are asymptotically faster than any known algorithm for classical computers.
The most widely known of these is Shor's factoring algorithm. Mostly it would be useful for breaking public key cryptography. The others are: Grovers search algorithm which can give a small speed boost to any classical algorithm that involves enumerating all possibilities and checking some property and quantum simulation: simulating the behavior of systems of many particles where quantum effects are important.
In the past 10 years, considerable progress has been made, but nobody still has a good handle on when scalable universal quantum computing might be a reality, though it no longer looks impossible--only very hard. D-wave does not claim their device is universal. In particular they don't say they can do factoring. They claim to be able to efficiently do quantum simulation and also traveling salesman type optimization problems. Evidence of them actually solving any hard problems is not widely available.
Uh (Score:3, Informative)
It is particularly good at pattern recognition, it operates at 10 milliKelvin, and it is shielded to limit electromagnetic interference to one nanotesla in three dimensions across the whole chip. Could this be the first successful commercial quantum computer?
Based on that description? No. I don't even know what the fuck any of that stuff you just said even means, man (except for the bit about pattern recognition, which was an unquantified statement anyway and about as useful as "the computer is fast"). Speak in a language I can understand, like, the average framerate it can run Crysis at.
No proof (Score:5, Informative)
See some skepticism here:
http://scottaaronson.com/blog/?p=306 [scottaaronson.com]
http://scottaaronson.com/blog/?p=291 [scottaaronson.com]
http://scottaaronson.com/blog/?s=d-wave [scottaaronson.com]
Re:How does it work? (Score:4, Informative)
sqrt(N) is small compared to the other promised speedups of quantum computers which are typically reduction from super-polynomial or exponential time to polynomial time.
The real crux is that the type of problems that you often want to apply Grover's algorithm to are already O(2^n). Grovers algorithm reduces that to O(2^(n/2)). With a similar size quantum computer you could only solve problems of roughly twice the size.
Still interesting and potentially useful, The main advantage is its wide applicability. Many classical algorithms can simply be directly translated to a quantum equivalent, then have Grover's algorithm applied. Finding a special-purpose quantum algorithm is typically very hard or impossible.
Re:How does it work? Parallel universes. (Score:3, Informative)
A good reason to look there is to get an intuition of the concept of computing using parallel universes.
Re:How does it work? (Score:2, Informative)
D-wave does not claim their device is universal. In particular they don't say they can do factoring. They claim to be able to efficiently do quantum simulation...
Being able to "efficiently do quantum simulation" makes a device a universal quantum computer. That is what "universal" means.
Re:28 Qubits ought to be enough for everybody (Score:4, Informative)
Actually, it doesn't matter how fast a classical computer operates, a quantum computer WILL go exponentially faster regardless. I researched quantum computers in a laureate report I did a few year back. Quantum computers are able to achieve a dual state as a result of calculations. Also, quantum computers operate on the mathematical principles of a unitary matrix. One of the properties of a unitary matrix is it's reversibility, so that any operation that can be perform can be "unperformed". So take the ability to reverse calculations and achieve more than one answer at once, and you can "unperform" at an exponential rate. For example, you have a matrix with an "and" gate. If you where to reverse the and gate on the value '0', superposition will allow you to get the answers '10', '01', and '00' all at the same time. This means that a 64-qubit computer and theoretically "unrun" 2^64 (more than the molecules in the universe) times faster than a 64-bit computer. Now that is just a simplified gist of things. I don't want any physicists saying "you forgot the Hademard gate etc." The process is much more elaborate, and much more prone to other factors.
Now as for you other comments: 1) quantum computers will be a better candidate for simulating AI on a common commercial scale, and 2) quantum computing already is possible. The discovery that will most likely be made is the ability to create a room-temperature equivalent of a Bose-Einstein condensate so that topological quantum computers (the most reliable model so far) can be fit onto something the size of a thumb.
Re:Still not easy to build at home (Score:3, Informative)
Probably, their Hamiltonian phase-space is severely limited. I.e. their quantum computer can't explore all possible configurations of phase-space.
That means it'll need a lot more qubits than an 'ideal' computer for some tasks.
Hadamard gate (Score:5, Informative)
I don't want any physicists saying "you forgot the Hademard gate etc."
I think you meant "Hadamard gate".
-- Any Physicist
(Much easier to google for the wikipedia article with that spelling.)
Re:28 Qubits ought to be enough for everybody (Score:4, Informative)
this has so far not been proven. What is proven is that a quantum computer can outperform a classical computer polynomially (in algorithms based on unstructured search) and that it can outperform the best currently known classical algorithms for some problems (factoring, quantum simulation) exponentially. Moreover, exponential separation has been proven in terms of "query complexity" for "oracle problems" (in which a quantum black box is assumed to be available and only the number of accesses to the black box is counted as cost) and in terms of "communication complexity" in quantum communication (where the number of (qu)bits that need to be exchanged between two locations is counted as cost).
Quantum computers are able to achieve a dual state as a result of calculations. Also, quantum computers operate on the mathematical principles of a unitary matrix. One of the properties of a unitary matrix is it's reversibility, so that any operation that can be perform can be "unperformed". So take the ability to reverse calculations and achieve more than one answer at once, and you can "unperform" at an exponential rate.
that does not follow. having a superposition of 2^100 answers doesn't help you to get out a single one (since when you perform a measurement (and a quantum computer is supposed to give us a conventional ("classical") answer to our problem) each answer occurs with exponentially small probability only. The hard part is to make all these many "answers" to interfere such that the right answer comes out with high probabiliy (that decreases only polynomially in the number of bits used as input). Also, reversibility is not needed for a quantum speed-up.
Re:What does this mean for encryption? (Score:2, Informative)
The problem is that tweo of these do basically give you the same maximum problem size as one does.
This only holds if the two computers can only communicate clasically and have no prior entanglement -- and right now we're better at communicating qubits than building them. (see "quantum encryption", which relies on precisely this operation!)
My present impression is that the effort of adding qbits grows quadratically or the like, as each qbit has to be entangled with each other qbit (that is n*n entanglements).
No. It's only a constant amount of work to entangle an unentangled n'th qubit with n-1 others -- any quantum operation will do it.
While you are producing the complicated state you can use error correction to preserve that state, which adds only a constant factor overhead. The problem thus far is that the best techniques previously simply do not scale, although we have plenty of ideas that would. This is largely a matter of engineering, but that takes time.
Re:Headline is wrong and you are wrong too (Score:3, Informative)
"A kelvin is a unit of temperature difference,"
It is a unit of thermodynamic temperature.
"a defined fraction of the temperature of the triple point of water above absolute zero."
Note the inclusion of absolute zero in the definition.
"It is not a scale referenced to Absolute Zero."
Yes, it is; it is a unit of thermodynamic temperature. Didn't you pay attention in your basic chemistry class?
"But the milli prefix is not capitalised, because capital M implies the Mega prefix"
If you spent more time reading my post rather than rushing off to be "right," you'd have noticed that I was arguing that the term "millikelvin" is not a proper noun, and that if it was, the first letter of the word "millikelvin" would be capitalized. And while the symbol for the prefix "mega-" is capitalized, when it is spelled out it follows the same rules of capitalization as the rest of English; you'd only capitalize "megakelivin" if it appeared at the beginning of the sentence, was used in a title, or the like.
"The correct, pedantic version is "10 mk above Absolute Zero", or "10 millikelvins above Absolute Zero"."
The symbol for kelvin needs to be capitalized, "above absolute zero" is redundant, and "absolute zero" (at least as thermodynamic temperatures go) is not a proper noun or title and should not be capitalized. The temperature was 10 mK.
Let me try the HTML link again: here [nist.gov]
Re:28 Qubits ought to be enough for everybody (Score:4, Informative)
Actually, it doesn't matter how fast a classical computer operates, a quantum computer WILL go exponentially faster regardless.
I really, really hope that you failed whatever course the report was for. There is not, at present, any known problem which for which a quantum-computing algorithm is known to be exponentially faster than the fastest classical algorithm.
Factoring is known to be sub-exponential, so Shor's O(n^3) quantum algorithm does not provide an exponential speedup.
The strongest known result in terms of speedup for quantum algorithms is for unordered search, from O(n) to O(sqrt(n)), which, again, is not an exponential speedup.
There are some intuitive arguments for why an exponential speedup might be possible. There are also some intuitive arguments for why it shouldn't be. There is no proof either way, as things currently stand.
(Note: I am not an expert in the field. This reflects my understanding, which was current as of about 5 years ago. To the best of my knowledge, things have not changed, but I don't read the literature like I do in other areas).