License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.15
URN: urn:nbn:de:0030-drops-62795
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6279/
Arad, Itai ;
Santha, Miklos ;
Sundaram, Aarthi ;
Zhang, Shengyu
Linear Time Algorithm for Quantum 2SAT
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 Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = 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 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.
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:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6279},
URN = {urn:nbn:de:0030-drops-62795},
doi = {10.4230/LIPIcs.ICALP.2016.15},
annote = {Keywords: Quantum SAT, Davis-Putnam Procedure, Linear Time Algorithm}
}
Keywords: |
|
Quantum SAT, Davis-Putnam Procedure, Linear Time Algorithm |
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
23.08.2016 |