Authors Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27
www.theoryofcomputing.org
Linear-Time Algorithm for Quantum 2SAT
Itai Arad∗ Miklos Santha∗† Aarthi Sundaram∗‡ Shengyu Zhang∗§
Received May 16, 2016; Revised August 22, 2017; Published March 9, 2018
Abstract: A well-known result about satisfiability theory is that the 2-SAT problem can be
solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT
problem, we are given a family of 2-qubit projectors Πi j on a system of n qubits, and the
task is to decide whether the Hamiltonian H = ∑ Πi j has a 0-eigenvalue, or all eigenvalues
are greater than 1/nα for some α = O(1). The problem is not only a natural extension of
the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of
finding a ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied
model believed to capture certain key properties in modern condensed matter physics. Bravyi
has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity
O(n4 ) in the algebraic model of computation where every arithmetic operation on complex
numbers can be performed in unit time, and n is the number of variables. In this paper we
give a deterministic algorithm in the algebraic model with running time O(n + m), where m
is the number of local projectors, therefore achieving the best possible complexity in that
model. We also show that if in the input every number has a constant size representation then
the bit complexity of our algorithm is O((n + m)M(n)), where M(n) denotes the complexity
of multiplying two n-bit integers.
ACM Classification: F.2
AMS Classification: 68Q25, 81P68
Key words and phrases: quantum satisfiability, davis-putnam procedure, linear time algorithm
A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata,
Languages and Programming (ICALP’16), 2016 [1].
∗ Supported by the Singapore Ministry of Education and the National Research Foundation, also under the Tier 3 Grant
MOE2012-T3-1-009; by the European Commission IST STREP project Quantum Algorithms (QALGO) 600700; and the
French ANR Blanc Program Contract ANR-12-BS02-005.
† Also thanks STIAS for their hospitality during October and November 2015.
‡ Also thanks the Centre for Quantum Technologies for their support during my graduate studies when this work was done.
§ Supported in part by RGC of Hong Kong (Project no. CUHK419413 and 14239416).
© 2018 Itai Arad and Miklos Santha and Aarthi Sundaram and Shengyu Zhang
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2018.v014a001
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
1 Introduction
Various formulations of the satisfiability problem of Boolean formulae arguably constitute the centerpiece
of classical complexity theory. In particular, a great amount of attention has been paid to the SAT problem,
in which we are given a formula in the form of a conjunction of clauses, where each clause is a disjunction
of literals (variables or negated variables), and the task is to find a satisfying assignment if there is one, or
determine that none exists when the formula is unsatisfiable. In the case of the k-SAT problem, where k
is a positive integer, the number of literals in each clause is at most k. While k-SAT is an NP-complete
problem [7, 16, 21] when k ≥ 3, the 2-SAT problem is well-known to be efficiently solvable.
Polynomial time algorithms for 2-SAT come in various flavours. Let us suppose that the input
formula has n variables and m clauses. The algorithm of Krom [19] based on the resolution principle
and on transitive closure computation decides if the formula is satisfiable in time O(n3 ) and finds a
satisfying assignment in time O(n4 ). The limited backtracking technique of Even, Itai and Shamir [11]
has linear time complexity in m, as well as the elegant procedure of Aspvall, Plass and Tarjan [2] based
on computing strongly connected components in a graph. A particularly simple randomized procedure of
complexity O(n2 ) is described by Papadimitriou [22].
For our purposes the Davis-Putnam procedure [9] is of singular importance. This is a resolution-
principle based general SAT solving algorithm, which with its refinement due to Davis, Putnam, Logemann
and Loveland [8], forms the basis for the most efficient SAT solvers even today. While on general SAT
instances it works in exponential time, on 2-SAT formulae it is of polynomial complexity.
The high level description of the procedure for 2-SAT is relatively simple. Let us suppose that our
formula φ only contains clauses with two literals. Pick an arbitrary unassigned variable xi and assign
xi = 0. The formula is simplified: a clause (x̄i ∨ x j ) becomes true and therefore can be removed, and a
clause (xi ∨ x j ) forces x j = 1. This can be, in turn, propagated to other clauses to further simplify the
formula until a contradiction is found or no more propagation is possible. If no contradiction is found
and the propagation stops with the simplified formula φ0 , then we recurse on the satisfiability of φ0 .
Otherwise, when a contradiction is found, that is, at some point the propagation assigns two different
values to the same variable, we reverse the choice made for xi , and propagate the new choice xi = 1. If
this also leads to a contradiction we declare φ to be unsatisfiable, otherwise we recurse on the result of
this propagation, the simplified formula φ1 .
There is a deep and profound link between k-SAT formulas and k-local Hamiltonians, the central
objects of condensed matter physics. A k-local Hamiltonian on n qubits is a Hermitian operator of the
form H = ∑m i=1 hi , where each hi is individually a Hermitian operator acting non-trivially on at most k
qubits. Local Hamiltonians model the local interactions between quantum spins. Of central importance
are the eigenstates of the Hamiltonian that correspond to its minimal eigenvalue. These are called ground
states, and their associated eigenvalue is known as the ground energy. Ground states govern much of
the low temperature physics of the system, such as quantum phase transitions and collective quantum
phenomena [24, 25]. Finding a ground state of a local Hamiltonian shares important similarities with the
k-SAT problem: in both problems we are trying to find a global minimum of a set of local constraints.
The connection with complexity theory is also of physical significance. With the advent of quantum
information theory and quantum complexity theories, it has become clear that the complexity of finding
a ground state and its energy is intimately related to its entanglement structure. In recent years, much
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 2
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
attention has been devoted to understanding this structure, revealing a rich and intricate behaviour such as
area laws [10] and topological order [17].
The connection between classical k-SAT and quantum local Hamiltonians was formalized by Ki-
taev [18] who introduced the k-local Hamiltonian problem. We are given a k-local Hamiltonian H, along
with two constants a < b such that b − a > 1/nα for some constant α, and a promise that the ground
energy is at most a (the YES case) or is at least b (the NO case). Our task is to decide which case
holds. Given a quantum state |ψi, the energy of a local term hψ|hi |ψi can be viewed as a measure of
how much |ψi “violates” hi , hence the ground energy is the quantum analog of the minimal number of
violations in a classical k-SAT formula. Therefore, in spirit, the k-local Hamiltonian problem corresponds
to MAX-k-SAT, and indeed Kitaev has shown [18] that 5-local Hamiltonian is QMA-complete, where the
complexity class QMA is the quantum analogue of classical class MA, the probabilistic version of NP.
The problem quantum k-SAT, the quantum analogue of k-SAT, is a close relative of the k-local
Hamiltonian problem. Here we are given a k-local Hamiltonian that is made of k-local projectors,
H = ∑m α
i=1 Qi , and we are asked whether the ground energy is 0 or it is greater than b = 1/n for some
constant α. Notice that in the YES case, the energy of each projector at a ground state is necessarily 0
because, by definition, projectors are non-negative operators. Classically, this corresponds to a perfectly
satisfiable formula. Physically, this is an example of a frustration-free Hamiltonian, in which a global
ground state is also a ground state of every local term. Bravyi [4] has shown that quantum k-SAT is
QMA1 -complete for k ≥ 4, where QMA1 stands for QMA with one-sided error (that is on YES instances
the verifier accepts with probability 1). The QMA1 -completeness of quantum 3-SAT was recently proven
by Gosset and Nagaj [12].
This paper is concerned with the quantum 2-SAT problem, which we will also denote simply by
Q2SAT. One major result concerning this problem is due to Bravyi [4], who has proven that it belongs
to the complexity class P. More precisely, he has proven that Q2SAT can be decided by a deterministic
algorithm in time O(n4 ) in the algebraic model of computation, where every arithmetic operation on
complex numbers can be performed in unit time. In addition, on satisfiable instances he could construct
a ground state that has a polynomial classical description. In the case of Q2SAT, the Hamiltonian is
given as a sum of 2-qubits projectors; each projector is defined on a 4-dimensional Hilbert space and can
therefore be of rank 1, 2 or 3. In this paper, we give an algorithm for Q2SAT of linear complexity.
Theorem 1.1. In the algebraic model of computation there is a deterministic algorithm for Q2SAT whose
running time is O(n + m), where n is the number of variables and m is the number of local terms in the
Hamiltonian.
Our algorithm shares the same trial and error approach of the Davis-Putnam procedure for classical
2-SAT, but handles many of the difficulties arising in the quantum setting. Firstly, a ground state of
the input to Q2SAT may be entangled, a feature that classical 2-SAT does not have. Thus the idea of
setting some qubit to a certain state and propagating from there does not have foundation in the first place.
Indeed, if a rank-3 projection leaves the only allowed state entangled, then any ground state is entangled
in those two qubits. We account for this by showing a product-state theorem, which asserts that for any
frustration-free Q2SAT instance H that contains only rank-1 and rank-2 projectors, there always exists a
ground state in the form of a tensor product of single-qubit states.
This structural theorem grants us the following approach: We try some candidate solution |ψii on a
qubit i, and propagate it along the graph. If no contradiction is found, it turns out that we can detach the
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 3
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
explored part and recurse on the rest of the graph. If a contradiction is found, then we can identify two
candidates (i, |ψii ) and ( j, |φ i j ) such that either assigning |ψii to qubit i or assigning |φ i j to qubit j is
correct, if there exists a solution at all. More details follow next.
To illustrate the main idea of our algorithm, let us assume, for simplicity, that the system is only
made of rank-1 projectors. Consider, then a rank-1 projector in the system, say, Π12 = |ψihψ| over
qubits 1 and 2. The product-state theorem implies that it suffices to search for a product ground state.
Thus on the first two qubits, we are looking for states |αi, |β i such that (hα| ⊗ hβ |)Π12 (|αi ⊗ |β i) = 0,
which is equivalent to hα| ⊗ hβ | · |ψi = 0. In other words, we look for a product state |αi ⊗ |β i that is
perpendicular to |ψi. Assume that we have assigned qubit 1 with the state |αi and we are looking for a
state |β i for qubit 2. The important point, which enables us to solve Q2SAT efficiently, is that just like in
the classical case, there are only two possibilities: (i) for any |β i, the state |αi ⊗ |β i is perpendicular to
|ψi, or (ii) there is only one state |β i (up to an overall complex phase), for which (hα| ⊗ hβ |) · |ψi = 0.
The first case happens if and only if |ψi is by itself a product state of the form |ψi = |α ⊥ i ⊗ |ξ i, where
|α ⊥ i is perpendicular to |αi and |ξ i is arbitrary. If the second case happens, we say that the state |αi is
propagated to the state |β i by the constraint state |ψi.
The above dichotomy enables us to propagate a product state |si on part of the system until we
either reach a contradiction, or find that no further propagation is possible and we are left with a
smaller Hamiltonian H 0 . This smaller Hamiltonian consists of a subset of the original projectors without
introducing new projectors. This crucial fact implies that, analogous to the classical case, the original
Hamiltonian H is satisfiable if and only if the smaller Hamiltonian H 0 is satisfiable.
We still need to specify how the state |αi is chosen to initialize the propagation. An idea is to begin
with projectors |ψihψ| for which |ψi is a product state |γi ⊗ |δ i. In such cases a product state solution
must either have |γ ⊥ i at the first qubit or |δ ⊥ i at the second. To maintain a linear running time, we
propagate these two choices simultaneously until one of the propagations stops without contradiction, in
which case the corresponding qubit assignment is made final. If both propagations end with contradictions,
the input is rejected.
The more interesting case of the algorithm happens when we have only entangled rank-1 projectors.
What should our initial state be then? We make an arbitrary assignment (say, |0i) to any of the still
unassigned qubits and propagate this choice. If the propagation ends without contradiction, we recurse. If
a contradiction is found then we confront a challenging problem. In the classical case we could reverse
our choice, say x0 = 0, and try the other possibility, x0 = 1. But in the quantum case we have an infinite
number of potential assignment choices. The solution is found by the following observation: Whenever a
contradiction is reached, it can be attributed to a cycle of entangled projectors in which the assignment
has propagated from qubit i along the cycle and returned to it with another value (see Figure 1(a)). Then
using the technique of “sliding,” which was introduced in Ref. [15], one can show that this cycle is
equivalent to a system of one double edge and a “tail” (see Figure 1(b)). Using a simple structure lemma,
we are guaranteed that at least one of the projectors of the double edge can be turned into a product state
projector, which, as in the previous stage, gives us only two possible free choices.
As we have stated, our algorithm works in the algebraic model of computation: we suppose that
every arithmetic operation on complex numbers can be done in unit time. There are several ways to
work in a more realistic model. One possibility would be to consider complex numbers with bounded
precision in which case exact computation is no more possible and therefore an error analysis should be
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 4
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
Figure 1: Handling a contradicting cycle: (a) we slide edges that touch i along the two paths to j until (b)
we get a double edge with two “tails.” (c) we use a structure lemma to deduce that at least one of these
edges can be written as a product projector (a dashed edge).
made. Bravyi [4] suggests considering bounded degree algebraic numbers, in which case the length of
the representations and the cost of the operations can be analyzed by considering their bit-wise costs,
termed the bit complexity. For the sake of completeness, following the thread of working within the
framework of bounded algebraic numbers, we provide an analysis of the bit complexity of our algorithm
in the final section of the paper. More precisely, we prove that if in the input every number has a constant
size representation then the bit complexity of our algorithm is O((n + m) M(n)), where M(n) denotes the
complexity of multiplying two n-bit integers. Finding an algorithm with a better bit complexity seems to
be a hard problem and we leave this challenge as an open problem.
Classically, Davis-Putnam [9] and DPLL algorithms [8] are widely-used heuristics, forming the basis
of today’s most efficient solvers for general SAT. For quantum k-SAT, it could also be a good heuristic if
we try to find product-state solutions, and in that respect our algorithm makes the first-step exploration.
Simultaneously albeit independently from our work de Beaudrap and Gharibian [3] also presented a
linear time algorithm for quantum 2SAT. The main difference between the two algorithms is how they
deal with instances having only entangled rank-1 projectors. Contrarily to us, [3] handles these instances
by using transfer matrix techniques to find discretizing cycles [20].
2 Preliminaries
2.1 Notation
We will use the notation [n] = {1, . . . , n}. For a graph G = (V, E), and for a subset U ⊆ V of the vertices,
we denote by G(U) the subgraph induced by U. Our Hilbert space is defined over n qubits, and is written
as H = H1 ⊗ H2 ⊗ · · · ⊗ Hn , where Hi is the two-dimensional Hilbert space of the ith qubit. We shall
often write |αii to emphasize that the 1-qubit state |αi lives in Hi . Similarly, |ψii j denotes a 2-qubit
state that lives in Hi ⊗ H j . For a 1-qubit state |αi = α0 |0i + α1 |1i, we define its perpendicular state as
|α ⊥ i = ᾱ1 |0i − ᾱ0 |1i, where ᾱ denotes the complex conjugate of α.
A 2-local projector on qubits i 6= j is a projector of the form Πi j = Π̂i j ⊗ Irest , where Π̂i j is a 2-qubit
projector working on Hi ⊗ H j and Irest is the identity operator on the rest of the system. Similarly, a
1-local projector on qubit i is a projector of the form Πii = Π̂ii ⊗ Irest , where Π̂ii is a 1-qubit projector
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 5
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
working on Hi and Irest is the identity operator on the rest of the system. We define the rank of a 2-local
projector Πi j = Π̂i j ⊗ Irest to be the dimension of the subspace that Π̂i j projects to, and we denote it by
rank(Πi j ). The rank of a 1-local projector is defined analogously. The 2-local projectors of rank 3 and
the 1-local projectors of rank 1 are considered to be of maximal rank. A 2-local projector Πi j = Π̂i j ⊗ Irest
of rank 1 where Π̂i j = |ψihψ|i j is called entangled if |ψi is an entangled state, and it is called a product
projector if |ψi is a product state.Recall that a 2-qubit state |ψii j is a product state if it can be written as a
tensor product of 2 single-qubit states |ψii j = |ψ1 ii ⊗ |ψ2 i j ; and a 2-qubit state which is not a product
state is an entangled state. Additionally, given a 2-local projector Π̂i j , it is possible to determine if it is
entangled using the Peres-Horodecki criterion [14, 23].
2.2 The Q2SAT problem
In this paper, we define a 2-local Hamiltonian on an n-qubit system to be a Hermitian operator H =
∑e∈I Πe , for some I ⊆ {(i, j) ∈ [n] × [n] : 1 ≤ i ≤ j ≤ n}, where Πe is a 2-local or a 1-local projector, for
e ∈ I. We suppose that rank(Πii ) = 1, for all (i, i) ∈ I, and 0 < rank(Πi j ) < 4, for all (i, j) ∈ I when
i < j. We also suppose that for every i ∈ [n], there is some e ∈ I such that Πe acts on qubit i.
The ground energy of a Hamiltonian H = ∑e∈I Πe is its smallest eigenvalue, and a ground state of H
is an eigenvector corresponding to the smallest eigenvalue. The subspace of the ground states is called
the ground space. A Hamiltonian is frustration-free if it has a ground state that is simultaneously also
the ground state of each local term. As explained in the introduction, if the Hamiltonian is made of
local projectors, it is frustration-free if and only if there is a state that is a mutual zero eigenstate of all
projectors, which happens if and only if the ground energy is 0. Therefore, if |Γi is a ground state of a
frustration-free 2-local Hamiltonian then Πe |Γi = 0 for all e ∈ I. We can also view each local projector
as a constraint on at most two qubits, then a ground state of a frustration free Hamiltonian satisfies every
constraint.
It turns out that for the representation of a 2-local Hamiltonian, it will be helpful to eliminate the
rank-2 projectors by decomposing each one of them into a sum of two rank-1 projectors. For every
(i, j) ∈ I such that rank(Πi j ) = 2, let Πi j = Πi j,1 + Πi j,2 , where Πi j,1 and Πi j,2 are rank-1 projectors.
Such projectors can be found in constant time. We therefore suppose without loss of generality that H is
specified by
H= ∑ Πi j + ∑ (Πi j,1 + Πi j,2 ) ,
rank(Πi j )6=2 rank(Πi j )=2
which we call the rank-1 decomposition of H.
To the rank-1 decomposition we associate a weighted, directed multigraph with self-loops G(H) =
(V, E, w), which we call the constraint graph of H. By definition
V = {i ∈ [n] : ∃ j ∈ [n] such that (i, j) ∈ I or ( j, i) ∈ I} .
For every rank-3 and rank-1 projector acting on two qubits, there is an edge in each direction between the
two nodes representing them. For every projector acting on a single qubit, there is a self-loop. Finally, for
every rank-2 projector, there are two parallel edges, one in each direction, between the nodes representing
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 6
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
its qubits. Because of the parallel edges, E is not a subset of V ×V . Formally, E = E1 ∪ E2 where
E1 = {(i, j) ∈ [n] × [n] : (i, j) ∈ I and rank(Πi j ) ∈ {1, 3}, or ( j, i) ∈ I and rank(Π ji ) ∈ {1, 3}} ,
and
E2 = {(i, j, b) ∈ [n] × [n] × [2] : (i, j) ∈ I and rank(Πi j ) = 2, or ( j, i) ∈ I and rank(Π ji ) = 2} .
We say that an edge e ∈ E goes from i to j if e ∈ {(i, j), (i, j, 1), (i, j, 2)}. We define erev , the reverse of
the edge e, by (i, j)rev = ( j, i), (i, j, 1)rev = ( j, i, 1) and (i, j, 2)rev = ( j, i, 2) respectively. For a 2-qubit
projector Π̂ we define its reverse projector Π̂rev by Π̂rev |αi|β i = Π̂|β i|αi. For i < j and b ∈ [2], if
Πi j = Π̂i j ⊗ Irest , then we set Π ji = Π̂rev
i j ⊗ Irest , and Π ji,b is defined analogously. The weight of the edges
(i, j) and (i, j, b) are defined as w(i, j) = Πi j , and w(i, j, b) = Πi j,b .
Π12,1
2
Π23
Π12,2
Π32
1 2 Π12,1 2 Π12,2 4 Π14 ⊥
Π21,1 Π21,2
3
1 2 1 Π21,1 1 Π21,2 3 Π23 ⊥
Π14 3 2 Π32 ⊥
Π41
Π44
4 4 4 Π44 1 Π41 ⊥
⊥
(a) (b)
Figure 2: (a) The constraint graph for Hamiltonian H = Π12 + Π14 + Π23 + Π44 where rank(Π44 ) =
rank(Π23 ) = 1, rank(Π12 ) = 2 and rank(Π14 ) = 3 using its rank-1 decomposition. (b) The adjacency
list representation for the constraint graph G(H)
We will suppose that the input to our problem is the constraint graph G(H) of the Hamiltonian, given
in the standard adjacency list representation of weighted graphs, naturally modified for dealing with the
parallel edges as shown in Figure 2. In this representation there is a doubly linked list of size at most n
containing one element for each vertex, and the element i in this list is also pointing towards a doubly
linked list containing an element for every edge going from i to j. For an edge (i, j), this element contains
j, the non-trivial part of projector Πi j , Π̂i j , and a pointer towards the next element in the list and for an
edge (i, j, b) it also contains the value b. We also suppose that for every edge e, there is a double link
between the elements representing e and erev . The problem Q2SAT is defined formally as follows.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 7
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
Q2SAT
Input: The constraint graph G(H) of a 2-local Hamiltonian H, given in the adjacency list
representation.
Output: A solution if H is frustration free, “H is unsatisfiable” if it is not.
2.3 Simple ground states
Our algorithm is based crucially on the following product state theorem, which says that any frustration-
free Q2SAT Hamiltonian has a ground state that is a product state of single qubit and two-qubit states,
where the latter only appear in the support of rank-3 projectors. A slightly weaker claim of that form
has already appeared in Theorem 2 of Ref. [5]. The difference here is that we specifically attribute the
2-qubit states in such a state to rank-3 projectors. Just as in Ref. [5], our derivation relies on the notion of
a genuinely entangled state:
Definition 2.1 (Genuinely entangled states). A state |ψi over n qubits is genuinely entangled if for any
bi-partition of the qubits into two subsets A, B, it cannot be written as a product state |ψi = |ψA i ⊗ |ψB i,
where |ψA i, |ψB i are defined on the qubits of A and B respectively.
Using this definition, Theorem 1 of [5] is restated below.
Proposition 2.2. Any 2-local frustration-free Hamiltonian on n ≥ 3 qubits that has a genuinely entangled
ground state also has a ground state, thats is a product of one-qubit and two-qubits states.
We will also need the following fact about 2-dimensional subspaces in C2 ⊗ C2 .
Proposition 2.3. Any 2-dimensional subspace V of the 2-qubit space C2 ⊗ C2 contains at least one
product state.
Proof. Take a basis {|ψi, |φ i} of the two-dimensional subspace V ⊥ , the orthogonal complement of
V . Our goal is to find a product state |αi ⊗ |β i ∈ V such that hψ|(|αi ⊗ |β i) = hφ |(|αi ⊗ |β i) = 0.
To that aim, expand |ψi, |αi and |β i in the standard basis as |ψi = ∑i j ψi j |i ji, |φ i = ∑i j φi j |i ji, and
|αi = ∑i αi |ii, |β i = ∑ j β j | ji. Then we need to find coefficients αi and β j such that ∑i j φi∗j · αi β j = 0 and
∑i j ψi∗j · αi β j = 0. We can move to a matrix notation, in which ψi∗j , φi∗j are the entries of 2 × 2 matrices
Ψ, Φ, and αi , β j are the coordinates of the 2-vectors α, β . In that notation, we are looking for vectors
α, β such that
α T Ψβ = α T Φβ = 0 . (2.1)
If the matrix Φ is singular, we pick β inside its the null space, and choose α such that α T Ψβ = 0.
Otherwise, when Φ is non-singular, we let β be a right eigenvector of the matrix Φ−1 Ψ, i. e., Φ−1 Ψβ = cβ ,
where c is some eigenvalue. Then Ψβ = cΦβ , and therefore to satisfy equation (2.1), we can choose α
such that α T Φβ = 0.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 8
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
For later use we note that the above proof is constructive, implying that the product state can be found
in constant time. Our product state theorem is stated as follows.
Theorem 2.4. Any frustration-free Q2SAT Hamiltonian H = ∑e∈I Πe has a ground state that is a tensor
product of one qubit and two-qubit states, where two-qubit states only appear in the support of rank-3
projectors.
Proof. Consider a frustration-free 2-local Hamiltonian H and let |Γi be a ground state of H. Much like
any natural number can be written as a product of prime numbers, using Definition 2.1, any state over n
qubits can be written as a product state of one or more genuinely entangled states. In particular, |Γi can
be written as a product state
|Γi = |α (1) i ⊗ |α (2) i ⊗ · · · ⊗ |α (r) i ,
where each |α (i) i is a genuinely entangled state defined on a subset S(i) of qubits. Notice if H contains
a rank-3 projector Π jk = I − |ψihψ| jk , then necessarily every ground state of H will contain |ψi jk at a
tensor product with the rest of the system. Therefore, if |ψi jk is entangled, there must exist a subset
S(i) = { j, k} in the above decomposition with |α (i) i = |ψi jk . Similarly, if |ψi jk is a product state, there
must exist two subsets S(i1 ) = { j}, and S(i2 ) = {k}. Consequently, if S(i) has more than two qubits, there
cannot be any rank-3 projector defined on these qubits.
Consider now a subset S(i) that either: (i) contains three or more qubits, or (ii) contains exactly two
qubits, but there does not exists a rank-3 projector that is defined on these qubits. Define H (i) to be the
Hamiltonian that is the sum of all projectors whose support is inside S(i) . By definition and from the above
paragraph, H (i) does not contain a rank-3 projector. Therefore we can use either Proposition 2.2 (when
S(i) has three or more qubits) or Proposition 2.3 (when S(i) has two qubits) to deduce that in addition to
|α (i) i, H (i) has a ground state |β (i) i that is a product state of single qubit states:
(i) (i)
|β (i) i = |β1 i ⊗ |β2 i ⊗ · · · . (2.2)
The remaining S(i) are either single qubits subsets, or 2-qubits subsets that match the support of entangled
rank-3 projectors. For all these cases, we define |β (i) i = |α (i) i.
We now claim that the state |β i = |β (1) i ⊗ · · · ⊗ |β (r) i, which is a product of one-qubit and two-qubit
states, is a ground state of the full Hamiltonian H = ∑e∈I Πe , including terms that act across the different
S(i) . For that, we need to show that Πe |β i = 0 for every projector Πe in H. If the support of Πe is inside
one of the Si subsets, then by definition Πe |β (i) i = 0 and therefore Πe |β i = 0. Assume then that Πe is
supported on a qubit from S(i) and a qubit from S( j) with i 6= j. We now consider 3 cases:
1. If both S(i) and S( j) contain only one qubit then Πe |β (i) i ⊗ |β ( j) i = Πe |α (i) i ⊗ |α ( j) i = 0.
2. If S(i) is made of one qubit but S( j) has two or more qubits, then expand |α ( j) i = λ0 |0i ⊗ |y0 i +
λ1 |1i ⊗ |y1 i. Here, the standard basis vectors |0i, |1i are defined on the qubit of S j that is in the
support of Πe , while |y0 i, |y1 i are defined on the rest of the qubits in S j , and are not necessarily
orthogonal. The vectors λ0 |y0 i, λ1 |y1 i are by assumption linearly independent, as otherwise |α j i
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 9
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
could have been written as a product state, violating the assumption that it is genuinely entangled.
Then, as the condition Πe |α (i) i ⊗ |α ( j) i = 0 is equivalent to
Πe |α (i) i ⊗ |0i ⊗ λ0 |y0 i + Πe |α (i) i ⊗ |1i ⊗ λ1 |y1 i = 0 ,
we conclude that Πe |α (i) i ⊗ |0i = Πe |α (i) i ⊗ |1i = 0. Therefore, Πe annihilates the subspace
|α (i) i ⊗ C2 , and in particular it annihilates |β (i) i ⊗ |β ( j) i because |β (i) i = |α (i) i.
3. The third case in which both S(i) and S( j) contain two or more qubits cannot happen. Indeed, in
this case we expand the parts of |α (i) i, |α ( j) i that are in the support of Πe in the standard basis, and
repeating the argument from the previous case, we conclude that Πe must annihilate 4 independent
vectors. It therefore cannot be a rank-1 or a rank-2 projector.
This completes the proof of the theorem.
2.4 Assignments
Let H = ∑e∈I Πe be a 2-local Hamiltonian. By Theorem 2.4, if H is frustration free then it has a ground
state that is the tensor product of 1-qubit and 2-qubit entangled states, where the latter only appear in
pairs of qubits in the support of rank-3 projectors. To build up a ground state of this form, our algorithm
will use partial assignments (or simply, assignments, for short). An assignment s is a mapping from
[n]. For every i ∈ [n], the value s(i) is either a 1-qubit state |αi, or a 2-qubit entangled state |γii j for
some j 6= i, or the symbol . If s(i) = |αi or s(i) = |γii j , then this value is assigned to qubit variable
i, and in the latter case the entangled state is shared with variable j. If in an assignment s(i) = |γii j ,
we require that s( j) = |γii j . The symbol is used for unassigned variables. It is common practice to
consider normalized quantum states, that is states |αi such that hα|αi = 1. However, in the course of our
algorithm, we will deal with and assign to the variables un-normalized states. This does not affect the
accuracy of the algorithm but can result in an un-normalized ground state as the output. It is possible to
additionally normalize the ground state without affecting the running time of the algorithm.
We define the support of s by supp(s) = {i ∈ [n] : s(i) 6= }. The assignment s is empty if supp(s) = 0. /
0 0
We denote the empty assignment by s . For assignments s and s , we say that s is an extension of s, if for
every i, such that s(i) 6= , we have s0 (i) = s(i). An assignment is total if s(i) 6= , for all i. Clearly, an
assignment defines a product state of 1-qubit and 2-qubits states on qubits in its support. We denote this
state by |si. We say that an assignment s satisfies a projector Πe , or simply that it satisfies the edge e if,
for any total extension s0 of s, we have Πe |s0 i = 0.
For H = ∑e∈I Πe given in rank-1 decomposition, and an assignment s, we define the reduced Hamil-
tonian Hs of s as
Hs = H − ∑ Πe .
s satisfies e
We will denote the constraint graph G(Hs ) of the reduced Hamiltonian Hs by Gs = (Vs , Es ). We call an
assignment s a pre-solution if it has a total extension s0 satisfying every constraint in H, and we call s a
solution if s itself satisfies every constraint in H. Obviously, an assignment is a solution if and only if Gs
is the empty graph. An assignment s is closed if supp(s) ∩Vs = 0. /
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 10
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
3 Propagation
The crucial building block of our algorithm is the propagation of values by rank-1 projectors. This is the
quantum analog of the classical propagation process when, for example, the clause xi ∨ x j propagates the
value xi = 0 to the value x j = 1 in the sense that given xi = 0, the choice x j = 1 is the only possibility to
make the clause true. In the quantum case this notion has already appeared in Ref. [20], and can, in fact,
also be traced back to Bravyi’s original work. Here, we shall adopt the following definition:
Definition 3.1 (Propagation). Let Πe = |ψihψ| be a rank-1 projector acting on variables i, j, and let |αi
either be a 1-qubit state assigned to variable i, or a 2-qubit entangled state assigned to variables k, i for
some k 6= j. We say that Πe propagates |αi if, up to an arbitrary complex phase eiθ , there exists a unique
1-qubit state |β i such that Πe |αi ⊗ |β i j = 0. In this case we say that |αi is propagated to |β i along Πe ,
or that Πe propagated |αi to |β i.
The following lemma shows how the propagation properties of Πe = |ψihψ| are determined by the
entanglement in |ψi.
Lemma 3.2. Consider the rank-1 projector Πe = |ψihψ|, defined on qubits i, j. If |ψi is entangled, it
propagates every 1-qubit state |αii to a state |β (α)i j such that if |αii is not a constant multiple of |α 0 ii
then |β (α)i j is not a constant multiple of |β (α 0 )i j . When |ψi is a product state |ψi = |xii ⊗ |yi j , the
projector Πe does not propagate states that are proportional to |x⊥ ii , while all other states are propagated
to |y⊥ i j .
Proof. Assume that |ψi is entangled and consider the state |αi. Our task is to show that there always
exists a unique |β i (up to an overall constant) such that Π(|αi ⊗ |β i) = 0, and that different |αi vectors
yield different |β i vectors.
Expanding |ψi, |αi, and |β i in the standard basis as |ψi = ∑i, j ψi j |ii ⊗ | ji; |αi = ∑i αi |ii; |β i =
∑ j β j | ji, the condition Πe (|αi ⊗ |β i) = 0 translates to ∑i, j ψi∗j αi β j = 0. Assuming that |ψi is entangled,
one can easily verify that the 2 × 2 matrix (ψi∗j ) is non-singular. Then using the simple fact that in a
two-dimensional space every non-zero vector has exactly one non-zero vector (up to an overall scaling)
to which it is orthogonal, it is straightforward to deduce that for every non-zero vector (α0 , α1 ) there is
a unique (up to scaling) non-zero vector (β0 , β1 ) such that ∑i, j ψi∗j αi β j = 0. Moreover, (β0 , β1 ) can be
calculated in constant time, and different (α0 , α1 ) necessarily yield different (β0 , β1 ).
The case when |ψi is a product state is straightforward.
As in the case of Proposition 2.3, we note that the proof above is constructive, and therefore the
propagation can be calculated in constant time.
We now present two lemmas that describe the global structure of a ground state of the system, when
part of it is known to be a tensor product of 1-qubit or 2-qubits states, which are then propagated by some
Πe .
Lemma 3.3 (Single qubit propagation). Consider a frustration-free Q2SAT system H = ∑e∈I Πe with
a rank-1 projector Πe = |ψihψ| between qubits i, j, and assume that H has a ground state of the form
|Γi = |αii ⊗ | resti, where |αii is defined on qubit i and | resti on the rest of the system. If Πe propagates
|αii to |β i j then necessarily | resti = |β i j ⊗ | rest0 i, where the state | rest0 i is defined on all the qubits of
the system except for i and j.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 11
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
Proof. For the first claim assume that Πe propagates |αii to |β i j . We may expand the state | resti as
| resti = |β i j ⊗ | rest1 i + |β ⊥ i j ⊗ | rest2 i ,
where the states | rest1 i, | rest2 i are defined on all the qubits of the system except for i and j, and are not
necessarily normalized. Plugging this expansion into the condition Πe |Γi = 0, we obtain the equation
(Πe |αii |β i j ) ⊗ | rest1 i + (Πe |αii |β ⊥ i j ) ⊗ | rest2 i = 0 .
Πe propagates |αii to |β i j , so we have Πe |αii |β i j = 0 and Πe |αii |β ⊥ i j 6= 0. Therefore, the above
equation implies that | rest2 i = 0, and we may set | rest0 i = | rest1 i.
Lemma 3.4 (Entangled 2-qubits propagation). Consider a frustration-free Q2SAT system H with a
rank-1 projector Πe = |ψihψ|i j between qubits i, j. Assume that H has a ground state of the form
|Γi = |φ iik ⊗ | resti, where |φ i is an entangled state on qubits i, k with k 6= j and | resti is defined on all
qubits except i and k. The following facts hold:
1. |ψi is a product state |ψi = |xii |yi j .
2. Πe propagates |φ iik to |y⊥ i j and necessarily, up to an overall phase, | resti = |y⊥ i j ⊗ | rest0 i where
| rest0 i is defined on all qubits except i, k and j.
Proof. Write |φ iik in a Schmidt decomposition |φ iik = λ1 |αii ⊗ |β ik + λ2 |α ⊥ ii ⊗ |β ⊥ ik , and note that
both λ1 , λ2 6= 0, because |φ iik is entangled. Plugging this into the condition Πe |Γi = 0, we get
Πe |Γi = λ1 |β ik ⊗ Πe |αii ⊗ | resti + λ2 |β ⊥ ik ⊗ Πe |α ⊥ ii ⊗ | resti = 0 .
As |β ik and |β ⊥ ik are linearly independent, we can conclude that
Πe |αii ⊗ | resti = Πe |α ⊥ ii ⊗ | resti = 0 .
To prove the first claim assume, by way of contradiction, that |ψi is entangled. Then by Lemma 3.2,
Πe propagates |αi and |α ⊥ i to two different states, say, |γ1 i j 6= |γ2 i j . However by Lemma 3.3, it follows
that | resti must be both in the form |γ1 i j ⊗ | rest0 i and |γ2 i j ⊗ | rest0 i—which leads to a contradiction.
For the second claim, assume that |ψi = |xii ⊗ |yi j is a product state. We find that
Πe |αii ⊗ | resti = Πe |α ⊥ ii ⊗ | resti = 0
because both states, |αii ⊗ | resti and |α ⊥ ii ⊗ | resti, are ground states of the single projector Hamiltonian
H̃ = Πe . Using Lemma 3.2 and Lemma 3.3, together with the fact that at least one of the states |αii , |α ⊥ ii
is different from |x⊥ ii , we conclude that | resti = |y⊥ i j ⊗ | rest0 i.
Let H be a 2-local Hamiltonian in rank-1 decomposition, let s be an assignment, and let Gs = (Vs , Es )
be the constraint graph of the reduced Hamiltonian Hs . We would like to describe in Gs the result of the
iterated propagation process where a value given to variable i is propagated along all possible projectors,
followed by the propagated values being propagated on their turn. This is repeated until no value assigned
during this process can be propagated further. The propagation can start either when the initial value is
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 12
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
already assigned by s, that is when s(i) = |δ i for |δ i ∈ {|αi, |γii j }, where |αi is some 1-qubit state and
|γii j some 2-qubit state, or when s(i) = , in which case we shall choose an arbitrary 1-qubit state |αi
and assign it to i.
Let s, i and |δ i be such that s(i) ∈ {, |δ i}. We say that in the constraint graph Gs an edge e ∈ Es
from i to j propagates |δ i if Πe propagates it, and we denote by prop(s, e, |δ i) the state |δ i is propagated
to. Now we can generalize the notion of propagation in Gs from edges to paths. Let i = i0 , i1 , . . . , ik
be vertices in Vs , and let e j be an edge from i j to i j+1 , for j = 0, . . . , k − 1. Let s(i) ∈ {, |δ i}, and
set |α0 i = |δ i. Let |α1 i, . . . , |αk i be states such that the propagation of |α j i along Πe j is |α j+1 i, for
j = 0, . . . , k − 1. Then we say that the path p = (e0 , . . . , ek−1 ) from i0 to ik propagates |δ i, and we set
prop(s, p, |δ i) = |αk i. We say that a vertex j ∈ Vs is accessible by propagating |δ i from i if either j = i
or there is a path from i to j that propagates |δ i. We denote by Vsprop (i, |δ i) the set of such vertices,
and by extprop s (i, |δ i) the extension of s by the values given to the vertices in Vsprop (i, |δ i) by iterated
propagation.
The set Vsprop (i, |δ i) divides the edges Es into three disjoint subsets: the edges E1 of the induced
subgraph G(Vsprop (i, |δ i)), the edges E2 between the induced subgraphs G(Vsprop (i, |δ i)) and G(Vs \
Vsprop (i, |δ i)), and the edges E3 of the induced subgraph G(Vs \Vsprop (i, |δ i)). While the edges in E1 ∪ E2
are satisfied by s0 = extprop s (i, |δ i), none of the edges in E3 is satisfied by it. Therefore Gs0 is nothing
prop
but G(Vs \ Vs (i, |δ i)) and it can be constructed by the following process. Given s and i, the edges
in E1 ∪ E2 can be traversed via a breadth first search rooted at i. The levels of the tree are decided
dynamically: at any level the next level is composed of those vertices whose value is propagated from
the current level. A vertex of Gs0 is of degree 0 if all its adjacent edges are in E2 , these vertices will be
removed from Vs0 . The algorithm Propagation uses a temporary queue Q to implement this process.
Procedure 1 Propagation(s, Gs , i, |δ i)
s(i) := |δ i
create a queue Q and put i into Q
while Q is not empty do
remove the head j of Q
for all edges e from j to k do
if e propagates s( j) then
if s(k) 6∈ {, prop(s, e, s( j))} then abort and return “unsuccessful”
if s(k) = then s(k) := prop(s, e, s( j))
enqueue k
remove e and erev from Es
if the list pointed to by k is empty then remove k from Vs
remove j from Vs
Lemma 3.5. (Propagation Lemma) Let Propagation(s, Gs , i, |δ i) be called when Hs does not have
rank-3 constraints, and s(i) ∈ {, |δ i}. Let s0 and G0 = (V 0 , E 0 ) be the outcome of the procedure. The
following hold true:
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 13
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
1. If Propagation(s, Gs , i, |δ i) does not return “unsuccessful” then s0 = extprop
s (i, |δ i) and G0 = Gs0 .
Moreover, if s is a pre-solution then s is a pre-solution, and if s is closed then s0 is also closed.
0
2. If Propagation(s, Gs , i) returns “unsuccessful” then there is no solution z that is an extension of s
and for which z(i) = |δ i.
3. The complexity of the procedure is O(|Es | − |Es0 |).
Proof. The assignments made during the breadth first search correspond exactly to the the paths propagat-
ing |δ i from i, therefore the extension of s created by the process is indeed s0 = extprop s (i, |δ i). The while
loop removes the edges between vertices in Vs (i, |δ i) and the edges between vertices in Vsprop (i, |δ i)
prop
and in Vs \Vsprop (i, |δ i). It also removes the vertices in Vsprop (i, |δ i) and the vertices in Vs \Vsprop (i, |δ i)
whose degree became 0. Therefore in Hs0 for every qubit there is a local projector that acts on this qubit,
and we have G0 = Gs0 .
Let us suppose that s is a pre-solution, and let z be an extension of s where z is a solution and it is a
product state on the vertices in Vs . By Theorem 2.4 there exists such a solution because Hs does not have
rank-3 constraints. We define the assignment z0 by
(
0 s0 ( j) if j ∈ supp(s0 ),
z ( j) =
z( j) otherwise.
Then z0 is a solution that is an extension of s0 , and therefore s0 is a pre-solution. If s is closed then so is s0
as it is only the vertices in Vsprop (i, |δ i) that get assigned during the process, and they are not included
into Vs0 .
Let us now suppose that the procedure returns “unsuccessful.” Then, there is a vertex k ∈ Vsprop (i, |δ i),
and two paths p and p0 in Gs from i to k such that prop(s, p, |δ i) = |β i, prop(s, p0 , |δ i) = |β 0 i and
6 |β 0 i. Let us also suppose that there exists a solution z that is an extension of s and for which
|β i =
z(i) = |δ i. Then, by the repeated use of Lemma 3.3 along with a single use of Lemma 3.4 when |δ i is
a 2-qubit entangled state, we conclude that z(k) is simultaneously equal to |β i and to |β 0 i—which is a
contradiction.
Finally Statement 3 follows because every step of the procedure can be naturally charged to an edge
in Es \ Es0 , and every edge is charged only a constant number of times.
4 The main algorithm
4.1 Description of the algorithm
Now we give a high level description of our algorithm, Q2SATSolver. It takes as input the adjacency
list representation of the constraint graph G(H) of a 2-local Hamiltonian H in rank-1 decomposition.
The algorithm uses four global variables: assignments s0 and s1 initialized to s , and graphs G0 and
G1 in the adjacency list representation, initialized to G(H). The algorithm consists of four phases, and
except for the first one, each phase consists of several stages, where essentially one stage corresponds
to one Propagation process. In the case of an unsatisfiable Hamiltonian the algorithm at some point
outputs “H is unsatisfiable” and stops. This happens when either the maximal rank constraints are already
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 14
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
unsatisfiable, or at some later point several values are assigned to the same variable during a propagation
process that should necessarily succeed to obtain a satisfying assignment.
In the case of a frustration-free Hamiltonian, at the beginning and at the end of each stage, we will
have s0 = s1 and G0 = G1 = Gs0 . In the first two phases only (s0 , G0 ) develops, and is copied to (s1 , G1 )
at the end of the phase. In the last two phases, (s0 , G0 ) and (s1 , G1 ) develop independently, but only the
result of one of the two processes is retained and is copied into the other variable at the end of the phase.
This parallel development of the two processes is necessary for complexity considerations, as it ensures
that some potentially useless work done during the stage is proportional to the useful work of the stage.
In the first phase, the procedure MaxRankRemoval satisfies, if at all possible, every constraint of
maximal rank. In the second phase, all these assignments are propagated, which, if the phase is successful,
results in a closed assignment s such that Hs has only rank-1 constraints. In the third phase the procedure
ParallelPropagation satisfies the product constraints one by one and propagates the assigned values. To
satisfy a product constraint, the only two possible choices are tried and propagated in parallel. In the
fourth phase, the remaining entangled constraints are taken care of, again, one by one. To satisfy an
entangled constraint an arbitrary value, which we choose to be |0i, is tried and propagated. In the case of
an unsuccessful propagation, we are able to efficiently find a product constraint implied by the entangled
constraints considered during the propagation, and therefore it becomes possible to proceed as in phase
three. In the case of a successful propagation, we are left with a satisfying assignment and the empty
constraint graph. Theorem 1.1 is an immediate consequence of the following result.
Algorithm 2 Q2SATSolver(G(H))
s0 = s1 := s , G0 = G1 := G(H) . Initialize global variables
MaxRankRemoval() . Phase 1: Remove maximal rank constraints
while there exist i ∈ V0 such that s(i) 6= do . Phase 2: Propagate all assigned values
P ROPAGATE(s0 , G0 , i, s0 (i))
if the propagation returns “unsuccessful” output “H is unsatisfiable”
s1 := s0 , G1 := G0
while there exists a product constraint Πi0 i1 = |α0⊥ ihα0⊥ |i0 ⊗ |α1⊥ ihα1⊥ |i1 in G0 do
ParallelPropagation(i0 , |α0 i, i1 , |α1 i) . Phase 3: Remove product constraints
while G0 is not empty do . Phase 4: Remove entangled constraints
ProbePropagation(i) for some vertex i
output |si for any total extension s of s0 .
Theorem 4.1. Let G(H) = (V, E) be the constraint graph of a 2-local Hamiltonian. Then, the following
facts hold:
1. If H is frustration-free, the algorithm Q2SATSolver(G(H)) outputs a ground state |si.
2. If H is not frustration-free, the algorithm Q2SATSolver(G(H)) outputs “H is unsatisfiable.”
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 15
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
3. The running time of the algorithm is O(|V | + |E|).
Theorem 4.1 will be proven in Section 4.5.
4.2 Max rank removal
The MaxRankRemoval procedure is conceptually very simple. As every maximal rank constraint has a
unique solution (up to a global phase), it uses this assignment for each constraint, and then checks if this
is globally consistent.
Procedure 3 MaxRankRemoval()
for all i ∈ V0 such that rank(Πii ) = 1 let |φ i be a state satisfying Πii do
s0 (i) := |φ i
for all i ∈ V0 , for all edge e ∈ E0 from i to j such that rank(Πe ) = 3 do
let |γi be the unique state that satisfies Πe
if |γi = |αii |β i j is a product state then
if s0 (i) ∈
/ {, |αi} then output “H is unsatisfiable”
if s0 (i) = then s0 (i) := |αi
if |γi is an entangled state then
if s0 (i) ∈
/ {, |γii j } then output “H is unsatisfiable”
if s0 (i) = then s0 (i) := |γii j
remove from E0 every edge e such that Πe is satisfied by s0 .
remove every isolated vertex from G0
s1 := s0 , G1 := G0
Lemma 4.2. Let s0 , G0 , s1 , G1 be the outcome of MaxRankRemoval. Then the following holds true:
1. If MaxRankRemoval does not output “H is unsatisfiable” then s0 satisfies every maximal rank
constraint, G0 = G(Hs0 ), s0 = s1 , and G0 = G1 . Moreover, if H is satisfiable then s0 is a pre-
solution.
2. If MaxRankRemoval outputs “H is unsatisfiable” then H is unsatisfiable.
3. The complexity of the procedure is O(|V | + |E|).
Proof. If the procedure does not output “H is unsatisfiable” then indeed s0 satisfies all maximal rank
constraints. The removal of the necessary edges and vertices ensures that G0 = G(Hs0 ), and obviously
s0 = s1 , G0 = G1 . If H is satisfiable, then it has a ground state for some total assignment s. This s is an
extension of s0 because there is a unique way to satisfy the maximal rank constraints.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 16
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
Maximal rank projectors are such that there is a unique assignment to their qubits that satisfies them.
The first part of the procedure creates the assignment that assigns these necessary values. If several
different values are assigned to some variable then H is unsatisfiable. Similarly, if s0 assigns an entangled
2-qubit state between variables i and k, and there is an entangled rank-1 constraint between i and j, then
by Lemma 3.4 it is impossible to extend s0 into a satisfying assignment, and therefore H is unsatisfiable.
This proves Statement 2.
The procedure can be executed by a constant number of vertex and edge traversals for s0 , and similarly
for s1 .
4.3 The ParallelPropagation procedure
The procedure ParallelPropagation is called when s0 is a closed assignment, and Gs0 contains an edge
with a product constraint. As there are only two ways to satisfy a product constraint, these are tried and
propagated in parallel. If one of these propagations terminates successfully, the other is stopped, which
ensures that the overall work done is proportional to the progress made.
Procedure 4 ParallelPropagation(i0 , |α0 i, i1 , |α1 i)
Run in parallel Propagation(s0 , G0 , i0 , |α0 i) and Propagation(s1 , G1 , i1 , |α1 i) step by step
until one of them terminates successfully or both terminate unsuccessfully
if both propagations terminate unsuccessfully then
output “H is unsatisfiable”
else let Propagation(s0 , G0 , i0 , |α0 i) terminate first (the other case is symmetric)
undo Propagation(s1 , G1 , i1 , |α1 i)
s1 := s0 , G1 := G0
Lemma 4.3. Let ParallelPropagation be called when s0 is closed, Hs0 does not have rank-3 constraints,
G0 = Gs0 , there exists a product edge in G0 from i0 to i1 with the constraint |α0⊥ ihα0⊥ |i0 ⊗ |α1⊥ ihα1⊥ |i1 ,
s1 = s0 and G1 = G0 . Let s00 , s01 , G00 , G01 be the outcome of the procedure. Then the following holds:
1. If ParallelPropagation does not output “H is unsatisfiable” then s00 is a proper closed extension of
s0 , G00 = Gs00 , s01 = s00 and G01 = G00 . Moreover, if s is a pre-solution then s00 is a pre-solution.
2. If ParallelPropagation outputs “H is unsatisfiable” then H is unsatisfiable.
3. The complexity of the procedure is O(|Es0 | − |Es00 |).
Proof. If the procedure does not output “H is unsatisfiable” then at least one of the parallel propagations
terminates successfully, say Propagation(s0 , G0 , i0 , |α0 i). Then s00 is a proper extension of s0 because s0
is closed and therefore s0 (i0 ) = . Obviously s01 = s00 and G01 = G00 , and all other claims follow from the
Propagation Lemma.
As Hs0 does not have rank-3 constraints, by Theorem 2.4 if it is frustration free, it has a product
ground state. In Hs0 there exists a product edge from i0 to i1 with constraint |α0⊥ ihα0⊥ |i0 ⊗ |α1⊥ ihα1⊥ |i1 ,
therefore only the assignments that have either |α0 i assigned to variable i0 or |α1 i assigned to variable i1
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 17
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
can be a solution. But if both propagations output “unsuccessful,” then, by the Propagation Lemma no
such assignment can satisfy Hs0 . Therefore Hs0 is not frustration free, and neither is H.
For the complexity analysis observe that the unsuccessful or unterminated propagation of the parallel
processes makes at most as many steps as the successful one. This is the reason for performing the two
propagations step by step in parallel. Undoing this propagation can be performed in the same order of
time as the propagation itself, for example, by copying the removed edges into temporary lists. The claim
on the complexity of the successful propagation follows from the Propagation Lemma.
4.4 The ProbePropagation procedure
The procedure ProbePropagation is evoked when s0 is a closed assignment, and Gs0 has only entangled
constraints. The general outline of the procedure is it follows. It begins by picking an arbitrary vertex
i ∈ Vs , assigning |0i (an arbitrary value) to it, and propagating this choice. In the lucky case of a
successful propagation, this call to the procedure ends. Otherwise, we reach a contradiction: there are
two paths p1 , p2 , starting from qubit i and ending at some qubit j, such that the propagation along p1
assigns the state |β1 i to qubit j, whereas the propagation along p2 assigns |β2 i to it—and these two
states are not proportional to each other. These two paths form a cycle, which we call a contradicting
cycle, as illustrated in Figure 1(a). Let us label the two paths by p1 := (i = i0 → i1 → · · · → ik = j) and
p2 := (i = i00 → i01 → · · · → i0` = j). Below, we introduce an operation called “sliding,” which enables us
to take the rank-1 projector on i and i1 and “slide” it along the path p1 so that it acts on i and j. Similarly,
we slide the projector of i and i01 , along p2 , ending this way with two rank-1 projectors acting on qubits i
and j, as shown in Figure 1(b). Assuming these two projectors are different (which, as we show, must
be the case because of the contradiction we initially obtained), their ground space is two dimensional,
and so is its complement. It follows from Proposition 2.3, that the complement subspace must contain a
product state, hence the two projectors can be replaced by two other projectors, one of which is a product
projector, without changing their ground space. We have therefore re-introduced a product constraint into
the system, which can then be handled by the ParallelPropagation procedure.
We continue by describing in detail the sliding operation, which first appeared in a similar form in
Ref. [15]. We formulate it as a lemma, and give its proof to ensure that it can be done efficiently in our
algebraic computation model.
Lemma 4.4 (Sliding Lemma). Consider a system on 3 qubits i, j and k, together with two rank-1
projectors Π1 := |ψ1 ihψ1 |i j on qubits (i, j) and Π2 := |ψ2 ihψ2 | jk on qubits ( j, k). If |ψ2 i is entangled,
then we can find another rank-1 projector Π3 := |ψ3 ihψ3 |ik on qubits (i, k) such that the ground space of
Π1 + Π2 is identical to the ground space of Π2 + Π3 . In addition, if a single qubit state |αii is propagated
by Π1 + Π2 to |β ik , it is also propagated to |β ik directly via Π3 .
Proof. Expand |ψ2 i jk in terms of the standard basis on qubit k as |ψ2 i jk = |xi j |0ik + |yi j |1ik . The
states |xi j , |yi j are not necessarily normalized or orthogonal to each other, but they must be linearly
independent, otherwise |ψ2 i can be written as a product state. Consequently, we can use Gaussian
elimination to find the transformation T on qubit j such that T |xi = |1i and T |yi = −|0i. Note that
T must be unique and non-singular, and that T |ψ2 i jk = |1i|0i − |0i|1i is the anti-symmetric state.
Let |ψ̃1 ii j = T |ψ1 ii j and |ψ̃2 i jk = T |ψ2 i jk respectively, and use them to define the rank-1 projectors
Π̃1 = |ψ̃1 i j ihψ̃1 i j |, Π̃2 = |ψ̃2 ihψ̃2 | jk . Any state in the ground space of Π̃1 + Π̃2 must be invariant under
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 18
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
... ... ... ...
Figure 3: The sliding of the edge (i0 , i1 ) over the path i1 → i2 → · · · → ik , until it becomes the edge
(i0 , ik ).
a swapping of qubits j, k because Π̃2 projects into the anti-symmetric subspace. Therefore, defining
|ψ3 iik = |ψ̃1 iik , and Π3 = |ψ3 ihψ3 |ik , the ground space of Π̃1 + Π̃2 is identical to the ground space of
Π3 + Π̃2 . Now, applying the inverse transformation T −1 on qubit j, the projector Π̃2 returns to Π2 , while
Π3 remains unchanged. As both T and T −1 are non-singular, it follows that ground space of Π1 + Π2 is
identical to the ground space to Π2 + Π3 .
For the second claim, assume by way contradiction that Π3 does not propagate |αii to |β ik . Then
there is a 1-qubit state |γi 6= |β i, such that Π3 (|αii |γik ) = 0. As Π2 is an entangled rank-1 projector, it
propagates |γik to some state |δ i j (see Lemma 3.2). Therefore, the state |αii |δ i j |γik is a ground state of
Π2 + Π3 , as well as of Π1 + Π2 . However, this contradicts the assumption that the latter propagates |αii
to |β ik .
Using the sliding lemma iteratively on a path p := i0 → i1 → · · · → ik that is made of entangled rank-1
projectors Πi0 ,i1 , . . . Πik−1 ,ik , we can transform the first projector Πi0 ,i1 to a projector Πi0 ,i2 , and then to
Πi0 ,i3 , and so on until we obtain Πi0 ,ik , as illustrated in Figure 3. Let us denote the underlying 2-qubit
state in Πi0 ,ik , by |slide(p)i, i. e.,
Πi0 ,ik := |slide(p)ihslide(p)| .
Then we reach the following corollary.
Corollary 4.5. Given a path p := i0 → i1 → · · · → ik of entangled rank-1 projectors Πi0 ,i1 , . . . , Πik−1 ,ik ,
apply the sliding lemma iteratively to obtain |slide(p)ii0 ,ik . Then the ground space of
Πi0 ,i1 + Πi1 ,i2 + · · · + Πik−1 ,ik
is equal to the ground space of
Πi1 ,i2 + · · · + Πik−1 ,ik + |slide(p)ihslide(p)| .
Moreover, if |αii0 is propagated to |β iik along p, then it is also propagated directly by |slide(p)ihslide(p)|.
We are now ready to state the ProbePropagation procedure and analyze it formally.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 19
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
Procedure 5 ProbePropagation(i)
Propagation(s0 , G0 , i, |0i).
if the propagation is successful then s1 := s0 , G1 := G0
else
Let j such that |s0 ( j)| > 1
find two paths p1 and p2 in G0 from i to j such that prop(s0 , p1 , |0i) 6=
prop(s0 , p2 , |0i)
find a product state |α ⊥ i ⊗ |β ⊥ i in the two-dimensional subspace span |slide(p1 )i, |slide(p2 )i
undo Propagation(s0 , G0 , i, |0i)
ParallelPropagation( j, |αi, j, |β i)
Lemma 4.6. Let ProbePropagation be called when s0 is closed, Hs0 has only rank-1 entangled constraints,
G0 = Gs0 , s1 = s0 and G1 = G0 . Let s00 , s01 , G00 , G01 be the outcome of the procedure. Then the following
holds:
1. If ProbePropagation does not output “H is unsatisfiable” then s00 is a proper closed extension of
s0 , G00 = Gs00 , s01 = s00 and G01 = G00 . Moreover, if s is a pre-solution then s00 is a pre-solution.
2. If the call to ParallelPropagation outputs “H is unsatisfiable” then H is unsatisfiable.
3. The complexity of the procedure is O(|Es0 | − |Es00 |).
Proof. If the procedure does not output “H is unsatisfiable” then either Propagation(s0 , G0 , i, |0i) or one
of the parallel propagations (say Propagation(s0 , G0 , i, |αi)) terminates successfully. Thus s00 is a proper
extension of s0 because s0 is closed and therefore s0 (i) = . Obviously s01 = s00 and G01 = G00 , and all
other claims follow from the Propagation Lemma.
Let us suppose that all three propagations are unsuccessful. By Corollary 4.5, any solution for Hs0
also satisfies the system obtained after sliding the constraints from i along paths p1 and p2 , with the new
constraints|slide(p1 )ihslide(p1 )|i j and |slide(p2 )ihslide(p2 )|i j . Using Proposition 2.3, as |α ⊥ ii ⊗ |β ⊥ i j
lies in span |slide(p1 )i, |slide(p2 )i , any state orthogonal to the latter subspace will also be orthogonal to
the former. Hence, any solution for Hs0 should also satisfy the product constraint |α ⊥ ihα ⊥ |i ⊗ |β ⊥ ihβ ⊥ | j .
Then, Lemma 4.3 implies that Hs0 , and by extension H is unsatisfiable if the call to ParallelPropagation,
made to satisfy |α ⊥ ihα ⊥ |i ⊗ |β ⊥ ihβ ⊥ | j , fails.
For the complexity analysis the interesting case is when the first propagation, that we call
Propagationfailure , is unsuccessful but one of the two parallel propagations is successful. Let us
call this successful one Propagationsuccess . The main observation here is that every propagating edge
in Propagationfailure will also be propagating in Propagationsuccess , because by Lemma 3.2 entangled
edges always propagate. The paths p1 and p2 can be found in time proportional to the size of the subgraph
visited by Propagationfailure . Indeed, observe that the edges of the two paths, except the last edge of
one of the two, are edges in the tree created by the breadth first search underlying Propagationfailure .
The way from a vertex to the root of the tree can be found by maintaining, for each vertex in the tree, a
pointer towards its parent. The product state |αi ⊗ |β i can be found in constant time by Proposition 2.3.
Therefore, by applying Lemma 4.3, the complexity is indeed O(|Es0 | − |Es00 |).
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 20
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
4.5 Analysis of the algorithm
Proof of Theorem 4.1. If H is frustration free then by Lemma 4.2 MaxRankRemoval outputs a pre-
solution s0 that satisfies every maximal rank constraint. By the Propagation Lemma, at the end of Phase 2,
s0 is additionally a closed solution. By Lemma 4.3 ParallelPropagation outputs s0 such that Hs contains
only entangled constraints. By Lemma 4.6 at the end of the algorithm Hs is now empty, and therefore s is
a solution.
If the algorithm does not output “H is unsatisfiable” then by Lemma 4.2, by the Propagation Lemma,
and by Lemma 4.3 and Lemma 4.6 it outputs an assignment s such that Gs is the empty graph, and
therefore s is a solution.
The complexity of MaxRankRemoval by Lemma 4.2 is O(|E|). After the second phase, the propa-
gation of the assigned values during MaxRankRemoval, the copying of s0 and G0 into respectively s1
and G1 can be done by executing the same propagation steps this time with s1 and G1 . The complexity
of the rest of the algorithm by the Propagation Lemma, Lemma 4.3 and Lemma 4.6 is a telescopic sum.
Observe that the constants hidden in the big-O notation in the terms of this sum are all the same, they are
equal to the absolute constant in the complexity analysis of the algorithm Propagation referenced in the
Propagation Lemma. Therefore the telescopic sum evaluates to O(|E|), and the overall complexity of the
algorithm is O(|E|).
5 Bit complexity of Q2SATSolver
As mentioned in the introduction, the algorithm Q2SATSolver has been analyzed in the algebraic model
of computation, where arithmetic operations on complex numbers are assumed to consume unit time.
This was done mainly in order to simplify the presentation. However, in order to assess the running time
of the algorithm in any realistic scenario, we must also take into account the actual cost of the arithmetic
operations. This is not a completely trivial task: on the one hand, the continuous nature of a Q2SAT
Hamiltonian implies that it should be represented using complex numbers with an exponentially high
accuracy. But on the other hand, we also want the representation to be as efficient as possible, in order to
minimize the total cost of each arithmetic operation. One way to approach this problem is to consider the
input in the framework of bounded algebraic numbers and analyze the complexity of the algorithm in
this setting. Essentially, this would require calculating the bit-wise cost of representing the input in this
framework and performing the arithmetic operations of the algorithm on it. In other words, we need to
calculate the bit complexity of the algorithm. The techniques used in this section are based on standard
methods in algebraic computational complexity, and further details can be found in [6].
Representing the input and the output
As we would like to work in the framework of algebraic numbers, it helps to first list the kinds of number
fields that will be used to represent the input and output. The simplest field to consider is that of rational
numbers, Q. To bound the size of the entries from Q, a kQ -number, for some integer k > 0, is defined
below.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 21
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
Definition 5.1 (kQ -number). A rational number u is a kQ -number if there exists integers u1 and u2 of at
most k-bits such that u = u1 /u2 .
A kQ -number u1 /u2 will be represented as the tuple (u1 , u2 ) requiring 2k bits. As quantum projectors
√
and states use complex entries, we also require numbers from Q(i), the extension field of Q with i = −1.
This leads to the following definition of a kQ(i) -number:
Definition 5.2 (kQ(i) -number). A complex number a + bi ∈ Q(i) is a kQ(i) -number if its coefficients a
and b are kQ -numbers.
A kQ(i) -number a+bi will be represented as the tuple (a, b) for kQ -numbers a and b, thereby requiring
√
4k bits in total. When the square root, t, of a square-free integer t (that is, an integer which is divisible
by no perfect square√other than 1) is generated during the course of the algorithm, we shall consider the
field extension Q(i, t) of Q(i) and the corresponding kQ(i, √t) -numbers, defined below.
√ √ √
Definition 5.3 (kQ(i, √t) -number). The number a1 + a2 t + a3 i + a4 ti ∈ Q(i, t) is a kQ(i, √t) -number
if its coefficients, a1 , a2 , a3 and a4 , are kQ -numbers.
Clearly, when the integer t can be represented as a k0 -bit integer, a kQ(i, √t) -number can be represented
using 8k + k0 bits by the tuple (a1 , a2 , a3 , a4 ,t) for kQ -numbers a1 , a2 , a3 , a4 .
The input Hamiltonian is a set of m different 2-qubit projectors whose non-trivial parts are 4 × 4
complex matrices. As mentioned in Section 2.2, for a 2-qubit projector Π = Π̂ ⊗ Irest , the input specifies
the non-trivial part Π̂ which is uniquely determined by its image subspace, img(Π̂). We consider each
projector is given as a kQ(i) -projector which is defined below for some constant k > 0.
Definition 5.4 (kQ(i) -projector). Consider a 2-qubit projector Π̂ of rank-r to be specified by r independent,
but not necessarily orthogonal, 4 × 1 vectors {v1 , . . . , vr } such that img(Π̂) = span {v1 , . . . , vr }. Π̂ is a
kQ(i) -projector if v1 , v2 , . . . , vr are given in the standard basis with kQ(i) -number coefficients.
Then, the Hamiltonian can be represented by m different kQ(i) -projectors, leading to a total space
consumption of at most m × 4 × 4 × 1 × 4k = 64mk bits. The ground state output will be a tensor product
of single qubit and 2-qubit states which are length
√ 2 and 4 complex vectors, respectively. Each entry of
these vectors could belong to Q, Q(i) or Q(i, t), for different square free integers t. We will show below
that there can be at most n different integers t, and that the state assigned to each variable consumes
O(n) bits. Recall from Section 2.4 that the algorithm proceeds by assigning un-normalized states without
affecting its accuracy. We also suppose that the basis vectors describing the image subspace of an input
projector need not be normalized.
Cost of arithmetic operations
A useful fact on the bit complexity of basic arithmetic operations that will be used repeatedly is stated
below. Let M(k, k0 ) be the time required to multiply a k-bit integer with a k0 -bit integer and let M(k) =
M(k, k). The currently known most efficient algorithm for integer multiplication uses Fourier transforms
∗
bounding M(k) = k log k8Θ(log k) [13] where
log∗ k = min{w ∈ N : log log w. .times
. . . . log k ≤ 1} .
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 22
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
0 -number. Adding, subtracting, multiplying or dividing a and
Fact 5.5. Let a be a kQ -number and b a kQ
b can be performed in time O(M(k, k )), and the result is an O(k + k0 )Q -number.
0
Now we consider the bit complexity incurred during the course of the Q2SATSolver algorithm.
Theorem 5.6. Let H be a Q2SAT Hamiltonian on n qubits consisting of m projectors with complex entries,
each given as two kQ(i) -numbers, for some constant k > 0. Then the bit complexity of Q2SATSolver(H)
is O((n + m) M(n)).
Proof. The straightforward approach is to calculate the bit complexity of each operation that manipulates
the projectors and assignments. In the first phase of MaxRankRemoval, the unique state satisfying each
2-qubit projector of rank-3 can be found using Gaussian elimination which for an O(1)-sized matrix is
equivalent to a constant number of multiplications. Using Fact 5.5, the 2-qubit state found will hence be
an O(k)Q(i) -number.
The second and third phases of the algorithm repeatedly propagate values across rank-1 constraints.
The bit complexity of propagation is now analyzed. Given a product constraint |αihα| ⊗ |β ihβ |, it
requires finding |α ⊥ i and |β ⊥ i using complex conjugates. Given an entangled constraint and a state
assigned to one end of the constraint, the propagated state can be found by solving a system of linear
equations. Assuming the initial state and the projector use kQ(i) -numbers, the propagated state will be
represented using 2kQ(i) -numbers. To propagate ` steps, each step using kQ(i) -number projectors, starting
0
with a kQ(i) -number state, the final propagated state will use (k0 + `k)Q(i) -numbers. Hence, an O(n) step
propagation will result in a final state represented with O(n)Q(i) -numbers when k = O(1) and k0 = O(n).
This is linear in the number of qubits and takes at most O(n)M(n, k) time. This covers the second and
third phases of the algorithm.
The last phase with ProbePropagation will deal with one or more disconnected components, each
made of only entangled constraints. The complexity of this phase is of interest when a contradiction arises
during propagation in a component and a satisfying assignment has to be found by sliding constraints and
using Proposition 2.3. Consider the way sliding across a constraint is done as described in Lemma 4.4.
Finding the transformation and its inverse both require a constant number of multiplications and the new
constraint after sliding will be given using (ck)Q(i) -numbers for some constant c. Sliding along O(n)
constraints will finally result in constraints represented by O(n)Q(i) -numbers and consumes O(n)M(n, k)
time.
Computing the product constraint in the resulting 2-dimensional subspace requires computing an
√
eigenvector as per Proposition 2.3 leading to the possibility of an irrational square root r being
introduced into the representation, for some square-free integer r. This highlights the necessity of
√
moving to the field extension Q(i, r). Assuming the two parallel rank-1 projectors were initially given
0 √
using kQ(i) -numbers, the product constraint will require O(k0 )Q(i, √r) -numbers to describe it. Also, r is
generated as the irrational part of the eigenvalue of a 2×2 matrix whose entries are O(k0 )Q(i) -numbers due
to which t will be an O(k0 )-bit integer. Hence, the representation of each O(k0 )Q(i, √t) -number will require
O(k0 ) bits. Any propagation after this point does not introduce new irrational square roots. The component,
if satisfiable after ` propagation steps, will have assignments given by O(k0 + `k)Q(i, √t) -numbers. An
O(n) step propagation in this setting will result in this component using O(n)Q(i, √t) -numbers for the
assignment with the operations bounded by O(nM(n, n)) = O(nM(n)) time when k0 = O(nk) = O(n).
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 23
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
Note that each disconnected component at the beginning of this phase may introduce different irrational
square roots into their partial assignments.
Recall that since propagation is carried forward with unnormalised states, this is the only phase
that may introduce square roots in the final assignment. The final output keeps all of these separate
representations and does not homogenize them into a single representation. To conclude, each propagating,
sliding or eigenvector finding step adds an overhead of at most M(n, k) < M(n) where bit complexity is
concerned. Using Theorem 4.1, the bit complexity of Q2SATSolver is therefore O((n + m)M(n)).
Remark 5.7. The above explanation started by assuming the base representation field as that of the
√
Gaussian rationals, Q(i), and extends to the appropriate Q(i, r) field for some square-free integer r
when required. It is also possible to consider any algebraic number field as the base field and extend
it appropriately using techniques from computational algebraic number theory [6]. Of course, any
overheads in performing arithmetic operations and calculating field extensions will have to be accounted
for accordingly.
References
[1] I TAI A RAD , M IKLOS S ANTHA , A ARTHI S UNDARAM , AND S HENGYU Z HANG: Linear time
algorithm for quantum 2SAT. In Proc. 43rd Internat. Colloq. on Automata, Languages and
Programming (ICALP’16), volume 55 of LIPIcs, pp. 15:1–15:14. Schloss Dagstuhl, 2016.
[doi:10.4230/LIPIcs.ICALP.2016.15, arXiv:1508.06340] 1
[2] B ENGT A SPVALL , M ICHAEL F. P LASS , AND ROBERT E NDRE TARJAN: A linear-time algorithm
for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121–123, 1979.
[doi:10.1016/0020-0190(79)90002-4] 2
[3] N IEL DE B EAUDRAP AND S EVAG G HARIBIAN: A linear time algorithm for quantum 2-SAT.
In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), volume 50 of LIPIcs, pp.
27:1–27:21. Schloss Dagstuhl, 2016. [doi:10.4230/LIPIcs.CCC.2016.27, arXiv:1508.07338] 5
[4] S ERGEY B RAVYI: Efficient algorithm for a quantum analogue of 2-SAT. Contemporary Mathemat-
ics, 536:33–48, 2011. [doi:10.1090/conm/536, arXiv:quant-ph/0602108] 3, 5
[5] J IANXIN C HEN , X IE C HEN , RUANYAO D UAN , Z HENGFENG J I , AND B EI Z ENG: No-go the-
orem for one-way quantum computing on naturally occurring two-level systems. Phys. Rev. A,
83(5):050301, 2011. [doi:10.1103/PhysRevA.83.050301, arXiv:1004.3787] 8
[6] H ENRI C OHEN: A Course in Computational Algebraic Number Theory. Volume 138 of Graduate
Texts in Mathematics. Springer, 1993. [doi:10.1007/978-3-662-02945-9] 21, 24
[7] S TEPHEN A. C OOK: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp.
151–158. ACM Press, 1971. [doi:10.1145/800157.805047] 2
[8] M ARTIN DAVIS , G EORGE L OGEMANN , AND D ONALD W. L OVELAND: A machine program for
theorem-proving. Commun. ACM, 5(7):394–397, 1962. [doi:10.1145/368273.368557] 2, 5
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 24
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
[9] M ARTIN DAVIS AND H ILARY P UTNAM: A computing procedure for quantification theory. J. ACM,
7(3):201–215, 1960. [doi:10.1145/321033.321034] 2, 5
[10] J ENS E ISERT, M ARCUS C RAMER , AND M ARTIN B. P LENIO: Area laws for the entanglement en-
tropy. Rev. Mod. Phys., 82(1):277–306, 2010. [doi:10.1103/RevModPhys.82.277, arXiv:0808.3773]
3
[11] S HIMON E VEN , A LON I TAI , AND A DI S HAMIR: On the complexity of timetable and multicom-
modity flow problems. SIAM J. Comput., 5(4):691–703, 1976. Preliminary version in FOCS’75.
[doi:10.1137/0205048] 2
[12] DAVID G OSSET AND DANIEL NAGAJ: Quantum 3-SAT is QMA1 -complete. SIAM J. Com-
put., 45(3):1080–1128, 2016. Preliminary version in FOCS’13. [doi:10.1137/140957056,
arXiv:1302.0290] 3
[13] DAVID H ARVEY, J ORIS VAN DER H OEVEN , AND G RÉGOIRE L ECERF: Even faster integer
multiplication. J. Complexity, 36:1–30, 2016. [doi:10.1016/j.jco.2016.03.001, arXiv:1407.3360] 22
[14] M ICHAŁ H ORODECKI , PAWEŁ H ORODECKI , AND RYSZARD H ORODECKI: Separability of mixed
states: necessary and sufficient conditions. Phys. Lett. A, 223(1–2):1–8, 1996. [doi:10.1016/S0375-
9601(96)00706-2, arXiv:quant-ph/9605038] 6
[15] Z HENGFENG J I , Z HAOHUI W EI , AND B EI Z ENG: Complete characterization of the ground-space
structure of two-body frustration-free Hamiltonians for qubits. Phys. Rev. A, 84(4):042338, 2011.
[doi:10.1103/PhysRevA.84.042338, arXiv:1010.2480] 4, 18
[16] R ICHARD M. K ARP: Reducibility among combinatorial problems. In Complexity of Computer
Computations, The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York, 1972.
[doi:10.1007/978-1-4684-2001-2_9] 2
[17] A LEXEI Y U . K ITAEV: Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–
30, 2003. [doi:10.1016/S0003-4916(02)00018-0, arXiv:quant-ph/9707021] 3
[18] A LEXEI Y U . K ITAEV, A LEXANDER S HEN , AND M IKHAIL N. V YALYI: Classical and Quantum
Computation. Amer. Math. Soc., 2002. [doi:10.1090/gsm/047] 3
[19] M ELVEN R. K ROM: 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. [doi:10.1002/malq.19670130104]
2
[20] C HRISTOPHER R. L AUMANN , RODERICH M OESSNER , A NTONELLO S CARDDICHIO , AND S HIV-
AJI L. S ONDHI : Random quantum satisfiability. Quantum Inf. Comput., 10(1):1–15, 2010. Link at
ACM DL. [arXiv:0903.1904] 5, 11
[21] L EONID A NATOLEVICH L EVIN: Universal sequential search problems. Problems of Information
Transmission, 9(3):265–266, 1973. Available at Math-Net.Ru. 2
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 25
I TAI A RAD AND M IKLOS S ANTHA AND A ARTHI S UNDARAM AND S HENGYU Z HANG
[22] C HRISTOS H. PAPADIMITRIOU: On selecting a satisfying truth assignment (extended abstract). In
Proc. 32nd FOCS, pp. 163–169. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185365] 2
[23] A SHER P ERES: Separability criterion for density matrices. Phys. Rev. Lett., 77(8):1413–1415, 1996.
[doi:10.1103/PhysRevLett.77.1413, arXiv:quant-ph/9604005] 6
[24] S UBIR S ACHDEV: Quantum phase transitions. Wiley Online Library, 2007.
[doi:10.1002/9780470022184.hmm108] 2
[25] G UIFRE V IDAL , J OSÉ I GNACIO L ATORRE , E NRIQUE R ICO , AND A LEXEI Y U . K ITAEV:
Entanglement in quantum critical phenomena. Phys. Rev. Lett., 90(22):227902, 2003.
[doi:10.1103/PhysRevLett.90.227902, arXiv:quant-ph/0211074] 2
AUTHORS
Itai Arad
Assistant professor
Technion - Israel Institute of Technology
arad itai fastmail com
https://phys.technion.ac.il/en/people?view=person&id=871
Miklos Santha
Directeur de Recherche
Université Paris Diderot
miklos santha gmail com
https://www.irif.fr/~santha/
Aarthi Sundaram
Hartree postdoctoral fellow
Joint Centre for Quantum Information and Computer Science
University of Maryland
aarthims gmail com
http://quics.umd.edu/people/aarthi-sundaram
Shengyu Zhang
Assistant professor
The Chinese University of Hong Kong
syzhang cse cuhk edu hk
http://www.cse.cuhk.edu.hk/~syzhang
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 26
L INEAR -T IME A LGORITHM FOR Q UANTUM 2SAT
ABOUT THE AUTHORS
I TAI A RAD was born and raised in a Kibbutz in the south of Israel, where the howling old
owl in the woods is hunting the horny back toad. He did his undergraduate studies in
mathematics and physics at Tel Aviv University (B. Sc. 1996), and later his Ph. D. studies
at the Weizmann Institute of Science under the supervision of Itamar Procaccia in the
subject of turbulence (Ph. D. 2001). After graduation he decided to study astrophysics,
by taking a postdoc position at the Institute of Astronomy at the University of Cambridge,
UK. He finally found his favourite research area with the help of Dorit Aharonov, who
introduced him to the subject of Quantum Computation. After a postdoc in Berkeley with
Umesh Vaziarani and some happy years at the Centre of Quantum Technologies (CQT)
in Singapore, he is now an Assistant Professor at the faculty of Physics at the Technion
in Israel. His research interests lie mainly in the intersection of condensed matter physics
and quantum information, including Hamiltonian Complexity, and questions about area
laws and tensor networks.
M IKLOS S ANTHA received his Diploma in mathematics in 1979 from Eötvös University
in Budapest, and his Ph. D. in mathematics in 1983 from the Université Paris 7. His
advisor was Jacques Stern. Since 1988 he has been a CNRS researcher, currently at the
Université Paris Diderot, IRIF. He is also a principal investigator at CQT in Singapore.
A ARTHI S UNDARAM hails from India, the land of diversity and contrasts. She received
a B. E. in Computer Science and M. Sc. in Mathematics from the Birla Institute of
Technology and Science at their Goa campus in 2012. An elective course offered by
Dr. Radhika Vatsan, during her undergraduate studies, introduced her to the world of
Quantum Computing and provided the impetus to pursue research in this subject. She
completed her Ph. D. at the Centre of Quantum Technologies (CQT) in 2017 in Singapore
under the guidance of Miklos Santha. She is currently a Hartree Postdoctoral Fellow at
the Joint Center for Quantum Information and Computer Science at the University of
Maryland. Her research interests span classical and quantum complexity theory, including
quantum algorithms, cryptography, Hamiltonian Complexity, and ideas pertaining to a
quantum polynomial hierarchy. Outside of work she is an avid Formula 1 and racing
enthusiast, and loves to peer through her camera lens to capture landscapes, architecture
and moments.
S HENGYU Z HANG received his B. S. in Mathematics at Fudan University in 1999, his M. S.
in Computer Science at Tsinghua University under the supervision of Mingsheng Ying in
2002, and his Ph. D. in Computer Science at Princeton University under the supervision
of Andrew Chi-Chih Yao in 2006. He then worked at NEC Laboratories America for a
summer, and at the California Institute of Technology for two years as a postdoctoral
researcher. In 2008, he joined The Chinese University of Hong Kong where he is now an
associate professor. His main research interests are algorithms and complexity theories
in various quantum and randomized models.
T HEORY OF C OMPUTING, Volume 14 (1), 2018, pp. 1–27 27