Many Google services we offer depend on sophisticated artificial intelligence technologies such as machine learning or pattern recognition. If one takes a closer look at such capabilities one realizes that they often require the solution of what mathematicians call hard combinatorial optimization problems. It turns out that solving the hardest of such problems requires server farms so large that they can never be built.
A new type of machine, a so-called quantum computer, can help here. Quantum computers take advantage of the laws of quantum physics to provide new computational capabilities. While quantum mechanics has been foundational to the theories of physics for about a hundred years the picture of reality it paints remains enigmatic. This is largely because at the scale of our every day experience quantum effects are vanishingly small and can usually not be observed directly. Consequently, quantum computers astonish us with their abilities. Let’s take unstructured search as an example. Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers. This mind boggling feat is known as Grover’s algorithm.
Over the past three years a team at Google has studied how problems such as recognizing an object in an image or learning to make an optimal decision based on example data can be made amenable to solution by quantum algorithms. The algorithms we employ are the quantum adiabatic algorithms discovered by Edward Farhi and collaborators at MIT. These algorithms promise to find higher quality solutions for optimization problems than obtainable with classical solvers.
On the hardware side we are collaborating with D-Wave in Vancouver, Canada. D-Wave develops processors that realize the adiabatic quantum algorithm by magnetically coupling superconducting loops called rf-squid flux qubits. This design realizes what is known as the Ising model which represents the simplest model for an interacting many-body system and it can be manufactured using proven chip fabrication methods. Unfortunately, it is not easy to demonstrate that a multi-qubit system such as the D-Wave chip indeed exhibits the desired quantum behavior and experimental physicists from various institutions are still in the process of characterizing the chip.
Today, at the Neural Information Processing Systems conference (NIPS 2009), we show the progress we have made. We demonstrate a detector that has learned to spot cars by looking at example pictures. It was trained with adiabatic quantum optimization using a D-Wave C4 Chimera chip. There are still many open questions but in our experiments we observed that this detector performs better than those we had trained using classical solvers running on the computers we have in our data centers today. Besides progress in engineering synthetic intelligence we hope that improved mastery of quantum computing will also increase our appreciation for the structure of reality as described by the laws of quantum physics.
The theory paper on which the demonstration is based can be found on the arXiv and a report describing the details of the implementation is here.
20 comments:
So does this mean that D-Wave was not a total scam after all? Gosh, they really could have come across with less bluster when they first went public!
Nope. DWave still seems to be a scam. Note that there was no claim that this system exhibits any characteristics of a quantum processor of any kind. The hardware only performs better than some servers - but it could very well just be a standard analog ASIC optimized for this application. Nothing quantum around. Too bad Google seems to have been fooled by hype and pseudoscience.
Video of demo is here:
http://videolectures.net/opt08_neven_tabcwt/
Hi Mike, it you'd like to take a look at evidence that their components and system are behaving quantum mechanically, there are a large number of links to PRLs etc describing the system at http://dwave.wordpress.com/system-overview/. See http://arxiv.org/abs/0909.4321 for the qubit they are using. Just the qubit by itself is eons more advanced than anything anyone else has done. What this team has done is potentially the most important result achieved to date in quantum computation. Before flaming them you should do some background research.
Saying something like-- it might not be quantum, therefor "Nothing quantum around"--is illogical. Evidence over opinion.
1.
2.
3. evidence
4.
5.
6. opinion
7.
8.
9.
Can I get a slight placement on a word known as "experience"? Where does that fit in there? Kind of far down, or kind of high up? I left you room wherever you want to put it. I have what's already ordered.
I am with the dude Mike. I am begging you. You do not agitate for someone to do more reading before posting, bitch, or I am sure the reading will never be enough until they agree with you.
There isn't anything new here. I think there is, until Mike saves me. It is rambunctious to say you are going to prove the ultimate nature of the universe as just a side benefit, and stick it on top of a browbeating, "Oh, by the way, it's quantum because we have been using it now for umpteen generations and it never even burned out."
What are these loops? Are they disposed in three dimensions like a cochlear implant in a hearing aid? Because, my dog can recognize cars.
---Steve
ITS A TRICK ITS JUST SKYNET. EVERYONE RUN.
Congrats Google A.I. team! Have you considered using diffusion reaction computational dynamics?
Google takes search really seriously.
Great post too: it's not easy to make a post with such scope readable.
Keep pushing the envelope!
Technology is getting so powerful. Soon it will be used to solve all the world's problems.
By the way, love Google and Chrome is the best!!! Thank you Google!
Replying to:
"Hi Mike, it you'd like to take a look at evidence that their components and system are behaving quantum mechanically, there are a large number of links to PRLs etc describing the system at http://dwave.wordpress.com/system-overview/. See http://arxiv.org/abs/0909.4321 for the qubit they are using. Just the qubit by itself is eons more advanced than anything anyone else has done. What this team has done is potentially the most important result achieved to date in quantum computation. Before flaming them you should do some background research."
I've read every PRL and I've read the PRA in which M.S. Amin explicitly states that the form of adiabatic QC that DWave claims to be performing can never give scaling benefits in any application.
The qubit is a SQUID loop with tunable coupling. Its design is similar to those used in many other experiments - see Nakamura, Martinis, Oliver, Clark, etc. However, there has never been a convincing demonstration of a quantum coherent effect in their system.
Before you flame my post, perhaps you should do the background reading in the whole field.
For Sppeed,
I'd put experience in at 6.
Better than just opinion, but evidence always comes first
I wouldn't say that Google has been fooled, even if in the end there was no quantum processor on sight.
Ok, nobody has proven until now that D-Wave *does* quantum computing, but...does it really matter?
Theoretically or academically it does, but on the practical side of life, and under Google's p.o.v. I guess, if it performs significantly better than other architectures at solving complex search problems, it would still work for them, and allow them to gain advantage over competitors relying on traditional systems.
Nerd fight.
So it isn't Skynet after all, it's D-Wave/Google who will build the T-800 and destroy the world :)
One of the things I've read about working qubits is that they are only correct about 75% of the time. The thing that blows my mind about this is that with a search engine, who cares about the bottom 25%? Send it the same question 1000 times and ask for the 75% most probably correct answers.
So for example, 2+2 = top.01% of 1000 times asked, your answer will end up 4. In day to day use, that's good enough for most applications. Now tie that back in with a standard processor to check the answer. it agrees, awesome, 100% accuracy.
Dear Mike,
Thanks for mentioning my work but this forced me to clarify some confusions.
1. The article you refer to, I think, is PRA 79, 022107 (2009). At the end of this article we state that local AQC requires quantum coherence in order to have scaling benefit. However, local AQC is unfeasible anyway because one needs to know the spectrum before hand. In real life one would never use local AQC, and for usual AQC (which is what we do in
practice) as we showed in the same paper, quantum coherence is not crucial.
2. This brings me to your other remark about coherence. There is a false belief that coherence is the only quantum mechanical effect that exists in the world. Quantum mechanics was not discovered by observing coherence but was by observing energy quantization. Indeed energy quantization is the only thing you need for AQC and coherence (I mean coherence in the energy basis) is unimportant. Of course strong coupling to environment will screw up energy quantization eventually, but there is much more robustness compared to other models of quantum computation.
Every measurement on our qubits so far has been in complete agreement with quantum mechanics, even in coherent regime. We have a measurement of quantum tunneling amplitude in the coherent regime in complete agreement with quantum predictions (see figure 15b in arXiv:0909.4321).
We haven't done coherent oscillation measurement because it is unimportant to us and it requires fast control which is not necessary for AQC.
3. Finally it comes the question of scaling of AQC. Up to now true scaling is unknown. There are some features that can make a problem very difficult (see arXiv:0904.1387) but there may be some ways around it (see arXiv:0909.4766). But for a company like Google or us it is not the scaling in the complexity theory sense that is important. What is important is whether the system can outperform classical computation on average for a particular type of problems.
Over on Scott Aaronson's blog Shtetl Optimized, I posted what started as a light-hearted commentary of this work ... but in the process of writing, my admiration grew, and that comment finished as a serious technical appreciation.
My appreciation and congratulations are therefore extended to Geordie Rose, D-Wave, and Google, for work that IMHO will come to be regarded as having great mathematical interest, as well as significant practical applications.
Technology is evolving with time. I am a college sophomore with a dual major in Physics and Mathematics @ University of California, Santa Barbara. By the way, i came across these excellent physics flash cards. Its also a great initiative by the FunnelBrain team. Amazing!!!
My understanding is that while contemporary quantum computing models can improve performance greatly, perhaps shifting the scope of problems that can be computed in 'reasonable' time, it does not alter the Von Neumann paradigm and Turing limits.
I stand to be corrected but my current understanding is that contemporary quantum models can be simulated on a convention computer or Turing machine. If indeed this is true then the quantum machine will suffer the same Turing/Godel computational limits.
That isn't to say that we might not someday invent a machine that uses quantum behavior which can't be simulated on a Turing machine but I don't believe we have reached that point yet and any such machine.
Post a Comment