MIT-CTP/4789

A Q UANTUM V ERSION OF S CH ÖNING ’ S A LGORITHM A PPLIED
TO Q UANTUM 2-SAT
Edward Farhi,1 Shelby Kimmel,1, 2 and Kristan Temme1, 3, 4

arXiv:1603.06985v1 [quant-ph] 22 Mar 2016

1 Center

for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2 Joint Center for Quantum Information and Computer Science (QuICS),
University of Maryland, College Park, MD 20742, USA
3 Institute for Quantum Information and Matter,
California Institute of Technology, Pasadena CA 91125, USA
4 IBM TJ Watson Research Center, Yorktown Heights, NY 10598, USA
(Dated: March 24, 2016)

We study a quantum algorithm that consists of a simple quantum Markov process, and we
analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm
solves this decision problem with high probability for n qubits, L clauses, and promise gap c
in time O(n2 L2 c−2 ). If the Hamiltonian is additionally polynomially gapped, our algorithm
efficiently produces a state that has high overlap with the satisfying subspace. The Markov
process we study is a quantum analogue of Schöning’s probabilistic algorithm for k-SAT.

I.

INTRODUCTION

For the n-bit classical constraint satisfaction problem k-SAT, several algorithms beat the exhaustive search runtime bound of 2n . They provide a runtime with a mildly exponential scaling,
O(r n ) with r < 2. One such algorithm is Schöning’s probabilistic algorithm that finds a solution
of 3-SAT in time O(1.334n) [1]. The algorithm works by exploring the solution space using a
simple Markov process. Although variants of the algorithm had been known for some time [2, 3],
Schöning was the first to prove the runtime bound for k ≥ 3. For 2-SAT, Papadimitriou earlier
introduced a variant of this algorithm that finds a satisfying assignment (if there is one) in time
O(n2 ) [3]. While linear-time 2-SAT algorithms exist [4, 5], Papidimitriou’s algorithm is admired
for its simplicity.
Quantum k-SAT is the quantum generalization of the classical k-SAT problem. Analogously
to classical k-SAT, Quantum 3-SAT is QMA1 -complete [6], while Quantum 2-SAT can be solved
in polynomial time [7]. Interestingly, existing algorithms for Quantum 2-SAT have paralleled algorithms for classical 2-SAT: Bravyi’s original algorithm for Quantum 2-SAT is similar to Krom’s
algorithm for classical 2-SAT [8] and uses inference rules; and two recent linear-time algorithms
for Quantum 2-SAT [9, 10] use ideas from linear-time classical 2-SAT algorithms [4, 5].
In this work, we describe an algorithm that is a quantum analogue of Papidimitriou’s classical
algorithm and analyze its behavior on restricted versions of Quantum 2-SAT. Like the classical
algorithm, our quantum version consists of repeated applications of a simple (quantum) Markov
process. As with the recent linear-time Quantum 2-SAT algorithms, we apply tools and intuition
from the classical algorithm to analyze the quantum version. However, our algorithm is a quantum
algorithm; past algorithms for Quantum 2-SAT have been classical. Since Schöning showed that
the classical version of this algorithm performs well for classical k-SAT with k > 2, there is hope
that the quantum version will have success on Quantum k-SAT with k > 2. Therefore, we think
understanding this quantum Markov process in the case of k = 2 is of value.
Papidimitriou’s classical algorithm for 2-SAT takes as input the number of bits n, a set of
1

2
clauses I, and a real parameter b > 0, where b is chosen depending on the desired probability of
success. Then the algorithm is as follows:
Classical Algorithm(n, I, b)
• Pick a string s uniformly at random from {0, 1}n .
• Repeat bn2 times:
– If there exist clauses in I that are not satisfied on s, randomly choose one of the
unsatisfied clauses, and then randomly choose one of the bits in that clause. Flip the
value of that bit and rename s to be the new string with the flipped bit.
– If s satisfies all clauses, return s and terminate.
• If s does not satisfy all clauses, return “No satisfying string found.”
If there is no satisfying assignment, the algorithm will always return “No satisfying string found.”
If a satisfying string exists, this algorithm will return a satisfying assignment with probability p,
where (1 − p) ∝ b−1 .
The quantum algorithm that we consider is the natural generalization of this procedure to the
quantum domain for the problem Quantum k-SAT, which is the natural generalization of Classical
k-SAT to the quantum domain. We now give the definition of Quantum k-SAT on n qubits as it
was introduced by Bravyi (altered to include only rank-1 projectors) [7]:
Definition [Quantum k-SAT] Let c = Ω(n−g ) with g a positive constant. Given a set of L rank
one projectors (called “clauses”) Φα = |φα ihφα | each supported on k out of n qubits, define
H=

L
X

Φα .

(1)

α=1

One must decide between the following two cases:
1. The YES instance: There exists an n-qubit state ρ that satisfies tr[H ρ] = 0.
2. The NO instance: For any n-qubit state ρ, we have that tr[H ρ] ≥ c.
We now give a quantum algorithm for Quantum k-SAT on n qubits, but in this paper we focus
on k = 2. The quantum algorithm takes as input the number of qubits n, a set of L clauses
I = {Φα }, and two positive integers N and T , where N ≤ T . N and T are chosen based on
the desired probability of success. The clauses can be given either via a classical description, or
operationally, as measurement projectors. Then the algorithm is as follows:
Quantum Algorithm(n, I, N, T )
• Initialize the system in the maximally mixed state of n qubits.
• Initialize a counter N0 to equal 0.
• Repeat T times:

3
– Choose α uniformly at random from {1, . . . , L}, and measure Φα . If outcome 1 is
measured, choose one of the qubits in the support of Φα at random and apply a Haar
random unitary to that qubit. If outcome 0 is measured, set N0 = N0 + 1.
• If N0 ≥ N decide you are in a YES instance. Otherwise, decide NO.
One might expect that an algorithm for Quantum k-SAT first prepares a low energy state, and
then estimates the energy of the state using, for example, phase estimation. In our work we use
the repeated measurements of clauses to fulfill both roles. We prepare the low energy state by
repeatedly measuring clauses and applying random unitaries if the clauses are unsatisfied. We test
whether the state has low energy by tracking the number of satisfied outcomes. We will show that
if, over repeated measurements, most of the outcomes are satisfied, then we have a low energy
state.
Variants of this algorithm have been analyzed previously in different contexts. A similar algorithm was proposed to prepare graph states and Matrix Product States dissipatively [11], and a
variant was used as a tool for the constructive proof of a quantum local Lovász lemma for commuting projectors [12, 13].
Given a YES instance of Quantum 2-SAT, since Quantum 2-SAT is in P , one might expect that
the Quantum Algorithm will converge to a satisfying state in polynomial time. We show that this is
indeed the case, at least for a restricted set of clauses. Chen et al. [14] showed that for every YES
instance of Quantum 2-SAT, there is always a satisfying assignment that is a product of single- and
two-qubit states. In fact, with the restricted clause set that we consider, there will be a satisfying
single-qubit product state of the form:
|ψ1 i1 ⊗ · · · ⊗ |ψn in

(2)

where the ket |·ii denotes the state of the ith qubit. For ease of notation, for YES instances, we use
the following basis:
|0ii = |ψi ii .

(3)

Hence, for the rest of this paper, |0i⊗n does not refer to the standard basis state, but to an unknown
product state that satisfies all clauses of a Quantum 2-SAT instance. In the basis where |0i⊗n is a
satisfying state, all of the clauses are of the form
General Clauses:
Φα = |φα ihφα | , with |φα i = aα |01ii,j + bα |10ii,j + cα |11ii,j ,

(4)

where i, j label the two qubits in the clause Φα . For reasons that we will discuss later, we can
only prove that the Quantum Algorithm succeeds in polynomial time if in the YES instance the
clauses are restricted to have cα = 0. In the NO case, the clauses have no restrictions. We call this
problem Restricted Quantum 2-SAT, and we show that the Quantum Algorithm can succeed in
this setting when T = O(L4 n2 /c2 ). This restriction can be somewhat relaxed, and in Appendix A,
we show that the algorithm succeeds in polynomial time if in the YES instance every clause
satisfies either cα = 0 or aα = bα = 0. So for now we work with
Restricted Clauses:
Φα = |φα ihφα | , with |φα i = aα |01ii,j + bα |10ii,j .

(5)

4
Note that |0i⊗n and |1i⊗n are both satisfying states with the restricted clause set.
In addition to solving Restricted Quantum 2-SAT, in the YES case the Quantum Algorithm
produces a state that has high overlap with a satisfying assignment. In this setting, the smallest
eigenvalue of H is 0, and we call ǫ the size of the smallest non-zero eigenvalue of H. We show
that after running the Quantum Algorithm for T = O(n2 L/ǫ) steps, the resultant state will have
large overlap with a state ρ that has tr[H ρ] = 0.
The Quantum Algorithm may solve arbitrary Quantum 2-SAT instances in polynomial time,
but our analysis can only show that it succeeds in polynomial time on Restricted Quantum 2SAT. On the other hand, Bravyi’s algorithm and recent linear-time quantum algorithms [9, 10]
give procedures for deciding all Quantum 2-SAT instances in polynomial time, but are classical
algorithms. Our algorithm is a quantum algorithm, so our analysis techniques may be of broader
interest. In particular, our approach may have applications to Quantum k-SAT for k > 2.
II.

ANALYSIS OF THE QUANTUM ALGORITHM FOR RESTRICTED QUANTUM 2-SAT

On a YES instance, the Quantum Algorithm can be viewed as a quantum Markov process that
converges to a quantum state that is annihilated by all the clauses. A quantum Markov process
is described by a completely positive trace preserving (CPTP) map [15]. Call ρt the state of
the system at time t. The CPTP map T describes the update of ρt at each step of the chain, so
ρt+1 = T (ρt ).
Call Tα the map that describes the procedure of checking whether clause Φα is satisfied, and if
it is not satisfied, applying a random unitary to one of the qubits in the support of Φα . Let i and j
be the two qubits associated with clause Φα . Then
1
2

1
2

Tα (ρ) = (1−Φα ) ρ (1−Φα ) + Λi (Φα ρΦα ) + Λj (Φα ρΦα )
where Λi is the unitary twirl map acting on qubit i:
Z
1i
Λi (ρ) = d[Ui ]Ui ρUi† =
⊗ tri [ρ] ,
2

(6)

(7)

and d[Ui ] is the Haar measure. At each time step, we choose α from {1, . . . , L} uniformly and
random and apply the map Tα . This corresponds to the CPTP update map
L

T (ρ ) =

1X
Tα (ρ).
L α=1

(8)

During the measurement step, when α is chosen uniformly at random and one measures Φα ,
the probability of obtaining outcome 1 at time t is
1X
1
tr[Φα ρt ] = tr[Hρt ].
(9)
L α
L
A. Expectation of Total Spin

In analyzing the classical algorithm, Papadimitriou and Schöning kept track of the Hamming
distance between the current string and the satisfying assignment. Inspired by this idea, we find it
useful to analyze the expectation value of Ŝ and Ŝ 2 , where Ŝ is twice the total spin:

5

Ŝ =

n
X

σ

z
i

2

Ŝ =

and

i=1

n
X

σ zi σ zj .

(10)

i,j=1

P
Note that Ŝ is closely related to the quantum Hamming weight operator ni=1 21 (1 − σ zi ).
We show that with the restricted clause set, the expectation value of Ŝ is constant under the
action of T , whereas the expectation value of Ŝ 2 can not decrease under the action of T .
Lemma 1 Given a set of restricted clauses {Φ1 , . . . , ΦL } (i.e. all of the form of Eq. (5)), with T
defined as in Eq. (8), then
tr[ŜT (ρ)] − tr[Ŝ ρ] = 0
2X
tr[Ŝ 2 T (ρ)] − tr[Ŝ 2 ρ] =
tr[Φα ρ] ≥ 0.
L α

(11)
(12)

P ROOF : Let T † be the dual of T , so that
tr[ŜT (ρ)] = tr[T † (Ŝ)ρ]

and

tr[Ŝ 2 T (ρ)] = tr[T † (Ŝ 2 )ρ].

(13)

1
2

(14)

First consider
1
2

Tα† (Ŝ) = (1−Φα )Ŝ(1−Φα ) + Φα Λi (Ŝ)Φα + Φα Λj (Ŝ)Φα ,

where i, j are the two qubits where Φα acts. Note that Ŝ − σ zi − σ zj is invariant under the action
of Tα† , so
Tα† (Ŝ) =Ŝ − σ zi − σ zj + (1−Φα ) (σ zi + σ zj ) (1−Φα )
1
2

1
2

+ Φα Λi (σ zi + σ zj )Φα + Φα Λj (σ zi + σ zj )Φα .

(15)

Due to the special properties of the restricted clauses, c.f. Eq. (5), we have
Φα (σ zi + σ zj ) = (σ zi + σ zj )Φα = 0,

(16)

for all α, which together with Λi (σ zi ) = 0 and Λi (σ zj ) = σ zj for i 6= j gives
Tα† (Ŝ) = Ŝ.

(17)

T † (Ŝ) = Ŝ,

(18)

This implies

so we see that the expectation value of Ŝ is unchanged by the action of T on a state:
tr[ŜT (ρ)] = tr[Ŝ ρ].

(19)

6
The expectation value of Ŝ 2 does change under the action of T . Φα acts only on qubits i and j,
so accordingly we break up Ŝ 2 as


X
2
z
z
2
z z
z
Ŝ = Ŝ − 2σ i σ j − 2
σ k (σ i + σ j )
k6=i,j



+ 2σ σ + 2
z
i

z
j

X

σ σ +σ
z
k(

z
i

k6=i,j

z
j)



.

(20)

Tα† leaves the first term unchanged. Now
1
2

1
2

Tα† (σ zi σ zj ) = (1−Φα )σ zi σ zj (1−Φα ) + Φα Λi (σ zi σ zj )Φα + Φα Λj (σ zi σ zj )Φα .

(21)

Because of the special properties of the clauses, c.f. Eq. (5), we have
Φα σ zi σ zj = σ zi σ zj Φα = −Φα .

(22)

Using Eq. (16) and that Λi (σ zi ) = 0, we have
Tα† (σ zi σ zj ) = σ zi σ zj + Φα .

(23)

Now notice
Tα† (σ zk (σ zi + σ zj )) =(1−Φα )σ zk (σ zi + σ zj )(1−Φα )
1
2
1
+ Φα Λj (σ zk (σ zi + σ zj ))Φα
2

+ Φα Λi (σ zk (σ zi + σ zj ))Φα

=σ zk (σ zi + σ zj ).

(24)

where we have again used Eq. (16). Putting the pieces together gives
Tα† (Ŝ 2 ) = Ŝ 2 + 2Φα .

(25)

The change in the expectation value of Ŝ 2 after the action of T is thus
tr[Ŝ 2 T (ρ)] − tr[Ŝ 2 ρ] =

2X
tr[Φα ρ] ≥ 0.
L α

(26)


B. Runtime of the Quantum Algorithm to Decide Restricted Quantum 2-SAT

The Quantum Algorithm decides between YES and NO cases based on the number of 0-valued
outcomes, i.e. satisfied projectors, obtained during the algorithm. The probability of getting a
0-outcome at step t is
1−

1
tr[H ρt ],
L

(27)

7
and so depends on the expectation value of H. Eq. (26) allows us to relate the expectation value of
H to the expectation value of Ŝ 2 . While the expectation value of H is not necessarily monotonic
over the course of the algorithm, the expectation value of Ŝ 2 is monotonic (by Lemma 1) and is
also bounded, since the maximum eigenvalue of Ŝ 2 on n qubits is n2 . We use these properties of
Ŝ 2 to track the expectation value of H over the course of the algorithm, and hence to track the
expected number of 0-valued outcomes.
We analyze the YES and NO cases seperately.
Result 1 Suppose we have a YES case of Restricted Quantum 2-SAT, and we run the Quantum
Algorithm for time
T =

f 2 L2 n2
,
2

(28)

where
f = max




7
,1 ,
c

(29)

then we have at least a 2/3 probability of observing at least N measurement outcomes with value
0 over the course of the algorithm, where
3

fL − 1
N =T
− f Ln.
(30)
fL

The choice of f = max 7c , 1 is not used in this proof, but is rather important for the soundness
analysis. We include it here for concreteness.
P ROOF : We start by using Lemma 1 to bound the expectation value of H over the course of the
algorithm. 0 ≤ tr[Ŝ 2 ρ] ≤ n2 for any state ρ on n qubits and so for any T
n2 ≥ tr[Ŝ 2 ρT ] − tr[Ŝ 2 ρ0 ]
T −1 

X
=
tr[Ŝ 2 ρt+1 ] − tr[Ŝ 2 ρt ]
=
=

t=0
T −1 X
X

2
L
2
L

tr[Φα ρt ]

t=0 α
T
−1
X

tr[H ρt ].

(31)

t=0

Let Πf be the projector onto the eigenstates of H with eigenvalue less than 1/f . We define

pt,f = tr[Πf ρt ].

(32)

Inserting the projector I − Πf into the last line of Eq. (31), we have
T −1

2X
n ≥
tr[H(I − Πf )ρt ]
L t=0
2

T −1

2 X
(1 − pt,f )
≥
f L t=0

(33)

8
where we used that ρt has probability 1 − pt,f of being in the subspace I − Πf , and states in this
subspace have expectation value of H at least 1/f . Rearranging terms gives
T −1
X

f Ln2
,
2

(34)

fL − 1
T.
fL

(35)

pt,f ≥ T −

t=0

and using Eq. (28) gives
T −1
X
t=0

pt,f ≥

By the pigeon hole principle, there is a set of times T such that the following are true:
fL − 1
for t ∈ T, and
fL
fL − 1
T.
|T| ≥
fL

pt,f ≥

(36)
(37)

At any time t, the probability of obtaining outcome 0 is
L

1X
1
1−
tr[Φα ρt ] = 1 − tr[H((I − Πf ) + Πf )ρt ].
L α=1
L

(38)

Since H is a sum of L projectors, its eigenvalues are at most L, so we have
tr[H(I − Πf )ρt ] ≤ L(1 − pt,f ).

(39)

Πf projects onto states with eigenvalue less than 1/f , so
tr[HΠf ρt ] <

1
p .
f t,f

(40)

Plugging these in gives
L

fL − 1
1X
tr[Φα ρt ] ≥
pt,f .
1−
L α=1
fL

(41)

Now assume t ∈ T, so Eq. (36) holds. Then we have for these times that the probability of
obtaining outcome 0 is
L

1X
1−
tr[Φα ρt ] ≥
L α=1



fL − 1
fL

2

(42)

Since we want a large number of 0-outcomes over the course of the algorithm, we will assume
a worst case scenario such that the probability of outcome 0 for all times t ∈ T is
2

fL − 1
.
(43)
pworst =
fL

9
In this case, the distribution of 0-outcomes for times t ∈ T is given by a binomial distribution.
We can use bounds on the binomial cumulative distribution function to bound the number of 0outcomes in this worst case scenario. Let G be the probability that less than N outcomes are 0 over
|T| times, where pworst is the probability of obtaining outcome 0 at any time. Using Hoeffding’s
bound, we have that


−2(|T|pworst − N)2
G ≤ exp
,
(44)
|T|
as long as |T|pworst ≥ N. Using Eq. (37) and Eq. (43), we have

3
fL − 1
|T|pworst ≥
T.
fL

(45)

Using Eq. (30), we see that
|T|pworst − N ≥ f Ln,

(46)

so the numerator of the exponent in Eq. (44) satisfies
2(|T|pworst − N)2 ≥ 2f 2 L2 n2 .

(47)

Finally, the denominator of the exponent in Eq. (44) satisfies
T≤T
f 2 L2 n2
=
,
2

(48)

so we have
G ≤ exp [−4] ≤ 1/3.

(49)

Thus with probability at least 2/3, we expect to see at least N outcomes with value 0 for times
t ∈ T. Considering times t with 1 ≤ t ≤ T rather than only times t ∈ T only gives more
opportunities for 0-outcomes, so we have probability of at least 2/3 of seeing N outcomes with
value 0 when the algorithm is run for time T .

Now we prove an analogous result in the NO case:
Result 2 Recall that in the NO case, the size of the smallest eigenvalue of H is promised to be c.
If we run the algorithm for time
T =

f 2 L2 n2
,
2

(50)

and choose
f = max




7
,1 ,
c

(51)

then we have at most a 1/3 probability of observing more than N measurement outcomes with
value 0 over the course of the algorithm, where, as in Result 1,

3
fL − 1
N =T
− f Ln.
(52)
fL

10
P ROOF : We show that if we have a NO case, we are unlikely to have more than N measurements
with outcome 0 over the course of the T applications of T . In the NO case, the probability of
obtaining outcome 0 at time t is
L

1−

1X
c
tr[Φα ρt ] ≤ 1 − .
L α=1
L

(53)

The worst case is when for all times t, the probability of obtaining outcome 0 is
c
L

q worst = 1 − .

(54)

This worst case scenario corresponds to a binomial distribution. We use bounds on the binomial
distribution to bound the probability of at least N outcomes with value 0. Let G be the probability of getting at least N outcomes with value 0 over T steps, where q worst is the probability of
obtaining outcome 0 at any step. Applying Hoeffding’s bound to the binomial distribution, we
have


−2(N − T q worst )2
G ≤ exp
(55)
T
as long as N ≥ T q worst . We now show that G is small.
We first analyze the term N − T q worst from Eq. (55). We have, using Eq. (52),
3


c
fL − 1
.
− f Ln − T 1 −
N − T q worst = T
fL
L

(56)

Since f L ≥ 1, we have
N − T q worst




c
3
− f Ln − T 1 −
≥T 1−
fL
L
1
3
= cf 2 Ln2 − f Ln2 − f Ln
2
2 

5
cf
−
≥ f Ln2
2
2

(57)

where in the second to last line we used Eq. (50), and in the last line we used that n ≥ 1. Setting
f = max{7/c, 1}, we have
N − T q worst ≥ f Ln2 ,

(58)

where the maximum over the two terms is used to ensure f ≥ 1. Then the numerator in Eq. (55)
satisfies
2(N − T q worst )2 ≥ 4T n2 .

(59)

G ≤ exp[−4n2 ] ≤ 1/3.

(60)

Plugging into Eq. (55) we have

Therefore, the probability of getting at least N outcomes with value 0 is less than 1/3.



11
Combining Result 1 and Result 2, to solve Restricted Quantum 2-SAT, we set


7
f = max
,1
c

(61)

and run the algorithm for time
T =

f 2 L2 n2
.
2

(62)

We count the number of 0-outcomes over the course of the algorithm, and check whether this is
greater than
N =T



fL − 1
fL

3

− f Ln.

(63)

We have shown that for a YES instance, there is at least a 2/3 probability of observing at least N
outcomes with value 0, but for a NO instance, there is at most a 1/3 probability of doing so.
C. Runtime to Produce a Ground State

Suppose we have a Hamiltonian with restricted clauses that is additionally polynomially gapped. In other words, the smallest non-zero eigenvalue of the Hamiltonian has size
Ω(1/poly(n)). Then we show that repeatedly applying the map T produces a state that has large
overlap with the ground subspace.
Result 3 Given clauses {Φα } where Φα = |φα ihφα | are restricted as in Eq. (5), and ǫ is the size
P
n2 L
of the smallest non-zero eigenvalue of H = α Φα , then for T ≥ 2(1−p)ǫ
, ρT = T T (ρ0 ) has a
fidelity tr[Π0 ρT ] with the ground state subspace that is greater than p.
P ROOF B Y C ONTRADICTION:
Let Π0 be the projector onto the satisfying subspace:
tr[HΠ0 ] = 0.

(64)

We first show that Π0 is a fixed point of the map T , so once part of the state is in this subspace, it
stays there. That is,
tr[Π0 ρt+1 ] − tr[Π0 ρt ] =

1X h
tr Π0 (1−Φα ) ρt (1−Φα )
L α

i
+ 12 Π0 Λi (Φα ρt Φα ) + 21 Π0 Λj (Φα ρt Φα ) − tr[Π0 ρt ]
1 X
tr[Π0 (Λi (Φα ρt Φα ) + Λj (Φα ρt Φα ))]
=
2L α

≥0,

since tr[Πρ] ≥ 0 for any projector Π and any state ρ.

(65)

12
Suppose tr[Π0 ρT ] < p. From Eq. (65), tr[Π0 ρt ] can not decrease with increasing t. So for all
t ≤ T,
tr[Π0 ρt ] < p

(66)

tr[(I − Π0 )ρt ] > 1 − p.

(67)

or equivalently,

Given that the spectral gap of H is ǫ, we have
tr[H ρt ] > ǫtr[(I − Π0 )ρt ].

(68)

tr[H ρt ] > ǫ(1 − p)

(69)

Combining Eqs. (67–68) gives

for all t ≤ T .
Copying Eq. (31), we have
T −1
X
2
n ≥
tr[H ρt ].
L
t=0
2

(70)

Using Eq. (69), we have
n2 >
Setting T ≥


n2 L
2(1−p)ǫ

(1 − p)2ǫT
.
L

gives a contradiction. Therefore, for T ≥

(71)
n2 L
,
2(1−p)ǫ

we must have tr[Π0 ρT ] ≥ p.

D. Difficulties with General Clauses

We have only been able to prove the Quantum Algorithm solves Quantum 2-SAT in polynomial
time when we restrict the form of the clauses. In this section, we describe what breaks down
when more general clauses are included in the instance. In this section, we assume that for YES
instances, the solution is a product of single-qubit states. (The instance can be easily pre-processed
to deal with any two-qubit product states in the solution, as in [9].) In the YES case, we consider
a basis in which the satisfying assignment takes the form |0i⊗n , so in this basis clauses are of the
form:
General Clauses:
Φα = |φα ihφα | , with |φα i = aα |01ii,j + bα |10ii,j + cα |11ii,j ,

(72)

The restricted clauses never cause the expectation of Ŝ 2 to decrease. However, when we include
General Clauses the expectation of Ŝ 2 can either increase or decrease under the action of Tα ,
depending on the state of the system.

13
Consider a clause of the form Φα = |φα ihφα | with |φα i = |+1i1,2 acting on the state ρ =
|011ih011|1,2,3 . (Here |+i is the eigenvector of the σ x operator with eigenvalue 1.) One can easily
check that
tr[Ŝ 2 ρ] = 5,

tr[Ŝ 2 Tα (ρ)] = 4.5,

(73)

so the expectation value of Ŝ 2 decreases.
When there are sufficiently many General Clauses, but still with a planted product state solution, |0i⊗n is the only satisfying state, so one might guess that a good tracking measure would be
the expectation value of Ŝ, which if it always increases, would bring the system closer and closer
to |0i⊗n . However, for General Clauses, Ŝ can also increase or decrease, and in fact for ρ and Φα
as above,
tr[Ŝ ρ] = 2,

tr[ŜTα (ρ)] = 1.75.

(74)

While in principle the expectation value Ŝ and Ŝ 2 under the action of T can increase or decrease, in numerical experiments, we find that they always increase.
The analysis in Section II was simple because the changes in expectation value of Ŝ and Ŝ 2
did not depend on the details of the state of the system, but rather only on the overlap of the state
with the satisfying subspace. With general clauses, the changes in expectation value of Ŝ and Ŝ 2
depend on the specifics of the state of the system, making these operators less useful as tracking
devices.
III.

CONCLUSIONS

We study a quantum generalization of Schöning’s algorithm. We show this quantum algorithm
can be used to solve Quantum SAT problems. In particular, we show that it can solve, in polynomial time, Quantum 2-SAT with certain restrictions on the clauses. It is possible that this quantum
algorithm succeeds in polynomial time for Quantum 2-SAT without any restriction on the clauses,
but we were not able to show it. Inspired by the classical analysis, we track quantities like the total
spin rather than energy. Furthermore, if the Hamiltonian is also polynomially gapped, the algorithm will produce, in polynomial time, a state that has high overlap with a satisfying assignment.
There are many open questions related to this work. Is there a way to extend our analysis to
unrestricted Quantum 2-SAT? How does the algorithm perform on Quantum k-SAT for k > 2?
Can the runtime bounds of our algorithm can be improved?
IV. ACKNOWLEDGMENTS

We thank Sevag Gharibian for helpful discussions. EF was funded by NSF grant CCF1218176 and ARO contract W911NF-12-1-0486. SK acknowledges support from the Department
of Physics at MIT, iQuISE Igert grant contract number DGE-0801525, and the Department of
Defense. KT acknowledges the support from the Erwin Schrödinger fellowship, Austrian Science
Fund (FWF): J 3219-N16 and funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NFS Grants PHY-1125565 and PHY-0803371) with support
of the Gordon and Betty Moore Foundation (GBMF-12500028).

14
Appendix A: Analysis with an Extended Clause Set

In Section II, we showed that the Quantum Algorithm can decide Quantum 2-SAT if (in the
YES case) the clauses are of a certain form, which we now call Type I Clauses:
Type I Clauses:
Φα = |φα ihφα | , with |φα i = aα |01ii,j + bα |10ii,j .

(A1)

In this appendix, we will show that the Quantum Algorithm almost matches the performance
demonstrated in the main body of this paper, when the restricted clause set is enlarged to include
both Type I and Type II clauses:
Type II Clauses:
Φα = |φα ihφα | , with |φα i = |11ii,j .

(A2)

When all clauses are Type I or Type II, |0i⊗n is a satisfying state.
In Section II we showed that for Φα a Type I clause,
tr[ŜTα (ρ)] − tr[Ŝ ρ] = 0,

(A3)

tr[Ŝ 2 Tα (ρ)] − tr[Ŝ 2 ρ] = 2tr[Φα ρ].

(A4)

We observe that Type II clauses exhibit the following properties:
Φα (σ zi + σ zj ) = (σ zi + σ zj )Φα = −2Φα ,

Φα σ zi σ zj = σ zi σ zj Φα = Φα .

(A5)

Applying Eq. (A5) to Eq. (15) and to the analysis in Eqs. (20–24), we have that for Type II clauses
Tα† (Ŝ) = Ŝ + Φα ,
Tα† (Ŝ 2 ) = Ŝ 2 − 2Φα + 2

(A6)
X

σ zk Φα .

(A7)

k6=i,j

Combining the effects of Type I and Type II clauses, we have
1 X
Φα ,
L α∈Type II

X
2 X
2 X 
†
2
2
z
T (Ŝ ) = Ŝ +
Φα +
−Φα +
σk Φα .
L α∈Type I
L α∈Type II
k6=i,j
T † (Ŝ) = Ŝ +

(A8)
(A9)

When only Type I clauses were present, the expectation of Ŝ 2 could only increase, but now Type
II clauses can cause Ŝ 2 to decrease. However, whenever ρt is not annihilated by all of the clauses,
either the expectation value of Ŝ increases (if a Type II clause is measured), or the expectation
value of Ŝ 2 increases (if a Type I clause is measured). We show that in combination, these effects
allow us to prove the following result.
Result 4 Given clauses {Φα }, where Φα are Type I or Type II,
T −1

2X
5n ≥
tr[H ρt ].
L t=0
2

(A10)

15
We first discuss the consequences of Result 4, and then give the proof. Note that Eq. (A10) is
almost identical to Eq. (31) and Eq. (70). The only difference is the factor of 5 that appears on the
left side of Eq. (A10). Thus to determine what happens when, in the YES case, we restrict to Type
I and Type II clauses, we need only replace Eq. (31) and Eq. (70) by Eq. (A10).
In Result 3 the number of time steps needed increases by a factor of 5 to obtain the same
outcome. In Result 1 we use the following transformation, which preserves the statement of the
result:
5f 2 L2 n2
,
2

3
fL − 1
N →T
− 2f Ln.
fL
T →

(A11)

Using this transformation in Result 2, the outcome is identical when we choose f
max{22/(5c), 1}.
We now proof Result 4:
P ROOF : Since n2 ≥ tr[Ŝ 2 ρ] ≥ 0, for any state ρ,
n2 ≥ tr[Ŝ 2 ρT ] − tr[Ŝ 2 ρ0 ]
T −1 

X
=
tr[Ŝ 2 ρt+1 ] − tr[Ŝ 2 ρt ]

=

t=0

T −1
X
2
=
L
t=0

X

tr[Φα ρt ] +

α∈Type I

X

α∈Type II

!
i
h
X 
tr −1 +
σ zk Φα ρt ,

(A12)

k6=i,j

line.
where we have used Eq. (A9) in the lastP
In the Type II sum, the term (−1 + k6=i,j σ zk ) has eigenvalues that are larger than −(n − 1),
P
so using that Φα and (−1 + k6=i,j σ zk ) commute (they act on different qubits), we obtain
!
T −1
X
X
2X
2
n ≥
tr[Φα ρt ] − (n − 1)
tr[Φα ρt ]
(A13)
L t=0 α∈Type I
α∈Type II
We have
tr[H ρt ] =

X

tr[Φα ρt ] +

X

tr[Φα ρt ],

(A14)

!
T −1
X
X
2
n2 ≥
tr[H ρt ] − n
tr[Φα ρt ] .
L t=0
α∈Type II

(A15)

α∈Type II

α∈Type I

which we can plug into Eq. (A13) to obtain

We now bound the term involving the Type II clauses. From Eq. (A8) we have
T −1 
T −1

X
X
1 X
tr[Φα ρt ] =
tr[Ŝ ρt+1 ] − tr[Ŝ ρt ]
L α∈Type II
t=0
t=0

= tr[Ŝ ρT ] − tr[Ŝ ρ0 ]
≤ 2n,

(A16)

16
where in the last line we have used that for any ρ, we have −n ≤ tr[Ŝ ρ] ≤ n. Plugging Eq. (A16)
into Eq. (A15), we have
T −1

2X
tr[H ρt ].
5n ≥
L t=0
2

(A17)


[1] T. Schöning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In Foundations
of Computer Science, 1999. 40th Annual Symposium on, pages 410–414. IEEE, 1999.
[2] S. Minton, M. D. Johnston, A. B. Philips, and P. Laird. Minimizing conflicts: a heuristic repair method
for constraint satisfaction and scheduling problems. Artificial Intelligence, 58(1):161–205, 1992.
[3] C. H. Papadimitriou. On selecting a satisfying truth assignment. In Foundations of Computer Science,
1991. Proceedings., 32nd Annual Symposium on, pages 163–169. IEEE, 1991.
[4] S. Even, A. Itai, and A. Shamir. On the complexity of time table and multi-commodity flow problems.
In Foundations of Computer Science, 1975., 16th Annual Symposium on, pages 184–193. IEEE, 1975.
[5] B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear-time algorithm for testing the truth of certain
quantified boolean formulas. Information Processing Letters, 8(3):121–123, 1979.
[6] D. Gosset and D. Nagaj. Quantum 3-sat is qma1-complete. In Foundations of Computer Science
(FOCS), 2013 IEEE 54th Annual Symposium on, pages 756–765. IEEE, 2013.
[7] S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. eprint arXiv:quant-ph/0602108,
February 2006.
[8] M. R. Krom. The decision problem for a class of first-order formulas in which all disjunctions are
binary. Mathematical Logic Quarterly, 13(1-2):15–20, 1967.
[9] N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-sat. arXiv preprint
arXiv:1508.07338, 2015.
[10] I. Arad, M. Santha, A. Sundaram, and S. Zhang. Linear time algorithm for quantum 2sat. arXiv
preprint arXiv:1508.06340, 2015.
[11] F. Verstraete, Michael M. Wolf, and J. I. Cirac. Quantum computation and quantum-state engineering
driven by dissipation. Nature Physics, 5(9):633–636, 2009.
[12] I. Arad and O. Sattath. A constructive quantum lovász local lemma for commuting projectors.
arXiv:1310.7766, 2013.
[13] M. Schwarz, T. S. Cubitt, and F. Verstraete. An information-theoretic proof of the constructive commutative quantum lovász local lemma. arXiv preprint arXiv:1311.6474, 2013.
[14] J. Chen, X. Chen, R. Duan, Z. Ji, and B. Zeng. No-go theorem for one-way quantum computing on
naturally occurring two-level systems. Phys. Rev. A, 83:050301, May 2011.
[15] E. B. Davies. Quantum theory of open systems. Academic Press, 1976.

