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(1)-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv: quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA1 [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

University of Waterloo (UW), Slovak Academy of Sciences (SAS)

Journal

SIAM. Journal on Computing (SICOMP)

Band

45

Seiten

1080-1128

Anzahl der Seiten

49

ISSN

0097-5397

DOI

https://doi.org/10.1137/140957056

Publikationsdatum

2016

Peer-reviewed

Ja

ÖFOS 2012

103036 Theoretische Physik

Schlagwörter

ASJC Scopus Sachgebiete

Allgemeine Mathematik, Allgemeine Computerwissenschaft

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/2dc8f04f-a3b6-48e7-af60-42057448bcd2