@inproceedings{8162,
  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.}},
  author       = {{Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}},
  booktitle    = {{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)}},
  editor       = {{Potapov, Igor and Spirakis, Paul and Worrell, James}},
  keywords     = {{search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}},
  location     = {{Liverpool, UK}},
  pages        = {{38:1--38:16}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}},
  title        = {{{On Efficiently Solvable Cases of Quantum k-SAT}}},
  doi          = {{10.4230/LIPIcs.MFCS.2018.38}},
  volume       = {{117}},
  year         = {{2018}},
}

@inproceedings{8160,
  abstract     = {{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       = {{Gharibian, Sevag and Yirka, Justin}},
  booktitle    = {{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}},
  editor       = {{Wilde, Mark}},
  keywords     = {{Complexity theory, Quantum Merlin Arthur (QMA), local Hamiltonian, local measurement, spectral gap}},
  location     = {{Paris, France}},
  pages        = {{2:1--2:17}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}},
  title        = {{{The Complexity of Simulating Local Measurements on Quantum Systems}}},
  doi          = {{10.4230/LIPIcs.TQC.2017.2}},
  volume       = {{73}},
  year         = {{2018}},
}

@article{8167,
  author       = {{Gharibian, Sevag and Sikora, Jamie}},
  issn         = {{1942-3454}},
  journal      = {{ACM Transactions on Computation Theory (TOCT)}},
  keywords     = {{Local Hamiltonian, ground state connectivity, quantum Hamiltonian complexity, reconfiguration problem}},
  number       = {{2}},
  pages        = {{8:1--8:28}},
  publisher    = {{ACM}},
  title        = {{{Ground State Connectivity of Local Hamiltonians}}},
  doi          = {{10.1145/3186587}},
  volume       = {{10}},
  year         = {{2018}},
}

@inproceedings{8159,
  abstract     = {{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       = {{de Beaudrap, Niel and Gharibian, Sevag}},
  booktitle    = {{Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}},
  editor       = {{Raz, Ran}},
  isbn         = {{978-3-95977-008-8}},
  keywords     = {{quantum 2-SAT, transfer matrix, strongly connected components, limited backtracking, local Hamiltonian}},
  location     = {{Tokyo, Japan}},
  pages        = {{27:1--17:21}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}},
  title        = {{{A Linear Time Algorithm for Quantum 2-SAT}}},
  doi          = {{10.4230/LIPIcs.CCC.2016.27}},
  volume       = {{50}},
  year         = {{2016}},
}