Adiabatic Quantum Computation and Simulation December 8 2005 Vlad Goldenberg Maciek Sakrejda 1 Introduction Adiabatic quantum computation came into the spotlight of quantum information processing researchers several years ago The idea suggested an alternative approach to quantum computing which can be shown to be equivalent to the earlier quantum circuit analysis but introduced possible convenience advantages over implementing the circuit model Recently the adiabatic approach to quantum computing has had dramatic up and downturns as a viable way to approach quantum computing along with related controversy regarding the consistency of the adiabatic theorem 1 1 Quantum Adiabatic Theorem The adiabatic theorem of quantum mechanics states that a system in an nth eigenstate evolving under a Hamiltonian will remain in the nth eigenstate throughout the evolution provided the neighborhood energy gaps are small enough and the evolution is carried out slowly enough That is let H 0 be the Hamiltonian of our system in the initial state Associated with this initial initial Hamiltonian are instantaneous eigenstates denoted be an evolving Hamiltonian at time t and it s by n0 i In general let H t eigenstates call n t i such that H t n t i First allow T to be the final time for the Hamiltonian evolution and make the substitution s Tt Then it is possible to design a linearly varying Hamiltonian such that H s H 0 1 s H 1 s so that at timet 0 the Hamiltonian is in the initial state and at time t T the Hamiltonian is in the final state of the system Ali2004 suggests that a 1 stringent critereon for the time evolution of the Hamiltonian are the following min min0 s 1 Ej s Ek s d max max H s ds max T 2 min 1 2 3 These formulas put a minimum value on how long T must be for the final state to be close to the ground state It is possible to design the initial and final Hamiltonians such that the ground eigenstates are the input and desired output of the computation Aharanov2005 points out that if the final Hamiltonian encodes the result of the computation as it s ground state but the ground state determines what Hamiltonian is needed then the output state must be known before the computation is accomplished which beats the point of using the adiabatic model They point out however that nothing need be known about the final output state because it can be shown that as long as the ground state of the final Hamiltonian has a non negligible inner product with the result of the computation it is still possible to perform a quantum computation adiabatically 1 2 Adiabatic vs Circuit Model Ali2004 suggests that it is not necessary to be in the ground state to perform a calculation It is argued that it is sufficient that by properly designing the evolution of the Hamiltonian to have the effect of applying an instantaneous gate a qubit gate can be performed adiabatically with the result of the computation not necessarily being in the ground state of the final Hamiltonian Aharanov2005 showed that any quantum circuit model can be implemented with an adiabatic model with polynomial time and conversely any adiabatic algorithm can be simulated with a quantum circuit model and therefore concluded that the two approaches are equivalent 2 Implementation Various papers have suggested seperate methods for implementing adaibatic quantum computation including Aharanov2005 ground state implementation and the Ali2004 two state system implementation The specific implementation of Ali2004 shall be discussed 2 1 2 state Single Qubit Gate Let us say that we would like to implement the single qubit Hadamard gate using adiabatic computation We know that the transformation is represented 2 by H 1 1 1 1 Therefore the action of H on the computational basis is 1 H 0i 0i 1i 2 1 H 1i 0i 1i 2 Now we can let our initial and final Hamiltonians be the projectors of the basis states and their corresponding outputs with corresponding eigenvalues That is H 0 E 0ih0 E 1ih1 E E H 1 0i 1i h0 h1 0i 1i h0 h1 2 2 If we follow the previous prescription for linear Hamiltonian evolution H s H 0 1 s H 1 s We see that since according to the adiabatic theorem the ground eigenstate should remain in the instantaneous ground state and the first excited state should remain in the instantaneous first excited state the final evolution will be equivalent to the circuit model of the single qubit Hadamard gate 3 Satisfiability Another interesting problem to which we can apply adiabatic quantum computation is the satisfiability question from complexity theory specifically the 3 SAT problem Unfortunately the adiabatic quantum approach has been shown to take exponential time in the worst case as do all known classical algorithms but this is nevertheless an interesting problem to consider in order to illustrate the workings of the adiabatic approach The 3 SAT problem consists of n bits in M clauses of 3 bits each where we can reuse bits across clauses C1 C2 CM Each clause has a satisfying assignment that depends on the value of its three bits and the 3 SAT problem as a whole has a satisfying assignment if and only if all of its clauses are satisfied As all adiabatic quantum problems we approach this one by specifying a time dependent Hamiltonian and an initial state The Hamiltonian takes the form of a linear combination of Hamiltonians each acting on a separate 3 qubit clause and only on the qubits in that clause H t HC1 t HC2 t HCM t 3 As always we define t as slowly varying between zero and T and the initial state as the ground eigenstate of H 0 For each clause the ground state of its corresponding Hamiltonian at time T encodes the satisfying assignments of the clause and therefore the total Hamiltonian H T encodes the solution to the satisfiability problem in its ground state We can define an energy function hC for a clause such that the energy is 0 if the assignment satisfies the clause and 1 otherwise The total energy h is the sum of these terms Thus h is zero if all clauses are satisfied otherwise it is greater than zero We can then use this energy to define the final Hamiltonian Hf as a sum of the individual Hf C terms that act on the qubits in each clause and where each Hf C acts by multiplying the state by its corresponding energy as given by hC We can see that the final Hamiltonian is nonnegative and that it is equal to zero only when operating on a superposition state of qubits that satisfy all constituent clauses We then define the initial Hamiltonian to be the