Learning quantum Gibbs states locally and efficiently

• URL: http://arxiv.org/abs/2504.02706v1
• Date: Thu, 03 Apr 2025 15:42:23 GMT
• Title: Learning quantum Gibbs states locally and efficiently
• Authors: Chi-Fang Chen, Anurag Anshu, Quynh T. Nguyen,
• Abstract summary: Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences.<n>We present a learning algorithm that learns each local term of a $n$-qubit $D$-dimensional Hamiltonian to an additive error $epsilon$ with sample complexity.
• Score: 7.728643029778198
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any inverse temperature $\beta$, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of a $n$-qubit $D$-dimensional Hamiltonian to an additive error $\epsilon$ with sample complexity $\tilde{O}\left(\frac{e^{\mathrm{poly}(\beta)}}{\beta^2\epsilon^2}\right)\log(n)$. The protocol uses parallelizable local quantum measurements that act within bounded regions of the lattice and near-linear-time classical post-processing. Thus, our complexity is near optimal with respect to $n,\epsilon$ and is polynomially tight with respect to $\beta$. We also give a learning algorithm for Hamiltonians with bounded interaction degree with sample and time complexities of similar scaling on $n$ but worse on $\beta, \epsilon$. At the heart of our algorithm is the interplay between locality, the Kubo-Martin-Schwinger condition, and the operator Fourier transform at arbitrary temperatures.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  We give a complexity-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians. We show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances.
  arXiv  Detail & Related papers  (2024-01-25T05:01:02Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Learning many-body Hamiltonians with Heisenberg-limited scaling [3.460138063155115]
  We propose the first algorithm to achieve the Heisenberg limit for learning interacting $N$-qubit local Hamiltonian. After a total evolution time of $mathcalO(epsilon-1)$, the proposed algorithm can efficiently estimate any parameter in the $N$-qubit Hamiltonian to $epsilon$-error with high probability.
  arXiv  Detail & Related papers  (2022-10-06T16:30:51Z)
• Quantum simulation of real-space dynamics [7.143485463760098]
  We conduct a systematic study of quantum algorithms for real-space dynamics. We give applications to several computational problems, including faster real-space simulation of quantum chemistry.
  arXiv  Detail & Related papers  (2022-03-31T13:01:51Z)
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states [0.9453554184019105]
  We show how to learn the coefficients of a Hamiltonian to error $varepsilon$ with sample complexity $S = O(log N/(betavarepsilon)2)$ and time linear in the sample size, $O(S N)$. In the appendix, we show virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e-it Hilon in a small $t regime with similar sample and time complexity.
  arXiv  Detail & Related papers  (2021-08-10T18:00:49Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.