pdf icon
Volume 14 (2018) Article 1 pp. 1-27
Linear-Time Algorithm for Quantum 2SAT
Received: May 16, 2016
Revised: August 22, 2017
Published: March 9, 2018
Download article from ToC site:
[PDF (454K)]    [PS (3771K)]    [PS.GZ (781K)]
[Source ZIP]
Keywords: quantum satisfiability, Davis-Putnam procedure, linear-time algorithm
ACM Classification: F.2
AMS Classification: 68Q25, 81P68

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 $\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.