Conference item icon

Conference item

A linear time algorithm for quantum 2-SAT

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(

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CCC.2016.27

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Host title:
31st Conference on Computational Complexity (CCC 2016)
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Journal:
31st Conference on Computational Complexity (CCC 2016) More from this journal
Volume:
50
Pages:
27:1--27:21
Publication date:
2016-01-01
Acceptance date:
2016-02-06
DOI:
ISSN:
1868-8969
ISBN:
9783959770088
Keywords:
Pubs id:
pubs:609604
UUID:
uuid:faa4ce29-98e2-4438-8ba1-be786a634c1d
Local pid:
pubs:609604
Source identifiers:
609604
Deposit date:
2016-03-11

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP