# Learning quantum many-body systems from a few copies

Cambyse Rouzé, Daniel Stilck França

► To cite this version:

Cambyse Rouzé, Daniel Stilck França. Learning quantum many-body systems from a few copies. Quantum, 2024, 8, pp.1319. 10.22331/q-2024-04-30-1319. hal-04622145

HAL Id: hal-04622145

https://hal.science/hal-04622145

Submitted on 24 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# Learning quantum many-body systems from a few copies

Cambyse Rouzé, Daniel Stilck França

► To cite this version:

Cambyse Rouzé, Daniel Stilck França. Learning quantum many-body systems from a few copies. Quantum, 2024, 8, pp.1319. 10.22331/q-2024-04-30-1319. hal-04622145

HAL Id: hal-04622145

https://hal.science/hal-04622145v1

Submitted on 24 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Learning quantum many-body systems from a few copies

Cambyse Rouzé¹ and Daniel Stilck França²,³

¹Department of Mathematics, Technische Universität München, 85748 Garching, Germany

²QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark

³Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France
11.03.2024

Estimating physical properties of quantum states from measurements is one of the most fundamental tasks in quantum science. In this work, we identify conditions on states under which it is possible to infer the expectation values of all quasi-local observables of a state from a number of copies that scale polylogarithmically with the system's size and polynomially on the locality of the target observables. We show that this constitutes a provable exponential improvement in the number of copies over state-of-the-art tomography protocols. We achieve our results by combining the maximum entropy method with tools from the emerging fields of classical shadows and quantum optimal transport. The latter allows us to fine-tune the error made in estimating the expectation value of an observable in terms of how local it is and how well we approximate the expectation value of a fixed set of few-body observables. We conjecture that our condition holds for all states exhibiting some form of decay of correlations and establish it for several subsets thereof. These include widely studied classes of states such as one-dimensional thermal and high-temperature Gibbs states of local commuting Hamiltonians on arbitrary hypergraphs or outputs of shallow circuits. Moreover, we show improvements of the maximum entropy method beyond the sample complexity that are of independent interest. These include identifying regimes in which it is possible to perform the postprocessing efficiently as well as novel bounds on the condition number of covariance matrices of many-body states.

# 1 Introduction

The subject of quantum tomography has as its goal devising methods for efficiently obtaining a classical description of a quantum system from access to experimental data. However, all tomographic methods for general quantum states inevitably require resources that scale exponentially in the size of the sys-

tem [33, 55], be it in terms of the number of samples required or the post-processing needed to perform the task.

Fortunately, most of the physically relevant quantum systems can be described in terms of a (quasi)-local structure. These range from that of a local interaction Hamiltonian corresponding to a finite temperature Gibbs state to that of a shallow quantum circuit. Hence, locality is a physically motivated requirement that brings the number of parameters describing the system to a tractable number. Effective tomographic procedures should be able to incorporate this information. And, indeed, starting from physically motivated assumptions, many protocols in the literature achieve a good recovery guarantee in trace distance from a number of copies that scales *polynomially* with system size [5, 10, 23, 29, 64, 67].

Furthermore, in many cases, one is interested in learning only physical properties of the state on which tomography is being performed. These are mostly encoded into the expectation values of quasi-local observables that often only depend on reduced density matrices of subregions of the system. By Helstrom's theorem, obtaining a good recovery guarantee in trace distance is equivalent to demanding that the expectation value of all bounded observables are close for the two states, a much larger class of observables than quasi-local ones.

It is, in turn, desirable to design tomographic procedures that can take advantage of the fact that we wish to only approximate quasi-local observables, instead of demanding a recovery in trace distance. And some methods in the literature take advantage of that. For instance, the overlapping tomography or classical shadows methods of [22, 24, 40, 43] allow for approximately learning all *k*-local reduced density matrices of an *n*-qubit state with failure probability *δ* using $O(e^{ck}k \log(n\delta^{-1})\epsilon^{-2})$ copies without imposing any assumptions on the underlying state. This constitutes an exponential improvement in the system size compared to the previously mentioned many-body setting at the expense of an undesirable exponential dependency in the locality of the observables.

In light of the previous discussion, it is natural to ask the guiding question of our work: *is it possible to devise a tomography protocol that has a sample complexity that is logarithmic in system size and polyno-

Cambyse Rouzé: rouzecambyse@gmail.com

Daniel Stilck França: daniel.stilck_franca@ens-lyon.fr
Learning quantum many-body systems from a few copies

Cambyse Rouzé¹ and Daniel Stilck França²,³

¹Department of Mathematics, Technische Universität München, 85748 Garching, Germany

²QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark

³Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France
11.03.2024

Estimating physical properties of quantum states from measurements is one of the most fundamental tasks in quantum science. In this work, we identify conditions on states under which it is possible to infer the expectation values of all quasi-local observables of a state from a number of copies that scale polylogarithmically with the system's size and polynomially on the locality of the target observables. We show that this constitutes a provable exponential improvement in the number of copies over state-of-the-art tomography protocols. We achieve our results by combining the maximum entropy method with tools from the emerging fields of classical shadows and quantum optimal transport. The latter allows us to fine-tune the error made in estimating the expectation value of an observable in terms of how local it is and how well we approximate the expectation value of a fixed set of few-body observables. We conjecture that our condition holds for all states exhibiting some form of decay of correlations and establish it for several subsets thereof. These include widely studied classes of states such as one-dimensional thermal and high-temperature Gibbs states of local commuting Hamiltonians on arbitrary hypergraphs or outputs of shallow circuits. Moreover, we show improvements of the maximum entropy method beyond the sample complexity that are of independent interest. These include identifying regimes in which it is possible to perform the postprocessing efficiently as well as novel bounds on the condition number of covariance matrices of many-body states.

# 1 Introduction

The subject of quantum tomography has as its goal devising methods for efficiently obtaining a classical description of a quantum system from access to experimental data. However, all tomographic methods for general quantum states inevitably require resources that scale exponentially in the size of the sys-

tem [33, 55], be it in terms of the number of samples required or the post-processing needed to perform the task.

Fortunately, most of the physically relevant quantum systems can be described in terms of a (quasi)-local structure. These range from that of a local interaction Hamiltonian corresponding to a finite temperature Gibbs state to that of a shallow quantum circuit. Hence, locality is a physically motivated requirement that brings the number of parameters describing the system to a tractable number. Effective tomographic procedures should be able to incorporate this information. And, indeed, starting from physically motivated assumptions, many protocols in the literature achieve a good recovery guarantee in trace distance from a number of copies that scales *polynomially* with system size [5, 10, 23, 29, 64, 67].

Furthermore, in many cases, one is interested in learning only physical properties of the state on which tomography is being performed. These are mostly encoded into the expectation values of quasi-local observables that often only depend on reduced density matrices of subregions of the system. By Helstrom's theorem, obtaining a good recovery guarantee in trace distance is equivalent to demanding that the expectation value of all bounded observables are close for the two states, a much larger class of observables than quasi-local ones.

It is, in turn, desirable to design tomographic procedures that can take advantage of the fact that we wish to only approximate quasi-local observables, instead of demanding a recovery in trace distance. And some methods in the literature take advantage of that. For instance, the overlapping tomography or classical shadows methods of [22, 24, 40, 43] allow for approximately learning all *k*-local reduced density matrices of an *n*-qubit state with failure probability *δ* using $O(e^{ck}k \log(n\delta^{-1})\epsilon^{-2})$ copies without imposing any assumptions on the underlying state. This constitutes an exponential improvement in the system size compared to the previously mentioned many-body setting at the expense of an undesirable exponential dependency in the locality of the observables.

In light of the previous discussion, it is natural to ask the guiding question of our work: *is it possible to devise a tomography protocol that has a sample complexity that is logarithmic in system size and polyno-

Cambyse Rouzé: rouzecambyse@gmail.com

Daniel Stilck França: daniel.stilck_franca@ens-lyon.fr
mial in the locality of the observables we wish to estimate?

At first, this might sound like a tall order: as we show in Section G by importing results of [27], even if we start from the assumption that the underlying state we wish to learn is a high-temperature product state with $n$ qubits, the number of samples required to obtain an estimate that is $\epsilon$ close in trace distance from the target state scales like $\Omega(n\epsilon^{-2})$. Thus, to obtain a sample complexity that is logarithmic in system size we cannot quantify closeness in trace distance and need to resort to more physically motivated distinguishability measures. Moreover, we show in Section G that even for product states the classical shadows protocol will fail to produce a good estimate for $k$-local observables if the number of samples is not exponential in $k$. We conclude that protocols like shadow tomography on their own cannot achieve our goal of a sample complexity that is polynomial in the locality of the underlying observables and needs to be combined with other estimation methods in a nontrivial way.

Despite these challenges, we provide an affirmative answer for the guiding question above for a large class of physically motivated states. We achieve this by combining two insights. First, we observe that recently introduced Wasserstein distances [21, 26, 31, 45, 56, 59] are better suited than the trace distance to estimate by how much the expectation values of physically motivated observables can differ on two states. We introduce these distances and motivate this claim below. But in summary, the Wasserstein distance quantifies how well we can distinguish states through observables whose expectation value does not change much when we apply a unitary acting only on a few qubits. By focusing on the Wasserstein distance instead of the trace distance we can bypass the $\Omega(n\epsilon^{-2})$ lower bound we mentioned previously. Intuitively, this means that exponentially fewer samples are required to estimate all such local expectation values than arbitrary, global ones.

The second insight is to combine techniques from quantum optimal transport with the well-established maximum entropy method [42] and the classical shadows protocols in a novel way. In particular, we will demonstrate that so-called transportation cost inequalities [21, 26, 31, 45, 56, 59] allow us to control how well we approximate the expectation value of $k$-local observables by how well we approximate certain observables that only act on a constant number of qubits. Thus, we only use the shadows protocol to estimate the expectation of many observables that are highly local, the regime in which classical shadows excel, and bypass the exponential scaling of only using shadows for such an estimation task. This way we obtain a provable exponential improvement over known methods of many-body tomography [5, 10, 23, 29, 64, 67] that focus on the trace dis-

tance and recent shadow tomography or overlapping tomography techniques [22, 24, 40, 43], as summarized in Table 1.

Examples for which we obtain exponential improvements include thermal states of 1D systems and high-temperature thermal states of commuting Hamiltonians on arbitrary hypergraphs and outputs of shallow circuits. Furthermore, based on results by [34, 49], we conjecture that our results should hold for any high-temperature Gibbs state, even. More ambitiously, we conjecture that our results can be extended to states exhibiting exponential decay of correlations. This would allow us to extend our findings to classes of states that are not known to be tractable classically, such as ground states of gapped Hamiltonians in higher dimensional lattices [39].

The main ingredient to obtain our improvements are so-called transportation cost (TC) inequalities [61]. They allow us to bound the difference of expectation values of Lipschitz observables, a concept we will review shortly, on two states by their relative entropy. Such inequalities constitute a powerful tool from the theory of optimal transport [65] and are traditionally used to prove sharp concentration inequalities [58, Chapter 3]. Moreover, they have been recently extended to quantum states [26, 56, 59]. By combining such inequalities with the maximum entropy principle, we are able to easily control the relative entropy between the states and, thus, the difference of expectation values of Lipschitz observables.

Our revisit of the maximum entropy principle is further motivated by recent breakthroughs in Hamiltonian learning [5, 34], shadow tomography [40], the understanding of correlations and computational complexity of quantum Gibbs states [35, 46, 49, 51, 52] and quantum functional inequalities [18, 26] that shed new light on this seasoned technique.

Before we summarize our contributions in more detail, we first define and revise the main concepts required for our results, namely Lipschitz observables, transportation cost inequalities and the maximum entropy principle.

## 1.1 Lipschitz observables

In the classical setting, given a metric $d$ on a sample space $S$, the regularity of a function $f: S \to \mathbb{R}$ can be quantified by its Lipschitz constant [58, Chapter 3]

$$ \|f\|_{\text{Lip}} = \sup_{x,y \in S} |f(x) - f(y)|/d(x,y). \quad (1) $$

For instance, if we consider functions on the $n$-dimensional hypercube $\{-1, 1\}^n$ endowed with the Hamming distance, the Lipschitz constant quantifies by how much a function can change per flipped spin. It should then be clear that physical quantities like average magnetization have a small Lipschitz constant. Some recent works [56, 59] extended this notion to the noncommutative setting and we will focus on the
mial in the locality of the observables we wish to estimate?

At first, this might sound like a tall order: as we show in Section G by importing results of [27], even if we start from the assumption that the underlying state we wish to learn is a high-temperature product state with $n$ qubits, the number of samples required to obtain an estimate that is $\epsilon$ close in trace distance from the target state scales like $\Omega(n\epsilon^{-2})$. Thus, to obtain a sample complexity that is logarithmic in system size we cannot quantify closeness in trace distance and need to resort to more physically motivated distinguishability measures. Moreover, we show in Section G that even for product states the classical shadows protocol will fail to produce a good estimate for $k$-local observables if the number of samples is not exponential in $k$. We conclude that protocols like shadow tomography on their own cannot achieve our goal of a sample complexity that is polynomial in the locality of the underlying observables and needs to be combined with other estimation methods in a nontrivial way.

Despite these challenges, we provide an affirmative answer for the guiding question above for a large class of physically motivated states. We achieve this by combining two insights. First, we observe that recently introduced Wasserstein distances [21, 26, 31, 45, 56, 59] are better suited than the trace distance to estimate by how much the expectation values of physically motivated observables can differ on two states. We introduce these distances and motivate this claim below. But in summary, the Wasserstein distance quantifies how well we can distinguish states through observables whose expectation value does not change much when we apply a unitary acting only on a few qubits. By focusing on the Wasserstein distance instead of the trace distance we can bypass the $\Omega(n\epsilon^{-2})$ lower bound we mentioned previously. Intuitively, this means that exponentially fewer samples are required to estimate all such local expectation values than arbitrary, global ones.

The second insight is to combine techniques from quantum optimal transport with the well-established maximum entropy method [42] and the classical shadows protocols in a novel way. In particular, we will demonstrate that so-called transportation cost inequalities [21, 26, 31, 45, 56, 59] allow us to control how well we approximate the expectation value of $k$-local observables by how well we approximate certain observables that only act on a constant number of qubits. Thus, we only use the shadows protocol to estimate the expectation of many observables that are highly local, the regime in which classical shadows excel, and bypass the exponential scaling of only using shadows for such an estimation task. This way we obtain a provable exponential improvement over known methods of many-body tomography [5, 10, 23, 29, 64, 67] that focus on the trace dis-

tance and recent shadow tomography or overlapping tomography techniques [22, 24, 40, 43], as summarized in Table 1.

Examples for which we obtain exponential improvements include thermal states of 1D systems and high-temperature thermal states of commuting Hamiltonians on arbitrary hypergraphs and outputs of shallow circuits. Furthermore, based on results by [34, 49], we conjecture that our results should hold for any high-temperature Gibbs state, even. More ambitiously, we conjecture that our results can be extended to states exhibiting exponential decay of correlations. This would allow us to extend our findings to classes of states that are not known to be tractable classically, such as ground states of gapped Hamiltonians in higher dimensional lattices [39].

The main ingredient to obtain our improvements are so-called transportation cost (TC) inequalities [61]. They allow us to bound the difference of expectation values of Lipschitz observables, a concept we will review shortly, on two states by their relative entropy. Such inequalities constitute a powerful tool from the theory of optimal transport [65] and are traditionally used to prove sharp concentration inequalities [58, Chapter 3]. Moreover, they have been recently extended to quantum states [26, 56, 59]. By combining such inequalities with the maximum entropy principle, we are able to easily control the relative entropy between the states and, thus, the difference of expectation values of Lipschitz observables.

Our revisit of the maximum entropy principle is further motivated by recent breakthroughs in Hamiltonian learning [5, 34], shadow tomography [40], the understanding of correlations and computational complexity of quantum Gibbs states [35, 46, 49, 51, 52] and quantum functional inequalities [18, 26] that shed new light on this seasoned technique.

Before we summarize our contributions in more detail, we first define and revise the main concepts required for our results, namely Lipschitz observables, transportation cost inequalities and the maximum entropy principle.

## 1.1 Lipschitz observables

In the classical setting, given a metric $d$ on a sample space $S$, the regularity of a function $f: S \to \mathbb{R}$ can be quantified by its Lipschitz constant [58, Chapter 3]

$$ \|f\|_{\text{Lip}} = \sup_{x,y \in S} |f(x) - f(y)|/d(x,y). \quad (1) $$

For instance, if we consider functions on the $n$-dimensional hypercube $\{-1, 1\}^n$ endowed with the Hamming distance, the Lipschitz constant quantifies by how much a function can change per flipped spin. It should then be clear that physical quantities like average magnetization have a small Lipschitz constant. Some recent works [56, 59] extended this notion to the noncommutative setting and we will focus on the
<table><caption>Table 1: Summary of underlying assumptions and sample complexity of other approaches to perform tomography on quantum many-body states.</caption><thead><tr><th>Structure</th><th>Assumptions on State</th><th>Assumptions on Observable</th><th>Samples</th></tr></thead><tbody><tr><td>Many-body tomography</td><td>Many-body</td><td>none</td><td>poly(n, ε<sup>-1</sup>) [5]</td></tr><tr><td>Classical Shadows</td><td>none</td><td>k-local</td><td>poly(e<sup>ck</sup>, log(n), ε<sup>-1</sup>) [40]</td></tr><tr><td>This work</td><td>Many-body+transportation</td><td>k-local</td><td>poly(k, log(n), ε<sup>-1</sup>)</td></tr></tbody></table>

approach of [56] in the main text. This is justified by the fact that it is more intuitive and technically simpler. For the approach followed in [56], the Lipschitz constant of an observable on $n$ qudits is defined as <fnref n="1" />

$$ \frac{\|O\|_{\text{Lip,\square}}}{\sqrt{n}} := \max_{1 \le i \le n} \max_{\substack{\rho, \sigma \in \mathcal{D}_{d^n} \\ \text{tr}_i[\rho] = \text{tr}_i[\sigma]}} \text{tr}[O(\rho - \sigma)], \quad (2) $$

where $\mathcal{D}_{d^n}$ denotes the set of $n$-qudit states. That is, $\|O\|_{\text{Lip,\square}}$ quantifies the amount by which the expectation value of $O$ changes for states that are equal when tracing out one site. It is clear that $\|O\|_{\text{Lip}} \le 2\sqrt{n}\|O\|_{\infty}$ always holds by Hölder's inequality, but it can be the case that $\|O\|_{\text{Lip,\square}} \ll \sqrt{n}\|O\|_{\infty}$. For instance, consider for some $k > 0$ the $n$-qubit observable

$$ O = n^{-1} \sum_{i=1}^{n} \otimes_{j=i}^{i+k} Z_j, \quad (3) $$

where for each site $j$, $Z_j$ denotes the Pauli observable $Z$ acting on site $j$ and we take addition modulo $n$. It is not difficult to see that $\|O\|_{\text{Lip,\square}} = 2kn^{-1/2}$, while $\|O\|_{\infty} = 1$. We refer to the discussion in Fig. 1 for another example.

Moreover, one can show that shallow local circuits or short-time local dynamics satisfying a Lieb-Robinson bound cannot substantially increase the Lipschitz constant of an observable when evolved in the Heisenberg picture. That is, if we have that $\Phi_t^*$ is the quantum channel that describes some local dynamics at time/depth $t$ in the Heisenberg picture and it satisfies a Lieb-Robinson bound, then we have:

$$ \|\Phi_t^*(O)\|_{\text{Lip,\square}} = O(e^{vt}\|O\|_{\text{Lip,\square}}), $$

where $v$ denotes the Lieb-Robinson velocity. This result is discussed in more detail in Section B.1 of the supplemental material. Thus, averages over local observables and short-time evolutions thereof all belong to the class of observables that have a small Lipschitz constant when compared to generic observables. These facts justify our claim that quasi-local observables are Lipschitz.

Once we are given a Lipschitz constant on observables or a set of quasi-local observables, we can define a Wasserstein-1 distance on states by duality [56, 59].

The latter quantifies how well we can distinguish two states by their action on regular or local observables and is given by

$$ W_1(\rho, \sigma) := \sup_{O:\|O\|_{\text{Lip,\square}} \le 1} \text{tr}[O(\rho - \sigma)]. \quad (4) $$

The definition (4) is in direct analogy with the variational definition of the trace distance, given by:

$$ \|\rho - \sigma\|_{\text{tr}} := \sup_{O:\|O\|_{\infty} \le 1} \text{tr}[O(\rho - \sigma)]. \quad (5) $$

Note, however, that the two quantities have different scalings. To illustrate this point, let us consider the observable in Eq. (3). If we measure the distance in trace distance, then we need that $\|\rho - \sigma\|_{\text{tr}} \le \epsilon$ to ensure that $\sigma$ approximates the expectation of value of $\rho$ up to $\epsilon$ on $O$. On the other hand, as $\|O\|_{\text{Lip,\square}} \le 2kn^{-1/2}$, the bound $W_1(\rho, \sigma) \le \frac{\epsilon\sqrt{n}}{2k}$ is sufficient to guarantee the same approximation. This difference in scaling is at the heart of our results, as we will see now.

## 1.2 Transportation cost inequalities

The paragraphs before motivated the idea that observables with a small Lipschitz constant capture quasilocal observables, and thus, that controlling the Wasserstein distance between two states gives rise to a more physically motivated distance measure than the trace distance. However, it is a priori not clear how to effectively control the Wasserstein distance between states, as it does not admit a closed formula in terms of eigenvalues like the trace distance.

In this work, we will achieve this by relating Wasserstein distances to the relative entropy between two states, $D(\rho||\sigma) := \text{tr}[\rho(\log(\rho) - \log(\sigma))]$, for $\sigma$ of full-rank. This can be achieved through the notion of a transportation cost inequality: an $n$-qudit state $\sigma$ is said to satisfy a transportation cost inequality with parameter $\alpha > 0$ if the Wasserstein distance of $\sigma$ to any other state $\rho$ can be controlled by their relative entropy, i.e.

$$ W_1(\rho, \sigma) \le \sqrt{\frac{D(\rho||\sigma)}{2\alpha}} \quad (6) $$

holds for all states $\rho \in \mathcal{D}_{d^n}$.

Such inequalities are particularly powerful whenever the constant $\alpha$ does not depend on the system size $n$ or does so at most inverse polylogarithmically,

<footnote n="1">¹the definition of [56] has a different normalization and does not have the $\sqrt{n}$ term. This normalization will be convenient to treat the constants of [59] and [56] on an equal footing.</footnote>
<table><caption>Table 1: Summary of underlying assumptions and sample complexity of other approaches to perform tomography on quantum many-body states.</caption><thead><tr><th>Structure</th><th>Assumptions on State</th><th>Assumptions on Observable</th><th>Samples</th></tr></thead><tbody><tr><td>Many-body tomography</td><td>Many-body</td><td>none</td><td>poly(n, ε<sup>-1</sup>) [5]</td></tr><tr><td>Classical Shadows</td><td>none</td><td>k-local</td><td>poly(e<sup>ck</sup>, log(n), ε<sup>-1</sup>) [40]</td></tr><tr><td>This work</td><td>Many-body+transportation</td><td>k-local</td><td>poly(k, log(n), ε<sup>-1</sup>)</td></tr></tbody></table>

approach of [56] in the main text. This is justified by the fact that it is more intuitive and technically simpler. For the approach followed in [56], the Lipschitz constant of an observable on $n$ qudits is defined as <fnref n="1" />

$$ \frac{\|O\|_{\text{Lip,\square}}}{\sqrt{n}} := \max_{1 \le i \le n} \max_{\substack{\rho, \sigma \in \mathcal{D}_{d^n} \\ \text{tr}_i[\rho] = \text{tr}_i[\sigma]}} \text{tr}[O(\rho - \sigma)], \quad (2) $$

where $\mathcal{D}_{d^n}$ denotes the set of $n$-qudit states. That is, $\|O\|_{\text{Lip,\square}}$ quantifies the amount by which the expectation value of $O$ changes for states that are equal when tracing out one site. It is clear that $\|O\|_{\text{Lip}} \le 2\sqrt{n}\|O\|_{\infty}$ always holds by Hölder's inequality, but it can be the case that $\|O\|_{\text{Lip,\square}} \ll \sqrt{n}\|O\|_{\infty}$. For instance, consider for some $k > 0$ the $n$-qubit observable

$$ O = n^{-1} \sum_{i=1}^{n} \otimes_{j=i}^{i+k} Z_j, \quad (3) $$

where for each site $j$, $Z_j$ denotes the Pauli observable $Z$ acting on site $j$ and we take addition modulo $n$. It is not difficult to see that $\|O\|_{\text{Lip,\square}} = 2kn^{-1/2}$, while $\|O\|_{\infty} = 1$. We refer to the discussion in Fig. 1 for another example.

Moreover, one can show that shallow local circuits or short-time local dynamics satisfying a Lieb-Robinson bound cannot substantially increase the Lipschitz constant of an observable when evolved in the Heisenberg picture. That is, if we have that $\Phi_t^*$ is the quantum channel that describes some local dynamics at time/depth $t$ in the Heisenberg picture and it satisfies a Lieb-Robinson bound, then we have:

$$ \|\Phi_t^*(O)\|_{\text{Lip,\square}} = O(e^{vt}\|O\|_{\text{Lip,\square}}), $$

where $v$ denotes the Lieb-Robinson velocity. This result is discussed in more detail in Section B.1 of the supplemental material. Thus, averages over local observables and short-time evolutions thereof all belong to the class of observables that have a small Lipschitz constant when compared to generic observables. These facts justify our claim that quasi-local observables are Lipschitz.

Once we are given a Lipschitz constant on observables or a set of quasi-local observables, we can define a Wasserstein-1 distance on states by duality [56, 59].

The latter quantifies how well we can distinguish two states by their action on regular or local observables and is given by

$$ W_1(\rho, \sigma) := \sup_{O:\|O\|_{\text{Lip,\square}} \le 1} \text{tr}[O(\rho - \sigma)]. \quad (4) $$

The definition (4) is in direct analogy with the variational definition of the trace distance, given by:

$$ \|\rho - \sigma\|_{\text{tr}} := \sup_{O:\|O\|_{\infty} \le 1} \text{tr}[O(\rho - \sigma)]. \quad (5) $$

Note, however, that the two quantities have different scalings. To illustrate this point, let us consider the observable in Eq. (3). If we measure the distance in trace distance, then we need that $\|\rho - \sigma\|_{\text{tr}} \le \epsilon$ to ensure that $\sigma$ approximates the expectation of value of $\rho$ up to $\epsilon$ on $O$. On the other hand, as $\|O\|_{\text{Lip,\square}} \le 2kn^{-1/2}$, the bound $W_1(\rho, \sigma) \le \frac{\epsilon\sqrt{n}}{2k}$ is sufficient to guarantee the same approximation. This difference in scaling is at the heart of our results, as we will see now.

## 1.2 Transportation cost inequalities

The paragraphs before motivated the idea that observables with a small Lipschitz constant capture quasilocal observables, and thus, that controlling the Wasserstein distance between two states gives rise to a more physically motivated distance measure than the trace distance. However, it is a priori not clear how to effectively control the Wasserstein distance between states, as it does not admit a closed formula in terms of eigenvalues like the trace distance.

In this work, we will achieve this by relating Wasserstein distances to the relative entropy between two states, $D(\rho||\sigma) := \text{tr}[\rho(\log(\rho) - \log(\sigma))]$, for $\sigma$ of full-rank. This can be achieved through the notion of a transportation cost inequality: an $n$-qudit state $\sigma$ is said to satisfy a transportation cost inequality with parameter $\alpha > 0$ if the Wasserstein distance of $\sigma$ to any other state $\rho$ can be controlled by their relative entropy, i.e.

$$ W_1(\rho, \sigma) \le \sqrt{\frac{D(\rho||\sigma)}{2\alpha}} \quad (6) $$

holds for all states $\rho \in \mathcal{D}_{d^n}$.

Such inequalities are particularly powerful whenever the constant $\alpha$ does not depend on the system size $n$ or does so at most inverse polylogarithmically,

<footnote n="1">¹The definition of [56] has a different normalization and does not have the $\sqrt{n}$ term. This normalization will be convenient to treat the constants of [59] and [56] on an equal footing.</footnote>
and can be thought of as a strengthening of Pinsker's inequality.

Transportation cost inequalities are closely related to the notion of Gaussian concentration [12, 56, 59], i.e. that Lipschitz functions strongly concentrate around their mean. Establishing analogs of such concentration inequalities for quantum many-body systems has been a fruitful line of research in the last years and they are related to fundamental questions in statistical physics, see e.g. [3, 15, 49, 50, 62]. Although we are certain that inequalities like Eq. (6) also shed new light on this matter, here we will focus on their application to learning a classical description of a state through maximum entropy methods. We refer to Table 2 for a summary of classes of states known to satisfy it, as discussed in more detail below. Unfortunately, for some important classes, the inequalities are only known for the more technically involved variations of the Wasserstein distance, and we refer the reader to the supplemental material, Section B.2 for precise definitions.

Recent works have established transportation cost inequalities with $\alpha$ either constant or logarithmic in system size for several classes of Gibbs states of commuting Hamiltonians [18, 26, 56]. In summary, they are known to hold for local Hamiltonians on arbitrary hypergraphs at high enough temperatures or in 1D. In this work we enlarge the class of examples by showing them for outputs of short-depth circuits in Sec. C.1. Note that Eq. (6) is trivial for pure states, as then the relative entropy between that state and any other is always $+\infty$. Thus, we first find an appropriate full-rank approximation of the pure state for which the inequality holds, as we will discuss below.

## 1.3 Maximum-entropy methods

Let us now show how transportation cost inequalities can be combined with maximum entropy methods. Such methods start from the assumption that we are given a set of self-adjoint, linearly independent Hermitian observables over an $n$-qudit system, $E_1, \dots, E_m \in \mathcal{M}_{d_m}^{sa}$, with $\|E_i\|_{\infty} \le 1$, a maximal inverse temperature $\beta > 0$ and the promise that the state we wish to learn can be expressed as:

$$ \sigma \equiv \sigma(\lambda) = \frac{\exp\left(-\beta \sum_{i=1}^{m} \lambda_i E_i\right)}{\mathcal{Z}(\lambda)}, \quad (7) $$

where $\lambda \in \mathbb{R}^m$ with sup norm $\|\lambda\|_{\ell_{\infty}} \le 1$ and

$$ \mathcal{Z}(\lambda) = \text{tr} \left[ \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) \right] $$

the partition function. Denoting by $e(\lambda)$ the vector with components $e_i(\lambda) = \text{tr}[E_i \sigma(\lambda)]$, the crux of the maximum entropy method is that $\lambda$ is the unique op-

timizer of

$$ \min_{\substack{\mu \in \mathbb{R}^m \\ \|\mu\|_{\ell_{\infty}} \le 1}} \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda), \quad (8) $$

which gives us a convex variational principle to learn the state given $e(\lambda)$. We refer to Sec. A for a discussion of the maximum entropy principle and its properties.

Typical examples of observables $E_i$ are e.g. all 2-local Pauli observables corresponding to edges of a given graph. This models the situation in which we are guaranteed that the state is a thermal state of a Hamiltonian with a known locality structure. More generally, for most of the examples discussed here the $E_i$ are given as follows: we start from a hypergraph $G = (V, E)$ and assume that there is a maximum radius $r_0 \in \mathbb{N}$ such that, for any hyperedge $A \in E$, there exists a vertex $v \in V$ such that the ball $B(v, r_0)$ centered at $v$ and of radius $r_0$ includes $A$. The $E_i$ are then given by a basis of the traceless matrices on each hyperedge $A$. This definition captures the notion of a local Hamiltonian w.r.t. the hypergraph.

Our framework also encompasses pure states after making an appropriate approximation. For instance, in this article we will also consider the outputs of shallow quantum circuits and believe our framework extends to unique ground states of gapped Hamiltonians, which are pure. Indeed, although it might not be a-priori clear, we will show below how the outputs of constant depth constant circuits are contained in the class of ground states of gapped, commuting Hamiltonians. And these are well-approximated by Gibbs states at finite temperature. Although this connection between Gibbs states of commuting Hamiltonians and outputs of shallow circuits might not be obvious at first, it makes some intuitive sense that the outputs of a shallow circuit are characterized by the reduced density matrix of the lightcone of each qubit. And the same holds for Gibbs states: one of their defining properties is that they are uniquely determined by the marginals. And this is the property that links these two classes of states.

Let us specify further what it means to learn the output of a shallow circuit. Suppose that $|\psi\rangle = \mathcal{U}|0\rangle^{\otimes n}$ is the output of an unknown shallow circuit $\mathcal{U}$ of depth $L$ with respect to a known interaction graph $(V, E)$ on $n$ vertices. That is,

$$ \mathcal{U} = \prod_{\ell \in [L]} \bigotimes_{e \in \mathcal{E}_{\ell}} \mathcal{U}_{\ell, e}, $$

where each $\mathcal{E}_{\ell} \subset E$ is a subset of non-intersecting edges. Thus, in this setting the locality of the circuit is known, but the underlying unitary is not. As we then show in Theorem C.1, the state $|\psi\rangle$ is $\epsilon^2$ close in Wasserstein distance to the Gibbs state $\sigma$ corresponding to the Hamiltonian with local terms $\mathcal{U}Z_i\mathcal{U}^\dagger$ at the inverse temperature $\beta = \log(\epsilon^{-1})$. By a simple light-cone argument we can bound the support of
and can be thought of as a strengthening of Pinsker's inequality.

Transportation cost inequalities are closely related to the notion of Gaussian concentration [12, 56, 59], i.e. that Lipschitz functions strongly concentrate around their mean. Establishing analogs of such concentration inequalities for quantum many-body systems has been a fruitful line of research in the last years and they are related to fundamental questions in statistical physics, see e.g. [3, 15, 49, 50, 62]. Although we are certain that inequalities like Eq. (6) also shed new light on this matter, here we will focus on their application to learning a classical description of a state through maximum entropy methods. We refer to Table 2 for a summary of classes of states known to satisfy it, as discussed in more detail below. Unfortunately, for some important classes, the inequalities are only known for the more technically involved variations of the Wasserstein distance, and we refer the reader to the supplemental material, Section B.2 for precise definitions.

Recent works have established transportation cost inequalities with $\alpha$ either constant or logarithmic in system size for several classes of Gibbs states of commuting Hamiltonians [18, 26, 56]. In summary, they are known to hold for local Hamiltonians on arbitrary hypergraphs at high enough temperatures or in 1D. In this work we enlarge the class of examples by showing them for outputs of short-depth circuits in Sec. C.1. Note that Eq. (6) is trivial for pure states, as then the relative entropy between that state and any other is always $+\infty$. Thus, we first find an appropriate full-rank approximation of the pure state for which the inequality holds, as we will discuss below.

## 1.3 Maximum-entropy methods

Let us now show how transportation cost inequalities can be combined with maximum entropy methods. Such methods start from the assumption that we are given a set of self-adjoint, linearly independent Hermitian observables over an $n$-qudit system, $E_1, \dots, E_m \in \mathcal{M}_{d_m}^{sa}$, with $\|E_i\|_{\infty} \le 1$, a maximal inverse temperature $\beta > 0$ and the promise that the state we wish to learn can be expressed as:

$$ \sigma \equiv \sigma(\lambda) = \frac{\exp\left(-\beta \sum_{i=1}^{m} \lambda_i E_i\right)}{\mathcal{Z}(\lambda)}, \quad (7) $$

where $\lambda \in \mathbb{R}^m$ with sup norm $\|\lambda\|_{\ell_{\infty}} \le 1$ and

$$ \mathcal{Z}(\lambda) = \mathrm{tr} \left[ \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) \right] $$

the partition function. Denoting by $e(\lambda)$ the vector with components $e_i(\lambda) = \mathrm{tr}[E_i \sigma(\lambda)]$, the crux of the maximum entropy method is that $\lambda$ is the unique op-

timizer of

$$ \min_{\substack{\mu \in \mathbb{R}^m \\ \|\mu\|_{\ell_{\infty}} \le 1}} \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda), \quad (8) $$

which gives us a convex variational principle to learn the state given $e(\lambda)$. We refer to Sec. A for a discussion of the maximum entropy principle and its properties.

Typical examples of observables $E_i$ are e.g. all 2-local Pauli observables corresponding to edges of a given graph. This models the situation in which we are guaranteed that the state is a thermal state of a Hamiltonian with a known locality structure. More generally, for most of the examples discussed here the $E_i$ are given as follows: we start from a hypergraph $G = (V, E)$ and assume that there is a maximum radius $r_0 \in \mathbb{N}$ such that, for any hyperedge $A \in E$, there exists a vertex $v \in V$ such that the ball $B(v, r_0)$ centered at $v$ and of radius $r_0$ includes $A$. The $E_i$ are then given by a basis of the traceless matrices on each hyperedge $A$. This definition captures the notion of a local Hamiltonian w.r.t. the hypergraph.

Our framework also encompasses pure states after making an appropriate approximation. For instance, in this article we will also consider the outputs of shallow quantum circuits and believe our framework extends to unique ground states of gapped Hamiltonians, which are pure. Indeed, although it might not be a-priori clear, we will show below how the outputs of constant depth constant circuits are contained in the class of ground states of gapped, commuting Hamiltonians. And these are well-approximated by Gibbs states at finite temperature. Although this connection between Gibbs states of commuting Hamiltonians and outputs of shallow circuits might not be obvious at first, it makes some intuitive sense that the outputs of a shallow circuit are characterized by the reduced density matrix of the lightcone of each qubit. And the same holds for Gibbs states: one of their defining properties is that they are uniquely determined by the marginals. And this is the property that links these two classes of states.

Let us specify further what it means to learn the output of a shallow circuit. Suppose that $|\psi\rangle = \mathcal{U}|0\rangle^{\otimes n}$ is the output of an unknown shallow circuit $\mathcal{U}$ of depth $L$ with respect to a known interaction graph $(V, E)$ on $n$ vertices. That is,

$$ \mathcal{U} = \prod_{\ell \in [L]} \bigotimes_{e \in \mathcal{E}_{\ell}} \mathcal{U}_{\ell, e}, $$

where each $\mathcal{E}_{\ell} \subset E$ is a subset of non-intersecting edges. Thus, in this setting the locality of the circuit is known, but the underlying unitary is not. As we then show in Theorem C.1, the state $|\psi\rangle$ is $\epsilon^2$ close in Wasserstein distance to the Gibbs state $\sigma$ corresponding to the Hamiltonian with local terms $\mathcal{U}Z_i\mathcal{U}^\dagger$ at the inverse temperature $\beta = \log(\epsilon^{-1})$. By a simple light-cone argument we can bound the support of
each $UZ_iU^\dagger$, since we know the underlying structure of the circuit. We then show in Thm. C.1 that it is indeed possible to efficiently learn the outputs of such circuits as long as the support of each time-evolved $Z_i$ is at most logarithmic in system size.

We see from Eq. (8) that the expectation values of the $E_i$ completely characterize the state $\sigma(\lambda)$. But it is possible to obtain a more quantitative version of this statement through the following identity, also observed in [5]:

$$D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle. \quad (9)$$

In addition to showing that if $e(\lambda) = e(\mu)$ then $\sigma(\mu) = \sigma(\lambda)$, Eq. (9) implies that by controlling how well the local expectations values of one state approximate another, we can also easily control their relative entropies. In particular, if $m = O(n)$ and $\|e(\mu) - e(\lambda)\|_{\ell_1} = O(\epsilon n)$ for some $\epsilon > 0$, we obtain from an application of Hölder's inequality that:

$$D(\sigma(\mu)\|\sigma(\lambda)) \le D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = O(\beta\epsilon n). \quad (10)$$

We refer to Section A for more details. Thus, if we can find a state that approximates the expectation value of each $E_i$ up to $\epsilon$, we are guaranteed to have a $O(\beta\epsilon)$ relative entropy density. This observation is vital to ensure that the maximum entropy principle still yields a good estimate of the state even under some statistical noise in the vector of expectation values $e(\lambda)$. Indeed, the variational principle of Eq. (8) would allow us to recover the state exactly if we had access to the exact values of $e(\lambda)$. However, it turns out that solving Eq. (8) with some estimate $\hat{e}(\lambda)$ such that $\|\hat{e}(\lambda) - e(\lambda)\|_{\ell_\infty} \le \epsilon$ still yields a Gibbs state $\sigma(\mu)$ satisfying Eq. (10). The maximum entropy problem is a strictly convex optimization problem. Thus, it can be solved efficiently with access to the gradient of the target function. The gradient turns out to be proportional to $e(\lambda) - e(\mu)$, where $\mu$ is the current guess for the optimum. Although we will discuss the details of solving the problem later in Sec. A, in a nutshell, the maximum entropy problem can be solved efficiently if it is possible to efficiently compute expectation values of the observables $E_i$ on the family of Gibbs states under consideration.

## 1.4 Combining TC with the maximum entropy principle

Suppose now that we have that each of the $E_i$ acts on at most $l_0$ qudits. Then, by using e.g. the method of classical shadows, we can estimate the expectation values of all $E_i$ up to $\epsilon$ with failure probability at most $\delta > 0$ with $O(4^{l_0}\epsilon^{-2}\log(m\delta^{-1}))$ samples. From our discussion above, we see that this is enough to obtain a state $\sigma(\mu)$ satisfying Eq. (10). Further assuming

that we have a TC with some constant $\alpha > 0$ for $\sigma(\lambda)$ we conclude that:

$$\begin{aligned} |\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| &\le \|O\|_{\text{Lip}} W_1(\sigma(\lambda), \sigma(\mu)) \\ &\le \|O\|_{\text{Lip}} \sqrt{\frac{D(\sigma(\mu)\|\sigma(\lambda))}{2\alpha}} \\ &= O(\sqrt{\beta\epsilon n} \|O\|_{\text{Lip}}). \end{aligned}$$

Finally, recall that for sums of $k$ local operators on a 2D lattice like in Fig. 1, where we have $k = L^2$, the Lipschitz constant satisfies $\|O\|_{\text{Lip}} = O(\sqrt{n})$ and we require a precision of $O(\epsilon n/k)$ to obtain a relative error of $\epsilon$. Putting all these elements together, we conclude that by setting $\epsilon = \beta\tilde{\epsilon}^2/(k^2)$ for some $\tilde{\epsilon} > 0$ we arrive at

$$|\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| = O(\tilde{\epsilon} k^{-1} n), \quad (11)$$

which constitutes a relative error for the expectation value. In particular, we see that the sample complexity required to obtain this error was

$$O(4^{l_0} k^4 \beta^2 \tilde{\epsilon}^{-4} \log(m)). \quad (12)$$

We then obtain:

**Theorem 1.1 (Learning Gibbs states).** Let $\sigma(\lambda)$ be a Gibbs state as defined in Eq. (7) and such that each $E_i$ acts on at most $l_0$ qudits. Moreover, suppose that $\sigma(\lambda)$ satisfies a TC inequality with $\alpha$ depending at most inverse logarithmically with system size. Then with probability of success $1 - \delta$ we can obtain a state $\sigma(\mu)$ such that for all observables $O \in \mathcal{M}_{d^n}$

$$|\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| \le O(\epsilon\sqrt{n} \|O\|_{\text{Lip}}) \quad (13)$$

from $O(4^{l_0}\beta^2 \text{poly}(\epsilon^{-1}, \log(m\delta^{-1})))$ samples of $\sigma(\lambda)$. Moreover, if it is possible to compute the expectation values of the $E_i$ on $\sigma(\tau)$ for $\|\tau\|_{\ell_\infty} \le 1$, then the postprocessing can also be in polynomial time.

We once again stress that the recovery guarantee in Eq. (13) suffices to give good relative approximations for the expectation value of quasilocal observables. Furthermore, if we did not resort to the Wasserstein distance but rather the trace distance, as in known results for the tomography of many-body states [5, 10, 23, 53, 67], the sample complexity would be exponentially worse, as we prove in Sec. G. More precisely, any algorithm that estimates Gibbs states on a lattice at inverse temperatures $\beta = \Omega(n^{-1/2})$ up to trace distance $\epsilon$ requires $\Omega(n\epsilon^{-2})$ samples. Thus, even for states whose inverse temperature goes to 0 as the system size increases, a focus on the trace distance instead of the Wasserstein distance implies an exponentially worse sample complexity.

Theorem 1.1 also provides an exponential improvement over shadow techniques in the locality of the observables, as we argue in Sec. G. However, unlike our methods, shadow techniques do not need to make any
each $UZ_iU^\dagger$, since we know the underlying structure of the circuit. We then show in Thm. C.1 that it is indeed possible to efficiently learn the outputs of such circuits as long as the support of each time-evolved $Z_i$ is at most logarithmic in system size.

We see from Eq. (8) that the expectation values of the $E_i$ completely characterize the state $\sigma(\lambda)$. But it is possible to obtain a more quantitative version of this statement through the following identity, also observed in [5]:

$$D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle. \quad (9)$$

In addition to showing that if $e(\lambda) = e(\mu)$ then $\sigma(\mu) = \sigma(\lambda)$, Eq. (9) implies that by controlling how well the local expectations values of one state approximate another, we can also easily control their relative entropies. In particular, if $m = O(n)$ and $\|e(\mu) - e(\lambda)\|_{\ell_1} = O(\epsilon n)$ for some $\epsilon > 0$, we obtain from an application of Hölder's inequality that:

$$D(\sigma(\mu)\|\sigma(\lambda)) \le D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = O(\beta\epsilon n). \quad (10)$$

We refer to Section A for more details. Thus, if we can find a state that approximates the expectation value of each $E_i$ up to $\epsilon$, we are guaranteed to have a $O(\beta\epsilon)$ relative entropy density. This observation is vital to ensure that the maximum entropy principle still yields a good estimate of the state even under some statistical noise in the vector of expectation values $e(\lambda)$. Indeed, the variational principle of Eq. (8) would allow us to recover the state exactly if we had access to the exact values of $e(\lambda)$. However, it turns out that solving Eq. (8) with some estimate $\hat{e}(\lambda)$ such that $\|\hat{e}(\lambda) - e(\lambda)\|_{\ell_\infty} \le \epsilon$ still yields a Gibbs state $\sigma(\mu)$ satisfying Eq. (10). The maximum entropy problem is a strictly convex optimization problem. Thus, it can be solved efficiently with access to the gradient of the target function. The gradient turns out to be proportional to $e(\lambda) - e(\mu)$, where $\mu$ is the current guess for the optimum. Although we will discuss the details of solving the problem later in Sec. A, in a nutshell, the maximum entropy problem can be solved efficiently if it is possible to efficiently compute expectation values of the observables $E_i$ on the family of Gibbs states under consideration.

## 1.4 Combining TC with the maximum entropy principle

Suppose now that we have that each of the $E_i$ acts on at most $l_0$ qudits. Then, by using e.g. the method of classical shadows, we can estimate the expectation values of all $E_i$ up to $\epsilon$ with failure probability at most $\delta > 0$ with $O(4^{l_0}\epsilon^{-2}\log(m\delta^{-1}))$ samples. From our discussion above, we see that this is enough to obtain a state $\sigma(\mu)$ satisfying Eq. (10). Further assuming

that we have a TC with some constant $\alpha > 0$ for $\sigma(\lambda)$ we conclude that:

$$\begin{aligned} |\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| & \le \|O\|_{\text{Lip}} W_1(\sigma(\lambda), \sigma(\mu)) \\ & \le \|O\|_{\text{Lip}} \sqrt{\frac{D(\sigma(\mu)\|\sigma(\lambda))}{2\alpha}} \\ & = O(\sqrt{\beta\epsilon n} \|O\|_{\text{Lip}}). \end{aligned}$$

Finally, recall that for sums of $k$ local operators on a 2D lattice like in Fig. 1, where we have $k = L^2$, the Lipschitz constant satisfies $\|O\|_{\text{Lip}} = O(\sqrt{n})$ and we require a precision of $O(\epsilon n/k)$ to obtain a relative error of $\epsilon$. Putting all these elements together, we conclude that by setting $\epsilon = \beta\tilde{\epsilon}^2/(k^2)$ for some $\tilde{\epsilon} > 0$ we arrive at

$$|\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| = O(\tilde{\epsilon} k^{-1} n), \quad (11)$$

which constitutes a relative error for the expectation value. In particular, we see that the sample complexity required to obtain this error was

$$O(4^{l_0} k^4 \beta^2 \tilde{\epsilon}^{-4} \log(m)). \quad (12)$$

We then obtain:

**Theorem 1.1 (Learning Gibbs states).** Let $\sigma(\lambda)$ be a Gibbs state as defined in Eq. (7) and such that each $E_i$ acts on at most $l_0$ qudits. Moreover, suppose that $\sigma(\lambda)$ satisfies a TC inequality with $\alpha$ depending at most inverse logarithmically with system size. Then with probability of success $1 - \delta$ we can obtain a state $\sigma(\mu)$ such that for all observables $O \in \mathcal{M}_{d^n}$

$$|\text{tr}[O(\sigma(\lambda) - \sigma(\mu))]| \le O(\epsilon\sqrt{n} \|O\|_{\text{Lip}}) \quad (13)$$

from $O(4^{l_0}\beta^2 \text{poly}(\epsilon^{-1}, \log(m\delta^{-1})))$ samples of $\sigma(\lambda)$. Moreover, if it is possible to compute the expectation values of the $E_i$ on $\sigma(\tau)$ for $\|\tau\|_{\ell_\infty} \le 1$, then the postprocessing can also be in polynomial time.

We once again stress that the recovery guarantee in Eq. (13) suffices to give good relative approximations for the expectation value of quasilocal observables. Furthermore, if we did not resort to the Wasserstein distance but rather the trace distance, as in known results for the tomography of many-body states [5, 10, 23, 53, 67], the sample complexity would be exponentially worse, as we prove in Sec. G. More precisely, any algorithm that estimates Gibbs states on a lattice at inverse temperatures $\beta = \Omega(n^{-1/2})$ up to trace distance $\epsilon$ requires $\Omega(n\epsilon^{-2})$ samples. Thus, even for states whose inverse temperature goes to 0 as the system size increases, a focus on the trace distance instead of the Wasserstein distance implies an exponentially worse sample complexity.

Theorem 1.1 also provides an exponential improvement over shadow techniques in the locality of the observables, as we argue in Sec. G. However, unlike our methods, shadow techniques do not need to make any
<table><caption>Table 2: Performance of the algorithm under various assumptions of the underlying state to obtain a state that is $\epsilon\sqrt{n}$ close in Wasserstein distance. All the estimates are up to polylog(n) factors. We refer to Sec. B.3 for proofs of the TC used and C for how to combine them with maximum entropy methods. In Section D we explain how to obtain the sample complexity by combining Thm. A.1 with strong convexity bounds. For the postprocessing we refer to section E. The case of shallow circuits is discussed in more detail in Sec. C.1. By lightcone $l_0$ we mean the size of the largest lightcone of each qubit in the circuit.</caption><thead><tr><th>Structure</th><th>Samples</th><th>Postprocessing</th></tr></thead><tbody><tr><td>Lightcone l<sub>0</sub> circuit</td><td>ε<sup>-4</sup>2<sup>12l<sub>0</sub></sup></td><td>exp(3n)</td></tr><tr><td>Commuting Gibbs<br>for β &lt; β<sub>c</sub></td><td>ε<sup>-2</sup></td><td>poly(n)</td></tr><tr><td>1D commuting</td><td>min{ε<sup>-2</sup>e<sup>O(β)</sup>, ε<sup>-4</sup>}</td><td>poly(n)</td></tr></tbody></table>

assumptions on the underlying states. Thus, we see that Theorem 1.1 opens up the possibility of highly efficient characterization of quantum states and provably exponentially better sample complexities when compared with recovery in trace distance.

We also remark that it is possible to improve the scaling in accuracy in Eq. (12) from $\epsilon^{-4}$ to the expected $\epsilon^{-2}$. To do that, it is important to bound the condition number of the Hessian of the log-partition function, as we explain in the methods.

<figure><img src="image_2.png" /><figcaption>Figure 1: example of observable $O = \sum_i O_i$ for 2D lattice system of size $n$. Each $O_i$ is supported on a $L \times L$ square ($L = 3$ in the figure). We have $\|O\|_{\text{Lip}} = O(\sqrt{n})$ and $\|O\| = n/L^2$. Thus our methods require poly($L, \log(n), \epsilon^{-1}$) samples to estimate the expectation value of all such observables. Shadow-like methods require poly($e^{cL^2}, \log(n), \epsilon^{-1}$) samples, an exponentially worse dependency in $L$. Even for moderate values of $L$, say $L = 5$, this can lead to $10^7$ factor savings sample complexity and gives an exponential speedup for $L = \text{poly}(\log(n))$. Other many-body methods have a poly($L, n, \epsilon^{-1}$) [5, 10, 23, 53, 67] scaling, which in turn is exponentially worse in the system size.</figcaption></figure>

## 1.5 Numerical results

We will now compare the performance of our method to the classical shadow protocol [40] to estimate the average of a local observable on a Gibbs state. To ensure that we can still generate samples for a high number of qubits, we will consider the following family

of commuting Gibbs states in 1-D:

$$H(\lambda) = \tag{14} \\ - \sum_{k=0}^{n/2-1} S^{2k} (\lambda_k X_0 X_1 + \lambda_{n+k} X_0 X_1 Y_2 Y_3) S^{2k},$$

where $S$ is the shift operator, $\lambda \in B_{\ell_{\infty}}(0, 1)$ and we assumed $n$ is even. We will then estimate the expectation value of the observable:

$$O = \sum_{k=0}^{n/2-1} S^{2k} X_0 X_1 Y_2 Y_3 X_4 X_5 Y_6 Y_7 S^{2k}. \tag{15}$$

The results for one particular choice of Gibbs state in this class are shown in Fig. 2. It shows that even for observables of moderate locality like the one in Eq. (15), shadows are outperformed by maximum entropy methods by orders of magnitude. Also note that the quality of our estimates decays like $\sim 1/\sqrt{s}$, where $s$ is the number of samples, showing how the quality of the recovery is essentially independent of the system's size.

We also remark that for obtaining these results, we obtained the expectation values of the $X_i X_{i+1}$ terms by measuring in the $X$ basis on each qubit and of the $XXYY$ terms by measuring in a sequence of $XXYY$ bases followed by the same basis shifted by 2.

## 2 Conclusion

In this article we have demonstrated that ideas from quantum optimal transport yield provable exponential improvements in the sample complexity required to learn a quantum state when compared to state-of-the-art methods. More precisely, we showcased how the interplay between maximum entropy methods and the Wasserstein distance, which is mediated by a transportation cost inequality, allows for fine-tuning the complexity of observables whose expectation value we wish to estimate and the number of samples required for that. Through our techniques, we essentially settled most questions related to how efficiently it is possible to learn a commuting Gibbs state and significantly advanced our understanding of general Gibbs states. With the impressive growth in
<table><caption>Table 2: Performance of the algorithm under various assumptions of the underlying state to obtain a state that is $\epsilon\sqrt{n}$ close in Wasserstein distance. All the estimates are up to polylog(n) factors. We refer to Sec. B.3 for proofs of the TC used and C for how to combine them with maximum entropy methods. In Section D we explain how to obtain the sample complexity by combining Thm. A.1 with strong convexity bounds. For the postprocessing we refer to section E. The case of shallow circuits is discussed in more detail in Sec. C.1. By lightcone $l_0$ we mean the size of the largest lightcone of each qubit in the circuit.</caption><thead><tr><th>Structure</th><th>Samples</th><th>Postprocessing</th></tr></thead><tbody><tr><td>Lightcone l<sub>0</sub> circuit</td><td>ε<sup>-4</sup>2<sup>12l<sub>0</sub></sup></td><td>exp(3n)</td></tr><tr><td>Commuting Gibbs<br>for β &lt; β<sub>c</sub></td><td>ε<sup>-2</sup></td><td>poly(n)</td></tr><tr><td>1D commuting</td><td>min{ε<sup>-2</sup>e<sup>O(β)</sup>, ε<sup>-4</sup>}</td><td>poly(n)</td></tr></tbody></table>

assumptions on the underlying states. Thus, we see that Theorem 1.1 opens up the possibility of highly efficient characterization of quantum states and provably exponentially better sample complexities when compared with recovery in trace distance.

We also remark that it is possible to improve the scaling in accuracy in Eq. (12) from $\epsilon^{-4}$ to the expected $\epsilon^{-2}$. To do that, it is important to bound the condition number of the Hessian of the log-partition function, as we explain in the methods.

<figure><img src="image_3.png" /><figcaption>Figure 1: example of observable $O = \sum_i O_i$ for 2D lattice system of size $n$. Each $O_i$ is supported on a $L \times L$ square ($L = 3$ in the figure). We have $\|O\|_{\text{Lip}} = O(\sqrt{n})$ and $\|O\| = n/L^2$. Thus our methods require poly($L, \log(n), \epsilon^{-1}$) samples to estimate the expectation value of all such observables. Shadow-like methods require poly($e^{cL^2}, \log(n), \epsilon^{-1}$) samples, an exponentially worse dependency in $L$. Even for moderate values of $L$, say $L = 5$, this can lead to $10^7$ factor savings sample complexity and gives an exponential speedup for $L = \text{poly}(\log(n))$. Other many-body methods have a poly($L, n, \epsilon^{-1}$) [5, 10, 23, 53, 67] scaling, which in turn is exponentially worse in the system size.</figcaption></figure>

## 1.5 Numerical results

We will now compare the performance of our method to the classical shadow protocol [40] to estimate the average of a local observable on a Gibbs state. To ensure that we can still generate samples for a high number of qubits, we will consider the following family

of commuting Gibbs states in 1-D:

$$ H(\lambda) = \tag{14} \\ - \sum_{k=0}^{n/2-1} S^{2k} (\lambda_k X_0 X_1 + \lambda_{n+k} X_0 X_1 Y_2 Y_3) S^{2k}, $$

where $S$ is the shift operator, $\lambda \in B_{\ell_\infty}(0, 1)$ and we assumed $n$ is even. We will then estimate the expectation value of the observable:

$$ O = \sum_{k=0}^{n/2-1} S^{2k} X_0 X_1 Y_2 Y_3 X_4 X_5 Y_6 Y_7 S^{2k}. \tag{15} $$

The results for one particular choice of Gibbs state in this class are shown in Fig. 2. It shows that even for observables of moderate locality like the one in Eq. (15), shadows are outperformed by maximum entropy methods by orders of magnitude. Also note that the quality of our estimates decays like $\sim 1/\sqrt{s}$, where $s$ is the number of samples, showing how the quality of the recovery is essentially independent of the system's size.

We also remark that for obtaining these results, we obtained the expectation values of the $X_i X_{i+1}$ terms by measuring in the $X$ basis on each qubit and of the $XXY$ terms by measuring in a sequence of $XXY$ bases followed by the same basis shifted by 2.

## 2 Conclusion

In this article we have demonstrated that ideas from quantum optimal transport yield provable exponential improvements in the sample complexity required to learn a quantum state when compared to state-of-the-art methods. More precisely, we showcased how the interplay between maximum entropy methods and the Wasserstein distance, which is mediated by a transportation cost inequality, allows for fine-tuning the complexity of observables whose expectation value we wish to estimate and the number of samples required for that. Through our techniques, we essentially settled most questions related to how efficiently it is possible to learn a commuting Gibbs state and significantly advanced our understanding of general Gibbs states. With the impressive growth in
<figure><img src="image_3.png" /><figcaption>Figure 2: Performance on a Gibbs state from the family of Eq. (14) and the 8-local observable in Eq. (15). We have set the number of qubits to 100, $\beta = 1.1$ and the $\lambda_i$ uniformly at random between 0.5 and 0.9. The x-axis denotes the logarithm of the number of samples in base 10 and the y the error in absolute value to the true value. We ran each protocol 300 times on the same Gibbs state to see how the estimate varied. We see that even with $10^4$ samples the shadows method still has errors of the order $10^0$ in the 75 percentile, whereas the maximum entropy already yields good estimates when the number of samples is of order $10^2$, showcasing that maximum entropy methods outperform classical shadows by orders of magnitudes for observables of moderate locality like those in Eq. (15).</figcaption></figure>

the size of quantum devices available in the lab over the last years, we believe that the polylogarithmic in system size sample complexities obtained here will come in handy to calibrate and characterize systems containing thousands or millions of qubits.

We believe that the framework and philosophy we began to develop here will find applications in other areas of quantum information theory. Indeed, although a bound in trace distance is the golden standard and one of the most widely accepted and used measures of distance between quantum states in quantum information and computation, we argued that in many physically relevant settings, demanding a trace distance bound might be too strong. More importantly, replacing the trace distance by a Wasserstein distance bound can lead to exponential complexity gains, as in this article. Thus, we believe that this approach is likely to lead to substantial gains and improvements also in other areas like quantum machine learning, process tomography or in quantum many-body problems.

Some of the outstanding open questions raised by this article are establishing that a suitable notion of exponential decay of correlations in general implies a transportation cost inequality and showing that TC holds for a larger class of systems. We believe that our framework should also extend to ground states of gapped Hamiltonians in 1D, however, such a statement would still require us to refine our bounds. The results presented here also make us conjecture that any high-temperature Gibbs state satisfies a TC inequality, even for long-range interactions, which would make our techniques applicable to essentially

all physically relevant models at high temperatures.

That being said, to the best of our knowledge, all states that are known to satisfy a TCI can also be simulated efficiently classically. However, there is a-priori no reason to believe that a TCI necessarily implies that the underlying states can be simulated classically and we believe that this is more of a reflection of the fact that the study of TCI is still incipient. Furthermore, although we explained how to do the tomography of the Gbibs state with the maximum entropy principle, other Hamiltonian learning procedures also apply, as all we need is to upper-bound the relative entropy through Eq. (9). Thus, breakthroughs in Hamiltonian learning would then also apply to the setting in this paper. In particular, through efficient Hamiltonian learning methods, it might be possible to use the results derived here to verify if a quantum device correctly implemented a shallow circuit.

Moreover, it would also be interesting to investigate other applications of Gaussian concentration in many-body physics [3, 15, 49, 50, 62] from the angle of transportation cost inequalities.

# 3 Methods

## 3.1 Summary of the maximum entropy procedure and contributions

Now that we have discussed how our results yield better sample complexities for some classes of states, we discuss the maximum entropy algorithm in more detail and comment on how our results equip it with better performance guarantees.
<figure><img src="image_4.png" /><figcaption>Figure 2: Performance on a Gibbs state from the family of Eq. (14) and the 8-local observable in Eq. (15). We have set the number of qubits to 100, $\beta = 1.1$ and the $\lambda_i$ uniformly at random between 0.5 and 0.9. The x-axis denotes the logarithm of the number of samples in base 10 and the y the error in absolute value to the true value. We ran each protocol 300 times on the same Gibbs state to see how the estimate varied. We see that even with $10^4$ samples the shadows method still has errors of the order $10^0$ in the 75 percentile, whereas the maximum entropy already yields good estimates when the number of samples is of order $10^2$, showcasing that maximum entropy methods outperform classical shadows by orders of magnitudes for observables of moderate locality like those in Eq. (15).</figcaption></figure>

the size of quantum devices available in the lab over the last years, we believe that the polylogarithmic in system size sample complexities obtained here will come in handy to calibrate and characterize systems containing thousands or millions of qubits.

We believe that the framework and philosophy we began to develop here will find applications in other areas of quantum information theory. Indeed, although a bound in trace distance is the golden standard and one of the most widely accepted and used measures of distance between quantum states in quantum information and computation, we argued that in many physically relevant settings, demanding a trace distance bound might be too strong. More importantly, replacing the trace distance by a Wasserstein distance bound can lead to exponential complexity gains, as in this article. Thus, we believe that this approach is likely to lead to substantial gains and improvements also in other areas like quantum machine learning, process tomography or in quantum many-body problems.

Some of the outstanding open questions raised by this article are establishing that a suitable notion of exponential decay of correlations in general implies a transportation cost inequality and showing that TC holds for a larger class of systems. We believe that our framework should also extend to ground states of gapped Hamiltonians in 1D, however, such a statement would still require us to refine our bounds. The results presented here also make us conjecture that any high-temperature Gibbs state satisfies a TC inequality, even for long-range interactions, which would make our techniques applicable to essentially

all physically relevant models at high temperatures.

That being said, to the best of our knowledge, all states that are known to satisfy a TCI can also be simulated efficiently classically. However, there is a-priori no reason to believe that a TCI necessarily implies that the underlying states can be simulated classically and we believe that this is more of a reflection of the fact that the study of TCI is still incipient. Furthermore, although we explained how to do the tomography of the Gbibs state with the maximum entropy principle, other Hamiltonian learning procedures also apply, as all we need is to upper-bound the relative entropy through Eq. (9). Thus, breakthroughs in Hamiltonian learning would then also apply to the setting in this paper. In particular, through efficient Hamiltonian learning methods, it might be possible to use the results derived here to verify if a quantum device correctly implemented a shallow circuit.

Moreover, it would also be interesting to investigate other applications of Gaussian concentration in many-body physics [3, 15, 49, 50, 62] from the angle of transportation cost inequalities.

# 3 Methods

## 3.1 Summary of the maximum entropy procedure and contributions

Now that we have discussed how our results yield better sample complexities for some classes of states, we discuss the maximum entropy algorithm in more detail and comment on how our results equip it with better performance guarantees.
As the maximum entropy principle in Eq. (20) corresponds to solving a convex optimization problem, it should come as no surprise that promises on the strong convexity of the underlying functions being optimized can be leveraged to give improved performance guarantees [14]. For the specific case of the maximum entropy principle, strong convexity guarantees translate to bounds of the form

$$LI \leq \nabla^2 \log(\mathcal{Z}(\mu)) \leq UI \quad (16)$$

for constants $L, U > 0$ and all $\mu \in B_{\ell_{\infty}}(0, 1)$. We refer to Sec. A of the supplemental material for a thorough discussion. We note that in [5] the authors show such results in a more general setting, although with $U, L$ polynomial in $n$, which is not sufficient for our purposes. For us it will be important to ensure that the condition number of the log-partition function is at most polylogarithmic in system size (i.e. $L^{-1}U = \tilde{O}(1)$).

If we define the function $f: \mu \mapsto \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda)$, then $\nabla f = \beta(e(\lambda) - e(\mu))$. It then follows from standard properties of strongly convex functions that:

$$\|\lambda - \mu\|_{\ell_2} = L^{-1}\beta\|e(\lambda) - e(\mu)\|_{\ell_2}$$

That is, whenever the expectation values are close, the underlying parameters must be close as well. In this case, we have from $\|e(\lambda) - e(\mu)\|_{\ell_2} = \mathcal{O}(\epsilon\sqrt{m})$ that:

$$\begin{aligned} & -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle \\ & \leq \beta \|\lambda - \mu\|_{\ell_2} \|e(\lambda) - e(\mu)\|_{\ell_2} = \mathcal{O}(L^{-1}\beta^2\epsilon^2m). \end{aligned} \quad (17)$$

As we will see in the proposition below, $L^{-1} = \mathcal{O}(e^{\beta\beta^{-2}})$ for commuting Hamiltonians, which gives a quadratic improvement in $\epsilon$ in Eq. (17) and yields the expected $\epsilon^{-2}$ scaling for the sample complexity in terms of the accuracy.

**Proposition 3.1** (Strengthened strong convexity constant for commuting Hamiltonians). For each $\mu \in B_{\ell_{\infty}}(0, 1)$, let $\sigma(\mu)$ be a Gibbs state at inverse temperature $\beta$ corresponding to the commuting Hamiltonian $H(\mu) = \sum_j \mu_j E_j$ on the hypergraph $G = (V, E)$, where $\text{tr}[E_i E_j] = 0$ for all $i, j$ and each local operator $E_j$ is traceless on its support. Then for $\beta$ such that the states $\sigma(\mu)$ satisfy exponential decay of correlations, the Hessian of the log-partition function is bounded by

$$\Omega(\beta^2 e^{-c\beta}) I \leq \nabla^2 \log \mathcal{Z}(\mu) \leq \mathcal{O}(\beta^2) I. \quad (18)$$

for some constant $c > 0$.

After the completion of the first version of this work, in [34, Corollary 4.4] Tang et al proved strong convexity bounds for high-temperature, (not necessarily geometrically) local Hamiltonians. More precisely,

for $\beta = \mathcal{O}(k^{-8})$, where $k$ is the maximal number of qubits each term acts on, they show that $L^{-1} \leq 2\beta^{-2}$. Although the result in Eq. (18) has the advantage of giving an estimate at any temperature, we see that also for noncommuting Gibbs states strong convexity holds at high enough temperatures.

The flowchart in Figure 3 gives the general scheme behind the maximum entropy method. Besides the exponential improvements in sample complexity laid out in Table 2, we also provide structural improvements which we elaborate on while also explaining the general scheme:

**Input:** The input consists of $m$ linearly independent operators $E_i$ of operator norm 1, some upper bound $\beta > 0$, precision parameter $\epsilon > 0$ and step size $\eta$. Moreover, we are given the promise that the state of interest satisfies (7). Although we will be mostly concerned with the case in which the observables are local, we show the convergence of the algorithm in general in Sec. A. The step size should be picked as $\eta = \mathcal{O}(U^{-1})$ with $U$ satisfying (16), as explained in Sec. A.1.

**Require:** We assume that we have access to copies of $\sigma(\lambda)$ and that we can perform measurements to estimate the expectation values of the observables $E_i$ up to precision $\epsilon > 0$. For most of the examples considered here, this will mostly require implementing simple, few-qudit measurements.

**Output:** The output is in the form of a vector of parameters $\mu$ of a Gibbs state $\sigma(\mu)$ as in Eq. (7). Note that unlike [5], our goal is not to estimate the vector of parameters $\lambda$, but rather obtain an approximation of the state satisfying $\sigma(\lambda) \approx \sigma(\mu)$. Here we will focus on quantifying the output's quality in relative entropy. More precisely, the output of the algorithm is guaranteed to satisfy $D(\sigma(\mu)\|\sigma(\lambda)) = \mathcal{O}(\epsilon n)$.

**Step 1:** In this step, we estimate the expectation values of each observable $E_i$ on the state $\sigma(\lambda)$ up to an error $\epsilon$. The resources to be optimized here are the number of samples of $\sigma(\lambda)$ we require and the complexity to implement the measurements. Using shadow tomography or Pauli grouping methods [13, 22, 40] we can do so requiring $\mathcal{O}(4^{r_0}\epsilon^{-2})$ polylog($m$)) samples and Pauli or 1-qubit measurements, where $r_0$ is maximum number of qubits the $E_i$ act on. This is discussed in more detail in Sec. C.

**Step 2:** The maximum entropy problem in Eq. (8) can be solved with gradient descent, as it corresponds to a strictly convex optimization problem [14]. At this step we simply initialize the algorithm to start at the maximally mixed state.
As the maximum entropy principle in Eq. (20) corresponds to solving a convex optimization problem, it should come as no surprise that promises on the strong convexity of the underlying functions being optimized can be leveraged to give improved performance guarantees [14]. For the specific case of the maximum entropy principle, strong convexity guarantees translate to bounds of the form

$$LI \leq \nabla^2 \log(\mathcal{Z}(\mu)) \leq UI \quad (16)$$

for constants $L, U > 0$ and all $\mu \in B_{\ell_{\infty}}(0, 1)$. We refer to Sec. A of the supplemental material for a thorough discussion. We note that in [5] the authors show such results in a more general setting, although with $U, L$ polynomial in $n$, which is not sufficient for our purposes. For us it will be important to ensure that the condition number of the log-partition function is at most polylogarithmic in system size (i.e. $L^{-1}U = \tilde{O}(1)$).

If we define the function $f: \mu \mapsto \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda)$, then $\nabla f = \beta(e(\lambda) - e(\mu))$. It then follows from standard properties of strongly convex functions that:

$$\|\lambda - \mu\|_{\ell_2} = L^{-1}\beta\|e(\lambda) - e(\mu)\|_{\ell_2}$$

That is, whenever the expectation values are close, the underlying parameters must be close as well. In this case, we have from $\|e(\lambda) - e(\mu)\|_{\ell_2} = \mathcal{O}(\epsilon\sqrt{m})$ that:

$$\begin{aligned} & -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle \\ & \leq \beta \|\lambda - \mu\|_{\ell_2} \|e(\lambda) - e(\mu)\|_{\ell_2} = \mathcal{O}(L^{-1}\beta^2\epsilon^2m). \end{aligned} \quad (17)$$

As we will see in the proposition below, $L^{-1} = \mathcal{O}(e^{\beta\beta^{-2}})$ for commuting Hamiltonians, which gives a quadratic improvement in $\epsilon$ in Eq. (17) and yields the expected $\epsilon^{-2}$ scaling for the sample complexity in terms of the accuracy.

**Proposition 3.1** (Strengthened strong convexity constant for commuting Hamiltonians). For each $\mu \in B_{\ell_{\infty}}(0, 1)$, let $\sigma(\mu)$ be a Gibbs state at inverse temperature $\beta$ corresponding to the commuting Hamiltonian $H(\mu) = \sum_j \mu_j E_j$ on the hypergraph $G = (V, E)$, where $\text{tr}[E_i E_j] = 0$ for all $i, j$ and each local operator $E_j$ is traceless on its support. Then for $\beta$ such that the states $\sigma(\mu)$ satisfy exponential decay of correlations, the Hessian of the log-partition function is bounded by

$$\Omega(\beta^2 e^{-c\beta})I \leq \nabla^2 \log \mathcal{Z}(\mu) \leq \mathcal{O}(\beta^2)I. \quad (18)$$

for some constant $c > 0$.

After the completion of the first version of this work, in [34, Corollary 4.4] Tang et al proved strong convexity bounds for high-temperature, (not necessarily geometrically) local Hamiltonians. More precisely,

for $\beta = \mathcal{O}(k^{-8})$, where $k$ is the maximal number of qudits each term acts on, they show that $L^{-1} \leq 2\beta^{-2}$. Although the result in Eq. (18) has the advantage of giving an estimate at any temperature, we see that also for noncommuting Gibbs states strong convexity holds at high enough temperatures.

The flowchart in Figure 3 gives the general scheme behind the maximum entropy method. Besides the exponential improvements in sample complexity laid out in Table 2, we also provide structural improvements which we elaborate on while also explaining the general scheme:

**Input:** The input consists of $m$ linearly independent operators $E_i$ of operator norm 1, some upper bound $\beta > 0$, precision parameter $\epsilon > 0$ and step size $\eta$. Moreover, we are given the promise that the state of interest satisfies (7). Although we will be mostly concerned with the case in which the observables are local, we show the convergence of the algorithm in general in Sec. A. The step size should be picked as $\eta = \mathcal{O}(U^{-1})$ with $U$ satisfying (16), as explained in Sec. A.1.

**Require:** We assume that we have access to copies of $\sigma(\lambda)$ and that we can perform measurements to estimate the expectation values of the observables $E_i$ up to precision $\epsilon > 0$. For most of the examples considered here, this will mostly require implementing simple, few-qudit measurements.

**Output:** The output is in the form of a vector of parameters $\mu$ of a Gibbs state $\sigma(\mu)$ as in Eq. (7). Note that unlike [5], our goal is not to estimate the vector of parameters $\lambda$, but rather obtain an approximation of the state satisfying $\sigma(\lambda) \approx \sigma(\mu)$. Here we will focus on quantifying the output's quality in relative entropy. More precisely, the output of the algorithm is guaranteed to satisfy $D(\sigma(\mu)\|\sigma(\lambda)) = \mathcal{O}(\epsilon n)$.

**Step 1:** In this step, we estimate the expectation values of each observable $E_i$ on the state $\sigma(\lambda)$ up to an error $\epsilon$. The resources to be optimized here are the number of samples of $\sigma(\lambda)$ we require and the complexity to implement the measurements. Using shadow tomography or Pauli grouping methods [13, 22, 40] we can do so requiring $\mathcal{O}(4^{r_0}\epsilon^{-2})$ polylog($m$)) samples and Pauli or 1-qubit measurements, where $r_0$ is maximum number of qubits the $E_i$ act on. This is discussed in more detail in Sec. C.

**Step 2:** The maximum entropy problem in Eq. (8) can be solved with gradient descent, as it corresponds to a strictly convex optimization problem [14]. At this step we simply initialize the algorithm to start at the maximally mixed state.
**Step 3:** It turns out that the gradient of the maximal entropy problem target function at $\mu_t$ is proportional to $e(\mu_t) - e(\lambda)$. Thus, to implement an iteration of gradient descent, it is necessary to compute $e(\mu_t)$, as we assumed we obtained an approximation of $e(\lambda)$ in Step 1. Moreover, it is imperative to ensure that the algorithm also converges with access to approximations to $e(\mu)$ and $e(\lambda)$. This is because most algorithms to compute $e(\mu_t)$ only provide approximate values [35, 37, 46, 51]. In addition, they usually have a poor scaling in the accuracy [51], making it necessary to show that the process converges with rough approximations to $e(\mu_t)$ and $e(\lambda)$. Here we show that it is indeed possible to perform this step with only approximate computations of expectation values. This allows us to identify classes of states for which the postprocessing can be done efficiently. These results are discussed in more detail in Sec. A.2.

**Convergence loop:** Now that we have seen how to compute one iteration of gradient descent, the next natural question is how many iterations are required to reach the stopping criterium. As this is a strongly convex problem, the convergence speed depends on the eigenvalues of the Hessian of the function being optimized [14, Section 9.1.2]. For max-entropy, this corresponds to bounding the eigenvalues of a generalized covariance matrix. In [5] the authors already showed such bounds for local Hamiltonians implying the convergence of the algorithm in a number of steps depending polynomially in $m$ and logarithmically on the tolerance $\epsilon$ for a fixed $\beta$. Here we improve their bound in several directions. First, we show that the algorithm converges after a polynomial in $m$ number of iterations for arbitrary $E_i$, albeit with a polynomial dependence on the error, as discussed in Sec. A.2. We then specialize to certain classes of states to obtain various improvements. For high-temperature, commuting Hamiltonians we provide a complete picture and show that the condition number of the Hessian is constant in Prop. 3.1. This implies that gradient descent converges in a number of iterations that scales logarithmically in system size and error.

**Stopping condition and recovery guarantees:** the stopping condition,

$$ \|e(\lambda) - e(\mu_t)\|_{\ell_2} \le \epsilon\sqrt{m}, $$

can be immediately converted to a relative entropy bound between the target state and the current iterate by the identity (9). This justifies its choice as a stopping criterion.

Since we already discussed the sample complexity of the maximum entropy method, let us now discuss some of its computational aspects. There are two quantities that govern the complexity of the algorithm: how many iterations we need to perform until we converge and how expensive each iteration is.

As the maximum entropy problem is strongly convex, one can show that $O(UL^{-1}\log(n\epsilon^{-1}))$ iterations suffice to converge. Here again $U, L$ are bounds on the Hessian as in Eq. (16). Nevertheless, we also show how to bypass requiring such bounds in Sec. A.1 and obtain that the maximum entropy algorithm converges after $O(m\epsilon^{-2})$ iterations without any locality assumptions on the $E_i$ or strong convexity guarantees. That is, the number of iterations is at most polynomial in $m$.

Let us now discuss the cost of implementing each iteration of the algorithm on a classical computer. This boils down to estimating $e(\mu_t)$ for the current iterate, which can be achieved in various ways. In the worst case, it is possible to just compute the matrix exponential and the expectation values directly, which yields a complexity of $O(d^{3n}m)$. However, for many of the classes considered here it is possible to do this computation in polynomial time. For instance, in [51] the authors show that for high-temperature Gibbs states it is possible to approximate the partition function efficiently. Thus, for the case of high-temperature Gibbs states, not necessarily commuting ones, we can do the postprocessing efficiently. It is also worth mentioning tensor network techniques to estimate $e(\mu_t)$. As we only require computing the expectation value of local observables, recent works show that it is possible to find tensor network states of constant bond dimension that approximate all expectation values of a given locality well [2, 25, 41]. From such a representation it is then possible to compute $e(\mu_t)$ efficiently in the 1D case by contracting the underlying tensor network. Unfortunately, however, in higher dimensions the contraction still takes exponential time. Table 2 provides a summary of the complexity of the postprocessing for various classes.

It is also worth considering the complexity of the postprocessing with access to a quantum computer, especially for commuting Hamiltonians. As all high-temperature Gibbs states satisfy exponential decay of correlations, the results of [17] imply that high-temperature Gibbs states can be prepared with a circuit of depth logarithmic in system size. Thus, by using the same method we used to estimate $e(\lambda)$ we can also estimate $e(\mu_t)$ by using the copies provided by the quantum computer. The complexity of the postprocessing for shadows is linear in system size. Thus, with access to a quantum computer we can perform the post-processing for each iteration in time $\tilde{O}(m\epsilon^{-2})$. As in this case we showed that the number of iterations is $\tilde{O}(1)$, we conclude that we can perform the postprocessing in time $\tilde{O}(m\epsilon^{-2})$. That is, for this class of systems our results give an arguably complete picture regarding the postprocessing, as it can be performed in a time comparable to writing down the vector of parameters, up to polylogarithmic factors. Furthermore, given that the underlying Gibbs states are known to satisfy TC and Prop. 3.1 gives es-
**Step 3:** It turns out that the gradient of the maximal entropy problem target function at $\mu_t$ is proportional to $e(\mu_t) - e(\lambda)$. Thus, to implement an iteration of gradient descent, it is necessary to compute $e(\mu_t)$, as we assumed we obtained an approximation of $e(\lambda)$ in Step 1. Moreover, it is imperative to ensure that the algorithm also converges with access to approximations to $e(\mu)$ and $e(\lambda)$. This is because most algorithms to compute $e(\mu_t)$ only provide approximate values [35, 37, 46, 51]. In addition, they usually have a poor scaling in the accuracy [51], making it necessary to show that the process converges with rough approximations to $e(\mu_t)$ and $e(\lambda)$. Here we show that it is indeed possible to perform this step with only approximate computations of expectation values. This allows us to identify classes of states for which the postprocessing can be done efficiently. These results are discussed in more detail in Sec. A.2.

**Convergence loop:** Now that we have seen how to compute one iteration of gradient descent, the next natural question is how many iterations are required to reach the stopping criterium. As this is a strongly convex problem, the convergence speed depends on the eigenvalues of the Hessian of the function being optimized [14, Section 9.1.2]. For max-entropy, this corresponds to bounding the eigenvalues of a generalized covariance matrix. In [5] the authors already showed such bounds for local Hamiltonians implying the convergence of the algorithm in a number of steps depending polynomially in $m$ and logarithmically on the tolerance $\epsilon$ for a fixed $\beta$. Here we improve their bound in several directions. First, we show that the algorithm converges after a polynomial in $m$ number of iterations for arbitrary $E_i$, albeit with a polynomial dependence on the error, as discussed in Sec. A.2. We then specialize to certain classes of states to obtain various improvements. For high-temperature, commuting Hamiltonians we provide a complete picture and show that the condition number of the Hessian is constant in Prop. 3.1. This implies that gradient descent converges in a number of iterations that scales logarithmically in system size and error.

**Stopping condition and recovery guarantees:** the stopping condition,

$$ \|e(\lambda) - e(\mu_t)\|_{\ell_2} \le \epsilon\sqrt{m}, $$

can be immediately converted to a relative entropy bound between the target state and the current iterate by the identity (9). This justifies its choice as a stopping criterion.

Since we already discussed the sample complexity of the maximum entropy method, let us now discuss some of its computational aspects. There are two quantities that govern the complexity of the algorithm: how many iterations we need to perform until we converge and how expensive each iteration is.

As the maximum entropy problem is strongly convex, one can show that $O(UL^{-1}\log(n\epsilon^{-1}))$ iterations suffice to converge. Here again $U, L$ are bounds on the Hessian as in Eq. (16). Nevertheless, we also show how to bypass requiring such bounds in Sec. A.1 and obtain that the maximum entropy algorithm converges after $O(m\epsilon^{-2})$ iterations without any locality assumptions on the $E_i$ or strong convexity guarantees. That is, the number of iterations is at most polynomial in $m$.

Let us now discuss the cost of implementing each iteration of the algorithm on a classical computer. This boils down to estimating $e(\mu_t)$ for the current iterate, which can be achieved in various ways. In the worst case, it is possible to just compute the matrix exponential and the expectation values directly, which yields a complexity of $O(d^{3n}m)$. However, for many of the classes considered here it is possible to do this computation in polynomial time. For instance, in [51] the authors show that for high-temperature Gibbs states it is possible to approximate the partition function efficiently. Thus, for the case of high-temperature Gibbs states, not necessarily commuting ones, we can do the postprocessing efficiently. It is also worth mentioning tensor network techniques to estimate $e(\mu_t)$. As we only require computing the expectation value of local observables, recent works show that it is possible to find tensor network states of constant bond dimension that approximate all expectation values of a given locality well [2, 25, 41]. From such a representation it is then possible to compute $e(\mu_t)$ efficiently in the 1D case by contracting the underlying tensor network. Unfortunately, however, in higher dimensions the contraction still takes exponential time. Table 2 provides a summary of the complexity of the postprocessing for various classes.

It is also worth considering the complexity of the postprocessing with access to a quantum computer, especially for commuting Hamiltonians. As all high-temperature Gibbs states satisfy exponential decay of correlations, the results of [17] imply that high-temperature Gibbs states can be prepared with a circuit of depth logarithmic in system size. Thus, by using the same method we used to estimate $e(\lambda)$ we can also estimate $e(\mu_t)$ by using the copies provided by the quantum computer. The complexity of the postprocessing for shadows is linear in system size. Thus, with access to a quantum computer we can perform the post-processing for each iteration in time $\tilde{O}(m\epsilon^{-2})$. As in this case we showed that the number of iterations is $\tilde{O}(1)$, we conclude that we can perform the postprocessing in time $\tilde{O}(m\epsilon^{-2})$. That is, for this class of systems our results give an arguably complete picture regarding the postprocessing, as it can be performed in a time comparable to writing down the vector of parameters, up to polylogarithmic factors. Furthermore, given that the underlying Gibbs states are known to satisfy TC and Prop. 3.1 gives es-
<figure><img src="image_4.png" /><figcaption>Figure 3: Flowchart for general maximum entropy algorithms.</figcaption></figure>

sentially optimal bounds on the covariance matrices, we believe that the present work essentially settles the question of how efficiently we can learn such Hamiltonians and corresponding Gibbs states. We discuss this in more detail in Sec. F.

Finally, an example of our bounds is illustrated in Fig. 4, where we show that the number of samples required to estimate a local observable to relative precision is essentially system-size independent.

<figure><img src="image_5.png" /><figcaption>Figure 4: Error in estimating a Lipschitz observable after performing the maximum entropy reconstruction method. The underlying state is a classical 1D-Gibbs state with randomly chosen nearest-neighbor interactions and inverse temperature $\beta = 1$. We estimated all the $Z_i Z_{i+1}$ expectation values from the original state based from $10^3$ samples of the original state. We then computed the upper bound on the trace distance predicted by Eq. (9) and Pinsker's inequality and compared it to the actual of discrepancy for a Lipschitz observable on the reconstructed and actual state. The Lipschitz observable was chosen as $\sum_i n^{-1} U Z_i Z_{i+2} U^\dagger$, where we picked $U$ as a depth 3 quantum circuit. We observe that the error incurred is essentially independent of system size, and we get good predictions even when the number of samples is smaller than it.</figcaption></figure>

# 4 Acknowledgements

DSF was supported by the VILLUM FONDEN via the QMATH Centre of Excellence under Grant No. 10059 and from the European Research Council (grant agreement no. 81876). The research of CR has been supported by project QTraj (ANR-20-CE40-0024-01) of the French National Research Agency (ANR) and by a Junior Researcher START Fellowship from the MCQST. DSF and CR are grateful to Richard Kueng, Fernando Brandão and Giacomo De Palma for interesting discussions.

# References

[1] Scott Aaronson. Shadow tomography of quantum states. In *STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, pages 325–338. ACM, New York, 2018. DOI: 10.1145/3188745.3188802.

[2] Álvaro M. Alhambra and J. Ignacio Cirac. Locally accurate tensor networks for thermal states and time evolution. *PRX Quantum*, 2 (4), November 2021. ISSN 2691-3399. DOI: 10.1103/prxquantum.2.040331.

[3] Anurag Anshu. Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems. *New Journal of Physics*, 18(8):083011, aug 2016. DOI: 10.1088/1367-2630/18/8/083011.

[4] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Efficient learning of commuting hamiltonians on lattices. Unpublished notes available at Anurag Anshu's website, (link to note).

[5] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Sample-efficient learning of interacting quantum
<figure><img src="image_5.png" /><figcaption>Figure 3: Flowchart for general maximum entropy algorithms.</figcaption></figure>

sentially optimal bounds on the covariance matrices, we believe that the present work essentially settles the question of how efficiently we can learn such Hamiltonians and corresponding Gibbs states. We discuss this in more detail in Sec. F.

Finally, an example of our bounds is illustrated in Fig. 4, where we show that the number of samples required to estimate a local observable to relative precision is essentially system-size independent.

<figure><img src="image_6.png" /><figcaption>Figure 4: Error in estimating a Lipschitz observable after performing the maximum entropy reconstruction method. The underlying state is a classical 1D-Gibbs state with randomly chosen nearest-neighbor interactions and inverse temperature $\beta = 1$. We estimated all the $Z_i Z_{i+1}$ expectation values from the original state based from $10^3$ samples of the original state. We then computed the upper bound on the trace distance predicted by Eq. (9) and Pinsker's inequality and compared it to the actual of discrepancy for a Lipschitz observable on the reconstructed and actual state. The Lipschitz observable was chosen as $\sum_i n^{-1} U Z_i Z_{i+2} U^\dagger$, where we picked $U$ as a depth 3 quantum circuit. We observe that the error incurred is essentially independent of system size, and we get good predictions even when the number of samples is smaller than it.</figcaption></figure>

# 4 Acknowledgements

DSF was supported by the VILLUM FONDEN via the QMATH Centre of Excellence under Grant No. 10059 and from the European Research Council (grant agreement no. 81876). The research of CR has been supported by project QTraj (ANR-20-CE40-0024-01) of the French National Research Agency (ANR) and by a Junior Researcher START Fellowship from the MCQST. DSF and CR are grateful to Richard Kueng, Fernando Brandão and Giacomo De Palma for interesting discussions.

# References

[1] Scott Aaronson. Shadow tomography of quantum states. In *STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, pages 325–338. ACM, New York, 2018. DOI: 10.1145/3188745.3188802.

[2] Álvaro M. Alhambra and J. Ignacio Cirac. Locally accurate tensor networks for thermal states and time evolution. *PRX Quantum*, 2 (4), November 2021. ISSN 2691-3399. DOI: 10.1103/prxquantum.2.040331.

[3] Anurag Anshu. Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems. *New Journal of Physics*, 18(8):083011, aug 2016. DOI: 10.1088/1367-2630/18/8/083011.

[4] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Efficient learning of commuting hamiltonians on lattices. Unpublished notes available at Anurag Anshu's website, (link to note).

[5] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. Sample-efficient learning of interacting quantum
systems. *Nature Physics*, may 2021. ISSN 1745-2473. DOI: 10.1038/s41567-021-01232-0.

[6] Huzihiro Araki. Gibbs states of a one dimensional quantum lattice. *Communications in Mathematical Physics*, 14(2):120-157, 1969. DOI: 10.1007/bf01645134.

[7] Ivan Bardet, Angela Capel, and Cambyse Rouzé. Approximate tensorization of the relative entropy for noncommuting conditional expectations. *arXiv preprint arXiv:2001.07981*, 2020. DOI: 10.1007/s00023-021-01088-3.

[8] Ivan Bardet, Ángela Capel, and Cambyse Rouzé. Approximate tensorization of the relative entropy for noncommuting conditional expectations. *Annales Henri Poincaré*, 23(1):101-140, July 2021. ISSN 1424-0661. DOI: 10.1007/s00023-021-01088-3.

[9] Thomas Barthel and Martin Kliesch. Quasilocality and efficient simulation of markovian quantum dynamics. *Physical review letters*, 108(23):230504, 2012. DOI: 10.1103/physrevlett.108.230504.

[10] T Baumgratz, A Nüßeler, M Cramer, and M B Plenio. A scalable maximum likelihood method for quantum state tomography. *New Journal of Physics*, 15(12):125004, dec 2013. DOI: 10.1088/1367-2630/15/12/125004.

[11] Salman Beigi, Nilanjana Datta, and Cambyse Rouzé. Quantum reverse hypercontractivity: its tensorization and application to strong converses. *Communications in Mathematical Physics*, 376 (2):753-794, 2020. DOI: 10.1007/s00220-020-03750-z.

[12] S.G Bobkov and F Götze. Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities. *Journal of Functional Analysis*, 163(1):1-28, April 1999. ISSN 00221236. DOI: 10.1006/jfan.1998.3326.

[13] Xavier Bonet-Monroig, Ryan Babbush, and Thomas E O'Brien. Nearly optimal measurement scheduling for partial tomography of quantum states. *Physical Review X*, 10(3):031064, 2020. DOI: 10.1103/physrevx.10.031064.

[14] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[15] Fernando G. S. L. Brandão and Marcus Cramer. Equivalence of Statistical Mechanical Ensembles for Non-Critical Quantum Systems. *arXiv:1502.03263 [cond-mat, physics:quant-ph]*, February 2015. arXiv: 1502.03263.

[16] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning. In *46th International Colloquium on Automata, Languages, and Programming*, volume 132 of LIPICS. Leibniz Int. Proc.

Inform., pages Art. No. 27, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.

[17] Fernando G. S. L. Brandão and Michael J. Kastoryano. Finite Correlation Length Implies Efficient Preparation of Quantum Thermal States. *Communications in Mathematical Physics*, 365 (1):1-16, January 2019. ISSN 0010-3616, 1432-0916. DOI: 10.1007/s00220-018-3150-8.

[18] Ángela Capel, Cambyse Rouzé, and Daniel Stilck França. The modified logarithmic sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions. *arXiv preprint arXiv:2009.11817*, 2020.

[19] Eric A Carlen and Jan Maas. An analog of the 2-wasserstein metric in non-commutative probability under which the fermionic fokker-planck equation is gradient flow for the entropy. *Communications in mathematical physics*, 331(3):887-926, 2014. DOI: 10.1007/s00220-014-2124-8.

[20] Eric A Carlen and Jan Maas. Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance. *Journal of Functional Analysis*, 273(5):1810-1869, 2017. DOI: 10.1016/j.jfa.2017.05.003.

[21] Eric A. Carlen and Jan Maas. Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems. *Journal of Statistical Physics*, 178(2):319-378, nov 2019. DOI: 10.1007/s10955-019-02434-w.

[22] Jordan Cotler and Frank Wilczek. Quantum overlapping tomography. *Physical Review Letters*, 124(10):100401, 2020. DOI: 10.32657/10356/170876.

[23] Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomography. *Nature Communications*, 1(1):149, dec 2010. ISSN 2041-1723. DOI: 10.1038/ncomms1147.

[24] Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley. Efficient quantum measurement of pauli operators in the presence of finite sampling error. *Quantum*, 5:385, January 2021. ISSN 2521-327X. DOI: 10.22331/q-2021-01-20-385. URL http://dx.doi.org/10.22331/q-2021-01-20-385.

[25] Alexander M. Dalzell and Fernando G. S. L. Brandão. Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians. *Quantum*, 3:187, September 2019. ISSN 2521-327X. DOI: 10.22331/q-2019-09-23-187.

[26] Giacomo De Palma and Cambyse Rouzé. Quantum concentration inequalities. *Annales Henri Poincaré*, 23(9):3391-3429, April 2022.
systems. *Nature Physics*, may 2021. ISSN 1745-2473. DOI: 10.1038/s41567-021-01232-0.

[6] Huzihiro Araki. Gibbs states of a one dimensional quantum lattice. *Communications in Mathematical Physics*, 14(2):120-157, 1969. DOI: 10.1007/bf01645134.

[7] Ivan Bardet, Angela Capel, and Cambyse Rouzé. Approximate tensorization of the relative entropy for noncommuting conditional expectations. *arXiv preprint arXiv:2001.07981*, 2020. DOI: 10.1007/s00023-021-01088-3.

[8] Ivan Bardet, Ángela Capel, and Cambyse Rouzé. Approximate tensorization of the relative entropy for noncommuting conditional expectations. *Annales Henri Poincaré*, 23(1):101-140, July 2021. ISSN 1424-0661. DOI: 10.1007/s00023-021-01088-3.

[9] Thomas Barthel and Martin Kliesch. Quasilocality and efficient simulation of markovian quantum dynamics. *Physical review letters*, 108(23):230504, 2012. DOI: 10.1103/physrevlett.108.230504.

[10] T Baumgratz, A Nüßeler, M Cramer, and M B Plenio. A scalable maximum likelihood method for quantum state tomography. *New Journal of Physics*, 15(12):125004, dec 2013. DOI: 10.1088/1367-2630/15/12/125004.

[11] Salman Beigi, Nilanjana Datta, and Cambyse Rouzé. Quantum reverse hypercontractivity: its tensorization and application to strong converses. *Communications in Mathematical Physics*, 376 (2):753-794, 2020. DOI: 10.1007/s00220-020-03750-z.

[12] S.G Bobkov and F Götze. Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities. *Journal of Functional Analysis*, 163(1):1-28, April 1999. ISSN 00221236. DOI: 10.1006/jfan.1998.3326.

[13] Xavier Bonet-Monroig, Ryan Babbush, and Thomas E O'Brien. Nearly optimal measurement scheduling for partial tomography of quantum states. *Physical Review X*, 10(3):031064, 2020. DOI: 10.1103/physrevx.10.031064.

[14] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[15] Fernando G. S. L. Brandão and Marcus Cramer. Equivalence of Statistical Mechanical Ensembles for Non-Critical Quantum Systems. *arXiv:1502.03263 [cond-mat, physics:quant-ph]*, February 2015. arXiv: 1502.03263.

[16] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning. In *46th International Colloquium on Automata, Languages, and Programming*, volume 132 of LIPICS. Leibniz Int. Proc.

*Inform.*, pages Art. No. 27, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.

[17] Fernando G. S. L. Brandão and Michael J. Kastoryano. Finite Correlation Length Implies Efficient Preparation of Quantum Thermal States. *Communications in Mathematical Physics*, 365 (1):1-16, January 2019. ISSN 0010-3616, 1432-0916. DOI: 10.1007/s00220-018-3150-8.

[18] Ángela Capel, Cambyse Rouzé, and Daniel Stilck França. The modified logarithmic sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions. *arXiv preprint arXiv:2009.11817*, 2020.

[19] Eric A Carlen and Jan Maas. An analog of the 2-wasserstein metric in non-commutative probability under which the fermionic fokker-planck equation is gradient flow for the entropy. *Communications in mathematical physics*, 331(3): 887-926, 2014. DOI: 10.1007/s00220-014-2124-8.

[20] Eric A Carlen and Jan Maas. Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance. *Journal of Functional Analysis*, 273(5):1810-1869, 2017. DOI: 10.1016/j.jfa.2017.05.003.

[21] Eric A. Carlen and Jan Maas. Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems. *Journal of Statistical Physics*, 178(2):319-378, nov 2019. DOI: 10.1007/s10955-019-02434-w.

[22] Jordan Cotler and Frank Wilczek. Quantum overlapping tomography. *Physical Review Letters*, 124(10):100401, 2020. DOI: 10.32657/10356/170876.

[23] Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomography. *Nature Communications*, 1(1):149, dec 2010. ISSN 2041-1723. DOI: 10.1038/ncomms1147.

[24] Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley. Efficient quantum measurement of pauli operators in the presence of finite sampling error. *Quantum*, 5:385, January 2021. ISSN 2521-327X. DOI: 10.22331/q-2021-01-20-385. URL http://dx.doi.org/10.22331/q-2021-01-20-385.

[25] Alexander M. Dalzell and Fernando G. S. L. Brandão. Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians. *Quantum*, 3:187, September 2019. ISSN 2521-327X. DOI: 10.22331/q-2019-09-23-187.

[26] Giacomo De Palma and Cambyse Rouzé. Quantum concentration inequalities. *Annales Henri Poincaré*, 23(9):3391-3429, April 2022.
ISSN 1424-0661. DOI: 10.1007/s00023-022-01181-1. URL http://dx.doi.org/10.1007/s00023-022-01181-1.

[27] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The minimax learning rates of normal and Ising undirected graphical models. *Electronic Journal of Statistics*, 14(1), January 2020. DOI: 10.1214/20-ejs1721.

[28] Roland L Dobrushin and Senya B Shlosman. Completely analytical interactions: constructive description. *Journal of Statistical Physics*, 46(5): 983-1014, 1987. DOI: 10.1007/bf01011153.

[29] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. *Nature Reviews Physics*, 2(7):382-390, jul 2020. ISSN 2522-5820. DOI: 10.1038/s42254-020-0186-4.

[30] Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng. Fast and robust quantum state tomography from few basis measurements. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. DOI: 10.4230/LIPICS.TQC.2021.7.

[31] Li Gao, Marius Junge, and Nicholas LaRacuente. Fisher Information and Logarithmic Sobolev Inequality for Matrix-Valued Functions. *Anales Henri Poincaré*, 21(11):3409-3478, Novem-ber 2020. ISSN 1424-0637, 1424-0661. DOI: 10.1007/s00023-020-00947-9.

[32] Nathael Gozlan and Christian Léonard. Transport inequalities. a survey. arXiv preprint arXiv:1003.3852, 2010.

[33] Jeongwan Haah, Aram Wettroth Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. *IEEE Trans. Inf. Theory*, 63(9):5628-5641, 2017. DOI: 10.1109/TIT.2017.2719044.

[34] Jeongwan Haah, Robin Kothari, and Ewin Tang. Optimal learning of quantum Hamiltonians from high-temperature Gibbs states, 2021. arXiv:2108.04842v1.

[35] Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*, pages 378-386, 2020. DOI: 10.1145/3357713.3384322.

[36] M. B. Hastings. Quantum belief propagation: An algorithm for thermal quantum systems. *Physical Review B*, 76(20), nov 2007. DOI: 10.1103/phys-revb.76.201102.

[37] M. B. Hastings. Quantum belief propagation: An algorithm for thermal quantum systems. *Physical Review B*, 76(20):201102, November 2007. ISSN 1098-0121, 1550-235X. DOI: 10.1103/Phys-RevB.76.201102.

[38] M. B. Hastings. Locality in Quantum Systems. arXiv:1008.5137 [math-ph, physics:quant-ph], August 2010. arXiv: 1008.5137.

[39] Matthew B. Hastings and Tohru Koma. Spectral Gap and Exponential Decay of Correlations. *Communications in Mathematical Physics*, 265 (3):781-804, August 2006. ISSN 0010-3616, 1432-0916. DOI: 10.1007/s00220-006-0030-4.

[40] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. *Nature Physics*, June 2020. DOI: 10.1038/s41567-020-0932-7.

[41] Yichen Huang. Locally accurate matrix product approximation to thermal states. *Science Bulletin*, 66(24):2456-2457, December 2021. ISSN 2095-9273. DOI: 10.1016/j.scib.2021.08.011. URL http://dx.doi.org/10.1016/j.scib.2021.08.011.

[42] E. T. Jaynes. Information Theory and Statistical Mechanics. *Physical Review*, 106(4):620-630, May 1957. ISSN 0031-899X. DOI: 10.1103/Phys-Rev.106.620.

[43] Andrew Jena, Scott Genin, and Michele Mosca. Pauli Partitioning with Respect to Gate Sets. *arXiv:1907.07859 [quant-ph]*, July 2019. arXiv: 1907.07859.

[44] Michael J. Kastoryano and Fernando G. S. L. Brandão. Quantum gibbs samplers: The commuting case. *Communications in Mathematical Physics*, 344(3):915-957, May 2016. ISSN 1432-0916. DOI: 10.1007/s00220-016-2641-8.

[45] Bobak Toussi Kiani, Giacomo De Palma, Miled Marvian, Zi-Wen Liu, and Seth Lloyd. Quantum earth mover's distance: A new approach to learning quantum data. arXiv preprint arXiv:2101.03037, 2021.

[46] M. Kliesch, C. Gogolin, M.J. Kastoryano, A. Rivera, and J. Eisert. Locality of Temperature. *Physical Review X*, 4(3):031019, July 2014. ISSN 2160-3308. DOI: 10.1103/PhysRevX.4.031019.

[47] Martin Kliesch, Christian Gogolin, and Jens Eisert. Lieb-Robinson Bounds and the Simulation of Time-Evolution of Local Observables in Lattice Systems. In Volker Bach and Luigi Delle Site, editors, *Many-Electron Approaches in Physics, Chemistry and Mathematics*, pages 301-318. Springer International Publishing, Cham, 2014. ISBN 978-3-319-06378-2 978-3-319-06379-9. DOI: 10.1007/978-3-319-06379-9_17. Series Title: Mathematical Physics Studies.

[48] Christian Kokail, Rick van Bijnen, Andreas Elben, Benoît Vermersch, and Peter Zoller. Entanglement hamiltonian tomography in quantum simulation. *Nature Physics*, 17(8):936-942, June 2021. ISSN 1745-2481. DOI: 10.1038/s41567-021-01260-w.

[49] Tomotaka Kuwahara and Keiji Saito. Gaussian
ISSN 1424-0661. DOI: 10.1007/s00023-022-01181-1. URL http://dx.doi.org/10.1007/s00023-022-01181-1.

[27] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The minimax learning rates of normal and Ising undirected graphical models. *Electronic Journal of Statistics*, 14(1), January 2020. DOI: 10.1214/20-ejs1721.

[28] Roland L Dobrushin and Senya B Shlosman. Completely analytical interactions: constructive description. *Journal of Statistical Physics*, 46(5): 983–1014, 1987. DOI: 10.1007/bf01011153.

[29] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. *Nature Reviews Physics*, 2(7):382–390, jul 2020. ISSN 2522-5820. DOI: 10.1038/s42254-020-0186-4.

[30] Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng. Fast and robust quantum state tomography from few basis measurements. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. DOI: 10.4230/LIPICS.TQC.2021.7.

[31] Li Gao, Marius Junge, and Nicholas LaRacuente. Fisher Information and Logarithmic Sobolev Inequality for Matrix-Valued Functions. *Anales Henri Poincaré*, 21(11):3409–3478, Novem-ber 2020. ISSN 1424-0637, 1424-0661. DOI: 10.1007/s00023-020-00947-9.

[32] Nathael Gozlan and Christian Léonard. Transport inequalities. a survey. arXiv preprint arXiv:1003.3852, 2010.

[33] Jeongwan Haah, Aram Wettroth Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. *IEEE Trans. Inf. Theory*, 63(9):5628–5641, 2017. DOI: 10.1109/TIT.2017.2719044.

[34] Jeongwan Haah, Robin Kothari, and Ewin Tang. Optimal learning of quantum Hamiltonians from high-temperature Gibbs states, 2021. arXiv:2108.04842v1.

[35] Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*, pages 378–386, 2020. DOI: 10.1145/3357713.3384322.

[36] M. B. Hastings. Quantum belief propagation: An algorithm for thermal quantum systems. *Physical Review B*, 76(20), nov 2007. DOI: 10.1103/phys-revb.76.201102.

[37] M. B. Hastings. Quantum belief propagation: An algorithm for thermal quantum systems. *Physical Review B*, 76(20):201102, November 2007. ISSN 1098-0121, 1550-235X. DOI: 10.1103/Phys-RevB.76.201102.

[38] M. B. Hastings. Locality in Quantum Systems. arXiv:1008.5137 [math-ph, physics:quant-ph], August 2010. arXiv: 1008.5137.

[39] Matthew B. Hastings and Tohru Koma. Spectral Gap and Exponential Decay of Correlations. *Communications in Mathematical Physics*, 265 (3):781–804, August 2006. ISSN 0010-3616, 1432-0916. DOI: 10.1007/s00220-006-0030-4.

[40] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. *Nature Physics*, June 2020. DOI: 10.1038/s41567-020-0932-7.

[41] Yichen Huang. Locally accurate matrix product approximation to thermal states. *Science Bulletin*, 66(24):2456–2457, December 2021. ISSN 2095-9273. DOI: 10.1016/j.scib.2021.08.011. URL http://dx.doi.org/10.1016/j.scib.2021.08.011.

[42] E. T. Jaynes. Information Theory and Statistical Mechanics. *Physical Review*, 106(4):620–630, May 1957. ISSN 0031-899X. DOI: 10.1103/Phys-Rev.106.620.

[43] Andrew Jena, Scott Genin, and Michele Mosca. Pauli Partitioning with Respect to Gate Sets. *arXiv:1907.07859 [quant-ph]*, July 2019. arXiv: 1907.07859.

[44] Michael J. Kastoryano and Fernando G. S. L. Brandão. Quantum gibbs samplers: The commuting case. *Communications in Mathematical Physics*, 344(3):915–957, May 2016. ISSN 1432-0916. DOI: 10.1007/s00220-016-2641-8.

[45] Bobak Toussi Kiani, Giacomo De Palma, Miled Marvian, Zi-Wen Liu, and Seth Lloyd. Quantum earth mover’s distance: A new approach to learning quantum data. arXiv preprint arXiv:2101.03037, 2021.

[46] M. Kliesch, C. Gogolin, M.J. Kastoryano, A. Rivera, and J. Eisert. Locality of Temperature. *Physical Review X*, 4(3):031019, July 2014. ISSN 2160-3308. DOI: 10.1103/PhysRevX.4.031019.

[47] Martin Kliesch, Christian Gogolin, and Jens Eisert. Lieb-Robinson Bounds and the Simulation of Time-Evolution of Local Observables in Lattice Systems. In Volker Bach and Luigi Delle Site, editors, *Many-Electron Approaches in Physics, Chemistry and Mathematics*, pages 301–318. Springer International Publishing, Cham, 2014. ISBN 978-3-319-06378-2 978-3-319-06379-9. DOI: 10.1007/978-3-319-06379-9_17. Series Title: Mathematical Physics Studies.

[48] Christian Kokail, Rick van Bijnen, Andreas Elben, Benoît Vermersch, and Peter Zoller. Entanglement hamiltonian tomography in quantum simulation. *Nature Physics*, 17(8):936–942, June 2021. ISSN 1745-2481. DOI: 10.1038/s41567-021-01260-w.

[49] Tomotaka Kuwahara and Keiji Saito. Gaussian
concentration bound and ensemble equivalence in
generic quantum many-body systems including
long-range interactions. *Annals of Physics*, 421,
168278, 2020. DOI: 10.1016/j.aop.2020.168278.

[50] Tomotaka Kuwahara and Keiji Saito. Eigenstate Thermalization from the Clustering Property of Correlation. *Physical Review Letters*, 124(20): 200604, May 2020. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.124.200604.

[51] Tomotaka Kuwahara, Kohtaro Kato, and Fernando G. S. L. Brandão. Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. *Phys. Rev. Lett.*, 124:220601, Jun 2020. DOI: 10.1103/PhysRevLett.124.220601.

[52] Tomotaka Kuwahara, Álvaro M. Alhambra, and Anurag Anshu. Improved Thermal Area Law and Quasilinear Time Algorithm for Quantum Gibbs States. *Physical Review X*, 11(1):011047, March 2021. ISSN 2160-3308. DOI: 10.1103/PhysRevX.11.011047.

[53] B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Pleinio, R. Blatt, and C. F. Roos. Efficient tomography of a quantum many-body system. *Nature Physics*, 13(12):1158-1162, September 2017. DOI: 10.1038/nphys4244.

[54] Andrea Montanari et al. Computational implications of reducing data to sufficient statistics. *Electronic Journal of Statistics*, 9(2):2370-2390, 2015. DOI: 10.1214/15-ejs1059.

[55] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Daniel Wichs and Yishay Mansour, editors, *Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016*, Cambridge, MA, USA, June 18-21, 2016, pages 899-912. ACM, 2016. DOI: 10.1145/2897518.2897544.

[56] Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd. The quantum wasserstein distance of order 1. *IEEE Transactions on Information Theory*, pages 1-1, 2021. DOI: 10.1109/tit.2021.3076442.

[57] David Poulin. Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics. *Physical Review Letters*, 104(19):190401, May 2010. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.104.190401.

[58] Maxim Raginsky and Igal Sason. *Concentration of Measure Inequalities in Information Theory, Communications, and Coding*. Now Publishers,

Norwell, MA, 2014. ISBN 978-1-60198-907-9.
OCLC: 1193114287.

[59] Cambyse Rouzé and Nilanjana Datta. Concentration of quantum states from quantum functional and transportation cost inequalities. *Journal of Mathematical Physics*, 60(1):012202, January 2019. DOI: 10.1063/1.5023210.

[60] Brian Swingle and Isaac H. Kim. Reconstructing quantum states from local data. *Physical Review Letters*, 113(26):260501, December 2014. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.113.260501. arXiv: 1407.2658.

[61] M. Talagrand. Transportation cost for Gaussian and other product measures. *Geometric and Functional Analysis*, 6(3):587-600, may 1996. DOI: 10.1007/bf02249265.

[62] Hal Tasaki. On the Local Equivalence Between the Canonical and the Microcanonical Ensembles for Quantum Spin Systems. *Journal of Statistical Physics*, 172(4):905-926, August 2018. ISSN 0022-4715, 1572-9613. DOI: 10.1007/s10955-018-2077-y.

[63] Kristan Temme, Fernando Pastawski, and Michael J Kastoryano. Hypercontractivity of quasi-free quantum semigroups. *Journal of Physics A: Mathematical and Theoretical*, 47(40):405303, October 2014. ISSN 1751-8113, 1751-8121. DOI: 10.1088/1751-8113/47/40/405303.

[64] Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo. Neural-network quantum state tomography. *Nature Physics*, 14(5):447-450, may 2018. ISSN 1745-2473. DOI: 10.1038/s41567-018-0048-5.

[65] Cédric Villani. *Optimal Transport*, volume 338 of *Grundlehren der mathematischen Wissenschaften*. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-540-71049-3 978-3-540-71050-9. DOI: 10.1007/978-3-540-71050-9.

[66] Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov. Interaction screening: Efficient and sample-optimal learning of Ising models. In *Advances in Neural Information Processing Systems*, pages 2595-2603, 2016.

[67] Jun Wang, Zhao-Yu Han, Song-Bo Wang, Zeyang Li, Liang-Zhu Mu, Heng Fan, and Lei Wang. Scalable quantum tomography with fidelity estimation. *Phys. Rev. A*, 101:032321, Mar 2020. DOI: 10.1103/PhysRevA.101.032321.

[68] Akram Youssry, Christopher Ferrie, and Marco Tomamichel. Efficient online quantum state estimation using a matrix-exponentiated gradient method. *New J. Phys.*, 21(3):033006, 2019. DOI: 10.1088/1367-2630/ab0438.
concentration bound and ensemble equivalence in
generic quantum many-body systems including
long-range interactions. *Annals of Physics*, 421:
168278, 2020. DOI: 10.1016/j.aop.2020.168278.

[50] Tomotaka Kuwahara and Keiji Saito. Eigenstate Thermalization from the Clustering Property of Correlation. *Physical Review Letters*, 124(20): 200604, May 2020. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.124.200604.

[51] Tomotaka Kuwahara, Kohtaro Kato, and Fernando G. S. L. Brandão. Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. *Phys. Rev. Lett.*, 124:220601, Jun 2020. DOI: 10.1103/PhysRevLett.124.220601.

[52] Tomotaka Kuwahara, Álvaro M. Alhambra, and Anurag Anshu. Improved Thermal Area Law and Quasilinear Time Algorithm for Quantum Gibbs States. *Physical Review X*, 11(1):011047, March 2021. ISSN 2160-3308. DOI: 10.1103/PhysRevX.11.011047.

[53] B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Pleinio, R. Blatt, and C. F. Roos. Efficient tomography of a quantum many-body system. *Nature Physics*, 13(12):1158-1162, September 2017. DOI: 10.1038/nphys4244.

[54] Andrea Montanari et al. Computational implications of reducing data to sufficient statistics. *Electronic Journal of Statistics*, 9(2):2370-2390, 2015. DOI: 10.1214/15-ejs1059.

[55] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Daniel Wichs and Yishay Mansour, editors, *Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016*, Cambridge, MA, USA, June 18-21, 2016, pages 899-912. ACM, 2016. DOI: 10.1145/2897518.2897544.

[56] Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd. The quantum wasserstein distance of order 1. *IEEE Transactions on Information Theory*, pages 1-1, 2021. DOI: 10.1109/tit.2021.3076442.

[57] David Poulin. Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics. *Physical Review Letters*, 104(19):190401, May 2010. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.104.190401.

[58] Maxim Raginsky and Igal Sason. *Concentration of Measure Inequalities in Information Theory, Communications, and Coding*. Now Publishers,

Norwell, MA, 2014. ISBN 978-1-60198-907-9.
OCLC: 1193114287.

[59] Cambyse Rouzé and Nilanjana Datta. Concentration of quantum states from quantum functional and transportation cost inequalities. *Journal of Mathematical Physics*, 60(1):012202, January 2019. DOI: 10.1063/1.5023210.

[60] Brian Swingle and Isaac H. Kim. Reconstructing quantum states from local data. *Physical Review Letters*, 113(26):260501, December 2014. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.113.260501. arXiv: 1407.2658.

[61] M. Talagrand. Transportation cost for Gaussian and other product measures. *Geometric and Functional Analysis*, 6(3):587-600, may 1996. DOI: 10.1007/bf02249265.

[62] Hal Tasaki. On the Local Equivalence Between the Canonical and the Microcanonical Ensembles for Quantum Spin Systems. *Journal of Statistical Physics*, 172(4):905-926, August 2018. ISSN 0022-4715, 1572-9613. DOI: 10.1007/s10955-018-2077-y.

[63] Kristan Temme, Fernando Pastawski, and Michael J Kastoryano. Hypercontractivity of quasi-free quantum semigroups. *Journal of Physics A: Mathematical and Theoretical*, 47(40):405303, October 2014. ISSN 1751-8113, 1751-8121. DOI: 10.1088/1751-8113/47/40/405303.

[64] Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo. Neural-network quantum state tomography. *Nature Physics*, 14(5):447-450, may 2018. ISSN 1745-2473. DOI: 10.1038/s41567-018-0048-5.

[65] Cédric Villani. *Optimal Transport*, volume 338 of *Grundlehren der mathematischen Wissenschaften*. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-540-71049-3 978-3-540-71050-9. DOI: 10.1007/978-3-540-71050-9.

[66] Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov. Interaction screening: Efficient and sample-optimal learning of Ising models. In *Advances in Neural Information Processing Systems*, pages 2595-2603, 2016.

[67] Jun Wang, Zhao-Yu Han, Song-Bo Wang, Zeyang Li, Liang-Zhu Mu, Heng Fan, and Lei Wang. Scalable quantum tomography with fidelity estimation. *Phys. Rev. A*, 101:032321, Mar 2020. DOI: 10.1103/PhysRevA.101.032321.

[68] Akram Youssry, Christopher Ferrie, and Marco Tomamichel. Efficient online quantum state estimation using a matrix-exponentiated gradient method. *New J. Phys.*, 21(3):033006, 2019. DOI: 10.1088/1367-2630/ab0438.
## Supplemental Material

This is the supplemental material to "Learning many-body states from very few copies". We will start in Sec. A with a review of the basic properties of the maximum entropy principle to learn quantum states. This is followed by a discussion of Lipschitz constants, Wasserstein distances and transportation cost inequalities in Sec. B. After that, in Sec. C we more explicitly discuss the interplay between the maximum entropy method and transportation cost inequalities. We then briefly discuss scenarios in which the postprocessing required for the maximum entropy method can be performed efficiently in Sec. E. In Sec. F we discuss a class of examples where we show that all technical results required to obtain the strongest guarantees of our work hold, that is, Gibbs states of commuting Hamiltonians at high enough temperature and 1D commuting Hamiltonians. Finally, in Sec. G we discuss lower bounds on the sample complexity of both shadow protocols and many-body algorithms that focus on a recovery in trace distance.

We start by setting some basic notations. Throughout this article, we denote by $M_k$ the algebra of $k \times k$ matrices on $\mathbb{C}^k$, whereas $M_k^{sa}$ denotes the subspace of self-adjoint matrices. The set of quantum states over $\mathbb{C}^k$ is denoted by $\mathcal{D}_k$. Typically, $k$ will be taken as $d^n$ for $n$ qudit systems. The trace on $M_k$ is denoted by $\text{tr}$. Given two quantum states $\rho, \sigma$, we denote by $S(\rho) = -\text{tr}[\rho \log(\rho)]$ the von Neumann entropy of $\rho$, and by $D(\rho||\sigma)$ the relative entropy between $\rho$ and $\sigma$, i.e. $D(\rho||\sigma) = \text{tr}[\rho(\log(\rho) - \log(\sigma))]$ whenever the support of $\rho$ is contained in that of $\sigma$ and $+\infty$ otherwise. The trace distance is denoted by $||\rho - \sigma||_{\text{tr}} := \text{tr} [|\rho - \sigma|]$ and the operator norm of an observable by $||O||_{\infty}$. Scalar products are denoted by $\langle \cdot | \cdot \rangle$. Moreover, we denote the $\ell_p$ norm of vectors by $|| \cdot ||_{\ell_p}$, and for $x \in \mathbb{R}^m$ and $r \in \mathbb{R}$, $B_{\ell_p}(x, r)$ denotes the ball of radius $r$ in $\ell_p$ norm around $x$. The identity matrix is denoted by $I$. The adjoint of an operator $A$ is denoted by $A^\dagger$ and that of a channel $\Phi$ with respect to the trace inner product by $\Phi^*$. For a hypergraph $G = (V, E)$ we will denote the distance between subsets of vertices induced by the hypergraph by dist.

## A Maximum entropy principle for quantum Gibbs states

One of the main aspects of this work concerns the effectiveness of the maximum entropy method for the tomography of quantum Gibbs states in various settings and regimes. Thus, we start by recalling some basic properties of the maximum entropy method. Our starting assumption is that the target state is well-described by a quantum Gibbs state with respect to a known set of operators and that we are given an upper bound on the inverse temperature:

**Definition A.1** (Gibbs state with respect to observables). Given a set of observables $\mathcal{E} = \{E_i\}_{i=1}^m$, $E_1, \dots, E_m \in M_k^{sa}$ being linearly independent with $||E_i||_\infty \le 1$, we call a state $\sigma \in \mathcal{D}_{d^n}$ a Gibbs state at inverse temperature $\beta > 0$ if there exists a vector $\lambda \in \mathbb{R}^m$ with $||\lambda||_{\ell_\infty} \le 1$ such that:

$$ \sigma = \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) / \mathcal{Z}(\lambda), \quad \text{where} \quad \mathcal{Z}(\lambda) = \text{tr} \left[ \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) \right] \quad (19) $$

denotes the partition function. In what follows, we will denote $\sigma$ by $\sigma(\lambda)$ and $\sum_i \lambda_i E_i = H(\lambda)$, where the dependence of $\sigma(\lambda)$ on $\beta$ is implicitly assumed.

We are mostly interested in the regime where $m \ll d^n$. Then the above condition can be interpreted as imposing that the matrix log($\sigma$) is sparse with respect to a known basis $\mathcal{E}$. A canonical example for such states are Gibbs states of local Hamiltonians on a lattice, for which $m = \mathcal{O}(n)$ and the observables $E_i$ are taken as tensor products of Pauli matrices acting on neighboring sites. But we could also consider a basis consisting of quasi-local operators or some subspace of Pauli strings.

Next, we review some basic facts about quantum Gibbs states. One of their main properties is that they satisfy a well-known maximum entropy principle [42]. This allows us to simultaneously show that the expectation values of the observables $\mathcal{E}$ completely characterize the state $\sigma(\lambda)$ and further provides us with a variational principle to learn a description from which we can infer an approximation of other expectation values. Let us start with the standard formulation of the maximum entropy principle:

**Proposition A.1** (Maximum entropy principle). Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a quantum Gibbs state (19) with respect to the basis $\mathcal{E}$ at inverse temperature $\beta$ and introduce $e_i(\lambda) := \text{tr}[\sigma(\lambda)E_i]$ for $i = 1, \dots, m$. Then $\sigma(\lambda)$ is the unique optimizer of the maximum entropy problem:

$$ \begin{array}{ll} \underset{\rho \in \mathcal{D}_{d^n}}{\text{maximize}} & S(\rho) \quad (20) \\ \text{subject to} & \text{tr}[E_i \rho] = e_i(\lambda) \quad \text{for all } i = 1, \dots, m. \end{array} $$
## Supplemental Material

This is the supplemental material to "Learning many-body states from very few copies". We will start in Sec. A with a review of the basic properties of the maximum entropy principle to learn quantum states. This is followed by a discussion of Lipschitz constants, Wasserstein distances and transportation cost inequalities in Sec. B. After that, in Sec. C we more explicitly discuss the interplay between the maximum entropy method and transportation cost inequalities. We then briefly discuss scenarios in which the postprocessing required for the maximum entropy method can be performed efficiently in Sec. E. In Sec. F we discuss a class of examples where we show that all technical results required to obtain the strongest guarantees of our work hold, that is, Gibbs states of commuting Hamiltonians at high enough temperature and 1D commuting Hamiltonians. Finally, in Sec. G we discuss lower bounds on the sample complexity of both shadow protocols and many-body algorithms that focus on a recovery in trace distance.

We start by setting some basic notations. Throughout this article, we denote by $M_k$ the algebra of $k \times k$ matrices on $\mathbb{C}^k$, whereas $M_k^{sa}$ denotes the subspace of self-adjoint matrices. The set of quantum states over $\mathbb{C}^k$ is denoted by $\mathcal{D}_k$. Typically, $k$ will be taken as $d^n$ for $n$ qudit systems. The trace on $M_k$ is denoted by tr. Given two quantum states $\rho, \sigma$, we denote by $S(\rho) = -\text{tr}[\rho \log(\rho)]$ the von Neumann entropy of $\rho$, and by $D(\rho||\sigma)$ the relative entropy between $\rho$ and $\sigma$, i.e. $D(\rho||\sigma) = \text{tr}[\rho(\log(\rho) - \log(\sigma))]$ whenever the support of $\rho$ is contained in that of $\sigma$ and $+\infty$ otherwise. The trace distance is denoted by $\|\rho - \sigma\|_{tr} := \text{tr} [|\rho - \sigma|]$ and the operator norm of an observable by $\|O\|_{\infty}$. Scalar products are denoted by $\langle \cdot | \cdot \rangle$. Moreover, we denote the $\ell_p$ norm of vectors by $\| \cdot \|_{\ell_p}$, and for $x \in \mathbb{R}^m$ and $r \in \mathbb{R}$, $B_{\ell_p}(x, r)$ denotes the ball of radius $r$ in $\ell_p$ norm around $x$. The identity matrix is denoted by $I$. The adjoint of an operator $A$ is denoted by $A^\dagger$ and that of a channel $\Phi$ with respect to the trace inner product by $\Phi^*$. For a hypergraph $G = (V, E)$ we will denote the distance between subsets of vertices induced by the hypergraph by dist.

## A Maximum entropy principle for quantum Gibbs states

One of the main aspects of this work concerns the effectiveness of the maximum entropy method for the tomography of quantum Gibbs states in various settings and regimes. Thus, we start by recalling some basic properties of the maximum entropy method. Our starting assumption is that the target state is well-described by a quantum Gibbs state with respect to a known set of operators and that we are given an upper bound on the inverse temperature:

**Definition A.1** (Gibbs state with respect to observables). Given a set of observables $\mathcal{E} = \{E_i\}_{i=1}^m$, $E_1, \dots, E_m \in M_{d^n}^{sa}$ being linearly independent with $\|E_i\|_{\infty} \le 1$, we call a state $\sigma \in \mathcal{D}_{d^n}$ a Gibbs state at inverse temperature $\beta > 0$ if there exists a vector $\lambda \in \mathbb{R}^m$ with $\|\lambda\|_{\ell_\infty} \le 1$ such that:

$$ \sigma = \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) / \mathcal{Z}(\lambda), \quad \text{where} \quad \mathcal{Z}(\lambda) = \text{tr} \left[ \exp \left( -\beta \sum_{i=1}^{m} \lambda_i E_i \right) \right] \quad (19) $$

denotes the partition function. In what follows, we will denote $\sigma$ by $\sigma(\lambda)$ and $\sum_i \lambda_i E_i = H(\lambda)$, where the dependence of $\sigma(\lambda)$ on $\beta$ is implicitly assumed.

We are mostly interested in the regime where $m \ll d^n$. Then the above condition can be interpreted as imposing that the matrix log($\sigma$) is sparse with respect to a known basis $\mathcal{E}$. A canonical example for such states are Gibbs states of local Hamiltonians on a lattice, for which $m = \mathcal{O}(n)$ and the observables $E_i$ are taken as tensor products of Pauli matrices acting on neighboring sites. But we could also consider a basis consisting of quasi-local operators or some subspace of Pauli strings.

Next, we review some basic facts about quantum Gibbs states. One of their main properties is that they satisfy a well-known maximum entropy principle [42]. This allows us to simultaneously show that the expectation values of the observables $\mathcal{E}$ completely characterize the state $\sigma(\lambda)$ and further provides us with a variational principle to learn a description from which we can infer an approximation of other expectation values. Let us start with the standard formulation of the maximum entropy principle:

**Proposition A.1** (Maximum entropy principle). Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a quantum Gibbs state (19) with respect to the basis $\mathcal{E}$ at inverse temperature $\beta$ and introduce $e_i(\lambda) := \text{tr}[\sigma(\lambda)E_i]$ for $i = 1, \dots, m$. Then $\sigma(\lambda)$ is the unique optimizer of the maximum entropy problem:

$$ \begin{array}{ll} \underset{\rho \in \mathcal{D}_{d^n}}{\text{maximize}} & S(\rho) \quad (20) \\ \text{subject to} & \text{tr}[E_i \rho] = e_i(\lambda) \quad \text{for all } i = 1, \dots, m. \end{array} $$
Moreover, $\sigma(\lambda)$ optimizes:

$$ \min_{\substack{\mu \in \mathbb{R}^m \\ \|\mu\|_{\ell_\infty} \le 1}} \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda). \qquad (21) $$

*Proof.* The proof is quite standard, but we include it for completeness. Note that for any state $\rho \ne \sigma$ that is a feasible point of Eq. (20) we have that:

$$ \begin{aligned} S(\sigma(\lambda)) - S(\rho) &= D(\rho \| \sigma(\lambda)) + \operatorname{tr}[(\rho - \sigma(\lambda)) \log(\sigma(\lambda))] \\ &= D(\rho \| \sigma(\lambda)) - \beta \sum_{i=1}^{m} \lambda_i \operatorname{tr}[E_i(\rho - \sigma(\lambda))] \\ &= D(\rho \| \sigma(\lambda)) > 0, \end{aligned} $$

where we have used the fact that $\operatorname{tr}[E_i(\rho - \sigma(\lambda))] = 0$ for all feasible points and that the relative entropy between two different states is strictly positive. This shows that $\sigma(\lambda)$ is the unique solution of (20). Eq. (21) is nothing but the dual program of Eq. (20). $\square$

Eq. (20) above gives a variational principle to find a quantum Gibbs state corresponding to certain expectation values. As it is well-known, one can use gradient descent to solve the problem in Eq. (21), as it is a strongly convex problem. Various recent works have discussed learning of Gibbs states [5, 48, 60] and it is certainly not a new idea to do so through maximum entropy methods. Nevertheless, we will discuss how to perform the postprocessing in more detail, as some recent results allow us to give this algorithm stronger performance guarantees. Finally, it should be said that although we draw inspiration from [5], our main goal will be to learn a set of parameters $\mu \in \mathbb{R}^m$ such that the Gibbs states $\sigma(\mu)$ and $\sigma(\lambda)$ are approximately the same on sufficiently regular observables while optimizing the sample complexity. This is in contrast to the goal of [5], which was to learn the vector of parameters $\lambda$. Learning $\lambda$ corresponds to a stronger requirement, in the sense that if the vectors of parameters are close, then the underlying states are also close, as made precise in the following Prop. A.2.

One of the facts that we are going to often exploit is that it is possible to efficiently estimate the relative entropy between two Gibbs states $\sigma(\lambda)$ and $\sigma(\mu)$ given the parameters $\lambda, \mu$ and the expectation values of observables in $\mathcal{E}$. This also yields an efficiently computable bound on the trace distance. Indeed, as observed in [5], we have that:

**Proposition A.2.** Let $\sigma(\mu), \sigma(\lambda) \in \mathcal{D}_{d^n}$ be Gibbs states with respect to a set of observables $\mathcal{E}$ at inverse temperature $\beta$. Denote $e(\lambda) = (\operatorname{tr}[\sigma(\lambda)E_i])_{i \in \mathbb{R}^m}$. Then

$$ \|\sigma(\mu) - \sigma(\lambda)\|_{tr}^2 \le D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle. \qquad (22) $$

*Proof.* The equality in Eq. (22) follows from a simple manipulation. Indeed:

$$ D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = \beta \sum_{i=1}^{m} (\lambda_i - \mu_i) \operatorname{tr}[[\sigma(\mu) - \sigma(\lambda)]E_i]. $$

The bound on the trace distance then follows by applying Pinkser's inequality. $\square$

The statement of Proposition A.2 allows us to obtain quantitative estimates on how well a given Gibbs state approximates another one in terms of the expectation values of known observables. In particular, a simple application of Hölder's inequality shows that if two Gibbs states are such that $|\operatorname{tr}[E_i[\sigma(\mu) - \sigma(\lambda)]]| \le \epsilon$, then the sum of their relative entropies is at most

$$ \beta |\langle \lambda - \mu | e(\lambda) - e(\mu) \rangle| \le \beta \|\lambda - \mu\|_{\ell_{\infty}} m\epsilon \le 2m\epsilon\beta, \qquad (23) $$

where the outer bound arises from our assumption that $\|\lambda\|_{\ell_{\infty}}, \|\mu\|_{\ell_{\infty}} \le 1$. Moreover, it is straightforward to relate the difference of the target function in Eq. (21) evaluated at two vectors to the difference of relative entropies between the target state and their corresponding Gibbs states:

**Lemma A.1.** Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a Gibbs state with respect to a set of observables $\mathcal{E}$ at inverse temperature $\beta > 0$ and define, for any $\mu \in \mathbb{R}^m$,

$$ f(\mu) := \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} e_i(\lambda) \mu_i. \qquad (24) $$
Moreover, $\sigma(\lambda)$ optimizes:

$$ \min_{\substack{\mu \in \mathbb{R}^m \\ \|\mu\|_{\ell_\infty} \le 1}} \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} \mu_i e_i(\lambda). \qquad (21) $$

*Proof.* The proof is quite standard, but we include it for completeness. Note that for any state $\rho \ne \sigma$ that is a feasible point of Eq. (20) we have that:

$$ \begin{aligned} S(\sigma(\lambda)) - S(\rho) &= D(\rho \| \sigma(\lambda)) + \operatorname{tr}[(\rho - \sigma(\lambda)) \log(\sigma(\lambda))] \\ &= D(\rho \| \sigma(\lambda)) - \beta \sum_{i=1}^{m} \lambda_i \operatorname{tr}[E_i(\rho - \sigma(\lambda))] \\ &= D(\rho \| \sigma(\lambda)) > 0, \end{aligned} $$

where we have used the fact that $\operatorname{tr}[E_i(\rho - \sigma(\lambda))] = 0$ for all feasible points and that the relative entropy between two different states is strictly positive. This shows that $\sigma(\lambda)$ is the unique solution of (20). Eq. (21) is nothing but the dual program of Eq. (20). $\square$

Eq. (20) above gives a variational principle to find a quantum Gibbs state corresponding to certain expectation values. As it is well-known, one can use gradient descent to solve the problem in Eq. (21), as it is a strongly convex problem. Various recent works have discussed learning of Gibbs states [5, 48, 60] and it is certainly not a new idea to do so through maximum entropy methods. Nevertheless, we will discuss how to perform the postprocessing in more detail, as some recent results allow us to give this algorithm stronger performance guarantees. Finally, it should be said that although we draw inspiration from [5], our main goal will be to learn a set of parameters $\mu \in \mathbb{R}^m$ such that the Gibbs states $\sigma(\mu)$ and $\sigma(\lambda)$ are approximately the same on sufficiently regular observables while optimizing the sample complexity. This is in contrast to the goal of [5], which was to learn the vector of parameters $\lambda$. Learning $\lambda$ corresponds to a stronger requirement, in the sense that if the vectors of parameters are close, then the underlying states are also close, as made precise in the following Prop. A.2.

One of the facts that we are going to often exploit is that it is possible to efficiently estimate the relative entropy between two Gibbs states $\sigma(\lambda)$ and $\sigma(\mu)$ given the parameters $\lambda, \mu$ and the expectation values of observables in $\mathcal{E}$. This also yields an efficiently computable bound on the trace distance. Indeed, as observed in [5], we have that:

**Proposition A.2.** Let $\sigma(\mu), \sigma(\lambda) \in \mathcal{D}_{d^n}$ be Gibbs states with respect to a set of observables $\mathcal{E}$ at inverse temperature $\beta$. Denote $e(\lambda) = (\operatorname{tr}[\sigma(\lambda)E_i])_{i \in \mathbb{R}^m}$. Then

$$ \|\sigma(\mu) - \sigma(\lambda)\|_{tr}^2 \le D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = -\beta \langle \lambda - \mu | e(\lambda) - e(\mu) \rangle. \qquad (22) $$

*Proof.* The equality in Eq. (22) follows from a simple manipulation. Indeed:

$$ D(\sigma(\mu)\|\sigma(\lambda)) + D(\sigma(\lambda)\|\sigma(\mu)) = \beta \sum_{i=1}^{m} (\lambda_i - \mu_i) \operatorname{tr}[[\sigma(\mu) - \sigma(\lambda)]E_i]. $$

The bound on the trace distance then follows by applying Pinkser's inequality. $\square$

The statement of Proposition A.2 allows us to obtain quantitative estimates on how well a given Gibbs state approximates another one in terms of the expectation values of known observables. In particular, a simple application of Hölder's inequality shows that if two Gibbs states are such that $|\operatorname{tr}[E_i[\sigma(\mu) - \sigma(\lambda)]]| \le \epsilon$, then the sum of their relative entropies is at most

$$ \beta |\langle \lambda - \mu | e(\lambda) - e(\mu) \rangle| \le \beta \|\lambda - \mu\|_{\ell_{\infty}} m \epsilon \le 2m\epsilon\beta, \qquad (23) $$

where the outer bound arises from our assumption that $\|\lambda\|_{\ell_{\infty}}, \|\mu\|_{\ell_{\infty}} \le 1$. Moreover, it is straightforward to relate the difference of the target function in Eq. (21) evaluated at two vectors to the difference of relative entropies between the target state and their corresponding Gibbs states:

**Lemma A.1.** Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a Gibbs state with respect to a set of observables $\mathcal{E}$ at inverse temperature $\beta > 0$ and define, for any $\mu \in \mathbb{R}^m$,

$$ f(\mu) := \log(\mathcal{Z}(\mu)) + \beta \sum_{i=1}^{m} e_i(\lambda) \mu_i. \qquad (24) $$
Then for any other two vectors $\mu, \xi \in \mathbb{R}^m$ with $\|\mu\|_{\ell_\infty}, \|\xi\|_{\ell_\infty} \le 1$:

$$f(\mu) - f(\xi) = D(\sigma(\lambda)\|\sigma(\mu)\| - D(\sigma(\lambda)\|\sigma(\xi)\|)).$$

*Proof.* The proof follows from straightforward manipulations. □

Thus, we see that a decrease of the target function $f$ when solving the max entropy problem is directly connected to the decrease of the relative entropy between the target state and the current iterate. We will later use this to show the convergence of gradient descent for solving the max entropy problem with arbitrary $\mathcal{E}$. However, before that we discuss how the convergence of the state $\sigma(\mu)$ to $\sigma(\lambda)$ is related to the convergence of the parameters $\mu$ to $\lambda$.

## A.1 Strong convexity and convergence guarantees

The maximum entropy problem (20) being a convex problem, it should come as no surprise that properties of the Hessian of the function being optimized are vital to understanding its complexity and stability. For the maximum entropy problem, the Hessian at a point is given by a generalized covariance matrix corresponding to the underlying Gibbs state. As the results of [5] showcase, the eigenvalues of such covariance matrices govern both the stability of Eq. (21) with respect to $\mu$ and the convergence of gradient descent to solve it. To see why, we recall some basic notions of optimization of convex functions and refer to [14] for an overview.

**Definition A.2 (Strong convexity).** Let $C \subset \mathbb{R}^m$ be a convex set. A twice differentiable function $f: C \to \mathbb{R}$ is called strongly convex with parameters $U, L > 0$ if we have for all $x \in C$ that:

$$UI \ge \nabla^2 f(x) \ge LI.$$

The optimization of strongly convex functions is well-understood. Indeed, we have:

**Proposition A.3.** Let $C \subset \mathbb{R}^m$ be a convex set and $f: C \to \mathbb{R}$ be strongly convex with parameters $L, U$ as in the definition above. Then, for all $\epsilon > 0$, the optimal value $\alpha := \min_{x \in C} f(x)$ is achieved up to error $\epsilon$ by the gradient descent algorithm initiated at $x^0 \in C$ with step size $U^{-1}$ after at most $S$ steps for

$$S \le \frac{U}{L} \log \left( \frac{f(x^0) - \alpha}{\epsilon} \right). \qquad (25)$$

Moreover, the gradient norm satisfies $\|\nabla f(x^k)\|_{\ell_2}^2 \le \delta$ after at most $S_\nabla$ steps with

$$S_{\nabla} \le \frac{U}{L} \log \left( \frac{2L(f(x^0) - \alpha)}{\delta} \right).$$

Finally, we have for all $\mu, \lambda \in C$ that:

$$\|\mu - \lambda\|_{\ell_2} \le L^{-1} \|\nabla f(\mu) - \nabla f(\lambda)\|_{\ell_2}. \qquad (26)$$

*Proof.* These are all standard results that can be found e.g. in [14, Section 9]. □

To see the relevance of these results for the maximum entropy problem, we recall the following Lemma:

**Lemma A.2.** Let $C = B_{\ell_\infty}(0, 1) \subset \mathbb{R}^m$, let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a Gibbs state with respect to a set of operators $\mathcal{E}$ at inverse temperature $\beta$ and define $f: C \to \mathbb{R}$ as in Eq. (24). Then:

$$(\nabla f(\mu))_i = \beta \operatorname{tr} [(\sigma(\lambda) - \sigma(\mu))E_i] \qquad (27)$$

and

$$(\nabla^2 f(\mu))_{ij} = \frac{\beta^2}{2} \operatorname{tr} [\{E_j, \Phi_{H(\mu)}(E_i)\}\sigma(\mu)] - \beta^2 e_i(\mu)e_j(\mu), \qquad (28)$$

with

$$\Phi_{H(\mu)}(E_i) = \int_{-\infty}^{+\infty} \nu_{\beta}(t) e^{-iH(\mu)t} E_i e^{iH(\mu)t} dt$$

where $\nu_\beta(t)$ is a probability density function whose Fourier transform is given by:

$$\hat{\nu}_{\beta}(\omega) = \frac{2 \tanh\left(\frac{\beta\omega}{2}\right)}{\beta\omega}.$$
Then for any other two vectors $\mu, \xi \in \mathbb{R}^m$ with $\|\mu\|_{\ell_{\infty}}, \|\xi\|_{\ell_{\infty}} \le 1$:

$$f(\mu) - f(\xi) = D(\sigma(\lambda)\|\sigma(\mu)\| - D(\sigma(\lambda)\|\sigma(\xi)\|).$$

*Proof.* The proof follows from straightforward manipulations. □

Thus, we see that a decrease of the target function $f$ when solving the max entropy problem is directly connected to the decrease of the relative entropy between the target state and the current iterate. We will later use this to show the convergence of gradient descent for solving the max entropy problem with arbitrary $\mathcal{E}$. However, before that we discuss how the convergence of the state $\sigma(\mu)$ to $\sigma(\lambda)$ is related to the convergence of the parameters $\mu$ to $\lambda$.

## A.1 Strong convexity and convergence guarantees

The maximum entropy problem (20) being a convex problem, it should come as no surprise that properties of the Hessian of the function being optimized are vital to understanding its complexity and stability. For the maximum entropy problem, the Hessian at a point is given by a generalized covariance matrix corresponding to the underlying Gibbs state. As the results of [5] showcase, the eigenvalues of such covariance matrices govern both the stability of Eq. (21) with respect to $\mu$ and the convergence of gradient descent to solve it. To see why, we recall some basic notions of optimization of convex functions and refer to [14] for an overview.

**Definition A.2 (Strong convexity).** Let $C \subset \mathbb{R}^m$ be a convex set. A twice differentiable function $f: C \to \mathbb{R}$ is called strongly convex with parameters $U, L > 0$ if we have for all $x \in C$ that:

$$U \ge \nabla^2 f(x) \ge LI.$$

The optimization of strongly convex functions is well-understood. Indeed, we have:

**Proposition A.3.** Let $C \subset \mathbb{R}^m$ be a convex set and $f: C \to \mathbb{R}$ be strongly convex with parameters $L, U$ as in the definition above. Then, for all $\epsilon > 0$, the optimal value $\alpha := \min_{x \in C} f(x)$ is achieved up to error $\epsilon$ by the gradient descent algorithm initiated at $x^0 \in C$ with step size $U^{-1}$ after at most $S$ steps for

$$S \le \frac{U}{L} \log \left( \frac{f(x^0) - \alpha}{\epsilon} \right). \qquad (25)$$

Moreover, the gradient norm satisfies $\|\nabla f(x^k)\|_{\ell_2}^2 \le \delta$ after at most $S_{\nabla}$ steps with

$$S_{\nabla} \le \frac{U}{L} \log \left( \frac{2L(f(x^0) - \alpha)}{\delta} \right).$$

Finally, we have for all $\mu, \lambda \in C$ that:

$$\|\mu - \lambda\|_{\ell_2} \le L^{-1} \|\nabla f(\mu) - \nabla f(\lambda)\|_{\ell_2}. \qquad (26)$$

*Proof.* These are all standard results that can be found e.g. in [14, Section 9]. □

To see the relevance of these results for the maximum entropy problem, we recall the following Lemma:

**Lemma A.2.** Let $C = B_{\ell_{\infty}}(0, 1) \subset \mathbb{R}^m$, let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a Gibbs state with respect to a set of operators $\mathcal{E}$ at inverse temperature $\beta$ and define $f: C \to \mathbb{R}$ as in Eq. (24). Then:

$$(\nabla f(\mu))_i = \beta \operatorname{tr} [(\sigma(\lambda) - \sigma(\mu))E_i] \qquad (27)$$

and

$$(\nabla^2 f(\mu))_{ij} = \frac{\beta^2}{2} \operatorname{tr} [\{E_j, \Phi_{H(\mu)}(E_i)\}\sigma(\mu)] - \beta^2 e_i(\mu)e_j(\mu), \qquad (28)$$

with

$$\Phi_{H(\mu)}(E_i) = \int_{-\infty}^{+\infty} \nu_{\beta}(t) e^{-iH(\mu)t} E_i e^{iH(\mu)t} dt$$

where $\nu_{\beta}(t)$ is a probability density function whose Fourier transform is given by:

$$\hat{\nu}_{\beta}(\omega) = \frac{2 \tanh\left(\frac{\beta\omega}{2}\right)}{\beta\omega}.$$
Proof. The quantum belief propagation theorem [36] states that:

$$ \frac{\partial}{\partial \lambda_i} e^{-\beta H(\lambda)} = -\frac{\beta}{2} \{e^{-\beta H(\lambda)}, \Phi_{H(\lambda)}(E_i)\}. $$

The claim then follows from a simple computation.

Thus, we see that in order to compute the gradient of the target function $f$ for the maximum entropy problem, we simply need to compute the expectation values of observables $\mathcal{E}$ on the current state and on the target state. Moreover, the Hessian is given by a generalized covariance matrix of the quantum Gibbs state. That this should indeed be interpreted as a covariance matrix is most easily seen by considering commuting Hamiltonians. Then indeed we have:

$$ (\nabla^2 f(\mu))_{ij} = \beta^2 [\text{tr}[\sigma(\mu)E_i E_j] - e_i(\mu)e_j(\mu)]. $$

For any Gibbs state it holds that:

**Proposition A.4.** For all $\mu \in B_{\ell_{\infty}}(0,1) \subset \mathbb{R}^m$, inverse temperature $\beta > 0$ and set of operators $\mathcal{E}$ of cardinality $m$, we have:

$$ \nabla^2 f(\mu) \le 2\beta^2 m I. $$

Proof. Note that

$$ \left| \text{tr} \left[ E_i \sigma(\mu) e^{iH(\mu)t} E_j e^{-iH(\mu)t} \right] \right| \le 1, $$

by Hölder's inequality, the submultiplicativity and unitary invariance of the operator norm and the fact that $\|E_i\|_{\infty} \le 1$. Similarly, we have that $|e_i(\mu)|, |e_j(\mu)| \le 1$. Thus, by Lemma A.2, $|\langle \nabla^2 f(\mu) \rangle_{ij}| \le 2\beta^2$. As $\nabla^2 f(\mu)$ is an $m \times m$ matrix, it follows from Gershgorin's circle theorem that $\nabla^2 f(\mu) \le 2\beta^2 mI$. $\square$

The proof above also showcases how exponential decay of correlations can be used to sharpen estimates on the maximal eigenvalue of $\nabla^2 f$, since in that case $(\nabla^2 f(\mu))_{ij}$ will have exponentially decaying entries. We discuss this in more detail when we focus on many-body states, for which we also consider the more challenging question of lower bounds.

## A.2 Convergence with approximate gradient computation and expectation values

Proposition A.3 already establishes the convergence of gradient descent whenever we can compute the gradient exactly and have a bound on $L$. Moreover, we see from Lemma A.2 that, in order to compute the gradient of the function $f$ above, it suffices to estimate local expectation values. Moreover, it is a standard result that gradient descent is strictly decreasing for strictly convex problems [14].

However, in many settings it is only possible or desirable to compute the expectation values of quantum Gibbs states approximately. Moreover, the expectation values of the target state are only known up to statistical fluctuations. It is then not too difficult to see that gradient descent still offers the convergence guarantees if we only approximately compute the gradient. We state the exact convergence guarantees and precision requirement for completeness.

**Theorem A.1** (Computational complexity and convergence guarantees). Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$ and $C_{\mathcal{E}}$ be the computational cost of computing $e'(\mu)$ satisfying

$$ \|e'(\mu) - e(\mu)\|_{\ell_2} \le \delta_{\mu} $$

for $\mu \in B_{\ell_{\infty}}(0,1)$ and $\delta_{\mu} > 0$. Moreover, assume that we are given an estimate $e'(\lambda)$ of $e(\lambda)$ satisfying

$$ \|e(\lambda) - e'(\lambda)\|_{\infty} \le \epsilon \qquad (29) $$

and that the partition function is strongly convex with parameters $U, L$. Then gradient descent starting at $\mu = 0$ with step size $\frac{1}{cU}$ and input data $e'(\lambda)$ converges to a state $\sigma(\mu_*)$ satisfying:

$$ \begin{aligned} \|\sigma(\lambda) - \sigma(\mu_*)\|_{tr}^2 &\le D(\sigma(\lambda)\|\sigma(\mu_*)\| + D(\sigma(\mu_*)\|\sigma(\lambda)\|) \\ &= \mathcal{O}(\beta\delta_{\mu}\min\{\sqrt{m}, \beta L^{-1}\delta_{\mu}\} + \beta\epsilon\min\{1, L^{-1}\beta\epsilon\}m). \end{aligned} $$
Proof. The quantum belief propagation theorem [36] states that:

$$ \frac{\partial}{\partial \lambda_i} e^{-\beta H(\lambda)} = -\frac{\beta}{2} \{e^{-\beta H(\lambda)}, \Phi_{H(\lambda)}(E_i)\}. $$

The claim then follows from a simple computation.

Thus, we see that in order to compute the gradient of the target function $f$ for the maximum entropy problem, we simply need to compute the expectation values of observables $\mathcal{E}$ on the current state and on the target state. Moreover, the Hessian is given by a generalized covariance matrix of the quantum Gibbs state. That this should indeed be interpreted as a covariance matrix is most easily seen by considering commuting Hamiltonians. Then indeed we have:

$$ (\nabla^2 f(\mu))_{ij} = \beta^2 [\text{tr}[\sigma(\mu)E_i E_j] - e_i(\mu)e_j(\mu)]. $$

For any Gibbs state it holds that:

**Proposition A.4.** For all $\mu \in B_{\ell_{\infty}}(0,1) \subset \mathbb{R}^m$, inverse temperature $\beta > 0$ and set of operators $\mathcal{E}$ of cardinality $m$, we have:

$$ \nabla^2 f(\mu) \le 2\beta^2 m I. $$

Proof. Note that

$$ \left| \text{tr} \left[ E_i \sigma(\mu) e^{iH(\mu)t} E_j e^{-iH(\mu)t} \right] \right| \le 1, $$

by Hölder's inequality, the submultiplicativity and unitary invariance of the operator norm and the fact that $\|E_i\|_{\infty} \le 1$. Similarly, we have that $|e_i(\mu)|, |e_j(\mu)| \le 1$. Thus, by Lemma A.2, $|\langle \nabla^2 f(\mu) \rangle_{ij}| \le 2\beta^2$. As $\nabla^2 f(\mu)$ is an $m \times m$ matrix, it follows from Gershgorin's circle theorem that $\nabla^2 f(\mu) \le 2\beta^2 mI$. $\square$

The proof above also showcases how exponential decay of correlations can be used to sharpen estimates on the maximal eigenvalue of $\nabla^2 f$, since in that case $(\nabla^2 f(\mu))_{ij}$ will have exponentially decaying entries. We discuss this in more detail when we focus on many-body states, for which we also consider the more challenging question of lower bounds.

## A.2 Convergence with approximate gradient computation and expectation values

Proposition A.3 already establishes the convergence of gradient descent whenever we can compute the gradient exactly and have a bound on $L$. Moreover, we see from Lemma A.2 that, in order to compute the gradient of the function $f$ above, it suffices to estimate local expectation values. Moreover, it is a standard result that gradient descent is strictly decreasing for strictly convex problems [14].

However, in many settings it is only possible or desirable to compute the expectation values of quantum Gibbs states approximately. Moreover, the expectation values of the target state are only known up to statistical fluctuations. It is then not too difficult to see that gradient descent still offers the convergence guarantees if we only approximately compute the gradient. We state the exact convergence guarantees and precision requirement for completeness.

**Theorem A.1** (Computational complexity and convergence guarantees). Let $\sigma(\lambda) \in \mathcal{D}_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$ and $C_{\mathcal{E}}$ be the computational cost of computing $e'(\mu)$ satisfying

$$ \|e'(\mu) - e(\mu)\|_{\ell_2} \le \delta_{\mu} $$

for $\mu \in B_{\ell_{\infty}}(0,1)$ and $\delta_{\mu} > 0$. Moreover, assume that we are given an estimate $e'(\lambda)$ of $e(\lambda)$ satisfying

$$ \|e(\lambda) - e'(\lambda)\|_{\infty} \le \epsilon \qquad (29) $$

and that the partition function is strongly convex with parameters $U, L$. Then gradient descent starting at $\mu = 0$ with step size $\frac{1}{cU}$ and input data $e'(\lambda)$ converges to a state $\sigma(\mu_*)$ satisfying:

$$ \begin{aligned} \|\sigma(\lambda) - \sigma(\mu_*)\|_{tr}^2 &\le D(\sigma(\lambda)\|\sigma(\mu_*)\| + D(\sigma(\mu_*)\|\sigma(\lambda)\|) \\ &= \mathcal{O}(\beta\delta_{\mu}\min\{\sqrt{m}, \beta L^{-1}\delta_{\mu}\} + \beta\epsilon\min\{1, L^{-1}\beta\epsilon\}m). \end{aligned} $$
in

$$ \mathcal{O}\left(\min\left\{UC_{\mathcal{E}}\beta^{-2}n\log(d)\delta_{\mu}^{-2}, \frac{UC_{\mathcal{E}}}{L}\log(n\epsilon^{-1})\right\}\right) $$

time.

We will prove this theorem at the end of this section, as before we will need some auxiliary statements. But the reader familiar with basic concepts from convex optimization should feel comfortable to skip them.

**Proposition A.5** (Convergence of gradient descent with constant relative precision). Let $\sigma(\lambda) \in D_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$, and for a Gibbs state $\sigma(\mu)$ let $z(\mu) \in \mathbb{R}^m$ be a vector such that

$$ \|z(\mu) - \beta(e(\lambda) - e(\mu))\|_{\ell_2} \le \frac{\beta}{4c} \|e(\mu) - e(\lambda)\|_{\ell_{\ell_2}} \quad (30) $$

for some $c > 10$. Then we have that:

$$ D(\sigma(\lambda)\|\sigma(\mu - \frac{z(\mu)}{cU})) - D(\sigma(\lambda)\|\sigma(\mu)) \le -\frac{9\beta^2\|e(\mu) - e(\lambda)\|_{\ell_2}^2}{10cU}, \quad (31) $$

where $U$ is a uniform bound on the operator norm of the Hessian of the function $f$ defined in Eq. (24).

*Proof.* From a Taylor expansion and strong convexity we have for any two points $\mu, \xi$ that:

$$ f(\xi) \le f(\mu) + \langle \nabla f(\mu) | (\xi - \mu) \rangle + \frac{U}{2} \|\xi - \mu\|_{\ell_2}^2. $$

Note that $\nabla f(\mu) = \beta(e(\lambda) - e(\mu))$ by Eq. (27). Setting $\xi = \mu - \frac{z}{cU} = \mu + \frac{1}{cU}(-\nabla f(\mu) + \nabla f(\mu) - z)$ we obtain:

$$ \begin{aligned} f\left(\mu - \frac{z}{cU}\right) & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \langle \nabla f(\mu) | \nabla f(\mu) - z \rangle + \frac{1}{2c^2U} \| - \nabla f(\mu) + \nabla f(\mu) - z \|_{\ell_2}^2 \\ & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \|\nabla f(\mu)\|_{\ell_2} \|\nabla f(\mu) - z\|_{\ell_2} + \frac{1}{2c^2U} (\|\nabla f(\mu)\|_{\ell_2} + \|\nabla f(\mu) - z\|_{\ell_2})^2, \end{aligned} $$

where in the last step we used the Cauchy-Schwarz inequality. By our assumption in Eq. (30) for $z \equiv z(\mu)$ we have:

$$ \begin{aligned} & f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \|\nabla f(\mu)\|_{\ell_2} \|\nabla f(\mu) - z\|_{\ell_2} + \frac{1}{2c^2U} (\|\nabla f(\mu)\|_{\ell_2} + \|\nabla f(\mu) - z\|_{\ell_2})^2 \\ & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{4c^2U} \|\nabla f(\mu)\|_{\ell_2}^2 + \frac{(1+(4c)^{-1})^2}{2c^2U} \|\nabla f(\mu)\|_{\ell_2}^2 \\ & = f(\mu) - \frac{1}{cU} \left(1 - \frac{1}{4c} - \frac{(1+(4c)^{-1})^2}{2c}\right) \|\nabla f(\mu)\|_{\ell_2}^2 \end{aligned} $$

and it can be readily checked that $\frac{1}{4c} + \frac{(1+(4c)^{-1})^2}{2c} \le \frac{1}{10}$ for $c \ge 10$. To conclude the proof, note that by Lemma A.1:

$$ D(\sigma(\lambda)\|\sigma(\mu - \frac{z}{cU})) - D(\sigma(\lambda)\|\sigma(\mu)) = f(\mu - \frac{z}{cU}) - f(\mu), $$

and insert $\|\nabla f(\mu)\|_{\ell_2}^2 = \beta^2\|e(\mu) - e(\lambda)\|_{\ell_2}^2$.

<figure><img src="image_6.png" /></figure>

Thus, we see that we make constant progress for the gradient descent algorithm if we only compute the derivative up to constant relative precision. We show now how to pick our stopping criterium based on approximate computations of the gradient which ensure convergence in polynomial time.

**Proposition A.6.** Let $\sigma(\lambda) \in D_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$. Suppose that at each time step $t$ of gradient descent we compute an estimate $e'(\mu_t)$ of $e(\mu_t)$ that satisfies

$$ \|e'(\mu_t) - e(\mu_t)\|_{\ell_{\ell_2}} \le \delta_{\mu}, $$
in

$$ \mathcal{O}\left(\min\left\{UC_{\mathcal{E}}\beta^{-2}n\log(d)\delta_{\mu}^{-2}, \frac{UC_{\mathcal{E}}}{L}\log(n\epsilon^{-1})\right\}\right) $$

time.

We will prove this theorem at the end of this section, as before we will need some auxiliary statements. But the reader familiar with basic concepts from convex optimization should feel comfortable to skip them.

**Proposition A.5** (Convergence of gradient descent with constant relative precision). Let $\sigma(\lambda) \in D_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$, and for a Gibbs state $\sigma(\mu)$ let $z(\mu) \in \mathbb{R}^m$ be a vector such that

$$ \|z(\mu) - \beta(e(\lambda) - e(\mu))\|_{\ell_2} \le \frac{\beta}{4c} \|e(\mu) - e(\lambda)\|_{\ell_{\ell_2}} \quad (30) $$

for some $c > 10$. Then we have that:

$$ D(\sigma(\lambda)\|\sigma(\mu - \frac{z(\mu)}{cU})) - D(\sigma(\lambda)\|\sigma(\mu)) \le -\frac{9\beta^2\|e(\mu) - e(\lambda)\|_{\ell_2}^2}{10cU}, \quad (31) $$

where $U$ is a uniform bound on the operator norm of the Hessian of the function $f$ defined in Eq. (24).

*Proof.* From a Taylor expansion and strong convexity we have for any two points $\mu, \xi$ that:

$$ f(\xi) \le f(\mu) + \langle \nabla f(\mu) | (\xi - \mu) \rangle + \frac{U}{2} \|\xi - \mu\|_{\ell_2}^2. $$

Note that $\nabla f(\mu) = \beta(e(\lambda) - e(\mu))$ by Eq. (27). Setting $\xi = \mu - \frac{z}{cU} = \mu + \frac{1}{cU}(-\nabla f(\mu) + \nabla f(\mu) - z)$ we obtain:

$$ \begin{aligned} & f\left(\mu - \frac{z}{cU}\right) \\ & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \langle \nabla f(\mu) | \nabla f(\mu) - z \rangle + \frac{1}{2c^2U} \| - \nabla f(\mu) + \nabla f(\mu) - z \|_{\ell_2}^2 \\ & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \|\nabla f(\mu)\|_{\ell_2} \|\nabla f(\mu) - z\|_{\ell_2} + \frac{1}{2c^2U} \left( \|\nabla f(\mu)\|_{\ell_2} + \|\nabla f(\mu) - z\|_{\ell_2} \right)^2, \end{aligned} $$

where in the last step we used the Cauchy-Schwarz inequality. By our assumption in Eq. (30) for $z \equiv z(\mu)$ we have:

$$ \begin{aligned} & f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{cU} \|\nabla f(\mu)\|_{\ell_2} \|\nabla f(\mu) - z\|_{\ell_2} + \frac{1}{2c^2U} \left( \|\nabla f(\mu)\|_{\ell_2} + \|\nabla f(\mu) - z\|_{\ell_2} \right)^2 \\ & \le f(\mu) - \frac{1}{cU} \|\nabla f\|_{\ell_2}^2 + \frac{1}{4c^2U} \|\nabla f(\mu)\|_{\ell_2}^2 + \frac{(1+(4c)^{-1})^2}{2c^2U} \|\nabla f(\mu)\|_{\ell_2}^2 \\ & = f(\mu) - \frac{1}{cU} \left( 1 - \frac{1}{4c} - \frac{(1+(4c)^{-1})^2}{2c} \right) \|\nabla f(\mu)\|_{\ell_2}^2 \end{aligned} $$

and it can be readily checked that $\frac{1}{4c} + \frac{(1+(4c)^{-1})^2}{2c} \le \frac{1}{10}$ for $c \ge 10$. To conclude the proof, note that by Lemma A.1:

$$ D(\sigma(\lambda)\|\sigma(\mu - \frac{z}{cU})) - D(\sigma(\lambda)\|\sigma(\mu)) = f(\mu - \frac{z}{cU}) - f(\mu), $$

and insert $\|\nabla f(\mu)\|_{\ell_2}^2 = \beta^2\|e(\mu) - e(\lambda)\|_{\ell_2}^2$.

<figure><img src="image_7.png" /></figure>

Thus, we see that we make constant progress for the gradient descent algorithm if we only compute the derivative up to constant relative precision. We show now how to pick our stopping criterium based on approximate computations of the gradient which ensure convergence in polynomial time.

**Proposition A.6.** Let $\sigma(\lambda) \in D_{d^n}$ be a quantum Gibbs state at inverse temperature $\beta$ with respect to a set of operators $\mathcal{E}$. Suppose that at each time step $t$ of gradient descent we compute an estimate $e'(\mu_t)$ of $e(\mu_t)$ that satisfies

$$ \|e'(\mu_t) - e(\mu_t)\|_{\ell_{\ell_2}} \le \delta_{\mu}, $$
and set the stopping criterion to be:

$$ \|e(\lambda) - e'(\mu_*)\|_{\ell_2} < (4c + 1)\delta_{\mu}. $$

for some constant $c > 10$. Then gradient descent starting at $\mu = 0$ with update rule $\mu_{t+1} := \mu_t - \frac{\beta(e(\lambda) - e'(\mu_t))}{cU}$ will converge to a state $\sigma(\mu_*)$ satisfying:

$$ \|\sigma(\lambda) - \sigma(\mu_*)\|_{tr}^2 \le D(\sigma(\lambda)\|\sigma(\mu_*)\| + D(\sigma(\mu_*)\|\sigma(\lambda)\|) \le 2(4c + 1)\beta\delta_{\mu}\sqrt{m} $$

after at most $O(U\beta^{-2}n\log(d)\delta_{\mu}^{-2})$ iterations.

**Proof.** First, we show that the relative precision bound required for Proposition A.5 holds under these assumptions. By our choice of the stopping criterion, at each time step we have the property that, while we did not stop,

$$ \begin{aligned} \|e(\lambda) - e(\mu_t)\|_{\ell_2} &= \|e(\mu) - e'(\mu_t) + e'(\mu_t) - e(\lambda)\|_{\ell_2} \\ &\ge \|e'(\mu_t) - e(\lambda)\|_{\ell_2} - \|e(\mu_t) - e'(\mu_t)\|_{\ell_2} \\ &\ge (4c + 1)\delta_{\mu} - \delta_{\mu} \\ &= 4c\delta_{\mu} \end{aligned} $$

by the reverse triangle inequality. As we assumed we have that $\|e'(\mu_t) - e(\mu_t)\|_{\ell_2} \le \delta_{\mu}$, it follows that $(4c)^{-1}\|e(\lambda) - e(\mu_t)\|_{\ell_2} \ge \|(e'(\mu_t) - e(\lambda)) - (e(\mu_t) - e(\lambda))\|_{\ell_2}$. Multiplying the inequality by $\beta$, we see that the conditions of Proposition A.5 are satisfied for $z(\mu_t) := \beta(e(\lambda) - e'(\mu_t))$. Let us now show the convergence. By our choice of initial point, we have that:

$$ D(\sigma(\lambda)\|\sigma(0)) \le n \log(d). $$

Now, suppose that we did not stop before $T$ iterations. It follows from a telescopic sum argument and Proposition A.5 that:

$$ D(\sigma(\lambda)\|\sigma(\mu_T)) \le n \log(d) - T \frac{9\beta^2(4c + 1)^2\delta_{\mu}^2}{10cU}, $$

since $\|e'(\mu_t) - e(\lambda)\| \ge (4c + 1)\delta_{\mu}$ at all iterations because we did not halt. As the relative entropy is positive, it follows that $T = O(\beta^{-2}Uc^{-1}n\log(d)\delta_{\mu}^{-2})$ before the stopping criterion is met. The recovery guarantee whenever the stopping criterion is met follows from Proposition A.2, the Cauchy-Schwarz inequality and the equivalence of norms $\|\lambda - \mu\|_{\ell_2} \le \sqrt{m}\|\lambda - \mu\|_{\ell_{\infty}} \le 2\sqrt{m}$. $\square$

Since we proved in Proposition A.4 that $U = O(\beta^2m)$, it follows that the number of iterations is $O(nm)$. Thus, we see that having a lower bound on the Hessian is not necessary to ensure convergence, but it can speed it up exponentially:

**Proposition A.7 (Exponential convergence of gradient descent with approximate gradients).** In the same setting as Proposition A.5 we have:

$$ f\left(\mu - \frac{z(\mu)}{cU}\right) - f(\lambda) \le \left(1 - \frac{18L}{10cU}\right) (f(\mu) - f(\lambda)). \quad (32) $$

In particular, gradient descent with approximate gradient computations starting at $\mu_0 = 0$ converges after $O(\frac{U}{L}\log(n\epsilon^{-1}))$ iterations to $\mu$ such that $f(\mu) - f(\lambda) \le \epsilon$.

**Proof.** For any strongly convex function $f$ and points $\mu, \xi \in C$ we have that:

$$ f(\xi) \ge f(\mu) + \langle \nabla f(\mu) | (\xi - \mu) \rangle + \frac{L}{2} \|\mu - \xi\|_{\ell_2}^2. $$

As explained in [14, Chapter 9], the R.H.S. of the equation above is a convex quadratic function of $\xi$ for $\mu$ fixed. One can then easily show that its minimum is achieved at $\tilde{\xi} = \mu - \frac{1}{L}\nabla f(\mu)$. From this we obtain:

$$ f(\mu) - f(\lambda) \ge -\frac{1}{2L} \|\nabla f(\mu)\|_{\ell_2}^2 = -\frac{\beta^2 \|e(\mu) - e(\lambda)\|_{\ell_2}^2}{2L}, $$
and set the stopping criterion to be:

$$ \|e(\lambda) - e'(\mu_*)\|_{\ell_2} < (4c + 1)\delta_{\mu}. $$

for some constant $c > 10$. Then gradient descent starting at $\mu = 0$ with update rule $\mu_{t+1} := \mu_t - \frac{\beta(e(\lambda) - e'(\mu_t))}{cU}$ will converge to a state $\sigma(\mu_*)$ satisfying:

$$ \|\sigma(\lambda) - \sigma(\mu_*)\|_{tr}^2 \le D(\sigma(\lambda)\|\sigma(\mu_*)\| + D(\sigma(\mu_*)\|\sigma(\lambda)\|) \le 2(4c + 1)\beta\delta_{\mu}\sqrt{m} $$

after at most $O(U\beta^{-2}n\log(d)\delta_{\mu}^{-2})$ iterations.

*Proof.* First, we show that the relative precision bound required for Proposition A.5 holds under these assumptions. By our choice of the stopping criterion, at each time step we have the property that, while we did not stop,

$$ \begin{aligned} \|e(\lambda) - e(\mu_t)\|_{\ell_2} &= \|e(\mu) - e'(\mu_t) + e'(\mu_t) - e(\lambda)\|_{\ell_2} \\ &\ge \|e'(\mu_t) - e(\lambda)\|_{\ell_2} - \|e(\mu_t) - e'(\mu_t)\|_{\ell_2} \\ &\ge (4c + 1)\delta_{\mu} - \delta_{\mu} \\ &= 4c\delta_{\mu} \end{aligned} $$

by the reverse triangle inequality. As we assumed we have that $\|e'(\mu_t) - e(\mu_t)\|_{\ell_2} \le \delta_{\mu}$, it follows that $(4c)^{-1}\|e(\lambda) - e(\mu_t)\|_{\ell_2} \ge \|(e'(\mu_t) - e(\lambda)) - (e(\mu_t) - e(\lambda))\|_{\ell_2}$. Multiplying the inequality by $\beta$, we see that the conditions of Proposition A.5 are satisfied for $z(\mu_t) := \beta(e(\lambda) - e'(\mu_t))$. Let us now show the convergence. By our choice of initial point, we have that:

$$ D(\sigma(\lambda)\|\sigma(0)) \le n \log(d). $$

Now, suppose that we did not stop before $T$ iterations. It follows from a telescopic sum argument and Proposition A.5 that:

$$ D(\sigma(\lambda)\|\sigma(\mu_T)) \le n \log(d) - T \frac{9\beta^2(4c + 1)^2\delta_{\mu}^2}{10cU}, $$

since $\|e'(\mu_t) - e(\lambda)\| \ge (4c + 1)\delta_{\mu}$ at all iterations because we did not halt. As the relative entropy is positive, it follows that $T = O(\beta^{-2}Uc^{-1}n\log(d)\delta_{\mu}^{-2})$ before the stopping criterion is met. The recovery guarantee whenever the stopping criterion is met follows from Proposition A.2, the Cauchy-Schwarz inequality and the equivalence of norms $\|\lambda - \mu\|_{\ell_2} \le \sqrt{m}\|\lambda - \mu\|_{\ell_{\infty}} \le 2\sqrt{m}$. $\square$

Since we proved in Proposition A.4 that $U = O(\beta^2m)$, it follows that the number of iterations is $O(nm)$. Thus, we see that having a lower bound on the Hessian is not necessary to ensure convergence, but it can speed it up exponentially:

**Proposition A.7** (Exponential convergence of gradient descent with approximate gradients). In the same setting as Proposition A.5 we have:

$$ f\left(\mu - \frac{z(\mu)}{cU}\right) - f(\lambda) \le \left(1 - \frac{18L}{10cU}\right) (f(\mu) - f(\lambda)). \quad (32) $$

In particular, gradient descent with approximate gradient computations starting at $\mu_0 = 0$ converges after $O(\frac{U}{L}\log(n\epsilon^{-1}))$ iterations to $\mu$ such that $f(\mu) - f(\lambda) \le \epsilon$.

*Proof.* For any strongly convex function $f$ and points $\mu, \xi \in C$ we have that:

$$ f(\xi) \ge f(\mu) + \langle \nabla f(\mu) | (\xi - \mu) \rangle + \frac{L}{2} \|\mu - \xi\|_{\ell_2}^2. $$

As explained in [14, Chapter 9], the R.H.S. of the equation above is a convex quadratic function of $\xi$ for $\mu$ fixed. One can then easily show that its minimum is achieved at $\tilde{\xi} = \mu - \frac{1}{L}\nabla f(\mu)$. From this we obtain:

$$ f(\mu) - f(\lambda) \ge -\frac{1}{2L} \|\nabla f(\mu)\|_{\ell_2}^2 = -\frac{\beta^2 \|e(\mu) - e(\lambda)\|_{\ell_2}^2}{2L}, $$
where the last identity follows from Eq. (27). By subtracting $f(\lambda)$ from both sides of the inequality (31) in Proposition A.5 and rearranging the terms we have that:

$$ 
\begin{aligned}
f\left(\mu - \frac{z(\mu)}{cU}\right) - f(\lambda) &\le f(\mu) - f(\lambda) - \frac{9\beta^2 \|e(\mu) - e(\lambda)\|_{\ell_2}^2}{10cU} \\
&\le f(\mu) - f(\lambda) - \frac{18L}{10cU}(f(\mu) - f(\lambda)) \\
&= \left(1 - \frac{18L}{10cU}\right) (f(\mu) - f(\lambda)).
\end{aligned}
$$

This yields the claim in Eq. (32). To obtain the second claim, note that applying Eq. (32) iteratively yields that after $k$ iterations we have that, for $\mu_k = \mu_{k-1} - \frac{z(\mu_{k-1})}{cU}$,

$$ (f(\mu_k) - f(\lambda)) \le \left(1 - \frac{18L}{10cU}\right)^k (f(0) - f(\lambda)). $$

By our choice of initial point and Lemma A.1 we have that $f(0) - f(\lambda) = O(n)$, which yields the claim solving for $k$ and noting that $-\log(1 - \frac{18L}{10cU}) = \Omega(\frac{L}{U})$. $\square$

**Remark A.1** (Comparison to mirror descent). It is also worth noting that the convergence guarantees of Proposition A.6 and update rules of gradient descent are very similar to the ones of mirror descent with the von Neumann entropy as potential, another algorithm used for learning of quantum states [1, 16, 30, 68]. In this context, mirror descent would use a similar update rule. However, instead of computing the whole gradient, i.e. all expectation values of the basis, for one iteration, mirror descent just requires us to find one $i$ such that $|e_i(\lambda) - e_i(\mu)| \ge \delta$ and updates the Hamiltonian in the direction $i$. This implies that the algorithm can be run online while we still estimate some other $e_i$, but we will not analyze this variation more in detail here.

Finally, we assumed so far that we knew the expectation values of the target state, $e(\lambda)$, exactly. However, it follows straightforwardly from Proposition A.6 that knowing each expectation value up to an error $\epsilon$ is sufficient to ensure that the additional error due to statistical fluctuations is at most $\epsilon m$. More precisely, if we have that $\|e(\lambda) - e'(\lambda)\|_{\infty} \le \epsilon$ for some $\epsilon > 0$, then any Gibbs state $\sigma(\mu_*)$ satisfying $\|e(\mu_*) - e'(\lambda)\|_{\ell_2} \le \delta$ satisfies:

$$ D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) \le 2\beta\delta\sqrt{m} + 2\beta\epsilon m $$

by Proposition A.2 and a Cauchy-Schwarz inequality. With these statements at hand we are finally ready to prove Thm. A.1.

**Proof of Thm. A.1.** We will show in Propositions A.6, A.7 that under the conditions outlined above, the maximum entropy problem will converge to a $\mu_*$ that satisfies:

$$ \|e'(\lambda) - e(\mu_*)\|_{\ell_2} \le (4c + 1)\delta_{\mu}. $$

Without making any assumptions on $L$ we can then bound

$$ 
\begin{aligned}
D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) &= \beta |\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| \\
&\le \beta (|\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| + |\langle\lambda - \mu_*|e'(\lambda) - e(\mu_*)\rangle|) \\
&\le (4c + 1)\delta_{\mu}\sqrt{m} + 2\beta\epsilon m
\end{aligned}
$$

by Hölder inequality and our assumptions on $e'(\lambda)$. Let us now discuss how strong convexity can improve these estimates. First note that by strong convexity and Cauchy-Schwarz we have:

$$ 
\begin{aligned}
D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) &= \beta |\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| \\
&\le \beta \|e(\lambda) - e(\mu_*)\|_{\ell_2} \|\lambda - \mu_*\|_{\ell_2} \\
&\le L^{-1}\beta^2 \|e(\lambda) - e(\mu_*)\|_{\ell_2}^2 \\
&\le L^{-1}\beta^2 (\|e'(\lambda) - e(\mu_*)\|_{\ell_2} + \|e(\lambda) - e'(\lambda)\|_{\ell_2})^2
\end{aligned}
$$

which yields the claim.

In short, we see that we can perform the recovery by simply computing the gradient approximately. In particular, as already hinted at in [5], this implies that recent methods developed to approximately compute the partition function of high-temperature quantum Gibbs states can be used to perform the postprocessing in polynomial time [35, 46, 49, 51]. This and other methods to compute the gradient are discussed in more detail in Sec. E. Furthermore, it should be noted that usually $L = \Omega(\beta^{-2})$ in the high temperature regime, making the bound independent of $\beta$ for such states. We refer to Sec. D for a summary of the cases for which bounds on $L$ are known.
where the last identity follows from Eq. (27). By subtracting $f(\lambda)$ from both sides of the inequality (31) in Proposition A.5 and rearranging the terms we have that:

$$ 
\begin{aligned}
f\left(\mu - \frac{z(\mu)}{cU}\right) - f(\lambda) &\le f(\mu) - f(\lambda) - \frac{9\beta^2 \|e(\mu) - e(\lambda)\|_{\ell_2}^2}{10cU} \\
&\le f(\mu) - f(\lambda) - \frac{18L}{10cU}(f(\mu) - f(\lambda)) \\
&= \left(1 - \frac{18L}{10cU}\right) (f(\mu) - f(\lambda)).
\end{aligned}
$$

This yields the claim in Eq. (32). To obtain the second claim, note that applying Eq. (32) iteratively yields that after $k$ iterations we have that, for $\mu_k = \mu_{k-1} - \frac{z(\mu_{k-1})}{cU}$,

$$ (f(\mu_k) - f(\lambda)) \le \left(1 - \frac{18L}{10cU}\right)^k (f(0) - f(\lambda)). $$

By our choice of initial point and Lemma A.1 we have that $f(0) - f(\lambda) = O(n)$, which yields the claim solving for $k$ and noting that $-\log(1 - \frac{18L}{10cU}) = \Omega(\frac{L}{U})$. $\square$

Remark A.1 (Comparison to mirror descent). It is also worth noting that the convergence guarantees of Proposition A.6 and update rules of gradient descent are very similar to the ones of mirror descent with the von Neumann entropy as potential, another algorithm used for learning of quantum states [1, 16, 30, 68]. In this context, mirror descent would use a similar update rule. However, instead of computing the whole gradient, i.e. all expectation values of the basis, for one iteration, mirror descent just requires us to find one $i$ such that $|e_i(\lambda) - e_i(\mu)| \ge \delta$ and updates the Hamiltonian in the direction $i$. This implies that the algorithm can be run online while we still estimate some other $e_i$, but we will not analyze this variation more in detail here.

Finally, we assumed so far that we knew the expectation values of the target state, $e(\lambda)$, exactly. However, it follows straightforwardly from Proposition A.6 that knowing each expectation value up to an error $\epsilon$ is sufficient to ensure that the additional error due to statistical fluctuations is at most $\epsilon m$. More precisely, if we have that $\|e(\lambda) - e'(\lambda)\|_{\infty} \le \epsilon$ for some $\epsilon > 0$, then any Gibbs state $\sigma(\mu_*)$ satisfying $\|e(\mu_*) - e'(\lambda)\|_{\ell_2} \le \delta$ satisfies:

$$ D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) \le 2\beta\delta\sqrt{m} + 2\beta\epsilon m $$

by Proposition A.2 and a Cauchy-Schwarz inequality. With these statements at hand we are finally ready to prove Thm. A.1.

Proof of Thm. A.1. We will show in Propositions A.6, A.7 that under the conditions outlined above, the maximum entropy problem will converge to a $\mu_*$ that satisfies:

$$ \|e'(\lambda) - e(\mu_*)\|_{\ell_2} \le (4c + 1)\delta_{\mu}. $$

Without making any assumptions on $L$ we can then bound

$$ 
\begin{aligned}
D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) &= \beta |\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| \\
&\le \beta (|\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| + |\langle\lambda - \mu_*|e'(\lambda) - e(\mu_*)\rangle|) \\
&\le (4c + 1)\delta_{\mu}\sqrt{m} + 2\beta\epsilon m
\end{aligned}
$$

by Hölder inequality and our assumptions on $e'(\lambda)$. Let us now discuss how strong convexity can improve these estimates. First note that by strong convexity and Cauchy-Schwarz we have:

$$ 
\begin{aligned}
D(\sigma(\lambda)\|\sigma(\mu_*)) + D(\sigma(\mu_*)\|\sigma(\lambda)) &= \beta |\langle\lambda - \mu_*|e(\lambda) - e(\mu_*)\rangle| \\
&\le \beta \|e(\lambda) - e(\mu_*)\|_{\ell_2} \|\lambda - \mu_*\|_{\ell_2} \\
&\le L^{-1}\beta^2 \|e(\lambda) - e(\mu_*)\|_{\ell_2}^2 \\
&\le L^{-1}\beta^2 (\|e'(\lambda) - e(\mu_*)\|_{\ell_2} + \|e(\lambda) - e'(\lambda)\|_{\ell_2})^2
\end{aligned}
$$

which yields the claim.

In short, we see that we can perform the recovery by simply computing the gradient approximately. In particular, as already hinted at in [5], this implies that recent methods developed to approximately compute the partition function of high-temperature quantum Gibbs states can be used to perform the postprocessing in polynomial time [35, 46, 49, 51]. This and other methods to compute the gradient are discussed in more detail in Sec. E. Furthermore, it should be noted that usually $L = \Omega(\beta^{-2})$ in the high temperature regime, making the bound independent of $\beta$ for such states. We refer to Sec. D for a summary of the cases for which bounds on $L$ are known.
# B Lipschitz constants and transportation cost inequalities

In this section, we identify conditions under which it is possible to estimate all expectation values of k-local observables up to an error $\epsilon$ by measuring $O(\text{poly}(k, \log(n), \epsilon^{-1}))$ copies of it, where $n$ is the system size, which constitutes an exponential improvement in some regimes. To obtain this result, we combine the maximum entropy method introduced in Section A with techniques from quantum optimal transport. In order to formalize and prove the result claimed, we resort to transportation cost inequalities and the notion of Lipschitz constants of observables, which we now introduce.

## B.1 Lipschitz constants and Wasserstein metrics

Transportation cost inequalities, introduced by Talagrand in the seminal paper [61], constitute one of the strongest tools available to show concentration of measure inequalities. In the quantum setting, their study was initiated in [19, 20, 56, 59]. Here we are going to show how they can also be used in the context of quantum tomography. On a high level, a transportation cost inequality for a state $\sigma$ quantifies by how much the relative entropy with respect to another state $\rho$ is a good proxy to estimate to what extent the expectation values of sufficiently regular observables differ on the states. As maximum entropy methods allow for a straightforward control of the convergence of the learning in relative entropy (cf. Section A), they can be combined to derive strong recovery guarantees. But first we need to define what we mean by a regular observable.

We start by a short discussion of Lipschitz constants and the Wasserstein-1 distance. To obtain an intuitive grasp of these concepts, one way is to first recall the variational formulation of the trace distance of two quantum states $\sigma, \rho$:

$$ \|\rho - \sigma\|_{tr} = \sup_{P=P^{\dagger}, \|P\|_{\infty} \le 1} \text{tr}[P(\rho - \sigma)]. $$

Seeing probability distributions as diagonal quantum states, we recover the variational formulation of the total variation distance by noting that we may restrict to diagonal operators $P$. Thus, the total variation distance quantifies by how much the expectation values of arbitrary bounded functions can differ under the two distributions. However, in many situations we are not interested in expectation values of arbitrary bounded observables, but rather observables that are sufficiently regular. E.g., most observables of physical interest are (quasi)-local. Thus, it is natural to look for distance measures between quantum states that capture the notion that two states do not differ by much when restricting to expectation values of sufficiently regular observables. These concerns are particularly relevant in the context of tomography protocols, as they should be designed to efficiently obtain a state that reflects the expectation values of extensive observables of the system. As we will see, one of the ways of ensuring that the sample complexity of the tomography algorithm reflects the regularity of the observables we wish to recover is through demanding a good recovery in the Wasserstein distance of order 1 [56, 59].

In the classical setting [58, Chapter 3], one way to define a Wasserstein-1 distance between two probability distributions is by replacing the optimization over all bounded diagonal observables by that over those that are sufficiently regular: given a metric $d$ on a sample space $\Omega$, we define the Lipschitz constant of a function $f: \Omega \to \mathbb{R}$ to be:

$$ \|f\|_{\text{Lip}} := \sup_{x,y \in \Omega} \frac{|f(x) - f(y)|}{d(x, y)}. $$

Denoting the Wasserstein-1 distance by $W_1$, it is given for two probability measures $p, q$ on $\Omega$ by

$$ W_1(p, q) := \sup_{f: \|f\|_{\text{Lip}} \le 1} |\mathbb{E}_p(f) - \mathbb{E}_q(f)|. \qquad (33) $$

That is, this metric quantifies by how much the expectation values of sufficiently regular functions can vary under $p$ and $q$, in clear analogy to the variational formulation of the trace distance. We refer to [58, 65] for other interpretations and formulations of this metric.

### B.1.1 Quantum Hamming Wasserstein distance

It is not immediately clear how to generalize these concepts to noncommutative spaces. There are by now several definitions of transport metrics for quantum states [26, 45, 56, 59]. As already noted in the main text, de Palma et al. defined the Lipschitz constant of an observable $O \in \mathcal{M}_{d^n}$ as [56]:

$$ \|O\|_{\text{Lip},\square} = \sqrt{n} \max_{\substack{1 \le i \le n \\ \rho, \sigma \in \mathcal{D}_{d^n}}} \max_{\text{tr}_i[\rho]=\text{tr}_i[\sigma]} \text{tr}[O(\rho - \sigma)]. \qquad (34) $$