Linear time algorithm for quantum 2SAT

2015/08/26 by Itai Arad, Miklos Santha, Arad, Itai +5 · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1508.06340

20 pages

arxiv created 2016/04/26 · arxiv updated 2016/04/27

Abstract

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 Π_ij on a system of n qubits, and the task is to decide whether the Hamiltonian H=∑ Π_ij has a 0-eigenvalue, or it is larger than 1/n^α for some α=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⁴). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

Cited by

• Quantum k-SAT Related Hypergraph Problems

Related

• Efficient algorithm for a quantum analogue of 2-SAT
• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• A Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT
• Quantum 2-SAT on low dimensional systems is QMA₁-complete: Direct embeddings and black-box simulation
• 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: O(2^(n)/(2)) Algorithm Is Nearly Optimal under QSETH