In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this article, we take a new direction by introducing the physically motivated notion of “ground state connectivity” of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. Roughly, “ground state connectivity” corresponds to the natural question: Given two ground states |Ψ〉 and |ϕ〉 of a local Hamiltonian H , is there an “energy barrier” (with respect to H ) along any sequence of local operations mapping |Ψ〉 to |ϕ〉? We show that the complexity of this question can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined “succinct” version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA-complete.
CLH is complete for the complexity class QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA-complete if and only if QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMAO and construct a classical oracle O such that BQPO⊆QIMAO.
Since BQPO⊆QMAO for any classical oracle O, this implies QIMAO=QMAO for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP-hard, and hence also against the possibility that it is QMA-complete.
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].
We study the variant of the k-local hamiltonian problem which is a natural generalization of k-CSPs, in which the hamiltonian terms all commute. More specifically, we consider a hamiltonian H over n qubits, where H is a sum of k-local terms acting non-trivially on O(log n) qubits, and all the k-local terms commute, and show the following - 1. We show that a specific case of O(log n) local commuting hamiltonians over the hypercube is in NP using the Bravyi-Vyalyi Structure theorem. 2. We give a simple proof of a generalized area law for commuting hamiltonians (which seems to be a folklore result) in all dimensions, and deduce the case for O(log n) local commuting hamiltonians. 3. We show that traversing the ground space of O(log n) local commuting hamiltonians is QCMA complete. The first two behaviours seem to indicate that deciding whether the ground space energy of O(log n)-local commuting hamiltonians is low or high might be in NP or possibly QCMA, though the last behaviour seems to indicate that it may indeed be the case that O(log n)-local commuting hamiltonians are QMA complete.
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.
QMA and QCMA are possible quantum analogues of the complexity class NP. In QMA the proof is a quantum state and the verification is a quantum circuit. In contrast, in QCMA the proof is restricted to be a classical state. It is not known whether QMA strictly contains QCMA. Here we show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit does not act as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it does not act on all states as the identity.