Theory of Computing
-------------------
Title : Linear-Time Algorithm for Quantum 2SAT
Authors : Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
Volume : 14
Number : 1
Pages : 1-27
URL : https://theoryofcomputing.org/articles/v014a001
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 $\Pi_{ij}$ on a system of $n$ qubits, and the task
is to decide whether the Hamiltonian $H=\sum \Pi_{ij}$ has a
0-eigenvalue, or all eigenvalues are greater than $1/n^\alpha$ for some
$\alpha=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 $\frac{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(n^4)$ 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.
A conference version of this paper appeared in the Proceedings of
the 43rd International Colloquium on Automata, Languages and
Programming (ICALP'16), 2016.