Posted

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 kk-local (kk-body) Hamiltonian is frustration-free, could be classified as being either in P\mathsf{P}; or complete for NP\mathsf{NP}, MA\mathsf{MA}, or QMA1\mathsf{QMA_1}. Here, we demonstrate new qubit variants of this problem that are complete for BQP1\mathsf{BQP_1}, coRP\mathsf{coRP}, QCMA\mathsf{QCMA}, PI(coRP,NP)\mathsf{PI(coRP,NP)}, PI(BQP1,NP)\mathsf{PI(BQP_1,NP)}, PI(BQP1,MA)\mathsf{PI(BQP_1,MA)}, SoPU(coRP,NP)\mathsf{SoPU(coRP,NP)}, SoPU(BQP1,NP)\mathsf{SoPU(BQP_1,NP)}, and SoPU(BQP1,MA)\mathsf{SoPU(BQP_1,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\mathsf{BQP_1}-complete problem. We first prove there are qudit QSAT problems that are complete for BQP1\mathsf{BQP_1}, coRP\mathsf{coRP}, and QCMA\mathsf{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\mathsf{PI} and SoPU\mathsf{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.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!