Quantum 3-SAT Is QMA$_1$-Complete

DOI10.1137/140957056zbMath1342.81087arXiv1302.0290OpenAlexW2554893608WikidataQ59482302 ScholiaQ59482302MaRDI QIDQ2816302

David Gosset, Daniel Nagaj

Publication date: 4 July 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

quantum computationHamiltonian complexityquantum \(k\)-SAT

Mathematics Subject Classification ID

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

Related Items (6)

The complexity of translationally invariant spin chains with low local dimension ⋮ Total functions in QMA ⋮ A Complete Characterization of Unitary Quantum Space ⋮ Linear-Time Algorithm for Quantum 2SAT ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Quantum 3-SAT Is QMA$_1$-Complete

Cites Work

• Quantum Arthur-Merlin games
• Eigenvalues, diameter, and mean distance in graphs
• Quantum 3-SAT Is QMA$_1$-Complete
• A quantum lovász local lemma
• Stronger methods of making quantum interactive proofs perfectly complete
• Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1-Complete
• New construction for a QMA complete three-local Hamiltonian
• Fast universal quantum computation with railroad-switch local Hamiltonians
• The Complexity of the Local Hamiltonian Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum 3-SAT Is QMA$_1$-Complete