A linear time algorithm for quantum 2-SATReport as inadecuate

A linear time algorithm for quantum 2-SAT - Download this document for free, or read online. Document in PDF available to download.

Reference: De Beaudrap, N and Gharibian, S, (2016). A linear time algorithm for quantum 2-SAT. 31st Conference on Computational Complexity (CCC 2016), 50, 27:1--27:21.Citable link to this page:


A linear time algorithm for quantum 2-SAT Series: Leibniz International Proceedings in Informatics (LIPIcs)

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 deterministiclinear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to thequantum setting, defining the problem quantum k-SAT. He showed that quantum 2-SAT isalso solvable in polynomial time on a classical computer, in particular in deterministic timeO(n4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n isthe number of variables. In this paper, we present an algorithm for quantum 2-SAT which runsin 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 similaritieswith 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].

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionConference Details: 31st Conference on Computational Complexity (CCC 2016)Notes:Copyright Niel de Beaudrap and Sevag Gharibian;licensed under Creative Commons License CC-BY31st Conference on Computational Complexity (CCC 2016).

Bibliographic Details

Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Publisher Website: http://www.dagstuhl.de/

Series:Leibniz International Proceedings in Informatics (LIPIcs)

Host: 31st Conference on Computational Complexity (CCC 2016)see more from them

Publication Website: http://computationalcomplexity.org/Archive/2016/program.html

Volume: 50

Extent: 27:1--27:21

Issue Date: 2016


Urn: uuid:faa4ce29-98e2-4438-8ba1-be786a634c1d

Source identifier: 609604

Doi: https://doi.org/10.4230/LIPIcs.CCC.2016.27

Issn: 1868-8969

Isbn: 978-3-95977-008-8 Item Description

Type: Conference;

Version: Publisher's versionKeywords: quantum 2-SAT transfer matrix strongly connected components limited backtracking local Hamiltonian Tiny URL: pubs:609604


Author: De Beaudrap, N - institutionUniversity of Oxford Oxford, MPLS, Computer Science - - - Gharibian, S - - - - Bibliographic Details

Source: https://ora.ox.ac.uk/objects/uuid:faa4ce29-98e2-4438-8ba1-be786a634c1d


Related documents