Finding Eigenvalues in Exponential Size Space:...
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22·
summary
An algorithm finds a principal eigenvalue and eigenvector of an exponentially large local Hamiltonian under the promise the target has a succinct description as matrix product states with polynomial bond dimension. It iteratively halves effective dimension by random subspace projections and re-expands using an approximate ground state projection built from scaled Chebyshev polynomials, keeping entanglement bounded so the final space is polynomial and solvable by ordinary linear algebra. The procedure is provable in 1D with a spectral-gap or polynomial low-energy band; it fails to extend efficiently to 2D.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 2:25The Problem
- 3:20Local Hamiltonian
- 5:45Intuition
- 11:30Matrix Product States
- 14:00History of Success
- 17:22Area Law
- 18:25Renormalisation Group
- 22:01Constraint Satisfaction
- 35:41Steps
- 38:22Applying operators
- 40:03H restricted
- 42:08Approximate ground state projection
- 51:11The Area Law
related talks
01h 07mEfficient Classical Simulation of Many-body Systems with Local Integrals of Motion
35mConvergence Theory for Iterative Eigensolvers
01h 01mA Polynomial-time Algorithm for Finding Ground States of Gapped Local Hamiltonians in 1D
12mShort Proof of a Spectral Chernoff Bound for Local Hamiltonians
48mTesting Positive Semidefiniteness and Eigenvalue Approximation
01h 15mDissipative State Preparation and the Dissipative Quantum Eigensolver
01h 11mOptimization and Sampling Under Symmetry: Part 1 -- Examples
56mSome Probabilistic Uses of Dirichlet Eigenvectors