A quantum constraint problem is a frustration-free Hamiltonian problem: given a collection of local operators, is there a state that is in the ground state of each operator simultaneously? It has previously been shown that these problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this list has not been shown to be exhaustive. We present three quantum constraint problems, that are (1) BQP_1-complete (also known as coRQP), (2) QCMA_1-complete and (3) coRP-complete. This provides the first natural complete problem for BQP_1. We also show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. These results suggest a significant diversity of complexity classes present in quantum constraint problems.
Quantum Constraint Problems can be complete for BQP, QCMA, and more
A quantum constraint problem is a frustration-free Hamiltonian problem: given a collection of local operators, is there a state that is in the ground state of each operator simultaneously? It has previously been shown that these problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this list has not been shown to be exhaustive. We present three quantum constraint problems, that are (1) BQP_1-complete (also known as coRQP), (2) QCMA_1-complete and (3) coRP-complete. This provides the first natural complete problem for BQP_1. We also show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. These results suggest a significant diversity of complexity classes present in quantum constraint problems.
Previously, all known variants of the Quantum Satisfiability (QSAT) problem - consisting of determining whether a k-local (k-body) Hamiltonian is frustration-free - could be classified as being either in 𝖯; or complete for NP, MA, or QMA₁. Here, we present new qubit variants of this problem that are complete for BQP₁, coRP, QCMA, PI(coRP,NP), PI(BQP₁,NP), PI(BQP₁,MA), SoPU(coRP,NP), SoPU(BQP₁,NP), and SoPU(BQP₁,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 BQP₁-complete problem. We first construct QSAT problems on qudits that are complete for BQP₁, coRP, and QCMA. These are made by restricting the finite set of Hamiltonians to consist of elements similar to H_{init}, H_{prop}, and H_{out}, seen in the circuit-to-Hamiltonian transformation. Usually, these are used to demonstrate hardness of QSAT and Local Hamiltonian problems, and so our proofs of hardness are simple. The difficulty lies in ensuring that all Hamiltonians generated with these three elements can be decided in their respective classes. For this, we build our Hamiltonian terms with high-dimensional data and clock qudits, ternary logic, and either monogamy of entanglement or specific clock encodings. We then show how to express these problems in terms of qubits, by proving that any QCSP can be reduced to a qubit problem while maintaining the same complexity - something not believed possible classically. The remaining six problems are obtained by considering "sums" and "products" of some of the QSAT problems mentioned here. Before this work, the QSAT problems generated in this way resulted in complete problems for PI and SoPU classes that were trivially equal to NP, MA, or QMA₁. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for coRP, BQP₁, and QCMA, we note that those constructions are flawed. Here, we rework them, provide correct proofs, and obtain improvements on the required qudit dimensionality.
A major goal of quantum complexity theory is to understand which computational problems can be solved with access to certain quantum resources. The subfield of Hamiltonian complexity specifically considers computational problems that ask about properties of local Hamiltonians, which are of critical importance in quantum complexity because they can be viewed as quantum generalizations of classical constraint satisfaction problems. In this work, we study the complexity of certain restricted variants of the Quantum-k-Sat problem, a quantum analog of the NP-complete k-Sat problem. We introduce new variants of Quantum-k-Sat which place a basis restriction on the input Hamiltonian H = Σᵢ hᵢ . Each variant is defined by a fixed collection of bases B₁, . . . , Bᵣ of n-qubit space. We require that each Hamiltonian term hi must be diagonal in one of these bases. Our results resolve the complexity of certaim basis-restricted variants of Quantum-k-Sat. First we show the Quantum-6-Sat problem with Hamiltonian terms restricted to be diagonal in an X/Z mixed basis is QMA₁-complete. Second, we combine basis restriction with the restriction of commutativity, and show the following easiness result, which applies generally to higher-level quantum systems (qudits) and bases Q and R (which are real-valued and satisfy an overlap condition): The commmuting Quantum-Sat problem on qudits, where Hamiltonian terms are either diagonal in the Q basis, the R basis, or a single mixed Q/R basis, is in NP.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA1 QMA 1 -complete (for k≥3 k ≥ 3 , and where QMA1 QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But 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 “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or 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. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. 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.
The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that the ground state of the k-local Hamiltonian minimizes the energy of every local interaction term simultaneously. This is a central question in quantum physics and a canonical QMA_1-complete problem. The Quantum k-SAT problem is not as well studied as the classical k-SAT problem in terms of special tractable cases, approximation algorithms and parameterized complexity. In this paper, we will give a graph-theoretic study of the Quantum k-SAT problem with the structures core and radius. These hypergraph structures are important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT instance in polynomial time if the derived hypergraph has a core of size n-m+a, where a is a constant, and the radius is at most logarithmic. If it exists, we can find a core of size n-m+a with the best possible radius in polynomial time, whereas finding a general minimum core with minimal radius is NP-hard.
The local Hamiltonian problem is the canonical QMA-complete problem, and O(2n) time classical algorithms and O(2n/2) time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs.
In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints.
We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but O(n) qubits participate in only constantly many constraints, while the remaining O(n) qubits each participate in O(n) constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of nδ, for any δ>0, our algorithm solves the problem in time O(2(1−ε)n) for some ε>0.
Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
In this work we define a new classical constraint satisfaction problem that shares many of the properties of the quantum local Hamiltonian problem, distinguishing it from the usual classical k-SAT problem. The problem consists of minimizing the number of violated local constraints over a restricted set of distributions of assignments. We show that these distributions can be 1-to-1 mapped to a superset of the quantum states, which we call k-local quasi-quantum states. Nevertheless, we claim that our optimization problem is essentially classical, by proving that it is an NP-complete problem. Interestingly, the optimal distribution shares many of the properties of quantum states. In particular, it is not determined straightforwardly by its local marginals, and consequently, it can be used as a classical toy model to study several aspects of Hamiltonian complexity that are different from their classical counter parts. These include the complexity of 1D systems (which is in P for classical CSPs, but is QMA-hard for quantum systems), and the lack of an easy search-to-decision reduction. Finally, we believe that our model can be used to gain insights into the quantum PCP conjecture. Indeed, while we have shown that approximating the minimal number of unsatisfiable constraints to within an Θ(1) is NP-hard, it is not clear if the problem remains hard if we want to approximate the minimal fraction of unsatisfiable constraints to within an Θ(1); as in the quantum PCP conjecture, naive quantization of the classical proofs does not seem to work.