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.
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1[4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.
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.
We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as H=∑aHa where (1) every term Ha acts nontrivially on a constant number of qubits, (2) every term Ha has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term Ha. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.
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 calculation of ground-state energies of physical systems can be formalized as the k-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterization holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.