[This post is authored by Matt Hastings, who has kindly guest blogged this article on adiabatic quantum computation. - T.]
In this guest post, I want to talk about adiabatic quantum computing. But first, a couple comments on how this post fits into “open notebook” science. I don’t keep a detailed notebook. Instead, I have a bunch of random ideas, most of which (>95%) I discard very quickly. I’m going to write about one idea of these ideas. I think this idea could be promising, so this post is not about a completely discarded idea. On the other hand, I think that there are many people who are much more capable of getting something out of this idea than I am. So, I think this is a way that I can use “open notebook” science to see if anyone else can use this.
There are many proposals for doing quantum computing. But basically all of them involve the following sequence of steps: you initialize a system to some quantum state, you evolve it under some Hamiltonian (which may be time-dependent), and then you measure something to get your answer. If you think about the usual gate model of quantum computing, you can imagine producing the effect of each of those 2-qubit gates by acting for a short time with a Hamiltonian that acts just on those two qubits (in fact, that is how it would actually have to be done in practice). If you think about measurement based quantum computing, there are in fact many measurement steps in between, not just one at the end, but all of those intervening measurement steps could be modeled by Hamiltonian dynamics in some larger Hilbert space. So, everything in quantum computing is just create a state, evolve, and then measure.
Adiabatic quantum computing is a special case of this. In adiabatic quantum computing you again evolve the system under a time-dependent Hamiltonian, , but you have two further constraints. First, your initial state is the ground state of . Next, the Hamiltonian changes very slowly in time, so that for all times your quantum state remains close to the ground state of .
Let me add some more notation, and write for a parameter dependent Hamiltonian. Then, I will pick
where is some function that tells me how depends on . I will pick , and , where is the largest that I consider. The reason for introducing this parameter is that it allows me to focus my attention on how the spectral gap of behaves. Then, once I know how the spectral gap behaves, I can then pick so be sufficiently slowly varying (varying slower than the inverse gap). This is more convenient than picking from the beginning, because now I can first pick a path in parameter space (a parameter-dependent Hamiltonian ) and then later analyze its properties. In fact, I should also mention that how rapidly we can allow to vary depends not just on the spectral gap of , but also on how rapidly varies with .
The original proposal for doing adibatic quantum computing by Farhi et. al. involved something like this: let , where was the Hamiltonian for some difficult optimization problem (say, 3-SAT) and was a simple Hamiltonian where the qubits didn’t interact with each other. Typically, we would pick to be diagonal in the basis, and pick to correspond to a magnetic field in the y-direction. The physical motivation for this choice is that will flip spins back and forth, and that will help the system tunnel between different local minima of , leaving the system ultimately in the ground state of . Note that in this scheme we have .
The performance of this scheme depends on how small the gap between the ground state and first excited state is. Numerics on small systems suggests that in many cases the gap remains large enough that this method can outperform classical algorithms for finding ground states of . However, it also seems that in the worst case the gap can still become exponentially small. Thus, in the worst case, the algorithm can still take an exponential time to run. This is not surprising, as we do not believe that a quantum algorithm will be able to solve NP-complete problems in less than exponential time.
I was told a couple weeks ago at a visit to MIT that one can improve this a little by making , where is a sum of random local few-qubit interactions. (inserting a litle detail about personal trips, etc… into this post, as seems to be required for any blog post) I wish I knew exactly where this is written.
The real understanding of the performance of this algorithm may have to wait until we have a working quantum computer. After all, there are many heuristics which are very effective classically but which cannot yet be proven to work well or which were only proven to work well a long time after their power was recognized in practice. Examples include the simplex method and belief propagation.
It has also been shown by Aharonov et. al. that such a linear interpolation, , is computationally as powerful as the gate model. This is based on showing how to directly translate a given quantum circuit into a pair of Hamiltonians and .
All such versions of adiabatic quantum computation have a small spectral gap, either exponentially small in the worst case of 3-SAT, or polynomially small in the case of mimicking the gate model. This is bad. Partly, it is bad because it makes the computation slow. But this isn’t such a problem: if the gap becomes polynomially small then the computation takes a polynomial time, but if the computation produces the same result as a polynomial depth quantum circuit (which also takes a polynomial time) then one can’t hope for anything better than this. The real reason that this is bad is due to errors. Noise from the environment can excite the system. A large spectral gap would help avoid this, and would be a form of natural error correction.
So, the question is: can we make adiabatic quantum computation with a large spectral gap (of order 1)? Immediately, we realize that this will imply that we follow a “long path” in parameter space if we want to do anything use. So, we have an that does not obey the simple form, . Instead, follows a long path from to , where is polynomially large. To see why we need a long path, suppose we follow a path in parameter space of length , and the inverse spectral gap is also . Then our quantum computer can do this computation in a time and so it really doesn’t have time to do anything nontrivial (quantum computers may be powerful, but not that powerful!).
What if is logarithmically large? This still isn’t good enough. One can use ideas of quasi-adiabatic continuation, that I and Wen and Tobias worked on, to show that as long as the inverse spectral gap is , this can still be simulated in polynomial time. Again, not much of a surprise: such an evolution can be performed by the quantum computer in logarithmic time, and we expect at most an exponential improvement from a quantum computer. You do have to worry a little bit about the error if you try to prove that it can be efficiently simulated classically using the adiabatic theorem, since there seems to be some controversy about exactly what error bounds you can get from adiabatic evolution, but quasi-adiabatic lets you prove what you want.
So now we realize that we need to be polynomially large. Recently I showed that even this doesn’t work if you stay in one dimension. In one dimension, the spectral gap implies that one can approximate the ground state by a matrix product state, and the adiabatic continuation lets one find this approximation on a classical computer. So, everything that can be done with an order unity spectral gap in one dimension can be done on a classical computer in polynomial time.
The upshot is that if we want the spectral gap to be of order unity, we need to have a polynomially long path, and we need to work in more than one dimension. So, my idea (finally!) is to see if there are any interesting algorithms based on such a long path. Is there any reason to believe that this will allow us to get nontrivial results? That is, is this idea at all useful? Well, topological quantum computing can be realized as adiabatic evolution: add some terms to the Hamiltonian which favor producing defects, and then slowly change those terms to drag the defects, and braid them. So, one answer is that not only is it possible, but that this possibility in fact already is well known. However, topological quantum computing relies on a highly degenerate ground state. What I would like to know is: is it possible to do this “long path” adiabatic quantum computing with a unique ground state and a spectral gap of order 1?
I don’t know. Maybe. I thought for a short time about whether one could at least come up with a Grover algorithm that worked this way, but didn’t get anywhere. I also thought for a little while about whether one combine this idea with the idea above of interpolating between an which is a uniform magnetic field in the y-direction, and which is a 3-SAT problem in the z-basis. Perhaps instead of linearly interpolating one could imagine changing between and in a position-dependent way. Maybe one could choose some long random path in parameter space.
So, I hope someone finds this interesting!