After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].
After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].
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.
It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are QMA-hard, PQMA[log]-hard and QCMA-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are PQMAEXP- and QCMAEXP-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping H (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by H, while preserving the structural and geometric properties of H (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).
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.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
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.