Linear-Time Algorithm for Quantum 2SAT

DOI10.4086/toc.2018.v014a001zbMath1395.68132OpenAlexW2962782131MaRDI QIDQ4568109

Miklos Santha, Itai Arad, Shengyu Zhang, Aarthi Sundaram

Publication date: 15 June 2018

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a001

zbMATH Keywords

linear-time algorithmDavis-Putnam procedurequantum satisfiability

Mathematics Subject Classification ID

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

Related Items (1)

Perturbation gadgets: arbitrary energy scales from a single strong interaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Even faster integer multiplication
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Fault-tolerant quantum computation by anyons
• Quantum 3-SAT Is QMA$_1$-Complete
• Colloquium: Area laws for the entanglement entropy
• On the Complexity of Timetable and Multicommodity Flow Problems
• Separability Criterion for Density Matrices
• Linear Time Algorithm for Quantum 2SAT
• Reducibility among Combinatorial Problems
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• The complexity of theorem-proving procedures

This page was built for publication: Linear-Time Algorithm for Quantum 2SAT