License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.38
URN: urn:nbn:de:0030-drops-96201
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9620/
Go to the corresponding LIPIcs Volume Portal

Aldi, Marco ; de Beaudrap, Niel ; Gharibian, Sevag ; Saeedi, Seyran

On Efficiently Solvable Cases of Quantum k-SAT

pdf-format:
LIPIcs-MFCS-2018-38.pdf (0.5 MB)

Abstract

The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open.
Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.

BibTeX - Entry

@InProceedings{aldi_et_al:LIPIcs:2018:9620,
  author =	{Marco Aldi and Niel de Beaudrap and Sevag Gharibian and Seyran Saeedi},
  title =	{{On Efficiently Solvable Cases of Quantum k-SAT}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9620},
  URN =		{urn:nbn:de:0030-drops-96201},
  doi =		{10.4230/LIPIcs.MFCS.2018.38},
  annote =	{Keywords: search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}
}

Keywords: search complexity, local Hamiltonian, Quantum SAT, algebraic geometry
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI