Sample-efficient learning of quantum many-body systems.

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi SoleimanifararXiv 2020 · DOI · OpenReview

TL;DR

This paper introduces the first provably sample-efficient algorithm for learning the Hamiltonian of a quantum many-body system from its thermal (Gibbs) state. The authors demonstrate that a number of samples polynomial in the system size is both necessary and sufficient for this task, a significant step towards applying machine learning to quantum physics.

What Problem Does This Paper Address?

Understanding and controlling quantum many-body systems is a central challenge in physics and quantum computing. A key aspect of this is learning the system's Hamiltonian, which dictates its behavior. This problem is analogous to learning graphical models (like Boltzmann machines) in classical machine learning, a well-studied area with efficient algorithms. However, directly translating classical methods to the quantum realm has been difficult due to fundamental differences, such as the non-commutativity of quantum operators. Specifically, the authors address the "quantum Hamiltonian learning problem": given samples of a quantum system's thermal state, can we efficiently learn the parameters of its Hamiltonian? While classical counterparts are well-understood, a rigorous, sample-efficient solution for the quantum case, especially for spatially local Hamiltonians, was lacking.

Methods

The core of the paper's contribution lies in developing a sample-efficient algorithm based on maximum entropy estimation. The authors first establish that the local marginals of the Gibbs state act as sufficient statistics for learning the Hamiltonian. This allows them to frame the problem as a maximum entropy optimization problem.

A key technical hurdle is that the classical proof of strong convexity for partition functions relies on the Markov property, which doesn't hold in the quantum case. To overcome this, the authors introduce novel techniques:

  • Establishing strong convexity of the log-partition function for quantum systems: This is a crucial technical contribution, proving that the objective function is well-behaved for optimization, even without the Markov property.
  • Developing a lower bound on the variance of quasi-local operators: This is a significant result in itself, providing a tool to analyze quantum systems that doesn't rely on classical assumptions.
  • Adapting classical optimization techniques: They leverage stochastic convex optimization frameworks and adapt them to the quantum setting, carefully handling statistical errors in the estimated marginals.

Datasets

Not discussed in the paper. The "data" consists of samples drawn from the Gibbs state of a quantum system, which are generated rather than pre-existing datasets.

Key Insights and Ideas

  • Quantum systems can be learned efficiently from thermal states: The paper demonstrates that, unlike some other quantum learning tasks, learning a local Hamiltonian from its Gibbs state is sample-efficient, requiring only a polynomial number of samples in the system size.
  • Strong convexity is key, even without the Markov property: The authors show that the strong convexity of the log-partition function is achievable in quantum systems, a property that classical methods heavily rely on, but which requires new mathematical tools in the quantum domain.
  • Local marginals are sufficient statistics: This insight allows for a direct translation of classical maximum entropy estimation techniques to the quantum Hamiltonian learning problem.
  • Variance of quasi-local operators as a fundamental quantity: The paper highlights the importance of bounding the variance of these operators, providing a new avenue for analyzing quantum systems.

Key Results

  • Sample-efficient algorithm: The paper presents the first algorithm for learning spatially local quantum Hamiltonians from Gibbs state samples with provable sample complexity.
  • Upper bound on sample complexity: The number of samples required is shown to be $N = O\left(\frac{m^3 c^2 \log(m/\delta)}{\beta^2 \epsilon^2}\right)$, where $m$ is the number of interaction terms, $\beta$ is the inverse temperature, $\epsilon$ is the desired accuracy, and $\delta$ is the failure probability. For spatially local Hamiltonians, $m = O(n)$ (where $n$ is the number of qudits), leading to a sample complexity polynomial in $n$.
  • Lower bound on sample complexity: A matching lower bound of $\Omega\left(\frac{\sqrt{m} + \log(1/\delta)}{\beta \epsilon^2}\right)$ is also established, showing that the derived upper bound is tight up to polynomial factors.
  • Strong convexity result: The paper proves that the log-partition function of a quantum many-body system is strongly convex, a critical property for the optimization algorithm.

Limitations and Future Work

  • Computational Complexity: While the sample complexity is efficient, the paper acknowledges that the maximum entropy estimation approach can lead to computationally expensive algorithms, as approximating the partition function is NP-hard. The authors leave the development of efficient running-time algorithms for future work.
  • Lower Bound Improvement: The current lower bound on variance is for any constant inverse-temperature $\beta$. Improving this bound, ideally to one independent of system size under physically motivated conditions, is an open question.
  • Commuting Hamiltonians: The authors suggest that their bounds could be improved for commuting Hamiltonians.
  • Calibrated Quantum Computers: Exploring the use of calibrated quantum computers or Gibbs samplers for solving the optimization problem is proposed as a future direction.
  • Refined Objective Functions: Developing more refined objective functions for quantum Hamiltonian learning, analogous to those for classical problems, is a significant future research avenue.

Summary updated

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.
BibTeX
@misc{anshu2020sample,
  author = {Anurag Anshu and Srinivasan Arunachalam and Tomotaka Kuwahara and Mehdi Soleimanifar},
  title = {{Sample-efficient learning of quantum many-body systems.}},
  year = {2020},
  eprint = {2004.07266},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.07266},
}
Figure