The physical implementation of quantum annealing algorithm

Question

From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum computers).

Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?

Does anyone have any ideas about that? Please tell me, if you know some links related this question.

Answer 1

From [FT11] (emphasis added):

Quantum annealing (QA) is a classical randomized algorithm ... suggested by the behaviour of quantum systems.

Thus, there is no part of QA that necessarily "depends on quantum hardware."

In classical annealing (CA), a term analogous to temperature is the source of the random perturbations that allow the algorithm to explore a problem's solution space. In QA, the temperature term is replaced by a term analogous to quantum tunneling field strength. Presumably, in a quantum implementation of QA, steps involving quantum tunneling would be carried out directly in hardware.

A comparison of the two techniques can be found here, and D-Wave's explanation here.

EDIT: from D-Wave's Processor operation documentation (emphasis added): Let there be an optimization problem of the form

$E(\vec{s})=-\sum\limits_ih_is_i + \sum\limits_{i,j>i}K_{ij}s_is_j$

where $-1\leq h_i$, $K_{ij} \leq +1$ and $s_i = \pm1$. There exists an optimal solution $\vec{s}_{gs}$ that minimizes the objective $E$. Map the problem onto a quantum Ising spin glass (QSG) Hamiltonian

$\frac{\mathcal{H}_{QSG}(t)}{E_0(t)}=-\sum\limits_ih_i\sigma_z^{(i)}+\sum\limits_{i,j>i}K_{ij}\sigma_z^{(i)}\sigma_z^{(j)}-\Gamma(t)\sum\limits_i\sigma_x^{(i)}$

Use a physical system to find the $|\vec{s_{gs}}\rangle$ by evolving $\Gamma(t)$ such that

$\Gamma(0) \ll h_i,K_{ij}$

$\Gamma(t_f) \gg h_i,K_{ij}$

Answer 2

The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be implemented in any universal model of quantum computation.

In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.

The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.

The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.

The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H_0 + (t/T)H_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H_1$.

It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H_0$ and $H_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.

Answer 3

This is an answer I gave to the question of how adiabatic quantum computing works in layman's terms on Quora. Just to warn you, it's a little simplistic and verbose. Here's the link: https://www.quora.com/Quantum-Computation/How-does-adiabatic-quantum-computation-work-in-laymans-terms/answer/Hadayat-Seddiqi

Adiabatic quantum computing (AQC, henceforth) is a fundamentally different paradigm to the quantum circuit or gate model that most researchers are working on. I will spare the details for the latter and refer you to questions such as the following:

https://www.quora.com/Quantum-Computation/How-does-quantum-computing-work

But I will point out that it's been mathematically shown that the adiabatic model and the gate model are equivalent, so that it is possible to find any equivalent algorithm that can be run on one type of machine for the other, though there is no guarantee on efficiency. That's important to note. Someone may find the adiabatic version of Shor's algorithm, but it's likely that it won't even beat classical computation methods.

In the adiabatic model, you have a few important things that go on, and they are outlined below:

-Encode your problem (in terms of a Boolean SAT problem) -Prepare initial state of qubits (program your problem) -Annealing process (slowly change from initial to final state) -Measure the system to get your answer

Looking at it that way, computing using an AQC seems very simple.

Encoding the problem At first you will need to translate your problem into one that the AQC can handle. In general, this will be in the form of a Boolean satisfiability problem. This will have a specific form in terms of mathematical notation, but the main idea behind it is that you will have an optimization problem that you need to find the minimum or maximum of. There will also be many constraints. Think in terms of a graph. You have a collection of nodes in a grid, and they're all connected at first. This graph is analogous to the "program" in an AQC, where the initial state of qubits are connected in a certain way.

Initial State For any QC, you need an initial state. In classical computing they are bits, in quantum computing they are qubits. I'll refer you again to the broader question of how QC works above to understand how qubits and QC in general work.

In AQC, the qubits have a certain connectivity. For example, if your qubits are the magnetic field direction (either up or down depending on if the current goes clockwise or counterclockwise around, but because of the Josephson junction it will be superposition of the two) through the loop of a superconducting quantum interference device (SQUID), then you have superconducting wires connecting these SQUIDs. These wires can be "turned off" as needed in order to encode the initial problem onto the device.

This is what an rf-SQUID with a Josephson junction looks like:

_{(source: www.quora.com)}

Here is another diagram from D-Wave's blog. The right figure shows the connectivity in their own machine.

Something important to note here is that D-Wave's system is not fully connected, which you can see because nodes 1,2,3, and 4 are not connected to each other. This means that their machine is a subset of a more powerful theoretical AQC, but because of experimental constraints they have gone with the architecture shown.

Annealing Process Now this is where the computation actually happens. I've come up with what I think is a decent analogy, so see if it makes sense to you.

Imagine you put a block of ice in a cup, and you turn up the heat to make it melt. Your goal is to make the ice melt as slowly as possible, so that when you have your cup of water, you have absolutely zero vibrations or waves. You can imagine that by some super-heating method that if the ice cube were to instantaneously turn into water, there would be waves going everywhere since the water would be rushing out to the walls of the cup. What you want to do is heat it slowly so that this never happens, not even in the slightest. Your tolerance is, say, 99%. If your ice cube is an AQC, vibrations in the final state (the water) are "excitations", which basically mean errors and, thus, giving you wrong answers. They may be close, but they wouldn't be optimal.

So you have this system of connected qubits in SQUID form is that you prepare this system with a magnetic field that is going a certain way. You then you slowly turn off your initial state while slowly turning on your final state. So basically you're going through a mixed state of initial and final energy, though by the end there will be basically no initial parts of the problem left in the state and you're left only with the final state. An alternative way is to start with both states on, but have the initial state be much, much stronger than the final part of the state, and then slowly turn off the very large, initial state. If you find this confusing, take a look at this equation

H stands for Hamiltonian, which is just a name for a matrix that defines the total energy state of the system. The three terms, you'll notice, can be grouped into two terms really. The big Z and X are referring to the spin matrices. So in terms of this equation, your initial state is governed by the last term, and your final state is governed by the first two terms. The spin matrices show the change from the X-basis state to the Z-basis state. When you prepare your initial system of qubits, you put them all into the X-spin state and then anneal to the Z-spin state. Imagine that h and J are much, much smaller than K initially. When you anneal, you slowly turn off K so that when you're done, you're only left with whatever is in the first two terms. This is how the annealing process works. You can think of a plot that looks like a symmetric X; one cross of the X is the linearly decreasing K coefficients, and the other cross is the linearly increasing h and J coefficients.

Now in order to anneal properly so that you get the correct answer, you need to be sure you're giving it enough time to settle without excitations. The above equation is time-dependent, or more specifically, the h, J, and K terms are time-dependent. Now the adiabatic theorem will tell you that unless you run for t = infinity, you will not reach 100% accuracy. Still, we can get close. Even 90% isn't so bad, given that you're quickly reaching a somewhat optimal solution.

In terms of the math and quantum mechanics, your state vector always needs to be in the lowest eigenstate of the Hamiltonian. An eigenstate, in linear algebra, would be equivalent to an eigenvector of some matrix. If you're familiar with quantum mechanics, you'll know that particles can only be in discrete energy states. The energy of this system would be the Hamiltonian, which is a matrix, and the lowest energy state is given by the lowest eigenvector of this Hamiltonian. If you wanted to know the actual energy level, that would be the lowest eigenvalue that goes with the aforementioned eigenvector/eigenstate. Now when you're annealing, you always want to be in the ground state. This is why you must move slowly, because if you move too quickly you are imparting energy into the system, causing excitations and jumps to higher energy levels. This is not good because that's where your errors come from.

Final State Once you've gone through the annealing process, you'll wonder a few things. How do I know I've gotten the right answer? How much time should I have given my program to run? Is there a way to do some on-the-fly error correction?

Well, you will have to do tests on your problem to know if you got the right answer. Typically if you're solving an NP-complete problem, you can check if your solution is correct pretty quickly. Still, you will want to run the computation many times until you put that particular algorithm to use in any serious case. There are measures for this as well, however, and they have to do with tracking the actual energy of the Hamiltonian, finding its ground state eigenvector, and then comparing it with what your qubit state actually is. The inner product of the two will show you your error. Note that this can only be done theoretically, as you wouldn't be able to track your quantum state without observing it (and therefore, changing it).

On the fly error correction is also possible in a simulation of an AQC. Let me back up here. There is an idea that you can write some numerical software so that you can simulate the annealing process and come up with a time-scheme for your particular algorithm. Since it's a simulation, you have access to your state vector at all times and you can measure the predicted error according to the mathematics. You can do on-the-fly error correction by looking at the measures of error and correctness, and then adjusting your annealing timesteps accordingly. Take a look at this graph:

This is what is called the eigenspectrum of a 1-qubit simulation. Basically, it is showing you the energies through the annealing time for 1 qubit. Look at the x-axis as time. The bottom curve is the ground state, and the upper curve is the first excited state. Notice how at some point you will get that the two curves are very close. This is a crucial point, because the smaller this energy "gap" is, the more likely it is that the state of the system will jump to this higher energy state instead of stay in the ground state. Clearly this is a time where you want to move very slowly. Conversely, when the energy gap is very large, you can move rather quickly without worrying if you're going to jump to a higher state since it's pretty unlikely. You can come up with a time-scheme that means you go very fast up until that n = 0.5 point, and start to go much more slowly until you've passed the small-gap threshold.

Anyway, so that's basically it. AQC hasn't been around for a long time, so people are still figuring out a lot of things about it, like how to characterize that energy gap and how they're related to your annealing times. It has lots of potential applications, of which I make note of in my answer to the question I linked at the top of this answer.

Answer 4

will take this question as basically "describe/clarify the approach of Dwave systems computers for quantum annealing & QM computation". a basic announcement of their approach in their initial Orion computer can be found in [1] and is apparently also the design used in later iterations.

another way of looking at it is their idea is to find an NP complete problem that is closely related to the natural physical dynamics and energy state evolution of a quantum mechanical qubit system. in this case it is Ising model(s), a mathematical model of ferromagnetism in statistical mechanics. it has been proven theoretically that finding solutions to the Ising model is NP complete (including the 2d version implemented in DWave computers).[2] but note a link apparently with further detail referred in [1] is currently missing on their site.[3]

so then the idea is that any NP complete problem can be converted to the 2-d Ising model problem. but note that conversions between most practical problems would involve many qbits and Dwave's current limit is 128 qbits (Dwave1 "Ranier"). they have announced a 512 qbit version "Vesuvius" that hasnt been released yet. DWave recently announced a sale to Lockheed Martin of the Dwave1 machine and for further development.[4] a detailed scientific paper was released in Nature[5].

[1] Quantum Computing Demo Announcement, 2007 Dr Georde Rose, Dwave systems

[2] The Ising Model Is NP-Complete Barry A. Cipra

[3] "two dimensional Ising model in a magnetic field" currently 404

[4] A Strange Computer Promises Great Speed

[5] Quantum annealing with manufactured spins Johnson et al