  All Hamiltonian complexity results to date have been proven by constructing a
local Hamiltonian whose ground state -- or at least some low-energy state -- is
a "computational history state", encoding a quantum computation as a
superposition over the history of the computation. We prove that all
history-state Hamiltonians must be critical. More precisely, for any
circuit-to-Hamiltonian mapping that maps quantum circuits to local Hamiltonians
with low-energy history states, there is an increasing sequence of circuits
that maps to a growing sequence of Hamiltonians with spectral gap closing at
least as fast as O(1/n) with the number of qudits n in the circuit. This result
holds for very general notions of history state, and also extends to
quasi-local Hamiltonians with exponentially-decaying interactions.
  This suggests that QMA-hardness for gapped Hamiltonians (and also
BQP-completeness of adiabatic quantum computation with constant gap) either
require techniques beyond history state constructions. Or gapped Hamiltonians
cannot be QMA-hard (respectively, BQP-complete).
