The Complexity of Translationally Invariant Problems beyond Ground State Energies

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 mathsf{QMA}-hard, mathsf{P}^{mathsf{QMA}[log]}-hard and mathsf{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 mathsf{P}^{mathsf{QMA}_{mathsf{EXP}}}- and mathsf{QCMA}_{mathsf{EXP}}-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.