Aldi, Marco ;
de Beaudrap, Niel ;
Gharibian, Sevag ;
Saeedi, Seyran
On Efficiently Solvable Cases of Quantum kSAT
Abstract
The constraint satisfaction problems kSAT and Quantum kSAT (kQSAT) are canonical NPcomplete and QMA_1complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with onesided error. Whereas kSAT has been wellstudied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for kQSAT. Here, we study the open problem of computing satisfying assignments to kQSAT 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 polynomialtime classical algorithm for kQSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for kQSAT instances from a certain nontrivial 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 3QSAT 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 blowups 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 kSAT}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {38:138:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9620},
URN = {urn:nbn:de:0030drops96201},
doi = {10.4230/LIPIcs.MFCS.2018.38},
annote = {Keywords: search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}
}
27.08.2018
Keywords: 

search complexity, local Hamiltonian, Quantum SAT, algebraic geometry 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 