Linear time algorithm for quantum 2SAT

DOI10.4230/LIPICS.ICALP.2016.15zbMATH Open1388.68064arXiv1508.06340OpenAlexW2887977568MaRDI QIDQ4598148FDOQ4598148

Authors: Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang 

Publication date: 19 December 2017

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 $P{i}_{ij}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=sumP{i}_{ij}$ has a 0-eigenvalue, or it is larger than $1/n^{a}lpha$ for some $alpha=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 $frac12$, 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.

Full work available at URL: https://arxiv.org/abs/1508.06340

Recommendations

• Linear-Time Algorithm for Quantum 2SAT
• scientific article; zbMATH DE number 6789292
• Efficient algorithm for a quantum analogue of 2-SAT
• Quantum 3-SAT Is QMA\(_1\)-complete
• On efficiently solvable cases of quantum \(k\)-SAT

zbMATH Keywords

linear-time algorithmDavis-Putnam procedurequantum SAT

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (6)

• Linear-Time Algorithm for Quantum 2SAT
• Title not available (Why is that?)
• On efficiently solvable cases of quantum \(k\)-SAT
• On efficiently solvable cases of quantum \(k\)-SAT
• The complexity of translationally invariant spin chains with low local dimension
• Efficient algorithm for a quantum analogue of 2-SAT

This page was built for publication: Linear time algorithm for quantum 2SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598148)