Arad, Itai ;
Santha, Miklos ;
Sundaram, Aarthi ;
Zhang, Shengyu
Linear Time Algorithm for Quantum 2SAT
Abstract
A canonical result about satisfiability theory is that the 2SAT problem can be solved in linear time, despite the NPhardness of the 3SAT problem. In the quantum 2SAT problem, we are given a family of 2qubit projectors Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0eigenvalue, or it is larger than 1/n^c for some c = O(1). The problem is not only a natural extension of the classical 2SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2local frustrationfree Hamiltonians of spin 1/2, a wellstudied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2SAT problem has a classical polynomialtime 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.
BibTeX  Entry
@InProceedings{arad_et_al:LIPIcs:2016:6279,
author = {Itai Arad and Miklos Santha and Aarthi Sundaram and Shengyu Zhang},
title = {{Linear Time Algorithm for Quantum 2SAT}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {15:115:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6279},
URN = {urn:nbn:de:0030drops62795},
doi = {10.4230/LIPIcs.ICALP.2016.15},
annote = {Keywords: Quantum SAT, DavisPutnam Procedure, Linear Time Algorithm}
}
2016
Keywords: 

Quantum SAT, DavisPutnam Procedure, Linear Time Algorithm 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 