Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

Sample-efficient learning of quantum many-body systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar

Published Nov 1, 2020• 10 citations
Publisher

Abstract

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

DOI
10.1109/focs46700.2020.00069

Related papers

Optimal Quantum Algorithm for Gibbs State Preparation

Cambyse Rouzé, Daniel Stilck França, Alvaro Martin Alhambra

It is of great interest to understand the thermalization of open quantum many-body systems, and how quantum computers are able to efficiently simulate that process. A recently introduced dissipative evolution, inspired by existing models of open system thermalization, has been shown to be efficiently implementable on a quantum computer. Here, we prove that, at high enough temperatures, this evolution reaches the Gibbs state in time scaling logarithmically with system size. The result holds for Hamiltonians that satisfy the Lieb-Robinson bound, such as local Hamiltonians on a lattice, and includes long-range systems. To the best of our knowledge, these are the first results rigorously establishing the rapid mixing property of high-temperature quantum Gibbs samplers, which is known to give the fastest possible speed for thermalization in the many-body setting. We then apply our result to the problem of estimating partition functions at high temperature, showing an improved performance over previous classical and quantum algorithms.

arXiv:2411.04885•Physical Review Letters•Jan 14, 2026•16 citations

An (almost) efficient classical algorithm for sampling from typical Gibbs states

Saleh Naghdi, Eric R. Anschuetz

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

quant-pharXiv:2609.40250•Oct 1, 2026•0 citations

The stationarity test: a framework for learning quantum many-body systems from their thermal states

Thiago Bergamaschi

The task of learning the Hamiltonian interactions governing a quantum system, given samples of its thermal (or 'Gibbs') states, is a foundational question at the intersection of quantum learning theory and many-body physics. In this paper, we draw connections to the quantum Gibbs sampling literature to introduce a natural learning algorithm we call the stationarity test: which simply "guesses" the Hamiltonian, and measures the rate-of-change of local observables, under the associated detailed-balanced quantum Markov chain [CKG23]. We leverage the stationarity test to address the following applications: 1. To give the first learning algorithm for the underlying interaction graph, i.e. structure learning, of lattice Hamiltonians at all temperatures, given copies of their Gibbs states. 2. To give the first learning algorithm for the coefficients of a lattice Hamiltonian, given only copies of its thermal metastable states, modeled as the "local minima" of the free energy. 3. In addition, we present a refinement to the recent area law for thermal metastable states [BCV25], which holds in the thermodynamic limit. Our learning algorithms are rigorous, time-efficient, and nearly sample-optimal in system size and accuracy. At a technical level, our arguments are based on new approximate locality and convexity properties for the quantum Fisher information of these Gibbs sampling algorithms.

quant-pharXiv:2610.01074•Oct 2, 2026•0 citations

On the sample complexity of quantum Boltzmann machine learning

Luuk Coopmans, Marcello Benedetti

Abstract Quantum Boltzmann machines (QBMs) are machine-learning models for both classical and quantum data. We give an operational definition of QBM learning in terms of the difference in expectation values between the model and target, taking into account the polynomial size of the data set. By using the relative entropy as a loss function, this problem can be solved without encountering barren plateaus. We prove that a solution can be obtained with stochastic gradient descent using at most a polynomial number of Gibbs states. We also prove that pre-training on a subset of the QBM parameters can only lower the sample complexity bounds. In particular, we give pre-training strategies based on mean-field, Gaussian Fermionic, and geometrically local Hamiltonians. We verify these models and our theoretical findings numerically on a quantum and a classical data set. Our results establish that QBMs are promising machine learning models.

arXiv:2306.14969•Communications Physics•Aug 14, 2024•27 citations

Thermal-Drift Sampling: Generating Thermal Ensembles for Learning Many-Body Systems

Jiyu Jiang, Mingrui Jing, Jizhe Lai +2 more

Thermal equilibrium states of many-body Hamiltonians are essential for probing quantum chaos, finite-temperature phases of matter, and training quantum machine learning models, yet generating large collections of such states across different Hamiltonians remains costly with existing methods. We introduce a powerful operation, the quantum thermal-drift channel, to construct a measurement-controlled sampling algorithm that autonomously generates thermal states together with their system Hamiltonians as labels for general physical models. We prove that our algorithm is efficient: the total gate count scales polynomially with system size and quadratically with inverse temperature, providing the first polynomial resource bound for random thermal state generation. We characterize the distribution of sampled Hamiltonians as a normal distribution reweighted by partition functions, which quantifies a trade-off between sampling accuracy and effective label range. Level-spacing statistics computed from sampled thermal states of a 2D transverse-field Ising model show a crossover to Wigner-Dyson universality, confirming that the sampler captures nontrivial chaotic correlations. Finally, a variational quantum classifier trained on the generated dataset achieves near-optimal accuracy in predicting Hamiltonian properties of unseen states. These results establish a scalable, quantum-native route for thermodynamic simulation and labeled quantum data generation in many-body systems.

quant-pharXiv:2602.05912•Feb 6, 2026•0 citations

Provable learning of quantum states with graphical models

Liming Zhao, Naixu Guo, Ming-Xing Luo +1 more

The complete learning of any unknown many-body systems requires a number of samples exponentially in the particle number. Several works consider subclasses of physical meaningful states such as stabilizer states or high-temperature Gibbs states that can be learned in polynomial sample complexity. Others consider to learn states under special assumptions, such as PAC learning and shadow tomography. In this work, we consider learning many-body systems that can be approximately represented by restricted Boltzmann machines (RBMs). We exhibit robustness results for efficient provable two-hop neighborhood learning method for ferromagnetic and locally consistent RBMs. We consider the L p norm as a distance measure, including both total variation distance and max-norm distance in the limit. We show that various quantum states can be learned with a sample complexity exponentially better than the naive state tomography. Our results establish a broader theoretical framework for the efficient learning of complex quantum many-body systems.

arXiv:2309.09235•Physical Review Research•Dec 8, 2025•0 citations
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.
It is of great interest to understand the thermalization of open quantum many-body systems, and how quantum computers are able to efficiently simulate that process. A recently introduced dissipative evolution, inspired by existing models of open system thermalization, has been shown to be efficiently implementable on a quantum computer. Here, we prove that, at high enough temperatures, this evolution reaches the Gibbs state in time scaling logarithmically with system size. The result holds for Hamiltonians that satisfy the Lieb-Robinson bound, such as local Hamiltonians on a lattice, and includes long-range systems. To the best of our knowledge, these are the first results rigorously establishing the rapid mixing property of high-temperature quantum Gibbs samplers, which is known to give the fastest possible speed for thermalization in the many-body setting. We then apply our result to the problem of estimating partition functions at high temperature, showing an improved performance over previous classical and quantum algorithms.
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum ppp-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum ppp-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum ppp-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
The task of learning the Hamiltonian interactions governing a quantum system, given samples of its thermal (or 'Gibbs') states, is a foundational question at the intersection of quantum learning theory and many-body physics. In this paper, we draw connections to the quantum Gibbs sampling literature to introduce a natural learning algorithm we call the stationarity test: which simply "guesses" the Hamiltonian, and measures the rate-of-change of local observables, under the associated detailed-balanced quantum Markov chain [CKG23]. We leverage the stationarity test to address the following applications: 1. To give the first learning algorithm for the underlying interaction graph, i.e. structure learning, of lattice Hamiltonians at all temperatures, given copies of their Gibbs states. 2. To give the first learning algorithm for the coefficients of a lattice Hamiltonian, given only copies of its thermal metastable states, modeled as the "local minima" of the free energy. 3. In addition, we present a refinement to the recent area law for thermal metastable states [BCV25], which holds in the thermodynamic limit. Our learning algorithms are rigorous, time-efficient, and nearly sample-optimal in system size and accuracy. At a technical level, our arguments are based on new approximate locality and convexity properties for the quantum Fisher information of these Gibbs sampling algorithms.
Abstract Quantum Boltzmann machines (QBMs) are machine-learning models for both classical and quantum data. We give an operational definition of QBM learning in terms of the difference in expectation values between the model and target, taking into account the polynomial size of the data set. By using the relative entropy as a loss function, this problem can be solved without encountering barren plateaus. We prove that a solution can be obtained with stochastic gradient descent using at most a polynomial number of Gibbs states. We also prove that pre-training on a subset of the QBM parameters can only lower the sample complexity bounds. In particular, we give pre-training strategies based on mean-field, Gaussian Fermionic, and geometrically local Hamiltonians. We verify these models and our theoretical findings numerically on a quantum and a classical data set. Our results establish that QBMs are promising machine learning models.
Thermal equilibrium states of many-body Hamiltonians are essential for probing quantum chaos, finite-temperature phases of matter, and training quantum machine learning models, yet generating large collections of such states across different Hamiltonians remains costly with existing methods. We introduce a powerful operation, the quantum thermal-drift channel, to construct a measurement-controlled sampling algorithm that autonomously generates thermal states together with their system Hamiltonians as labels for general physical models. We prove that our algorithm is efficient: the total gate count scales polynomially with system size and quadratically with inverse temperature, providing the first polynomial resource bound for random thermal state generation. We characterize the distribution of sampled Hamiltonians as a normal distribution reweighted by partition functions, which quantifies a trade-off between sampling accuracy and effective label range. Level-spacing statistics computed from sampled thermal states of a 2D transverse-field Ising model show a crossover to Wigner-Dyson universality, confirming that the sampler captures nontrivial chaotic correlations. Finally, a variational quantum classifier trained on the generated dataset achieves near-optimal accuracy in predicting Hamiltonian properties of unseen states. These results establish a scalable, quantum-native route for thermodynamic simulation and labeled quantum data generation in many-body systems.
The complete learning of any unknown many-body systems requires a number of samples exponentially in the particle number. Several works consider subclasses of physical meaningful states such as stabilizer states or high-temperature Gibbs states that can be learned in polynomial sample complexity. Others consider to learn states under special assumptions, such as PAC learning and shadow tomography. In this work, we consider learning many-body systems that can be approximately represented by restricted Boltzmann machines (RBMs). We exhibit robustness results for efficient provable two-hop neighborhood learning method for ferromagnetic and locally consistent RBMs. We consider the L p norm as a distance measure, including both total variation distance and max-norm distance in the limit. We show that various quantum states can be learned with a sample complexity exponentially better than the naive state tomography. Our results establish a broader theoretical framework for the efficient learning of complex quantum many-body systems.