Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914087962673152 |
|---|---|
| author | Haah, Jeongwan Kothari, Robin Tang, Ewin |
| author_facet | Haah, Jeongwan Kothari, Robin Tang, Ewin |
| contents | We study the problem of learning a Hamiltonian $H$ to precision $\varepsilon$, supposing we are given copies of its Gibbs state $ρ=\exp(-βH)/\operatorname{Tr}(\exp(-βH))$ at a known inverse temperature $β$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $ρ$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $β$) regime, their algorithm has sample complexity poly$(N, 1/β,1/\varepsilon)$ and can be implemented with polynomial, but suboptimal, time complexity.
In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S = O(\log N/(β\varepsilon)^{2})$ and time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal.
In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime with similar sample and time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_04842 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Optimal learning of quantum Hamiltonians from high-temperature Gibbs states Haah, Jeongwan Kothari, Robin Tang, Ewin Quantum Physics Data Structures and Algorithms Machine Learning We study the problem of learning a Hamiltonian $H$ to precision $\varepsilon$, supposing we are given copies of its Gibbs state $ρ=\exp(-βH)/\operatorname{Tr}(\exp(-βH))$ at a known inverse temperature $β$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $ρ$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $β$) regime, their algorithm has sample complexity poly$(N, 1/β,1/\varepsilon)$ and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S = O(\log N/(β\varepsilon)^{2})$ and time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime with similar sample and time complexity. |
| title | Optimal learning of quantum Hamiltonians from high-temperature Gibbs states |
| topic | Quantum Physics Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2108.04842 |