Quantum Adiabatic Computation

SAT problem is a basic problem of theoretical computer science. It is a typical NP complete problem. Owing to many important practical applications in modern science and technology, military affairs and economic management, for example, mathematical logic, inference , machine learning and VLSI design etc. can be come down to solve NP complete problem. So algorithm and approaches to solve SAT problem play an important role in the development of computing theory and a lot of fields. The environment that this paper compiles on the platform of GNU/Linux based on Libquantum C has realized the quantum adiabatic SAT algorithm. Through selecting a easier Hamiltonian of Ising model, the precision in the quantum adiabatic SAT algorithm is further reinforced. Experiment result shows, in precision aspect, two above-mentioned algorithms are better than QSS ( Quantum System Simulator ). A quantum algorithm for SAT problem was presented in [ 4 ]. This algorithm is based on quantum adiabatic evolution. The Hamiltonian which governs the evolution of the quantum system interpolates smoothly between an initial Hamiltonian whose ground state is easy to construct and a final Hamiltonian whose ground state encodes the desired solution. The evolution of the quantum state proceeds in continuous time according to the Schr?dinger equation, starting in the ground state of the initial Hamiltonian. If the Hamiltonian varies slowly enough, the evolution will closely track the instantaneous ground state and end in a state close to the desired, final ground state. Any problem which can be recast as the minimization of an energy function can potentially be solved in this way. A quantum system with the time-dependent Hamiltonian H(t) evolves according to the Schr?dinger equation | (t)? =H(t)|(t)?dti dψψ(1) Suppose that we wish to evolve from t=0 to t=T, the run time, and that we have a one-parameter family of Hamiltonians H (s) that varies smoothly for 0 ≤s ≤1. We set H (t )= H^t/T so that the run time T governs how slowly H varies. Let H (s)|l,s? =El (s)|l,s? (2) denote the instantaneous eigenstates of H (s) with energy eigenvalues El (s) arranged in non-decreasing order. Assume that E 0 ( s)≠E1(s) for all 0 ≤s ≤1,so that there is always a positive energy gap between the ground and first excited states. Time evolution according to (1), starting in the initial ground state | ψ(0)? =|l=0;s=0?, produces a final state | ψ(T)?. The adiabatic theorem says that in the T →∞, | ψ(T)? is the final ground state | ψ(0)? =|l=0;s=1?. Now imagine that the solution to an interesting computational problem can be characterizing as minimizing a particular energy function. This means we can construct a Hamiltonian H P(the problem Hamiltonian) which is diagonal in the computational basis and whose ground state encodes the solution to the problem. The quantum adiabatic theorem yields an idea for a way to construct this ground state. Suppose we have another Hamiltonian H B(the beginning Hamiltonian) whose ground state is easy toconstruct. If we choose the interpolating Hamiltonian H (s)= (1?s)HB+ sHP (3) so that H (t )= (1?tT)HB+ (tT)HP (4) then evolution from t=0 to t=T starting in the ground state of H B will, in the adiabatic limit, produce the ground state of H P, thus giving the solution to the problem. Let g min= m0≤s i≤n1( E1(s)?E0(s)) (5) and ε= m0≤as ≤x1?l=1;sddH^sl=0;s? (6) then choosing 2T >> gεmin (7) suffices to produce a final state arbitrarily close to the desired ground state. To realize algorithm we must give definition of the problem Hamiltonian H P and then consider constructing problem of initial Hamiltonian H B. We choose Ising type spin Hamiltonian in literature[11] The equation is the form ( α=x) that taken from Ising Model, In which J ij determines the strength of the interaction between the qubit labeled i and j, B i is the external field acting on the i th spin( here B iis regardedas a coefficient acting on i th qubit, B i>0). Since our algorithm is concerned with the operation of single qubit only, we select the first item in equation (8). The simulated experiment result of three problems in [13] shows: For the problem with small scale we compare quantum adiabatic SAT algorithm with QSS (Quantum System Simulator), the precision has obvious raising. Along with the increase of problem scale, the range of its precision raising changes little. The precision of improved algorithm using simplified Hamiltonian is higher than that of the original algorithm. Using equation (3), we evaluate eigenvalues of equation (2) and other relevant data for the second problem. According to the calculation of the energy gap, two algorithms all satisfy E 1 ( s)? E0(s)>0. So we guarantee the correctness of Schr?dinger equation evolution. Secondly quantum transition for the quantum adiabatic SAT algorithm occurs in the point s = 0.8 where the energy gap g min reaches its minimum and εreaches its maximum. The probability of the transition , 1-| ? l =0;s =1|ψ(T)?|2, is small. So we will find solution with higher probability in s=1 (or t=T). Improving quantum adiabatic SAT algorithm in s=0.7 is similar to quantum adiabatic SAT algorithm. Owing to εbased on two above-mentioned algorithms is less than the corresponding largest eigenvalue of dH ds, εis polynomially bounded, so we only have to consider the behavior of g min. Quantum adiabatic computation is a novel paradigm for the design of...