Transcript adiabatic quantum computing

Adiabatic Quantum Computing
Josh Ball with advisor Professor Harsh Mathur
ABSTRACT
Problems which are classically difficult to solve may be
solved much more quickly by quantum computing. A new
strategy for quantum computing, called adiabatic quantum
computing, has been developed to solve a particularly hard
problem called exact cover. Preliminary simulations suggest that
the new quantum algorithm solves the problem much faster than a
classical computer. We have investigated the algorithm and found
small speedups, but could not find a case where the algorithm
would fail. If the adiabatic quantum computing does in fact solve
these problems quickly in all cases then a large class of problems
could be solved quickly using this scheme.
EXACT COVER
In the problem of exact cover we are given n bits (recall that
a bit can either be zero or one) and a number of clauses. The
causes each contain three of the bits and require that a one of the
bits is one and the other two are zero. A solution to exact cover is
a bit assignment which satisfies all of the clauses. With multiple
clauses, the problem quickly becomes complicated.
0/1
0/1
0/1
Instead of linearly interpolating between the initial and final
Hamiltonians, the simulation produces better results when the rate of
change of the interpolation is proportional to the difference between
the lowest two eigenvalues of the current Hamiltonian. The rate of
change should start out fast, and then slow down when the
interpolation is about 70% done, then speed up again at the end.
0/1
CASES WITH NO SOLUTIONS
If the instance had no solution, the algorithm would
produce the next best states, that is, the states which
violated the minimum number of clauses. This is
expected. When you measure the final state, it has to be
something, so even when there is no solution you can
measure the final state and look at the answer. This answer
can be checked on a classical computer. Recall that
finding a solution to exact cover is difficult, while
checking the validity of an answer is easy. If the algorithm
produces an ‘incorrect’ answer multiple times, one can
conclude with increasing certainty, that the instance has no
solutions.
ADIABATIC QUANTUM COMPUTING
The Adiabatic Theorem in Quantum Mechanics states that a
system will stay in the nth eigenstate of the Hamiltonian if the
Hamiltonian is changes slowly enough. Computations can be
preformed by setting up the ground state of the initial Hamiltonian
as the combination of all the possible solution. The ground state of
the final Hamiltonian will be the solution. When the algorithm is
run, the Hamiltonian slowly interpolates from the initial to the final
Hamiltonian. Then we measure the state of the system and retrieve
the answer with high probability.
In the physical implementation of this algorithm, the initial
ground state will be produced by magnetic fields in the x direction
coupled to spins in an n-spin system. For an n spin system the
Hamiltonian is given by a 2n x 2n matrix. The initial Hamiltonian
can be written as a recursive formula which allows any such 2n x 2n
matrix to be built up from σx and the identity matrix.
 Hn
H n1  
 I
I 

Hn 
The final Hamiltonian is a diagonal matrix with elements
corresponding to how many clauses a particular state fails to
satisfy. We want the states which violate the most number of states
to “cost” the most energy. In the USA case there should be a single
diagonal element with value zero. This is the solution state which
satisfies every clause, and is the ground state.
Here is an example of the algorithm’s output for a
instance with no solutions. The plot is probability vs. time.
The most likely states are those which violate the minimum
number of clauses.
(1, 2, 3)
Of the first three bits, one and only one can be
a one, the other two must be zeros.
IMPROVING THE INTERPOLATION
The eigenvalues of the Hamiltonian change as the algorithm
is run and the Hamiltonian interpolates. The important feature to
see on the following graph is the lowest curve, which is the ground
state. Note how this curve does not cross any of the other curves.
This implies that when the algorithm is running, the system is not
likely to “jump” up to another state. This is good, since we want
the system to stay in the ground state.
The graph clearly indicates a better performance for the
improved interpolation. Notice how the effect is maximized for midranged values of T. When T is very big, the probability of finding
the correct answer tends towards 1. When T is near zero, the
probability is near zero; it is equal to that of each of the other states.
NON-USA CASES
The Non-USA cases are those which do not have one
solution. They are the instances of exact cover which may have
multiple solutions or none at all. They were of particular interest,
because we thought the algorithm could fail for some of these
cases. If one case failed, the algorithm would have been shown to
be faulty. In our investigation of over fifty Non-USA cases, we
could not find a single instance where the algorithm failed.
CASES WITH TWO SOLUTIONS
For the Non-USA cases with multiple solutions, the
algorithm will end in a state which is a combination of
these correct states. This result is unexpected for the
instances where there are crossings in the eigenvalues.
The algorithm still works in this case, producing the
correct answers. It should be noted that the algorithm
produces the correct answer with a slightly lower
probability than it does for similar cases without
crossings.