Showing changes from revision #8 to #9:
Added | Removed | Changed
Seems like everywhere I turn, someone’s writing about a new revolution that adiabatic quantum computers will gracefully usher in.
And increasingly more people have emailed me various questions about this stuff. So I’ve gotten used to fielding them.
All the while, mounds of stories have appeared that either totally omit the technical details, get them painfully backwards or quickly gloss them over.
So today I wanted to explain them, and not just a few core ideas, but some of the historic concepts that got this all started. You see, I feel that these ideas connect computer science in physics in a way I consider to be rather profound. Maybe you’ll think so too. Getting It’s really fundamental physics that touches on the deep questions related to this crazy universe we call home. Oh and getting a neat new computer out of the deal is a fun bonus too. Just check out how nice looking this stuff is
Just check out how nice looking this stuff is
There above you see the chip itself — it’s then attached to a refrigerator, like this
Then this happens
and finally it’s all boxed up before being shipped out. There’s even a herd being studied at Google
Why do I respond emotionally to these amazing pictures? Well, it all started as a young pup who carried a graphing calculator in his pocket all of the time. I wrote a quixotic email to (a then tiny) Vancouver British Columbia based company. Next, I was Northward bound.
And either you’ve guessed it by now or maybe you already knew: it’s this company, they’re the ones in the news trying to usher in this commercial quantum revolution.
Due to my ‘admiration’ of open offices, I ended up transforming a closet into my personal space. And I learned a thing or two about adiabatic quantum computing in my three-year closet tenure. adventure. If you want to hear about the life lessons I learned in my 10k closet hours, then you might want to subject yourself with to my TEDx talk,
I can’t bear to watch it myself, so I don’t know how it is. Please don’t tell.
You I see, guess you might say my keepers would open the closet door occasionally and toss problems in to keep me happy, happy. and One one of these I callmy first love . And so yes, I have a bit of a sentimental attachment to the topic.
Sometimes life seems more random than fiction could be. Case in point, (i) divulging to thousands of strangers I enjoyed the tranquillity 10k hours of closet concentration afforded me; or (ii) the dual reasons I call this delightful little gem, my first love—one should be apparent, but the other, well you wouldn’t have guessed it I don’t think. I wrote up the results in a first joint paper together with Peter Love. The name rings like a bell doesn’t it? And these days we call him the Love Professor, but before we wrote the paper, the Love Doctor sufficed. So whenever I talk about that paper, I always say I did that work with ‘Love’ and those in the field, they get it.
So now you know probably more than you wanted. But at least I hope you can relate to exactly why I’m writing a bit about adiabatic quantum computing for you.
Despite what you might be thinking by now, I don’t have all day. And I know you don’t either. Nor do we have the space to explain all of adiabatic quantum computing. And I bet you don’t want that anyway. So don’t worry.
What I will do is at least sketch the plateaus and valley’s, and leave investigating the trees and streams to those wanting to dig into some serious reading.
If you get stuck with something, just drop me a line. I must seem friendly enough, since people are doing this already. Oh and I want to somehow personally think of this as a prelude to a review article I’m planning to write on adiabatic quantum computing with Daniel Lidar. He directs an effort at USC, which first purchased one of these gadgets to conduct research on, see
But I can’t really dig into that review article until after I finish the book I’ve affectionately named, the everlasting gobstropper, I’m writing with John. Maybe I’m just blogging to distract myself from that. Anyway, who cares, enough chit chat. Let’s dive in.
Adiabatic quantum computing relies on the idea of embedding a problem instance into a physical system, such that the systems lowest energy configuration stores the problem instance solution.
So there you have it. But what does it mean?
The rest of this article is devoted largely to explaining the following words/phrases, all taken from that sentence above:
Before we get to the ugly details, let me tell you why adiabatic quantum computing is so attractive.
You see, many real-world physical systems evolve towards their minimal energy configurations by interacting with their environments or otherwise. That is, they settle naturally.
Stated roughly, the concept of adiabatic quantum computation resides on representing a computationally meaningful problem in the low-energy configuration of a physical system. The computational process then relies on evolving the system into its low-energy configuration and next, measuring the result. So in other words, we want to let nature do the hard work for us.
There are a number of physical systems that map to what are known as spin models. The basic jest of the idea is really appealing from a computational point of view, so let’s explain it that way. Here’s how it goes.
We start with some graph, like this
And then we get to decide the energy of the system — just put an arrow pointing up or done on all of our graph nodes, like this
The edges in this graph come in two types. In terms of physics, they either represent a ferromagnetic or an antiferromagnetic interaction. But we can just think of them as being either positive or negative.
The yellow nodes, these are supposed to be the spins. The arrow directions are meant to represent the magnetic dipole moments of the spins. But all that really matters for us now, is that they can be in one of two states (called, + or −). And I’m so nice to you that we won’t even need to worry about physical units today. Pretty soon, we’ll get to the punch line. But to summarize
The interactions in the physical systems we are concerned with can be mapped to graph edges
The state of the physical system is given by an assignment of either + or - on the nodes of the graph
For every +, - assignment of the spins, we can calculate an energy of this graph. Here’s how the trick works. First, we have to pick weights for the edges of the graph, so how about like this
For every edge, which of course connects a pair of spins here’s what you do. You multiply the edge weight by +1 if the spins are both pointing in the same directions. And you multiply by -1 if they are pointing in opposite directions. Then you just sum up the energy contribution for all of the edge weights. That’s it.
Here we have three edges and three spins. Start with the left most and top spin, we see that the spins are not aligned. So we multiply the connecting edge weight of -1 by another -1, resulting in a +1 contribution in the total sum.
Next, let’s consider the top spin and the right most one. They’re pointing in the same direction and +1 times -1 and just -1: this removes the above +1 for a sum of zero (don’t worry about the energy scale here, it’s not important and zero energy is valid in our picture).
For the final bottom pair of spins, following the same trick, we add a -1 to our sum.
So the total graph energy for this spin assignment is -1.
The lowest energy is found by iterating all possible arrow assignments and repeating this procedure above. It might not be unique, and finding it turns out to be closely related to many problems in computer science.
The point is however, that this is physics. This graph is an abstraction, but many systems really behave this way.
An adiabatic quantum computer essentially allows one to pick the graph and the edge weights. Finding the configuration of the spins then
Many naturally occurring systems exist which seem not to evolve into their lowest energy configurations in any sort of `reasonable' amount of time. The classic example of such systems are the spin-ices---these physical systems characteristically appear to never settle on any reasonable time-scale(s). As a physical spin system can be mapped (and conversely) to various computational problems, it then becomes a question of both physical and computational relevance to quantify the physical resources required to evolve a given system into its low-energy configuration. Such ideas can be stated as a consequence of a related physical principle.
The Church-Turing-Deutsch principle [Deutsch:85] is a physical form of the Church-Turing thesis stating, essentially, that a universal computing device can simulate every physical process. The relevance is that if a physical system exists which tends not to settle to its low-energy configuration, then this presents empirical evidence that computationally simulating the physical setting would be expensive. Conversely, given a physical system with a low-energy state representing a computationally challenging problem, such a system would then take ample time to settle. These concepts are at the heart of contemporary ideas which view computational complexity theory as being dictated by physical laws and conversely.
%A seminal result from the early days of computational complexity theory states %that Every NP-complete problem is Karp-reducible to the problem 3-SAT, by %the Cook-Levin Theorem [Cook,levin1973universal].
Such a concept began to be quantified and vivid physical relevance emerged when, in 1982, Barahona proved that finding the lowest energy configuration of Ising spins acting on a 2D lattice is $\NP$-hard [barahona_computational_1982]. Other seminal early results which connect physical process with computational complexity theory include the concepts of algorithmic simulated annealing [Kirkpatrick1983] by Kirpatrick et al.~which has long been applied to satisfiability (i.e.~K-SAT) and related problems.
These concepts and other concepts connecting physical processes and computation, seem to play an even richer role in quantum systems: in many known cases, quantum systems evolve into their lowest energy states faster than their classical counterparts. This can offer a computational advantage. Additionally, many basic properties of matter are poorly understood. Several long-standing questions about the ground state properties of physical systems seem to now rest centrally on ideas in computational complexity theory. Here we review several central concepts which have given rise to this rapidly evolving field.
Adiabatic Quantum Computing (AQC) is the term describing computations that harness the properties of the ground state of a physical system as a means to compute. There are three common approaches to AQC. The first is the use of adiabatic evolution to solve optimization problems: {\it adiabatic optimization}, the second is universal adiabatic quantum computation: {\it universal AQC}, and the third relies on annealing processes to again address optimization problems: {\it adiabatic quantum annealing}.
In all three approaches, a problem instance must first be efficiently embedded into the physical (lowest energy) state of a quantum system. This is done through representing problem instances in terms of the (tailored) representative system energy functions (a Hamiltonian). Then the system must be evolved into its lowest energy configuration to recover the result. The evolution of the system, constitutes the computing process in AQC. Clearly the run-time of this process is of central interest.
The computing process of AQC relies on the adiabatic theorem which states roughly that if a system starts off in a low-energy configuration with some initial Hamilton a ($H_0$), and the systems Hamiltonian changes slowly enough to some final Hamiltonian ($H_f$), the system will remain in its low-energy state. When the initial Hamiltonian of the system has a ground state which is (i) computationally easy to prepare, e.g.~can be done quickly, and (ii) the final Hamiltonian, $H_f$, embeds a computational problem of interest and (iii) the evolution satisfies the adiabatic theorem (or otherwise remains close to its ground state) then the final system’s state stores the result of a computation.
My biggest problem I have with this entire thing is not, ‘if it’s quantum’. It’s that everyone assumes that if it is quantum then that’s good. The objective of D-Wave is not a universal quantum computer or at least a quantum simulator (at least not now) but instead, a simulated annealing machine for optimization problems. I think they will simply never surpass classical devices in this area. Not the least of the reason being they’d have to catch up and surpass a technology which is still improving rapidly. So advancement of classical devices would have to drop to exponential, the advancement of their quantum annealers maybe could catch up to that, but the overall speedup is thought to be quadratic. Meaning, if everything goes well, and they even managed to catch up, classical devices would need to scale only polynomially to again beat their annealing machine.
Say I predict that a given physical system would be ‘computationally hard’ to simulate. Then if I physically construct this same physical system, would it constitute a ‘computationally powerful’ device? Turning the tables in this way constitutes the basic gist of quantum computation, but it took ages to arrive at! In this view, physical processes are viewed as computer programs.
Ground State Spin Logic, by James D. Whitfield, Mauro Faccin and Jacob D. Biamonte, in Europhysics Letters 99, 57004 (2012)
Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins, by Jacob Biamonte, in Physical Review A 77, 052331 (2008)
While any quantum algorithm can be run on a universal adiabatic quantum computer in principle, combinatorial optimisation problems appear to be the most suitable choice for near-term devices. Recent experimental progress has resulted in annealers with around 500 spins and studying the quantum properties of these devices has sparked dramatic interest and debate in this rapidly growing area. More generally, several notable results have emerged on the topic of ground state computation. These have paved a path towards a unified view of computer science and physics, formed by studying the computational complexity of evolving a physical system into its ground state. Here we present a comprehensive review of the constituent results of this field.
Anyways, why talk about quantum computers on Azimuth you might ask? Well, as you might have noticed, there’s an army of tech savvy environmental enthusiasts regularly contributing here. But you, yes you’re my target audience, not just them. Just check out some of the cool articles recently not to mention the many articles on quantum physics and network theory — see quantum network theory Part 1 and Part 2 by Tomi Johnson and Noether’s theorem: quantum vs stochastic by Ville Bergholm. So Azimuth is a good place to present a bit more of a technical account of this stuff.