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 QMA1-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.
column Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I Share on Authors: Diogo Fernandes University of Porto, Portugal University of Porto, PortugalView Profile , Inês Dutra University of Porto, Portugal University of Porto, PortugalView Profile Authors Info & Affiliations XRDS: Crossroads, The ACM Magazine for StudentsVolume 26Issue 1Fall 2019 pp 64–66https://doi.org/10.1145/3358251Published:17 September 2019 0citation289DownloadsMetricsTotal Citations0Total Downloads289Last 12 Months67Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access