2026-07-24T05:42:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6279 2024-03-06T10:37:39Z ddc:004 open_access

Linear Time Algorithm for Quantum 2SAT Arad, Itai Santha, Miklos Sundaram, Aarthi Zhang, Shengyu Quantum SAT Davis-Putnam Procedure Linear Time Algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Arad and Miklos Santha and Aarthi Sundaram and Shengyu Zhang 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.15 urn:nbn:de:0030-drops-62795 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.15 eng https://creativecommons.org/licenses/by/3.0/legalcode