(Matt Hastings) Adiabatic quantum computation with long paths

[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, {H(t)}, but you have two further constraints. First, your initial state is the ground state of {H(0)}. Next, the Hamiltonian {H(t)} changes very slowly in time, so that for all times your quantum state remains close to the ground state of {H(t)}.

Let me add some more notation, and write {H_s} for a parameter dependent Hamiltonian. Then, I will pick

\displaystyle  H(t)=H_{s(t)}, \ \ \ \ \ (1)

where {s(t)} is some function that tells me how {s} depends on {t}. I will pick {s(0)=0}, and {s(t_{final})=s_{max}}, where {s_{max}} is the largest {s} that I consider. The reason for introducing this parameter {s} is that it allows me to focus my attention on how the spectral gap of {H_s} behaves. Then, once I know how the spectral gap behaves, I can then pick {s(t)} so be sufficiently slowly varying (varying slower than the inverse gap). This is more convenient than picking {H(t)} from the beginning, because now I can first pick a path in parameter space (a parameter-dependent Hamiltonian {H_s}) and then later analyze its properties. In fact, I should also mention that how rapidly we can allow {s(t)} to vary depends not just on the spectral gap of {H_s}, but also on how rapidly {H_s} varies with {s}.

The original proposal for doing adibatic quantum computing by Farhi et. al. involved something like this: let {H_s=(1-s) H_0 + s H_1}, where {H_1} was the Hamiltonian for some difficult optimization problem (say, 3-SAT) and {H_0} was a simple Hamiltonian where the qubits didn’t interact with each other. Typically, we would pick {H_1} to be diagonal in the {S^z} basis, and pick {H_0} to correspond to a magnetic field in the y-direction. The physical motivation for this choice is that {H_0} will flip spins back and forth, and that will help the system tunnel between different local minima of {H_1}, leaving the system ultimately in the ground state of {H_1}. Note that in this scheme we have {s_{max}=1}.

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 {H_0}. 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 {H_s=(1-s)H_0+s H_1+s(1-s)H_{random}}, where {H_{random}} 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, {H_s=(1-s)H_0+s H_1}, 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 {H_0} and {H_1}.

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 {H_s} that does not obey the simple form, {H_s=s H_1+(1-s) H_0}. Instead, {H_s} follows a long path from {s=0} to {s=s_{max}}, where {s_{max}} is polynomially large. To see why we need a long path, suppose we follow a path in parameter space of length {O(1)}, and the inverse spectral gap is also {O(1)}. Then our quantum computer can do this computation in a time {O(1)} and so it really doesn’t have time to do anything nontrivial (quantum computers may be powerful, but not that powerful!).

What if {s_{max}} 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 {O(1)}, 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 {s_{max}} 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 {H_0} which is a uniform magnetic field in the y-direction, and {H_1} which is a 3-SAT problem in the z-basis. Perhaps instead of linearly interpolating one could imagine changing between {H_0} and {H_1} in a position-dependent way. Maybe one could choose some long random path in parameter space.

So, I hope someone finds this interesting!


9 Responses to (Matt Hastings) Adiabatic quantum computation with long paths

  1. […] 24, 2009 by mick For those who are into the adiabatic model of quantum computation I suggest going here and having a […]

  2. Matt – this is great of you to share and I hope you find some new collaborators this way! Whether or not we can work out what is the theoretical equivalent of a complete laboratory notebook, the point is this is clearly a substantial contribution that can be used by anyone else to move science forward.

  3. […] blog post on AQC February 25, 2009 Posted by Geordie in General. trackback … is here. This is an excellent post with good understanding of adiabatic quantum computation and some good […]

  4. Peadar Coyle says:

    I’m very interested in where the Berry Phase comes into this, I know for instance that the topological properties of this phase, occur in the fault tolerance of quantum computers. Is Adiabatic Quantum computing related?

  5. matt says:

    If you have a unique ground state, then the Berry phase is just that: a phase. So it can only be measured if you interfere two different parameter paths. I.e., initialize an auxiliary qubit to 0, apply a Hadamard, then conditioned on the value of the qubit apply one of two different parameter paths, then apply another Hadamard, then measure the qubit. Perhaps there are interesting things one do that way, but it certainly wouldn’t have any natural fault tolerance.

  6. […] (Matt Hastings) Adiabatic quantum computation with long paths – quantum futures programming […]

  7. Hey! I know this is kind of off-topic however I needed to ask.
    Does operating a well-established blog such as yours take
    a lot of work? I am brand new to running a blog but I do write in
    my journal daily. I’d like to start a blog so I can easily share my personal experience and views online. Please let me know if you have any ideas or tips for brand new aspiring blog owners. Appreciate it! twitter marketing, more twitter followers
    twitter followers at a discount and also fast, Get Real Followers for your profile.

  8. johnres says:

    You can use Long Path Tool, it works for such issues I will say….

  9. Its not my first time to pay a visit this web page, i am visiting this
    web site dailly and obtain pleasant information from here all the time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: