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.CCC.2016.27
URN: urn:nbn:de:0030-drops-58363
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5836/
Go to the corresponding LIPIcs Volume Portal

de Beaudrap, Niel ; Gharibian, Sevag

A Linear Time Algorithm for Quantum 2-SAT

pdf-format:
15.pdf (0.6 MB)

Abstract

The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

BibTeX - Entry

@InProceedings{debeaudrap_et_al:LIPIcs:2016:5836,
  author =	{Niel de Beaudrap and Sevag Gharibian},
  title =	{{A Linear Time Algorithm for Quantum 2-SAT}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Ran Raz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5836},
  URN =		{urn:nbn:de:0030-drops-58363},
  doi =		{10.4230/LIPIcs.CCC.2016.27},
  annote =	{Keywords: quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian}
}

Keywords: quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI