Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj (Jun 10 2025).
Abstract: Previously, all known variants of the Quantum Satisfiability (QSAT) problem, i.e. deciding whether a
k-local (
k-body) Hamiltonian is frustration-free, could be classified as being either in
P; or complete for
NP,
MA, or
QMA1​. Here, we demonstrate new qubit variants of this problem that are complete for
BQP1​,
coRP,
QCMA,
PI(coRP,NP),
PI(BQP1​,NP),
PI(BQP1​,MA),
SoPU(coRP,NP),
SoPU(BQP1​,NP), and
SoPU(BQP1​,MA). Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer's dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial
BQP1​-complete problem. We first prove there are qudit QSAT problems that are complete for
BQP1​,
coRP, and
QCMA by re-defining elements of the circuit-to-Hamiltonian transformation. We then show that any QCSP can be reduced to a problem in qubits while maintaining the same complexity - something believed not to be possible classically. The remaining six problems are obtained by considering "sums" and "products" of the first seven QSAT problems. Before this work, the QSAT problems generated in this way resulted in complete problems for
PI and
SoPU classes that were trivially equal to other known classes. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for the first three classes, we note that his constructions are flawed. Here, we rework them and obtain improvements on the required qudit dimensionality.