Establishes n^{Ω(k)} lower bounds for learning k-local Hamiltonians from time evolution, including single-coefficient and effective Hamiltonian learning, via a new connection to Boolean function analysis.
Narayanan
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We give an improved algorithm for learning a quantum Hamiltonian given copies of its Gibbs state, that can succeed at any temperature. Specifically, we improve over the work of Bakshi, Liu, Moitra, and Tang [BLMT24], by reducing the sample complexity and runtime dependence to singly exponential in the inverse-temperature parameter, as opposed to doubly exponential. Our main technical contribution is a new flat polynomial approximation to the exponential function, with significantly lower degree than the flat polynomial approximation used in [BLMT24].
fields
quant-ph 2representative citing papers
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.
citing papers explorer
-
Lower Bounds for Learning Hamiltonians from Time Evolution
Establishes n^{Ω(k)} lower bounds for learning k-local Hamiltonians from time evolution, including single-coefficient and effective Hamiltonian learning, via a new connection to Boolean function analysis.
-
Provable learning separation for predicting time-evolution of quantum many-body systems
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.