Improved algorithms for learning quantum Hamiltonians, via flat polynomials

Shyam Narayanan
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4360-4385, 2025.

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 (2024) 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 Bakshi et al.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-narayanan25a, title = {Improved algorithms for learning quantum Hamiltonians, via flat polynomials}, author = {Narayanan, Shyam}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {4360--4385}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/narayanan25a/narayanan25a.pdf}, url = {https://proceedings.mlr.press/v291/narayanan25a.html}, 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 (2024) 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 Bakshi et al.} }
Endnote
%0 Conference Paper %T Improved algorithms for learning quantum Hamiltonians, via flat polynomials %A Shyam Narayanan %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-narayanan25a %I PMLR %P 4360--4385 %U https://proceedings.mlr.press/v291/narayanan25a.html %V 291 %X 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 (2024) 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 Bakshi et al.
APA
Narayanan, S.. (2025). Improved algorithms for learning quantum Hamiltonians, via flat polynomials. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:4360-4385 Available from https://proceedings.mlr.press/v291/narayanan25a.html.

Related Material