History-state Hamiltonians are critical

Abstract

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).

35 pages. See arXiv:1703.10133v2 for related results

Cited by in corpus (5)

• Importance of the spectral gap in estimating ground-state energies
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Detailed Analysis of Circuit-to-Hamiltonian Mappings
• Translationally-Invariant Universal Quantum Hamiltonians in 1D