---
_id: '8162'
abstract:
- lang: eng
text: '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.'
author:
- first_name: Marco
full_name: Aldi, Marco
last_name: Aldi
- first_name: Niel
full_name: de Beaudrap, Niel
last_name: de Beaudrap
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Seyran
full_name: Saeedi, Seyran
last_name: Saeedi
citation:
ama: 'Aldi M, de Beaudrap N, Gharibian S, Saeedi S. On Efficiently Solvable Cases
of Quantum k-SAT. In: Potapov I, Spirakis P, Worrell J, eds. 43rd International
Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Vol
117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl
- Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:10.4230/LIPIcs.MFCS.2018.38'
apa: Aldi, M., de Beaudrap, N., Gharibian, S., & Saeedi, S. (2018). On Efficiently
Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, & J. Worrell
(Eds.), 43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018) (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.38
bibtex: '@inproceedings{Aldi_de Beaudrap_Gharibian_Saeedi_2018, place={Dagstuhl,
Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)},
title={On Efficiently Solvable Cases of Quantum k-SAT}, volume={117}, DOI={10.4230/LIPIcs.MFCS.2018.38},
booktitle={43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
author={Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran},
editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={38:1-38:16},
collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On
Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium
on Mathematical Foundations of Computer Science (MFCS 2018), edited by Igor
Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.'
ieee: 'M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable
Cases of Quantum k-SAT,” in 43rd International Symposium on Mathematical Foundations
of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, p. 38:1-38:16,
doi: 10.4230/LIPIcs.MFCS.2018.38.'
mla: Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” 43rd
International Symposium on Mathematical Foundations of Computer Science (MFCS
2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2018, p. 38:1-38:16, doi:10.4230/LIPIcs.MFCS.2018.38.
short: 'M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis,
J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of
Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
Dagstuhl, Germany, 2018, p. 38:1-38:16.'
conference:
location: Liverpool, UK
name: 43rd International Symposium on Mathematical Foundations of Computer Science
(MFCS 2018)
date_created: 2019-03-01T11:34:41Z
date_updated: 2023-02-28T11:01:16Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.MFCS.2018.38
editor:
- first_name: Igor
full_name: Potapov, Igor
last_name: Potapov
- first_name: Paul
full_name: Spirakis, Paul
last_name: Spirakis
- first_name: James
full_name: Worrell, James
last_name: Worrell
external_id:
arxiv:
- '1712.09617'
intvolume: ' 117'
keyword:
- search complexity
- local Hamiltonian
- Quantum SAT
- algebraic geometry
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2018/9620/
oa: '1'
page: 38:1-38:16
place: Dagstuhl, Germany
publication: 43rd International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)
publication_identifier:
unknown:
- 978-3-95977-086-6
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: On Efficiently Solvable Cases of Quantum k-SAT
type: conference
user_id: '71541'
volume: 117
year: '2018'
...