The Complexity of Translationally Invariant Problems beyond Ground State Energies

Understand

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.