Short proof of a spectral Chernoff bound for local Hamiltonians

2020/09/10 by Nilin Abrahamsen, Abrahamsen, Nilin · 1 citation
Mathematics · #FOS: Physical sciences #Graph theory and applications #Mathematical Physics (math-ph) #Quantum Physics (quant-ph) #Random Matrices and Applications #Spectral Theory in Mathematical Physics

paper · pdf · doi:10.48550/arxiv.2009.04993

openalex publication_date 2020/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a simple proof of a Chernoff bound for the spectrum of a k-local Hamiltonian based on Weyl's inequalities. The complexity of estimating the spectrum's ε(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ε(n)=d^-n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a>1 such that the problem is trivial for ε(n)=a^-n. We note that a related Chernoff bound due to Kuwahara and Saito (Ann. Phys. '20) for a generalized problem is also sufficient to establish such a dichotomy, its proof relying on a careful analysis of the cluster expansion.

Cited by

• Non-iid hypothesis testing: from classical to quantum

Related

• Simple algorithms to test and learn local Hamiltonians
• Two remarks on the local Hamiltonian problem
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• The 2-local Hamiltonian problem encompasses NP
• A Note on the Complexity of the Spectral Gap Problem