
Revised: August 22, 2017
Published: March 9, 2018
Abstract: [Plain Text Version]
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 Πij on a system of n qubits, and the task is to decide whether the Hamiltonian H=∑Πij 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 12, 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.
A conference version of this paper appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP'16), 2016.