---
_id: '8159'
abstract:
- lang: eng
  text: 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].
author:
- first_name: Niel
  full_name: de Beaudrap, Niel
  last_name: de Beaudrap
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: 'de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In:
    Raz R, ed. <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>. Vol 50. Leibniz International Proceedings in Informatics (LIPIcs).
    Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>'
  apa: de Beaudrap, N., &#38; Gharibian, S. (2016). A Linear Time Algorithm for Quantum
    2-SAT. In R. Raz (Ed.), <i>Proceedings of the 31st Conference on Computational
    Complexity (CCC 2016)</i> (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik. <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>
  bibtex: '@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz
    International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm
    for Quantum 2-SAT}, volume={50}, DOI={<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>},
    booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de
    Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21},
    collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
  chicago: 'Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
    2-SAT.” In <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>, edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings
    in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik, 2016. <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>.'
  ieee: 'N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,”
    in <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>,
    Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: <a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>.'
  mla: de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
    2-SAT.” <i>Proceedings of the 31st Conference on Computational Complexity (CCC
    2016)</i>, edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer
    Informatik, 2016, p. 27:1-17:21, doi:<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>.
  short: 'N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st
    Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum
    fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.'
conference:
  location: Tokyo, Japan
  name: 31st Conference on Computational Complexity (CCC 2016)
date_created: 2019-03-01T11:19:54Z
date_updated: 2023-02-28T11:01:53Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.CCC.2016.27
editor:
- first_name: Ran
  full_name: Raz, Ran
  last_name: Raz
extern: '1'
external_id:
  arxiv:
  - '1508.07338'
intvolume: '        50'
keyword:
- quantum 2-SAT
- transfer matrix
- strongly connected components
- limited backtracking
- local Hamiltonian
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://drops.dagstuhl.de/opus/volltexte/2016/5836/
oa: '1'
page: 27:1-17:21
place: Dagstuhl, Germany
publication: Proceedings of the 31st Conference on Computational Complexity (CCC 2016)
publication_identifier:
  isbn:
  - 978-3-95977-008-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: A Linear Time Algorithm for Quantum 2-SAT
type: conference
user_id: '71541'
volume: 50
year: '2016'
...