Quantum 3-SAT is QMA(1)-complete

Autor(en)

David Gosset, Daniel Nagaj

Abstrakt

Quantum satisfiability is a constraint satisfaction problem that

generalizes classical boolean satisfiability. In the quantum k-SAT

problem, each constraint is specified by a k-local projector and is

satisfied by any state in its nullspace. Bravyi showed that quantum

2-SAT can be solved efficiently on a classical computer and that quantum

k-SAT with k ≥ 4 is QMA₁-complete [4]. Quantum 3-SAT was known to be contained in QMA₁ [4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA₁-hard, and therefore complete for this complexity class.

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

University of Waterloo (UW)

Seiten

756-765

Anzahl der Seiten

10

DOI

https://doi.org/10.1109/FOCS.2013.86

Publikationsdatum

2013

ÖFOS 2012

103036 Theoretische Physik

Schlagwörter

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/08118c8e-2a4d-4449-bf25-9522dfe411cf