Linear time algorithm for quantum 2SAT
Preprint
Abstract
A canonical 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 it is larger 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 the 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. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is $O(n^4)$. In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubitsPhysical Review A, 2011
- Entanglement in Quantum Critical PhenomenaPhysical Review Letters, 2003
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are BinaryMathematical Logic Quarterly, 1967
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960