Consideration on Quantum Simulation ofAdaibatic Quantum Computation in SAT Problem
Shigeru Nakayama1 and Ichiro Iimura2121

Graduate School of Science and Enginnering, Kagoshima University, Japan
Dept. of Administration, Faculty of Administration, Prefectural University of Kumamoto, JapanThe continuous diﬀerential equation must be converted
into discrete expression for computer simulation.

Introduction

Adiabatic quantum computation[1] was proposed as aquantum algorithm with adiabatic evolution to solve combinatorial optimization problem. Then it has been applied
to many problems like Deutsch problem and Deutsch·Jozsaproblem[2]. Among them, satisﬁability problem (SAT)
has been tried to be solved by using adiabatic quantum computation[3]. Adiabatic quantum computation has
been actively studied to solve NP-complete problems.
This paper demonstrates the idea of adiabatic computation to solve function optimization problem. Then, thisidea is extended to adiabatic quantum computation tokeep the solution on the ground state in time evolutionof discrete expression of Schrödinger equation. Moreover,the paper shows detailed numerical calculation of the computer simulation in which the adiabatic quantum computation is applied to 1-SAT problem with two literals. Energy
gaps are also discussed in relation to transfer of observation
probabilities. We show quantum simulation of solving asimple SAT problem, modify the adiabatic quantum computation, and propose a method to solve 1-SAT problem
with two literals more eﬃciently with higher observation
probability.

|ψ(t + ∆)⟩ = e−iH∆ |ψ(t)⟩ ,where Plank constant is used as h̄ = 1 for simplicity, and∆ is a diﬀerential time contributing to a phase scaling
parameter on the right hand side of eq. (2).
3.2

Hamiltonian and unitary transform

Adiabatic quantum computation introduces a step parameter s ranging from 0 to 1. Then, the Hamiltonian H
can be written as
H(s) = (1 − s)Hi + sHf ,ψ (h) = e−i(1−s)Hi ∆−isHf ∆ ψ (h−1)

Satisfiability(SAT) Problem

Satisﬁability(SAT) is the problem of ﬁnding the variables for a given Boolean formula written using only AND,OR, NOT, variables(literals), and parentheses(clauses) tobe satisﬁable as TRUE. A litetal is a valuable or the negation. A clause has more than one literal.
The k-SAT problem includes k literals in one clause. Forexample, the formula (x1 ) AND (x2 ) is satisﬁable because
one can ﬁnd the values (x1 ) = true(1) and (x2 ) = true(1),which make (x1 ) AND (x2 ) true(1). According to theCook–Levin theorem, the Boolean satisﬁability problem
with k ≥ 3 is NP-complete.
33.1

Adiabatic Quantum Computation
Discrete expression of Schrödinger equation

SAT problem is to ﬁnd the state vector |ψ(t)⟩ where theeigenvalue (energy) of time-independent Hamiltonian H isminimized by using the adiabatic quantum computation.
Adiabatic quantum computation uses the Schrödingerequation.
ih̄∂ |ψ(t)⟩= H |ψ(t)⟩ .
∂t

(1)

(3)

as a function of step parameter s, where Hi is Hamiltonian of the initial state independent of any problem and
Hf is Hamiltonian of the ﬁnal state depending on a givenproblem. When the step parameter s is gradually changed
from 0 to 1, the Hamiltonian will be changed from theinitial Hamiltonian to ﬁnal Hamiltonian.
⟩Therefore, the state vector ψ (h) gradually changes
with each step by unitary transform as follows;

⟩2(2)

⟩(4)

where an integer parameter h（1 ≤ h ≤ j +1）is calculated
from s = h/(j + 1), j is the number of repetition steps,and U (h) is a unitary transform for adiabatic quantum
evolution written as,
U (h) = e−i(1−s)Hi ∆−isHf ∆ .

(5)

In the case of 1-SAT problem with two literals, the numberof repetition steps is used as j = 4 in our numerical simulation, and ∆ is a phase scaling parameter used as ∆ = 1
required for adiabatic quantum evolution.
(h)
USM = e−i(1−s)Hi has non-diagonal elements and is unitary transform for state mixing between interacting states.
This causes diversiﬁcation of the solutions. On the other(h)hand, UP S = e−isHf has only diagonal elements and isunitary transform for phase shifting where the phase of astate with high cost is shifted very much and that of astate with low cost is not shifted much. This results in
intensiﬁcation for searching solutions.
3.3

Hamiltonian modified by nonlinear step functions

We modify the linear step parameter s to a nonlinear
step function p(s) changing from 0 to 1. Hamiltonian canbe written as
H(s) = (1 − p(s))Hi + p(s)Hf ,Observation probability1(6)where we introduce a nonlinear step function p(s) changing
from 0 to 1. The nonlinear step function must be monotonic to fulﬁll both p(0) = 0 and p(1) = 1. In the case oflinear step function,p(s) = s.

(7)

Although the step function p(s) is originally used as a linear function[1, 2], we propose the nonlinear step function
and did the computer simulation to solve 1-SAT problem.
Here, we propose the cubic step function,

4.1

Hamiltonian of 1-SAT Problem
Initial and final Hamiltonians of 1-SAT problem

We use an example 1-SAT instance with 2 variables and2 clauses of (N OT (x1 )) AN D (N OT (x2 )), which has one
solution, x1 = f alse(0) and x2 = f alse(0). For a given
instance, the cost c(x1 x2 ) of an assignment x1 , x2 is thenumber of clauses it does not satisfy.
In matrix form [3], the initial Hamiltonian Hi is implemented with elementary quantum gates by use of
the Walsh-Hadamard transform with elements Wr.s =2−n/2 (−1)r.s , where H (0) = W DW and D is a diagonal
matrix with the value for state r given by the sum of thebits, i.e, the element Dr,r is just a count for the numberof bits equal to 1 in state r.

( 0Hi = W

000010000100002)W =12(2−1−10−120−1−10
2−10−1−12).

(9)The initial Hamiltonian Hi is independent of any SAT
problem. This Hamiltonian makes a state mixing factor
in the amplitude of each state, then it results in the diversiﬁcation of solution candiates.
The ﬁnal Hamiltonian Hf is a diagonal matrix depending on the SAT problem instance. In the 1-SAT problemof (N OT x1 ) AN D (N OT x2 ), each diagonal element has
each cost c(x1 x2 ) such as c(00) = 0, c(01) = 1, c(10) = 1,and c(11) = 2. Therefore, the ﬁnal Hamiltonian Hf isgiven by
0 0 0 0
 0 1 0 0 Hf = .
(10)
0 0 1 0 0 0 0 2This Hamiltonian introduces a phase shift factor in theamplitude of assignment i depending on its associated costc(i), where the higher cost results in more phase shift.
4.2

Quantum Adiabatic Evolution in 1-SAT problem

According to Hogg[3], the initial superposition statewith all equal probability amplitudes,
ψ⟩(0)=Cubic

0.7
0.6
0.5
0.4

Linear0.301 , 10

0.2
0.1

1100.2(8)and compare the linear step function with the cubic stepfunction.

1(|00⟩ + |01⟩ + |10⟩ + |11⟩),
2(11)

00

0.8

0p(s) = 4(s − 1/2)3 + 1/2,40.9

0.4

0.6

0.8

1sFig. 1. Observation probabilities of four state vectors as aparameter of step parameter s in the linear and cubic stepfunctions.
is also used in 1-SAT problem with 2 literals.
Therefore, we should make the observation probabilityof the state vector |00⟩ as high as possible⟩ from 25% in theinitial state |ψ0 ⟩. The initial state ψ (0) with equal superposition state is evolved by applying the unitary transformas follows:⟩⟩ψ (h) = e−i(1−p(s))Hi ∆−ip(s)Hf ∆ ψ (h−1) ,(12)where an integer parameter h（1 ≤ h ≤ j +1）is calculated
from s = h/(j + 1). Here, the repetition number j = 4 isused in our numerical simulation and ∆ is a phase scaling
parameter required for time evolution used as ∆ = 1.
In adiabatic quantum computation, the observation
probability of each state vector at each step can be calculated from taking the square of the absolute value of theprobability amplitude. At the last step s = 1(h = 5), theobservation probability of the |00⟩ state is 91.76% as shownin Fig. 1. On the other hand, we could not increase the observation probability in the linear step function p(s) = s.
We get the ﬁnal observation probability 69.54% of ﬁnding
the solution as shown in Fig. 1.
5Conclusion

In this paper, we proposed the nonlinear cubic step function p(s) = 4(s − 0.5)3 + 0.5 instead of the linear step
function p(s) = s in the adiabatic quantum computation
to eﬀectively solve 1-SAT problem. We could obtain thehigher observation probability of ﬁnding the solution byusing the nonlinear cubic step function.
References[1] E.Farhi, J.Goldstone, S.Gutmann, and M.Sipser, Quantum Computation by Adiabatic Evolution, quantph/0001106, 2000
[2] S.Das, R.Kobes, and G.Kunstter, Adiabatic Quantum Computation and Deutsch’s Algorithm, quantph/0111032, 2001.
[3] T. Hogg, Adiabatic Quantum Computing for Random Satisfiability Problems, quant-ph/0206059, 2002.