---
_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'
...
---
_id: '8160'
abstract:
- lang: eng
text: An important task in quantum physics is the estimation of local quantities
for ground states of local Hamiltonians. Recently, Ambainis defined the complexity
class P^QMA[log], and motivated its study by showing that the physical task of
estimating the expectation value of a local observable against the ground state
of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the
study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness
result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We
show that simulating even a single qubit measurement on ground states of 5-local
Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We
formalize the complexity theoretic study of estimating two-point correlation functions
against ground states, and show that this task is similarly P^QMA[log]-complete.
P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally
by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung
to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP
from Kitaev and Watrous. A central theme of this work is the subtlety involved
in the study of oracle classes in which the oracle solves a promise problem. In
this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness
proof for estimating spectral gaps of local Hamiltonians. By introducing a "query
validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness
for estimating spectral gaps under polynomial-time Turing reductions.
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Justin
full_name: Yirka, Justin
last_name: Yirka
citation:
ama: 'Gharibian S, Yirka J. The Complexity of Simulating Local Measurements on Quantum
Systems. In: Wilde M, ed. 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017). Vol 73. Leibniz International Proceedings
in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:2:1-2:17.
doi:10.4230/LIPIcs.TQC.2017.2'
apa: Gharibian, S., & Yirka, J. (2018). The Complexity of Simulating Local Measurements
on Quantum Systems. In M. Wilde (Ed.), 12th Conference on the Theory of Quantum
Computation, Communication and Cryptography (TQC 2017) (Vol. 73, p. 2:1-2:17).
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.TQC.2017.2
bibtex: '@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz
International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating
Local Measurements on Quantum Systems}, volume={73}, DOI={10.4230/LIPIcs.TQC.2017.2},
booktitle={12th Conference on the Theory of Quantum Computation, Communication
and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer
Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark},
year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in
Informatics (LIPIcs)} }'
chicago: 'Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local
Measurements on Quantum Systems.” In 12th Conference on the Theory of Quantum
Computation, Communication and Cryptography (TQC 2017), edited by Mark Wilde,
73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl,
Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. https://doi.org/10.4230/LIPIcs.TQC.2017.2.'
ieee: 'S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements
on Quantum Systems,” in 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017), Paris, France, 2018, vol. 73, p.
2:1-2:17, doi: 10.4230/LIPIcs.TQC.2017.2.'
mla: Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements
on Quantum Systems.” 12th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2017), edited by Mark Wilde, vol. 73,
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 2:1-2:17, doi:10.4230/LIPIcs.TQC.2017.2.
short: 'S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory
of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl
- Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.'
conference:
location: Paris, France
name: 12th Conference on the Theory of Quantum Computation, Communication and Cryptography
(TQC 2017)
date_created: 2019-03-01T11:25:27Z
date_updated: 2023-02-28T11:00:48Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.TQC.2017.2
editor:
- first_name: Mark
full_name: Wilde, Mark
last_name: Wilde
external_id:
arxiv:
- '1606.05626'
intvolume: ' 73'
keyword:
- Complexity theory
- Quantum Merlin Arthur (QMA)
- local Hamiltonian
- local measurement
- spectral gap
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577
oa: '1'
page: 2:1-2:17
place: Dagstuhl, Germany
publication: 12th Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2017)
publication_identifier:
unknown:
- 978-3-95977-034-7
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: The Complexity of Simulating Local Measurements on Quantum Systems
type: conference
user_id: '71541'
volume: 73
year: '2018'
...
---
_id: '8167'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Jamie
full_name: Sikora, Jamie
last_name: Sikora
citation:
ama: Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. ACM
Transactions on Computation Theory (TOCT). 2018;10(2):8:1-8:28. doi:10.1145/3186587
apa: Gharibian, S., & Sikora, J. (2018). Ground State Connectivity of Local
Hamiltonians. ACM Transactions on Computation Theory (TOCT), 10(2),
8:1-8:28. https://doi.org/10.1145/3186587
bibtex: '@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local
Hamiltonians}, volume={10}, DOI={10.1145/3186587},
number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM},
author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }'
chicago: 'Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local
Hamiltonians.” ACM Transactions on Computation Theory (TOCT) 10, no. 2
(2018): 8:1-8:28. https://doi.org/10.1145/3186587.'
ieee: 'S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,”
ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, p. 8:1-8:28,
2018, doi: 10.1145/3186587.'
mla: Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.”
ACM Transactions on Computation Theory (TOCT), vol. 10, no. 2, ACM, 2018,
p. 8:1-8:28, doi:10.1145/3186587.
short: S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10
(2018) 8:1-8:28.
date_created: 2019-03-01T11:49:31Z
date_updated: 2023-02-28T11:01:36Z
department:
- _id: '623'
- _id: '7'
doi: 10.1145/3186587
external_id:
arxiv:
- '1409.3182'
intvolume: ' 10'
issue: '2'
keyword:
- Local Hamiltonian
- ground state connectivity
- quantum Hamiltonian complexity
- reconfiguration problem
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1409.3182
oa: '1'
page: 8:1-8:28
publication: ACM Transactions on Computation Theory (TOCT)
publication_identifier:
issn:
- 1942-3454
publication_status: published
publisher: ACM
status: public
title: Ground State Connectivity of Local Hamiltonians
type: journal_article
user_id: '71541'
volume: 10
year: '2018'
...
---
_id: '8159'
abstract:
- lang: eng
text: The Boolean constraint satisfaction problem 3-SAT is arguably the canonical
NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial
time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically
motivated generalization of k-SAT to the quantum setting, defining the problem
"quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time
on a classical computer, in particular in deterministic time O(n^4), assuming
unit-cost arithmetic over a field extension of the rational numbers, where n is
number of variables. In this paper, we present an algorithm for quantum 2-SAT
which runs in linear time, i.e. deterministic time O(n+m) for n and m the number
of variables and clauses, respectively. Our approach exploits the transfer matrix
techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions
for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT
algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and
Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].
author:
- 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
citation:
ama: 'de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In:
Raz R, ed. Proceedings of the 31st Conference on Computational Complexity (CCC
2016). Vol 50. Leibniz International Proceedings in Informatics (LIPIcs).
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:10.4230/LIPIcs.CCC.2016.27'
apa: de Beaudrap, N., & Gharibian, S. (2016). A Linear Time Algorithm for Quantum
2-SAT. In R. Raz (Ed.), Proceedings of the 31st Conference on Computational
Complexity (CCC 2016) (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.CCC.2016.27
bibtex: '@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz
International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm
for Quantum 2-SAT}, volume={50}, DOI={10.4230/LIPIcs.CCC.2016.27},
booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC
2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de
Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21},
collection={Leibniz International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
2-SAT.” In Proceedings of the 31st Conference on Computational Complexity (CCC
2016), edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings
in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.27.'
ieee: 'N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,”
in Proceedings of the 31st Conference on Computational Complexity (CCC 2016),
Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: 10.4230/LIPIcs.CCC.2016.27.'
mla: de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum
2-SAT.” Proceedings of the 31st Conference on Computational Complexity (CCC
2016), edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer
Informatik, 2016, p. 27:1-17:21, doi:10.4230/LIPIcs.CCC.2016.27.
short: 'N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st
Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.'
conference:
location: Tokyo, Japan
name: 31st Conference on Computational Complexity (CCC 2016)
date_created: 2019-03-01T11:19:54Z
date_updated: 2023-02-28T11:01:53Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.CCC.2016.27
editor:
- first_name: Ran
full_name: Raz, Ran
last_name: Raz
extern: '1'
external_id:
arxiv:
- '1508.07338'
intvolume: ' 50'
keyword:
- quantum 2-SAT
- transfer matrix
- strongly connected components
- limited backtracking
- local Hamiltonian
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2016/5836/
oa: '1'
page: 27:1-17:21
place: Dagstuhl, Germany
publication: Proceedings of the 31st Conference on Computational Complexity (CCC 2016)
publication_identifier:
isbn:
- 978-3-95977-008-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: A Linear Time Algorithm for Quantum 2-SAT
type: conference
user_id: '71541'
volume: 50
year: '2016'
...