This concept, from quantum computational complexity theory (a subfield bridging quantum information science and computational complexity), establishes that finding the ground state and estimating the ground-state energy of a local Hamiltonian is computationally intractable: the classical variant (commuting/diagonal terms, e.g. an Ising spin-glass Hamiltonian encoding a k-SAT instance) is NP-hard, while the general quantum k-local Hamiltonian problem is QMA-complete, the quantum analog of NP-completeness. The central mechanism is the Feynman-Kitaev history-state construction, which reduces any QMA verifier circuit to a 5-local Hamiltonian (H_in + H_out + H_prop + H_clock) whose low-energy states encode the entire time-history of the computation, so that estimating the ground-state energy to inverse-polynomial accuracy decides acceptance. A key physical corollary is that because efficient ground-state preparation would require inverse-polynomial overlap achievable by phase estimation, systems whose ground states are hard to prepare (disordered spin glasses) are ones neither engineered devices nor nature can relax into efficiently.
This concept, from quantum computational complexity theory (a subfield bridging quantum information science and computational complexity), establishes that finding the ground state and estimating the…