Hamiltonian Complexity in the Thermodynamic Limit
summary
Proves a fixed, translationally invariant 2D Hamiltonian whose thermodynamic-limit ground energy density encodes an entire function: each bit of the infinite sum records the ground energy of a 1D finite chain sitting on Robinson tiling squares of size 4^{k^2}. Construction uses a cyclical clock with penalties giving the matrix as a Laplacian of a cycle so lowest eigenvalues follow 1 minus cos(pi/L), enabling exact analytic bounds; result is containment in FP^QMA_exp and hardness for FP^NEXP, with a gap from uncontrolled invalid queries.
AI-written summary · about
chapters (12)
- 0:00Introduction to the problem
- 1:26The role of QMA in complexity
- 3:28Thermodynamic limit challenges
- 6:56Computational complexity goals
- 8:24Variations of translational invariance
- 11:01Formalizing the 2D grid problem
- 13:57Encoding functions into Hamiltonians
- 17:04Construction and analytical bounds
- 21:22Finite vs infinite systems
- 24:58Implementing the cost function
- 33:04Open questions and conclusions
- 35:42Q&A session
related talks
01h 06mHow Hamiltonian complexity differs from quantum chemistry
48mIntroduction To Commuting Local Hamiltonian Problems
24mA subpolynomial-time algorithm for the free energy of one-dimensional...
12mShort Proof of a Spectral Chernoff Bound for Local Hamiltonians
50mMaking the Leap to Quantum PCPs
49mCircuit lower bounds for low-energy states of quantum code Hamiltonians
16mRobust Quantum Entanglement at (nearly) Room Temperature
01h 09mGap Amplification for Local Hamiltonians with Combinatorial Soundness