betaFeedback

WorksComputer Science

Quantum Maximum Entropy Inference and Hamiltonian Learning

Abstract

Maximum entropy inference and learning of graphical models are pivotal tasks in learning theory and optimization. This work extends algorithms for these problems, including generalized iterative scaling (GIS) and gradient descent (GD), to the quantum realm. While the generalization, known as quantum iterative scaling (QIS), is straightforward, the key challenge lies in the non-commutative nature of quantum problem instances, rendering the convergence rate analysis significantly more challenging than the classical case. Our principal technical contribution centers on a rigorous analysis of the convergence rates, involving the establishment of both lower and upper bounds on the spectral radius of the Jacobian matrix for each iteration of these algorithms. Furthermore, we explore quasi-Newton methods to enhance the performance of QIS and GD. Specifically, we propose using Anderson mixing and the L-BFGS method for QIS and GD, respectively. These quasi-Newton techniques exhibit remarkable efficiency gains, resulting in orders of magnitude improvements in performance. As an application, our algorithms provide a viable approach to designing Hamiltonian learning algorithms.

Introduction

Maximum entropy inference is a widely used method in machine learning, particularly in the context of graphical models ([37, 28, 1, 12, 24]) and natural language processing ([10]). In graphical models, it is known as the backward mapping, the problem of computing the model parameters from the marginal information ([47]). The inverse problem of estimating marginal parameters from the model parameters is called the forward mapping.

Maximum entropy inference is also a core concept in statistical physics ([26]) known as the Jaynes’ principle which links statistical mechanics and information theory. The Hammersley-Clifford theorem establishes that, in the classical case, any positive probability distribution satisfying the local Markov property can be represented as a Gibbs distribution ([31]). Hence, maximum entropy inference is equivalent to learning the classical Hamiltonian defining the Gibbs distribution ((Li & Korb, 2020)). In recent years, sample-efficient and time-efficient algorithms with demonstrated effectiveness for specific classical graphical models have emerged ([43, 12, 24, 29, 46]). However, it is technically non-trivial to extend these classical techniques into the quantum domain ((Wiebe et al., 2014a,b; Evans et al., 2019; Wang et al., 2017; Anshu et al., 2021; Amin et al., 2018; Bairey et al., 2019, 2020; Haah et al., 2022; Bakshi et al., 2023)) due to the non-commutativity of quantum Hamiltonian terms.

In quantum physics, the maximum entropy inference problem naturally arise when we only have partial local information about a quantum many-body system. Let HjH_j for j=1,2,…,mj = 1, 2, \ldots, m be local observables of, say, an nn-qubit quantum system. What the state of the system would likely be given only the local marginal information αj=tr⁡(Hjρ)\alpha_j = \operatorname{tr}(H_j\rho)? The Jaynes’ principle suggests that we take the state to be the one with the maximum von Neumann entropy, which is always a Gibbs state of the form ξH(μ)=1Z(μ)e−βH(μ)\xi_{H}(\mu) = \frac{1}{Z(\mu)}e^{-\beta H(\mu)} where H(μ)=∑j=1mμjHjH(\mu) = \sum_{j=1}^{m}\mu_jH_j is a quantum Hamiltonian parameterized by a vector of real numbers μ=(μj)j=1m\mu= (\mu_j)_{j=1}^{m}. That is, given as input the average values α=(αj)j=1m\alpha= (\alpha_j)_{j=1}^{m} encoding local information, the parameter vector μ\mu of the Hamiltonian is uniquely determined by α\alpha and the computation of α\alpha from μ\mu is an example of the backward mapping problems.

Maximum entropy problem

maximize:S(ρ)subject to:⟨Hj,ρ⟩=αj,ρ is a density matrix,\begin{aligned} \text{maximize:}\quad& S(\rho)\\ \text{subject to:}\quad& \langle H_j,\rho\rangle= \alpha_j,\\ & \rho\text{ is a density matrix,} \end{aligned}

Dual problem

minimize:ln⁡tr⁡exp⁡(∑jλjHj)−λ⋅αsubject to:λj∈R.\begin{aligned} \text{minimize:}\quad& \ln\operatorname{tr}\exp\left(\sum_j\lambda_jH_j\right)-\lambda\cdot\alpha\\ \text{subject to:}\quad& \lambda_j\in\mathbb{R}. \end{aligned}

Algorithms for solving the maximum entropy inference problem include the generalized iterative scaling method ([16, 18]) which has a rich history of study in statistics and gradient descent and variable metric methods originated from optimization research ([36]). In this paper, we study quantum generalizations of both the Generalized Iterative Scaling (GIS) algorithm and quasi-Newton methods for solving the Hamiltonian inference problem. Overall, the paper offers three key contributions. Firstly, we present a convergence rate analysis for both Quantum Iterative Scaling (QIS) and Gradient Descent (GD) algorithms. This is achieved by representing the iteration’s Jacobian in a concise and explicit formula, which extends a fundamental result from Liang et al. [34]. Secondly, we establish bounds on the eigenvalues of the Jacobian, proving polynomial convergence of both the QIS and GD algorithms. This contribution represents the main technical novelty of the paper. The non-commutativity of the Hamiltonian terms makes the convergence analysis highly non-trivial and different from classical proof techniques. We bound the Hessian of the log-partition function using the monotonicity of the Bogoliubov–Kubo–Mori (BKM) canonical-correlation form and a lower bound from Anshu et al. [4]. These bounds control the spectrum of the QIS Jacobian even though the Hessian does not have the simple form available in the classical setting. Lastly, we investigate two variants of quasi-Newton methods that accelerate the iterative processes for QIS and GD, respectively, resulting in significant performance improvements. In the following, we provide a detailed discussion of these three contributions, highlighting their technical significance and implications.

Explicit Jacobian Formula for Iterations. The QIS algorithm we consider here is a natural quantum counterpart to the GIS algorithm. When the matrices are all diagonal, the QIS algorithm reduces to the GIS algorithm for classical maximum entropy inference. Previous work (Ji, 2022) has shown that the algorithm indeed converges to the correct solution of the maximum entropy problem using the auxiliary function method and matrix inequalities. However, while the auxiliary function method is versatile, it falls short in providing a precise assessment of the algorithms’ convergence rates. To solve this problem, we perform a more tailored analysis of the QIS algorithm’s convergence rate in this paper. In the classical case, a corresponding convergence analysis for the GIS algorithm is detailed in Liang et al. [34]. This classical analysis leverages Ostrowski’s theorem, which bounds the convergence rate of an iterative procedure by the spectral radius of the Jacobian matrix associated with the iteration. Our contribution extends the classical analysis to the quantum setting and addresses the difficulty that the gradient of the exponential function for matrices is much more involved than the classical counterpart. We provide a closed-form formula for the Jacobian of the QIS iteration, generalizing the approach of Liang et al. [34]. The formula has a concise form 1−P−1L1 - P^{-1}L where PP is a diagonal matrix whose entries are the mean values of operators related to HjH_j over the Gibbs state and LL is the Hessian of the log-partition function. This connection to the Hessian matrix LL is crucial for the convergence proof.

The maximum entropy problem has a dual problem, which is an unconstrained optimization problem regarding the log-partition function in Figure 1. As a comparison, we consider the gradient descent (GD) algorithm for the dual problem. The Jacobian of the GD update process can be computed as 1−ηL1 - \eta L where LL is the Hessian of the log-partition function and η\eta is the step size of GD. In a sense, the Jacobian of the QIS update rule, 1−P−1L1 - P^{-1}L, can be seen as a mechanism to adaptively choose the step size for different directions. This is the main advantage that QIS has over the GD algorithm. Numerical simulations in Figure 2 of § 6 also show that QIS converges significantly faster than GD.

Maximum entropy problem and its dual problem

Figure 1. The maximum entropy problem and its dual problem. Here, S(ρ)=−tr⁡(ρln⁡ρ)S(\rho) = -\operatorname{tr}(\rho\ln\rho) is the von Neumann entropy of ρ\rho.

Figure 2. Comparison of QIS and GD algorithms. The loss in measured by the error in the objective function of the maximum entropy problem.

Upper and Lower Bounds for the Jacobian. As our main technical contribution, we analyze the eigenvalues of the Jacobian matrix by establishing both the lower and upper bounds for them.

First, we prove that all eigenvalues of the Jacobian are non-negative by showing the upper bound L⪯PL \preceq P for the Hessian of the log-partition function. The bound follows from monotonicity of the BKM canonical-correlation form under a completed quantum-to-classical measurement channel, as proved in Section C using the result of Petz [40].

Second, we show that the largest eigenvalue of the Jacobian is bounded away from 1 using the lower bound on the Hessian from Anshu et al. [4], recalled in Section D. The upper and lower bounds of the Jacobian together complete the convergence rate analysis of the QIS algorithm by using Ostrowski’s theorem (Theorem B.1). As a corollary, this shows that for local Hamiltonians satisfying certain technical conditions, the backward mapping problem can be reduced to the forward mapping problem efficiently. The forward mapping problem is unfortunately a hard problem in general and one may have to resort to approximate inference methods such as variational inference ([47, 14]) or Markov entropy decomposition ([22, 41])

Accelerations. While the QIS and GD algorithms enjoy provable convergence analysis and are expected to converge in a polynomial number of iterations for local Hamiltonians at constant temperature, it can exhibit sluggish performance in practical scenarios. For classical learning of model parameters, quasi-Newton methods are recommended for solving the maximum entropy inference problems, as suggested in a systematic comparison of classical maximum entropy inference algorithms performed in Malouf [36]. Even though the convergence analysis is usually less established, quasi-Newton methods are usually much faster in practice than iterative scaling and gradient descent algorithms.

In light of this, we investigate two families of quasi-Newton accelerations of the algorithms. The first family of heuristic acceleration is based on the Anderson mixing method (Anderson [3]). The Anderson mixing algorithm is a heuristic method for accelerating slow fixed-point iterative algorithms. It can be seamlessly integrated to work with the QIS algorithm as QIS is indeed a fixed-point iteration. The Anderson mixing accelerated QIS algorithm (AM-QIS) has exactly the same computational requirement of the QIS algorithm in terms of the oracle access and the type of measurements required on the quantum system. The second family is based on the BFGS method (Nocedal & Wright [38]; Yuan [51]) and in particular the limited memory variant, L-BFGS is applied to the GD algorithm (L-BFGS-GD). In our numerical simulations, we observed that AM-QIS and L-BFGS-GD have comparable performance, usually faster by orders of magnitude than the standard QIS and GD algorithms.

We believe that applying such quasi-Newton heuristics is important for quantum optimization algorithms like the QIS algorithm considered here. While quantum computing offers a promising new paradigm with the potential for substantial speedups in specific problems, the practical construction of large-scale quantum computers is still in its early stages. Current quantum computing technology has limitations in terms of scale and suffers from errors. Hence, quantum computing power remains a scarce and valuable resource. Given this situation, the careful optimization of resources required to solve problems on quantum computers emerges as a critical task. The use of Anderson mixing and BFGS for Hamiltonian inference algorithms and potentially for other fixed-point iterative quantum algorithms represents an attempt to achieve such resource optimization. Notably, this approach is not unique to quantum computing. In fact, the quasi-Newton method, which developed into an important optimization heuristics, was initially developed by W. Davidon while working with early classical computers, which often crashed before producing correct results. In response, he devised faster heuristics to expedite calculations later known as the first quasi-Newton method! Quantum computers are currently in its very early stages. They are unstable and prone to errors just like classical computers in the early days; hence, such heuristic speedups may be critical for numerical quantum algorithms.

Preliminary

In this section, we introduce some notations used in this paper. For two real vectors x,y∈Rmx,y \in\mathbb{R}^{m}, we define x⋅yx \cdot y as ∑i=1mxiyi\sum_{i=1}^{m} x_i y_i. We sometimes extend this notation to the case when yy is a vector of matrices and write, for example, λ⋅F\lambda\cdot F to mean the summation ∑jλjFj\sum_j \lambda_j F_j. For matrices A,BA,B, define ⟨A,B⟩=tr⁡(A†B)\langle A,B\rangle= \operatorname{tr}(A^\dagger B). We use A⪰BA \succeq B or B⪯AB \preceq A to mean A−BA-B is a positive semidefinite matrix. A density matrix ρ\rho is a positive semidefinite matrix of unit trace. The set of density matrices on Hilbert space X\mathcal{X} is denoted D(X)\mathrm{D}(\mathcal{X}).

Suppose X\mathcal{X} is a finite-dimensional Hilbert space and ff is a real convex function. We use Δ\Delta to denote the domain dom⁡f\operatorname{dom} f of ff, the interval on which ff takes well-defined finite values. Then ff extends to all Hermitian operators in Herm⁡Δ(X)\operatorname{Herm}_{\Delta}(\mathcal{X}) as f(X)=∑kf(λk)Πkf(X)=\sum_k f(\lambda_k)\Pi_k where X=∑kλkΠkX=\sum_k \lambda_k\Pi_k is the spectral decomposition of XX. Denote the interior and boundary of Δ\Delta as Δint\Delta_{\mathrm{int}} and Δbd=Δ∖Δint\Delta_{\mathrm{bd}}=\Delta\setminus\Delta_{\mathrm{int}} respectively. It is easy to see that the domain of matrix function ff is Herm⁡Δ(X)\operatorname{Herm}_{\Delta}(\mathcal{X}), and the interior of the domain is Herm⁡Δint(X)\operatorname{Herm}_{\Delta_{\mathrm{int}}}(\mathcal{X}). For a subset SS of Hermitian matrices, we use cl⁡(S)\operatorname{cl}(S) to denote the closure of SS.

Given convex function ff as above, the Bregman divergence for matrices is Df(X,Y)=tr⁡(f(X)−f(Y)−f′(Y)(X−Y))D_f(X,Y)=\operatorname{tr}(f(X)-f(Y)-f'(Y)(X-Y)), where X∈Herm⁡Δ(X)X\in\operatorname{Herm}_{\Delta}(\mathcal{X}) and Y∈Herm⁡Δint(X)Y\in\operatorname{Herm}_{\Delta_{\mathrm{int}}}(\mathcal{X}). An important case we focus on in this paper is f(x)=xln⁡x−xf(x)=x\ln x-x. In this case, the matrix Bregman divergence becomes the Kullback-Leibler divergence D(X,Y)=tr⁡(Xln⁡X−Xln⁡Y−X+Y)D(X,Y)=\operatorname{tr}(X\ln X-X\ln Y-X+Y) defined for non-normalized matrices X,YX,Y. When X,YX,Y are positive semidefinite matrices of trace 1, it recovers the Kullback-Leibler relative entropy D(X,Y)=tr⁡(Xln⁡X−Xln⁡Y)D(X,Y)=\operatorname{tr}(X\ln X-X\ln Y). We will need the matrix Bregman-Legendre projection L(Y,Λ)\mathcal{L}(Y,\Lambda) and Bregman-Legendre conjugate ℓ(Y,Λ)\ell(Y,\Lambda) for convex function f(x)=xln⁡x−xf(x)=x\ln x-x defined as L(Y,Λ)=exp⁡(ln⁡Y+Λ)\mathcal{L}(Y,\Lambda)=\exp(\ln Y+\Lambda), ℓ(Y,Λ)=tr⁡exp⁡(ln⁡Y+Λ)−tr⁡Y\ell(Y,\Lambda)=\operatorname{tr}\exp(\ln Y+\Lambda)-\operatorname{tr}Y. For Y∝1Y\propto\mathbb{1}, ℓ(Y,Λ)=tr⁡exp⁡(Λ)\ell(Y,\Lambda)=\operatorname{tr}\exp(\Lambda) and we omit YY and write it as ℓ(Λ)\ell(\Lambda).

In this paper, we consider spin Hamiltonians only and write them as H=∑j=1mHjH=\sum_{j=1}^{m}H_j where HjH_j’s are local terms acting on at most constant number of neighboring qubits according to certain interaction geometry. For example, a σz⊗σz\sigma_z\otimes\sigma_z term acting on the first two qubits is σz⊗σz⊗(1⊗n−2)\sigma_z\otimes\sigma_z\otimes(\mathbb{1}^{\otimes n-2}) for Pauli operator σz=(100−1)\sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. We often use ξH=1Ze−βH\xi_H=\frac{1}{Z}e^{-\beta H} to represent the Gibbs state of the Hamiltonian HH for inverse temperature β\beta specified in the context or β=1\beta=1 otherwise. Here Z=tr⁡e−βHZ=\operatorname{tr}e^{-\beta H} is the partition function normalizing the state to have trace 1 and plays an important role in statistical physics and also in our work.

Quantum Iterative Scaling

This section presents a version of the Quantum Iterative Scaling (QIS) algorithm and discusses its applications in the Hamiltonian inference problem.

We first introduce some notations used in the following discussions. For a given list of Hermitian matrices F=(Fj)j=1mF=(F_j)_{j=1}^{m}, define the linear family of quantum states L(ρ0)\mathcal{L}(\rho_0) as {ρ⪰0∣⟨Fj,ρ⟩=⟨Fj,ρ0⟩}\{\rho\succeq0\mid\langle F_j,\rho\rangle=\langle F_j,\rho_0\rangle\}. Define the exponential family E(σ0)\mathcal{E}(\sigma_0) as {1Zexp⁡(ln⁡σ0+λ⋅F)}\left\{\frac{1}{Z}\exp(\ln\sigma_0+\lambda\cdot F)\right\}. We introduce the new notation FjF_j playing the role of HjH_j in the previous discussion as we will need certain normalization conditions. In the end, we will choose Fj=Hj+12mF_j=\frac{H_j+1}{2m} so FjF_j is a scaled linear shift of HjH_j such that Fj⪰0F_j\succeq0 and ∑jFj⪯1\sum_jF_j\preceq\mathbb{1}.

We note that, in Ji (2022), the algorithms are designed for non-normalized matrices and, therefore, there is no need to explicitly normalize Y(t)Y^{(t)} in the update. Here, we perform explicit normalization to work with normalized quantum states and their von Neumann entropy. For Y(t)=exp⁡(ln⁡σ0+λ⋅F)Y^{(t)}=\exp(\ln\sigma_0+\lambda\cdot F), the normalization is equivalent to a linear update in the summation of the exponential function Y(t)=exp⁡(ln⁡σ0+λ⋅F−ln⁡Z)Y^{(t)}=\exp(\ln\sigma_0+\lambda\cdot F-\ln Z) where Z=tr⁡Y(t)Z=\operatorname{tr}Y^{(t)}. Hence, we have the following two methods to handle the normalization. The first is to let the algorithm to find the normalization implicitly, and this would require that 1\mathbb{1} is in the span of the FjF_j’s. This will be the case if the assumption on FjF_j is that ∑jFj=1\sum_jF_j=\mathbb{1}. The second is to perform the normalization explicitly as we did in the algorithm. This approach is advantageous as it works for all FjF_j’s satisfying ∑jFj⪯1\sum_jF_j\preceq\mathbb{1} even if 1\mathbb{1} is not in the span of FjF_j’s.

An important special case of the algorithm is when σ0=1/d\sigma_0=\mathbb{1}/d and D(ρ,σ0)=ln⁡(d)−S(ρ)D(\rho,\sigma_0)=\ln(d)-S(\rho) where dd is the dimension. Then, the minimization over the linear family is now exactly the maximum entropy problem as in Figure 1 with Hj=FjH_j=F_j, αj=⟨Fj,ρ0⟩\alpha_j=\langle F_j,\rho_0\rangle, and λj=−βμj\lambda_j=-\beta\mu_j. When all the operators FjF_j’s are diagonal in the computational basis, the QIS algorithm recovers the GIS algorithm (see e.g. Theorem 5.2 of Csiszár & Shields [15]).

Require: ρ0,σ0∈D(X)\rho_0,\sigma_0\in\mathcal{D}(\mathcal{X}) such that D(ρ0,σ0)<∞D(\rho_0,\sigma_0)<\infty.

Input: F=(F1,F2,…,Fk)∈Pos⁡(X)kF=(F_1,F_2,\ldots,F_k)\in\operatorname{Pos}(\mathcal{X})^k and ∑j=1kFj⪯1\sum_{j=1}^{k}F_j\preceq1.

Output: λ(1),λ(2),…\lambda^{(1)},\lambda^{(2)},\ldots such that

lim⁡t→∞D(ρ0,L(σ0,λ(t)⋅F))=inf⁡λ∈RkD(ρ0,L(σ0,λ⋅F)).\lim_{t\to\infty}D\left(\rho_0,\mathcal{L}(\sigma_0,\lambda^{(t)}\cdot F)\right)=\inf_{\lambda\in\mathbb{R}^k}D\left(\rho_0,\mathcal{L}(\sigma_0,\lambda\cdot F)\right).
  1. Initialize λ(1)=(0,0,…,0)\lambda^{(1)}=(0,0,\ldots,0).

  2. for t=1,2,…t=1,2,\ldots, do

  3. Compute Y(t)=L(σ0,λ(t)⋅F)Y^{(t)}=\mathcal{L}(\sigma_0,\lambda^{(t)}\cdot F).

  4. for j=1,2,…,kj=1,2,\ldots,k do

  5. δj(t)=ln⁡⟨Fj,ρ0⟩−ln⁡⟨Fj,Y(t)tr⁡Y(t)⟩\delta_j^{(t)}=\ln\langle F_j,\rho_0\rangle-\ln\left\langle F_j,\frac{Y^{(t)}}{\operatorname{tr}Y^{(t)}}\right\rangle.

  6. end for

  7. Update parameters λ(t+1)=λ(t)+δ(t)\lambda^{(t+1)}=\lambda^{(t)}+\delta^{(t)}.

  8. end for

Algorithm 1: Quantum iterative scaling algorithm.

To give some intuition behind the QIS algorithm, we define ξ(t)=Y(t)/tr⁡Y(t)\xi^{(t)}=Y^{(t)}/\operatorname{tr}Y^{(t)} and note that the update in the QIS algorithm is simply δj=ln⁡⟨Fj,ρ0⟩−ln⁡⟨Fj,ξ(t)⟩\delta_j=\ln\langle F_j,\rho_0\rangle-\ln\langle F_j,\xi^{(t)}\rangle, which is zero when the linear family constraint ⟨Fj,ρ⟩=⟨Fj,ρ0⟩\langle F_j,\rho\rangle=\langle F_j,\rho_0\rangle is satisfied by ρ=ξ(t)\rho=\xi^{(t)}. In this case, the algorithm stops updating λ\lambda in the jj-th direction as expected. Otherwise, if the difference between the current mean value ⟨Fj,ξ(t)⟩\langle F_j,\xi^{(t)}\rangle and the target value ⟨Fj,ρ0⟩\langle F_j,\rho_0\rangle is big, so will be the update δj\delta_j. The algorithm is, in this sense, adaptive when compared to algorithms like multiplicative weight update algorithms (Arora et al., [5]).

The maximum entropy problem has dual program in Figure 1 which is an unconstrained problem. Hence, it is also attractive to work with the dual using the gradient descent method (or corresponding quasi-Newton methods discussed later in the paper). The gradient of the dual objective function is ∂∂λj(ln⁡ℓ(λ⋅F)−λ⋅α)=⟨Fj,ξλ⋅F⟩−αj\frac{\partial}{\partial\lambda_j}\left(\ln\ell(\lambda\cdot F)-\lambda\cdot\alpha\right)=\langle F_j,\xi_{\lambda\cdot F}\rangle-\alpha_j, where ξλ⋅F\xi_{\lambda\cdot F} is the Gibbs state for Hamiltonian λ⋅F\lambda\cdot F. Therefore, in gradient descent, the update in each step is η(αj−⟨Fj,ξλ⋅F⟩)\eta\left(\alpha_j-\langle F_j,\xi_{\lambda\cdot F}\rangle\right), where η\eta is the learning rate. This leads to the gradient descent algorithm in Algorithm 2.

The QIS algorithm generally outperforms the bare-bones GD algorithm and avoids the problem of choosing the step size completely. Consider the update of the QIS algorithm ln⁡αj−ln⁡⟨Fj,ξλ⋅F⟩\ln\alpha_j-\ln\langle F_j,\xi_{\lambda\cdot F}\rangle, and the update of the GD algorithm η(αj−⟨Fj,ξλ⋅F⟩)\eta\left(\alpha_j-\langle F_j,\xi_{\lambda\cdot F}\rangle\right). For αj\alpha_j and ⟨Fj,ξλ⋅F⟩\langle F_j,\xi_{\lambda\cdot F}\rangle in (0,1](0,1], the QIS update is more aggressive than the dual gradient descent for learning rate η≤1\eta\leq1 while still guarantees the convergence. This effect is more evident when the two numbers αj\alpha_j and ⟨Fj,ξλ⋅F⟩\langle F_j,\xi_{\lambda\cdot F}\rangle are small, which holds in most applications. We will later see that choosing an appropriate learning rate will improve the performance of the GD algorithm considered in Section 4, but it is still less efficient compared to QIS.

Convergence Rate

In this section, we analyze the geometric convergence rate for the QIS algorithm in Algorithm 1 for the case when σ0=1/d\sigma_0=1/d. As a comparison, we will also analyze the convergence rate of the GD

Require: ρ0,σ0∈D(X)\rho_0, \sigma_0 \in D(\mathcal{X}) such that D(ρ0,σ0)<∞D(\rho_0,\sigma_0)<\infty.

Input: F=(F1,F2,…,Fk)∈Pos⁡(X)kF=(F_1,F_2,\ldots,F_k)\in\operatorname{Pos}(\mathcal{X})^k and ∑j=1kFj⪯1\sum_{j=1}^{k}F_j\preceq1.

Output: λ(1),λ(2),…\lambda^{(1)},\lambda^{(2)},\ldots such that

lim⁡t→∞D(ρ0,L(σ0,λ(t)⋅F))=inf⁡λ∈RkD(ρ0,L(σ0,λ⋅F)).\lim_{t\to\infty}D\left(\rho_0,\mathcal{L}(\sigma_0,\lambda^{(t)}\cdot F)\right)=\inf_{\lambda\in\mathbb{R}^k}D\left(\rho_0,\mathcal{L}(\sigma_0,\lambda\cdot F)\right).
  1. Initialize λ(1)=(0,0,…,0)\lambda^{(1)}=(0,0,\ldots,0).

  2. for t=1,2,…t=1,2,\ldots, do

  3. Compute Y(t)=L(σ0,λ(t)⋅F)Y^{(t)}=\mathcal{L}(\sigma_0,\lambda^{(t)}\cdot F).

  4. for j=1,2,…,kj=1,2,\ldots,k do

  5. δj(t)=η⟨Fj,ρ0⟩−η⟨Fj,Y(t)/tr⁡Y(t)⟩\delta_j^{(t)}=\eta\langle F_j,\rho_0\rangle-\eta\langle F_j,Y^{(t)}/\operatorname{tr}Y^{(t)}\rangle.

  6. end for

  7. Update parameters λ(t+1)=λ(t)+δ(t)\lambda^{(t+1)}=\lambda^{(t)}+\delta^{(t)}.

  8. end for

Algorithm 2: Gradient descent algorithm for Kullback-Leibler divergence minimization.

algorithm (Algorithm 2).

We will come across several matrices which are defined here for later references. For λ\lambda and FF, we define the corresponding Gibbs state as ξ=exp⁡(λ⋅F)tr⁡exp⁡(λ⋅F)\xi=\frac{\exp(\lambda\cdot F)}{\operatorname{tr}\exp(\lambda\cdot F)}, and for an operator OO, we use ⟨O⟩=tr⁡(Oξ)\langle O\rangle=\operatorname{tr}(O\xi) to mean the average value of OO with respect to ξ\xi. Define diagonal matrix P=∑j⟨Fj⟩∣j⟩⟨j∣P=\sum_j\langle F_j\rangle\lvert j\rangle\langle j\rvert. Finally, define LL to be the Hessian of the log-partition function ln⁡tr⁡exp⁡(λ⋅F)\ln\operatorname{tr}\exp(\lambda\cdot F) with λ\lambda as the variables.

We have the following two results regarding the QIS and GD algorithms respectively, proved in Section B.

Theorem 4.1. The Jacobian of the iterative update map λ(t)↦λ(t+1)\lambda^{(t)}\mapsto\lambda^{(t+1)} of Algorithm 1 for σ0=1/d\sigma_0=1/d is given by 1−P−1L1-P^{-1}L for PP and LL defined above with λ=λ(t)\lambda=\lambda^{(t)}.

Theorem 4.2. The Jacobian of the iterative update map λ(t)↦λ(t+1)\lambda^{(t)}\mapsto\lambda^{(t+1)} of Algorithm 2 is given by 1−ηL1-\eta L where LL is the Hessian of the log-partition function defined above.

By the Ostrowski theorem stated in Theorem B.1, the geometric convergence rate of the QIS algorithm is, therefore, governed by the spectral radius of the Jacobian 1−P−1L1-P^{-1}L. Hence, we need to prove bounds on the spectral radius. In Anshu et al. [4], a non-trivial lower bound on LL is proved (see Theorem D.1), giving an upper bound on the spectral radius. The other side of the spectral estimate uses the following result, proved in Appendix § 10.

Theorem 4.3. Let PP and LL be matrices defined above. We have L⪯PL\preceq P.

We are now able to state the convergence rate of the QIS and GD algorithms.

Theorem 4.4. For Hamiltonian H=∑j=1mμjHjH=\sum_{j=1}^{m}\mu_jH_j where conditions of Theorem D.1 are satisfied and HjH_j are traceless terms with norm ∥Hj∥≤1\lVert H_j\rVert\leq1, the QIS algorithm with Fj=1+Hj2mF_j=\frac{1+H_j}{2m} and the GD algorithm with the same choices of FjF_j and η=m\eta=m solve the Hamiltonian inference problem with geometric convergence rate 1−Ω(1m2)1-\Omega\left(\frac{1}{m^2}\right).

Proof of Theorem 4.4. We consider the QIS algorithm first, which is the more difficult case. By Theorem 4.1, JQIS=1−P−1LJ_{\mathrm{QIS}} = 1 - P^{-1}L. Hence, we can bound the spectral radius as

r(JQIS)=r(1−P−1L)=r(1−L1/2P−1L1/2)=∥1−L1/2P−1L1/2∥\begin{aligned} r(J_{\mathrm{QIS}}) &= r(1-P^{-1}L) \\ &= r(1-L^{1/2}P^{-1}L^{1/2}) \\ &= \left\|1-L^{1/2}P^{-1}L^{1/2}\right\| \end{aligned}

Here, the second line follows from the fact that ABAB and BABA have the same set of eigenvalues and the third step follows as L1/2P−1L1/2L^{1/2}P^{-1}L^{1/2} is Hermitian. By definition, PP is a diagonal matrix whose (j,j)(j,j)-th entry is ⟨Fj,ξ⟩=⟨1+Hj2m,ξ⟩≤1/m\left\langle F_j,\xi\right\rangle= \left\langle\frac{1+H_j}{2m},\xi\right\rangle\leq1/m. Theorem 4.3 then implies that 1−P−1L1-P^{-1}L has eigenvalues in [0,1][0,1] and

r(JQIS)=1−λmin⁡(L1/2P−1L1/2)≤1−mλmin⁡(L).(1)r(J_{\mathrm{QIS}})=1-\lambda_{\min}(L^{1/2}P^{-1}L^{1/2})\leq1-m\lambda_{\min}(L). \tag*{(1)}

The Hamiltonian is H(μ)=∑jμj(2mFj−1)H(\mu)=\sum_j\mu_j(2mF_j-1). Define λj=2mμj\lambda_j=2m\mu_j, and H~(λ)=∑jλjFj\widetilde{H}(\lambda)=\sum_j\lambda_jF_j. We have H~(λ)=H(μ)+μΣ1\widetilde{H}(\lambda)=H(\mu)+\mu_{\Sigma}1 where μΣ=∑jμj=∑jλj/(2m)\mu_{\Sigma}=\sum_j\mu_j=\sum_j\lambda_j/(2m). We compute

Lj,k=∂2ln⁡tr⁡exp⁡(λ⋅F)∂λj∂λk=∂2ln⁡tr⁡exp⁡(λ⋅F)∂μj∂μk∂μj∂λj∂μk∂λk=14m2∂2(ln⁡tr⁡exp⁡(H(μ))+∑jμj)∂μj∂μk=14m2∇μ2ln⁡tr⁡exp⁡(H(μ)).\begin{aligned} L_{j,k} &=\frac{\partial^2\ln\operatorname{tr}\exp(\lambda\cdot F)}{\partial\lambda_j\partial\lambda_k} \\ &=\frac{\partial^2\ln\operatorname{tr}\exp(\lambda\cdot F)}{\partial\mu_j\partial\mu_k}\frac{\partial\mu_j}{\partial\lambda_j}\frac{\partial\mu_k}{\partial\lambda_k} \\ &=\frac{1}{4m^2}\frac{\partial^2\left(\ln\operatorname{tr}\exp(H(\mu))+\sum_j\mu_j\right)}{\partial\mu_j\partial\mu_k} \\ &=\frac{1}{4m^2}\nabla_{\mu}^{2}\ln\operatorname{tr}\exp(H(\mu)). \end{aligned}

By Theorem D.1, we have λmin⁡(L)≥Ω(1m3)\lambda_{\min}(L)\geq\Omega\left(\frac{1}{m^3}\right). Together with Equation (1), this completes the proof using Theorem B.1.

By a similar calculation, we can prove the claim for the GD algorithm.

The above analysis shows that the QIS algorithm has a better geometric convergence rate even if we set η=m\eta=m in the GD algorithm. Numerical simulations in § 6 also confirm this observation. In some sense, the QIS algorithm is an adaptive gradient descent that can automatically choose the appropriate learning rate for different dimensions as ⟨Fj⟩\left\langle F_j\right\rangle may differ for each jj.

Acceleration by Quasi-Newton Methods

The convergence analysis in § 4 is of theoretical interest but polynomial convergence proved there is usually not enough for practical applications. In this section, we explore the application of quasi-Newton methods, which can significantly improve the efficiency of the adaptive learning algorithms considered in § 3. In particular, we study two families of methods, the Anderson mixing (Anderson, [3]) method and the BFGS method (Nocedal & Wright, [38]).

Anderson mixing (abbreviated as AM in the following) is a widely used method employed in numerical and computational mathematics to accelerate the convergence of fixed-point iterations. It particularly excels in scenarios where traditional iterative methods may converge slowly or struggle to find solutions efficiently. The essence of the Anderson mixing algorithm lies in its ability to dynamically combine and update a finite set of historical iterates. It adaptively selects a linear combination of these historical iterates, leveraging the past information to guide the algorithm toward convergence more effectively. This technique finds applications in various scientific and engineering domains, including quantum chemistry [21], machine learning [44], and solving complex systems of equations [13], where it often delivers substantial acceleration in computational tasks.

Applying the Anderson mixing method to the Hamiltonian inference problem, specifically to the Quantum Iterative Scaling (QIS) algorithm, is straightforward due to the inherent nature of QIS as a fixed-point iterative update algorithm. The Anderson-accelerated QIS (AM-QIS) algorithm combines both the QIS iterative step and simple classical processing, so it has exactly the same requirement as the standard QIS algorithm for the oracle access to the Gibbs state or the average values. Since the fixed-point map g(x)g(x) in QIS iteration is a contraction, we can set the mixing parameter βt≡1\beta_t \equiv1 defined in Section E and the convergence of AM-QIS follows from the results in Toth & Kelley [45]. We also use the Barzilai-Borwein (BB) method [9] for choosing the mixing parameter which turns out to be effective and provides further accelerations.

The BFGS method and the limited memory variant L-BFGS are the most influential among many quasi-Newton methods. They are the recommended choice for learning graphical models in the classical machine learning literature Malouf [36]. The BFGS method works with an unconstrained optimization problem min⁡x∈Rnf(x)\min_{x \in\mathbb{R}^{n}} f(x). The update in the BFGS algorithm has the form xk+1=xk−ηkHk∇f(xk)x_{k+1}=x_k-\eta_k H_k\nabla f(x_k), where ηk\eta_k is the step size which can usually be found by line search, and HkH_k is a matrix that is updated iteratively during the execution of the algorithm. We consider both a fixed choice or the BB method for the initial approximation of the inverse Hessian H0H_0 for a fair comparison with AM. The application of BFGS methods to our problem is also straightforward as the dual problem is an unconstrained optimization problem.

AM and BFGS have different application scenarios. AM is an acceleration method for solving fixed-point problems and the approximation GtG_t of the inverse Jacobian matrix is generally not symmetric. In contrast, BFGS is an optimization method and constructs a symmetric approximation HtH_t for the inverse Hessian matrix. Since an optimization problem can usually be recast as a fixed-point problem, AM also applies to solving optimization problems. However, BFGS may be more efficient in some cases due to the maintained symmetry structure compared with AM.

Experiments

We conducted numerical simulations to assess the comparative efficiency of four approaches: the standard QIS, the standard GD algorithm, AM-QIS, and the L-BFGS-GD algorithm applied to the dual problem. The Linux workstation we used for the numerical experiment has a 16-core CPU (Intel(R) Xeon(R) Platinum 8369HB CPU @ 3.30GHz) and 64GB of memory.

In the experimental setup, we adopted a method involving generating random Gibbs states for random local Hamiltonians, represented as H=∑jλjHjH=\sum_j\lambda_j H_j. Here, the local terms, denoted as HjH_j, consist of tensor products of local Pauli operators, and the λj\lambda_j parameters are the values to be learned. These Hamiltonians were then utilized to create Gibbs states ξH=1Ze−βH\xi_H=\frac{1}{Z}e^{-\beta H}. We feed the Gibbs states and their corresponding local average values αj=⟨Hj⊗1,ξH⟩\alpha_j=\langle H_j\otimes\mathbb{1},\xi_H\rangle to the algorithms. In this way, we know the ground truth about the values of λj\lambda_j's and the objective value of the optimization programs in Figure 1, and we choose to evaluate the algorithms’ performance by the error compared with the true objective value.

The results are summarized in Figure 2 and Figure 3. In Figure 2, we compare the performance of QIS and GD algorithms. We can see that QIS algorithm is more efficient than GD algorithm regardless of whether we ensure the completeness ∑Fj=1\sum F_j = 1 or not. In Figure 3, we compare the performance of AM-QIS and L-BFGS-GD, both with and without the Barzilai-Borwein method. We can see that AM-QIS and L-BFGS-GD are comparable in general. The standard QIS algorithm typically required approximately 1500 iterations to achieve an error level of 10−6∼10−810^{-6} \sim10^{-8} (measured using the objective function of the maximum entropy problem). In contrast, the AM-QIS and L-BFGS algorithms achieved the same accuracy with only about 8 (or 20) iterations with (or without) BB, showcasing a remarkable speedup of two orders of magnitude. The efficiency of the AM-QIS algorithm is stable and does not change much when the Hamiltonian is normalized and completed, while the efficiency of L-BFGS-GD algorithm (in § 6) is observed to be sensitive in this regard.

Figure 3. Comparisons of the AM-QIS and L-BFGS-GD algorithms. The § 6 on the left uses the Barzilai-Borwein method to choose the step size and § 6 on the right uses fixed step size. The dotted (red) and dashed (green) lines represent the performance of the algorithms when the input Hamiltonian terms are complete satisfying ∑jFj=1\sum_{j} F_j = 1.

Discussions

In this study, we considered adaptive learning algorithms for the Hamiltonian inference problem. We examined the convergence of the quantum iterative scaling algorithm (QIS) and the gradient descent (GD) algorithm for the dual problem. Furthermore, two quasi-Newton methods AM-QIS and L-BFGS-GD are proposed.

The QIS algorithm iteratively updates the Hamiltonian parameters adaptively by comparing ⟨Hj⊗1,ξH(λ)⟩\langle H_j \otimes1, \xi_H(\lambda) \rangle and the target value αj\alpha_j. Therefore it requires the ability to prepare ξH(λ)\xi_H(\lambda) for the trial parameter λ\lambda or estimate the local information of the state. This is generally a computationally demanding assumption, but if the physical system has exponentially decaying correlation and satisfy certain Markov property, the preparation of the Gibbs state or its local observations could be efficient [11, 30]. Furthermore, the issue may be solved or mitigated by combining quantum belief propagation algorithms proposed in Hastings [25]; Leifer & Poulin [32]; Poulin & Hastings [41] which present possible ways of computing the value ⟨Hj⊗1,ξH(λ)⟩\langle H_j \otimes1, \xi_{H(\lambda)}\rangle approximately without generating the full Gibbs state, thereby removing the use of the adaptive Gibbs oracle. We leave the exploration of this possibility as future work.

Prime and Dual Divergence Minimization Problems

The primal and dual formulation of the maximum entropy program in Figure 1 is a special case of the following duality result between two minimization problems of the Kullback-Leibler divergence given in Figure 4. The duality theorem of Ji (2022), or Jaynes’ principle, states that the following two problems have the same minimizer which is the unique intersection point of the linear family L(ρ0)\mathcal{L}(\rho_0) and exponential family cl⁡(E(σ0))\operatorname{cl}(\mathcal{E}(\sigma_0)) defined in § 3. When σ0\sigma_0 is the maximally mixed state 1/d1/d, the linear family minimization is the maximum entropy problem and the exponential family minimization is a dual program in Figure 1.

Figure 4. Linear family minimization

minimize: D(X,σ0)D(X,\sigma_0)

subject to: X∈L(ρ0)X \in\mathcal{L}(\rho_0).

Exponential family minimization

minimize: D(ρ0,Y)D(\rho_0,Y)

subject to: Y∈E(σ0)Y \in\mathcal{E}(\sigma_0).

Two optimization problems of the Kullback-Leibler divergence that are dual to each other.

Proofs for Convergence Rate

This section proves the explicit formulas for the Jacobian matrix of the iterations in QIS and GD algorithms.

Proof of Theorem 4.1. We first prove two identities about the partial derivative of the function ℓ\ell and its natural logarithm.

∂∂λj′ℓ(λ⋅F)=⟨Fj′,exp⁡(λ⋅F)⟩(2)\frac{\partial}{\partial\lambda_{j'}}\ell(\lambda\cdot F)=\left\langle F_{j'},\exp(\lambda\cdot F)\right\rangle \tag*{(2)}
∂∂λj′ln⁡ℓ(λ⋅F)=⟨Fj′,ξ⟩(3)\frac{\partial}{\partial\lambda_{j'}}\ln\ell(\lambda\cdot F)=\left\langle F_{j'},\xi\right\rangle \tag*{(3)}

for ξ\xi defined as

ξ=exp⁡(λ⋅F)tr⁡exp⁡(λ⋅F)(4)\xi=\frac{\exp(\lambda\cdot F)}{\operatorname{tr}\exp(\lambda\cdot F)} \tag*{(4)}

In fact, we have

∂∂λj′ℓ(λ⋅F)=∂∂λj′tr⁡exp⁡(λ⋅F)=tr⁡∑k=0∞∂∂λj′(λ⋅F)kk!=tr⁡∑k=1∞∑j=0k−1(λ⋅F)k−j−1Fj′(λ⋅F)jk!=⟨Fj′,∑k=1∞(λ⋅F)k−1(k−1)!⟩=⟨Fj′,exp⁡(λ⋅F)⟩,\begin{aligned} \frac{\partial}{\partial\lambda_{j'}}\ell(\lambda\cdot F) &= \frac{\partial}{\partial\lambda_{j'}}\operatorname{tr}\exp(\lambda\cdot F) \\ &= \operatorname{tr}\sum_{k=0}^{\infty}\frac{\partial}{\partial\lambda_{j'}}\frac{(\lambda\cdot F)^k}{k!} \\ &= \operatorname{tr}\sum_{k=1}^{\infty}\sum_{j=0}^{k-1}\frac{(\lambda\cdot F)^{k-j-1}F_{j'}(\lambda\cdot F)^j}{k!} \\ &= \left\langle F_{j'},\sum_{k=1}^{\infty}\frac{(\lambda\cdot F)^{k-1}}{(k-1)!}\right\rangle\\ &= \langle F_{j'},\exp(\lambda\cdot F)\rangle, \end{aligned}

where the second line follows from the Taylor expansion of the matrix expansion and the fourth line is by the cyclic property of trace. This proves Equation (2). Similarly, we have

∂∂λj′ln⁡ℓ(λ⋅F)=1ℓ(λ⋅F)∂∂λj′ℓ(λ⋅F)=1tr⁡exp⁡(λ⋅F)⟨Fj′,exp⁡(λ⋅F)⟩=⟨Fj′,ξ⟩,\begin{aligned} \frac{\partial}{\partial\lambda_{j'}}\ln\ell(\lambda\cdot F) &= \frac{1}{\ell(\lambda\cdot F)}\frac{\partial}{\partial\lambda_{j'}}\ell(\lambda\cdot F) \\ &= \frac{1}{\operatorname{tr}\exp(\lambda\cdot F)}\langle F_{j'},\exp(\lambda\cdot F)\rangle\\ &= \langle F_{j'},\xi\rangle, \end{aligned}

where the second line follows from Equation (2). This completes the proof of Equation (3).

Now, for j=1,2,…,kj=1,2,\ldots,k, the update in the algorithm is

δj=ln⁡⟨Fj,ρ0⟩−ln⁡⟨Fj,Y(t)/tr⁡Y(t)⟩.\delta_j=\ln\langle F_j,\rho_0\rangle-\ln\langle F_j,Y^{(t)}/\operatorname{tr}Y^{(t)}\rangle.

Hence, for j,j′∈{1,2,…,k}j,j'\in\{1,2,\ldots,k\} and ξ\xi defined in Equation (4),

∂δj∂λj′=−1⟨Fj,ξ⟩∂⟨Fj,ξ⟩∂λj′=−1⟨Fj,ξ⟩∂∂λj′∂∂λjln⁡ℓ(λ⋅F)=−Pj,j′−1Lj,j′.\begin{aligned} \frac{\partial\delta_j}{\partial\lambda_{j'}} &=-\frac{1}{\langle F_j,\xi\rangle}\frac{\partial\langle F_j,\xi\rangle}{\partial\lambda_{j'}} \\ &=-\frac{1}{\langle F_j,\xi\rangle}\frac{\partial}{\partial\lambda_{j'}}\frac{\partial}{\partial\lambda_j}\ln\ell(\lambda\cdot F) \\ &=-P^{-1}_{j,j'}L_{j,j'}. \end{aligned}

For the second line, we used Equation (3). Equivalently, the Jacobian matrix

(∂δj∂λj′)j,j′=−P−1L,\left(\frac{\partial\delta_j}{\partial\lambda_{j'}}\right)_{j,j'}=-P^{-1}L,

for matrices PP and LL defined in the statement of the theorem. The Jacobian JQISJ_{\mathrm{QIS}} of the QIS iteration can be written as

JQIS=1+(∂δj∂λj′)j,j′=1−P−1L.J_{\mathrm{QIS}}=1+\left(\frac{\partial\delta_j}{\partial\lambda_{j'}}\right)_{j,j'}=1-P^{-1}L.

This completes the proof the theorem.

Proof of Theorem 4.2. In an iteration of the algorithm, we have

δj=η⟨Fj,ρ0⟩−η⟨Fj,Y(t)tr⁡Y(t)⟩.\delta_j=\eta\langle F_j,\rho_0\rangle-\eta\left\langle F_j,\frac{Y^{(t)}}{\operatorname{tr}Y^{(t)}}\right\rangle.

The Jacobian JGDJ_{\mathrm{GD}} of each iteration has (j,j′)(j,j') entry

1−η∂∂λj′⟨Fj,ξ⟩=1−η∂∂λj′∂∂λjln⁡tr⁡exp⁡(λ⋅F)=1−ηL.\begin{aligned} 1-\eta\frac{\partial}{\partial\lambda_{j'}}\langle F_j,\xi\rangle\\ &=1-\eta\frac{\partial}{\partial\lambda_{j'}}\frac{\partial}{\partial\lambda_j}\ln\operatorname{tr}\exp(\lambda\cdot F) \\ &=1-\eta L. \end{aligned}

This completes the proof.

We recall a theorem of Ostrowski which we will use to prove the convergence rate by bounding the spectral radius of a Jacobian matrix.

Theorem B.1 (Ostrowski’s theorem ([39 Chapter 22]). Assume function ff is differentiable at the neighborhood of a fixed point ζ\zeta. For an iterative algorithm ζt+1=f(ζt)\zeta_{t+1}=f(\zeta_t). A sufficient condition for ζ\zeta to be a point of attraction is the spectral radius r(Jf)<1r(J_f)<1. Moreover, if ζ\zeta is an attraction point, the geometric convergence rate of the iterative algorithm is given by

lim sup⁡t→∞∥ζt+1−ζ∥∥ζt−ζ∥=r(Jf).\limsup_{t\to\infty}\frac{\|\zeta_{t+1}-\zeta\|}{\|\zeta_t-\zeta\|}=r(J_f).

Bounds on the Hessian Matrix

Theorem C.1 (Duhamel’s formula). Let A(s)A(s) be a matrix-valued function. Then

ddsexp⁡(A(s))=∫01dt exp⁡(tA(s))A′(s)exp⁡((1−t)A(s)).\frac{\mathrm{d}}{\mathrm{d}s}\exp(A(s))=\int_0^1\mathrm{d}t\ \exp(tA(s))A'(s)\exp((1-t)A(s)).

Define matrices

Δ=∑j∂ℓ(λ⋅F)∂λj∣j⟩⟨j∣,\Delta=\sum_j\frac{\partial\ell(\lambda\cdot F)}{\partial\lambda_j}|j\rangle\langle j|,
Λ=∑j,j′∂2ℓ(λ⋅F)∂λj∂λj′∣j⟩⟨j′∣.\Lambda=\sum_{j,j'}\frac{\partial^2\ell(\lambda\cdot F)}{\partial\lambda_j\partial\lambda_{j'}}|j\rangle\langle j'|.

In other words, Δ\Delta is a diagonal matrix and Λ\Lambda is the Hessian of the partition function Z=ℓ(λ⋅F)=tr⁡exp⁡(λ⋅F)Z=\ell(\lambda\cdot F)=\operatorname{tr}\exp(\lambda\cdot F). In the following, let ρ=exp⁡(λ⋅F)/tr⁡exp⁡(λ⋅F)\rho=\exp(\lambda\cdot F)/\operatorname{tr}\exp(\lambda\cdot F). We use ⟨,⟩\langle,\rangle for the Frobenius inner product on matrices, i.e., ⟨A,B⟩=tr⁡(A†B)\langle A,B\rangle=\operatorname{tr}(A^\dagger B), and ⟨,⟩ρ\langle,\rangle_\rho for the BKM inner product

⟨A,B⟩ρ=tr⁡(A†∫01ρtBρ1−t dt).\langle A,B\rangle_\rho=\operatorname{tr}\left(A^\dagger\int_0^1\rho^tB\rho^{1-t}\,\mathrm{d}t\right).

Proposition C.2. The jj-th diagonal entry of Δ\Delta is

Δjj=⟨Fj,exp⁡(λ⋅F)⟩=Z⟨Fj,I⟩ρ,\Delta_{jj}=\langle F_j,\exp(\lambda\cdot F)\rangle=Z\langle F_j,I\rangle_\rho,

and the jkjk-th entry of Λ\Lambda is

Λjk=Z⟨Fj,∫01ρtFkρ1−t dt⟩=Z⟨Fj,Fk⟩ρ.\Lambda_{jk}=Z\left\langle F_j,\int_0^1\rho^tF_k\rho^{1-t}\,\mathrm{d}t\right\rangle=Z\langle F_j,F_k\rangle_\rho.

We recall the Petz monotonicity theorem as follows.

Theorem C.3 (Theorem 2.2 and Equation (4.2) in [40]). Let HA\mathcal{H}_A and HB\mathcal{H}_B be finite-dimensional Hilbert spaces, and let E:L(HA)⟶L(HB)\mathcal{E}:\mathcal{L}(\mathcal{H}_A)\longrightarrow\mathcal{L}(\mathcal{H}_B) be completely positive and trace-preserving. Let E†:L(HB)⟶L(HA)\mathcal{E}^{\dagger}:\mathcal{L}(\mathcal{H}_B)\longrightarrow\mathcal{L}(\mathcal{H}_A) be its Hilbert--Schmidt adjoint. For every density operator ρ∈D(HA)\rho\in\mathcal{D}(\mathcal{H}_A) and every K∈L(HB)K\in\mathcal{L}(\mathcal{H}_B), it holds that

⟨K,K⟩E(ρ)≥⟨E†(K),E†(K)⟩ρ.\langle K,K\rangle_{\mathcal{E}(\rho)}\geq\langle\mathcal{E}^{\dagger}(K),\mathcal{E}^{\dagger}(K)\rangle_{\rho}.

In finite dimensions, all the operators under consideration are bounded.

Theorem C.4. For Λ\Lambda and Δ\Delta defined above, we have Λ⪯Δ\Lambda\preceq\Delta.

Proof. Fix an arbitrary v=(v1,…,vn)∈Cnv=(v_1,\ldots,v_n)\in\mathbb{C}^n, and define

F0=1−∑j=1nFj⪰0.F_0=1-\sum_{j=1}^{n}F_j\succeq0.

Complete the measurement by defining the quantum-to-classical channel

Φ~(X)=∑j=0ntr⁡(XFj)∣j⟩⟨j∣.\widetilde{\Phi}(X)=\sum_{j=0}^{n}\operatorname{tr}(XF_j)|j\rangle\langle j|.

The map Φ~\widetilde{\Phi} is CPTP because each Fj⪰0F_j\succeq0 and ∑j=0nFj=1\sum_{j=0}^{n}F_j=1. Define

W~=0∣0⟩⟨0∣+∑j=1nvj∣j⟩⟨j∣,B=∑j=1nvjFj,\widetilde{W}=0|0\rangle\langle0|+\sum_{j=1}^{n}v_j|j\rangle\langle j|,\qquad B=\sum_{j=1}^{n}v_jF_j,

and let p~=Φ~(ρ)\widetilde{p}=\widetilde{\Phi}(\rho). The Hilbert--Schmidt adjoint satisfies

Φ~†(W~)=∑j=1nvjFj=B.\widetilde{\Phi}^{\dagger}(\widetilde{W})=\sum_{j=1}^{n}v_jF_j=B.

Applying Theorem C.3 to the CPTP map Φ~\widetilde{\Phi} gives

⟨W~,W~⟩p~≥⟨B,B⟩ρ.\langle\widetilde{W},\widetilde{W}\rangle_{\widetilde{p}}\geq\langle B,B\rangle_{\rho}.

Since the coefficient of outcome 0 in W~\widetilde{W} is zero, that outcome contributes nothing, and Theorem C.2 gives

⟨W~,W~⟩p~=∑j=1ntr⁡(ρFj)∣vj∣2=1Zv†Δv.\begin{aligned} \langle\widetilde{W},\widetilde{W}\rangle_{\widetilde{p}} &=\sum_{j=1}^{n}\operatorname{tr}(\rho F_j)|v_j|^2\\ &=\frac{1}{Z}v^{\dagger}\Delta v. \end{aligned}

For the other side, the same proposition gives

⟨B,B⟩ρ=⟨∑jvjFj,∑kvkFk⟩ρ=∑j,kvj‾vk⟨Fj,Fk⟩ρ=1Zv†Λv.\begin{aligned} \langle B,B\rangle_{\rho} &=\left\langle\sum_jv_jF_j,\sum_kv_kF_k\right\rangle_{\rho}\\ &=\sum_{j,k}\overline{v_j}v_k\langle F_j,F_k\rangle_{\rho}\\ &=\frac{1}{Z}v^{\dagger}\Lambda v. \end{aligned}

Therefore, v†Δv≥v†Λvv^{\dagger}\Delta v\geq v^{\dagger}\Lambda v for every v∈Cnv\in\mathbb{C}^n, and hence Λ⪯Δ\Lambda\preceq\Delta. □\square

We now derive the upper Hessian bound in Theorem 4.3. Let

Z=tr⁡exp⁡(λ⋅F),pj=⟨Fj⟩ρ=tr⁡(ρFj).Z = \operatorname{tr}\exp(\lambda\cdot F), \qquad p_j = \langle F_j\rangle_{\rho} = \operatorname{tr}(\rho F_j).

By Theorem C.2, Δjj=Zpj\Delta_{jj} = Zp_j. Thus, for the diagonal matrix PP defined in § 4,

P=ΔZ.P = \frac{\Delta}{Z}.

For the Hessian L=∇λ2ln⁡ZL = \nabla_{\lambda}^{2}\ln Z, we have

Ljk=1Z∂2Z∂λj∂λk−1Z2∂Z∂λj∂Z∂λk=ΛjkZ−pjpk.L_{jk} = \frac{1}{Z}\frac{\partial^{2}Z}{\partial\lambda_j\partial\lambda_k} - \frac{1}{Z^{2}}\frac{\partial Z}{\partial\lambda_j}\frac{\partial Z}{\partial\lambda_k} = \frac{\Lambda_{jk}}{Z} - p_jp_k.

Thus, in matrix form,

L=ΛZ−ppT,L = \frac{\Lambda}{Z} - pp^{\mathsf{T}},

where p=(p1,…,pn)Tp = (p_1,\ldots,p_n)^{\mathsf{T}} is real. Using Λ⪯Δ\Lambda\preceq\Delta, we obtain

L⪯ΔZ−ppT=P−ppT⪯P.L \preceq\frac{\Delta}{Z} - pp^{\mathsf{T}} = P - pp^{\mathsf{T}} \preceq P.

This proves Theorem 4.3.

Lower Bound on the Hessian Matrix

For the other side of the spectral estimate, we recall the following lower bound on the Hessian from Anshu et al. [4].

Theorem D.1 (Theorem 6 of Anshu et al. [4]). Let H(μ)=∑j=1mμjHjH(\mu) = \sum_{j=1}^{m}\mu_jH_j be an ℓ\ell-local Hamiltonian over a finite dimensional lattice. For a given inverse temperature β\beta, there are constants c,c′>3c,c' > 3 depending on the geometric property of the lattice such that

∇μ2ln⁡tr⁡(e−βH(μ))⪰e−O(βc)βc′m1.\nabla_{\mu}^{2}\ln\operatorname{tr}\left(e^{-\beta H(\mu)}\right) \succeq\frac{e^{-O(\beta^{c})}\beta^{c'}}{m}\mathbf{1}.

Discussions on Quasi-Newton Methods

In this section, we give some details of the Anderson mixing method and L-BFGS method.

The Anderson mixing method interpolates history information in order to speed up a fixed-point iteration. More concretely, suppose g:Rd→Rdg:\mathbb{R}^{d}\to\mathbb{R}^{d} is a contraction and we are interested in finding the fix-point x=g(x)x = g(x). The standard fix-point iterative algorithm is to compute xt+1=g(xt)x_{t+1} = g(x_t) for t=0,1,2,…t = 0,1,2,\ldots, until a stopping criteria is met. In Anderson mixing, a relatively small history size m≥0m \ge0 is chosen and we define mt=min⁡{m,t}m_t = \min\{m,t\}. In our numerical implementation, we use m=10m = 10. Define the residual rt=g(xt)−xtr_t = g(x_t) - x_t and two matrices Xt,Rt∈Rd×mX_t,R_t \in\mathbb{R}^{d\times m} storing the historical information

Xt=(Δxt−mt,Δxt−mt+1,…,Δxt−1),X_t = \left(\Delta x_{t-m_t},\Delta x_{t-m_t+1},\ldots,\Delta x_{t-1}\right),
Rt=(Δrt−mt,Δrt−mt+1,…,Δrt−1).R_t = \left(\Delta r_{t-m_t},\Delta r_{t-m_t+1},\ldots,\Delta r_{t-1}\right).

where Δ\Delta is the forward difference operator and Δxk=xk+1−xk\Delta x_k = x_{k+1} - x_k. Then, the Anderson accelerated iteration can be written succinctly as xt+1=xt+Gtrtx_{t+1} = x_t + G_t r_t where

Gt=βtI−(Xt+βtRt)(RtTRt)−1RtT.G_t = \beta_t I - (X_t + \beta_t R_t)(R_t^{T}R_t)^{-1}R_t^{T}.

Here, βt\beta_t is the mixing parameter.

It is pointed out in Fang & Saad [20] that GtG_t approximates the inverse of the Jacobian of gg and Anderson mixing method can be thought of as a quasi-Newton method satisfying multisecant equations. We note that there is a matrix inverse in the above formula for GtG_t which can be implemented using Moore-Penrose pseudo-inverse. For stability and efficiency concerns, we found that the AM algorithms have the best performance in our numerical simulations when using a relative condition number of 1e−71\mathrm{e}{-7} in the pseudo-inverse, a cutoff threshold that sets small singular values of the matrix to zero. This is easily implemented by setting the rcond parameter of the pinv function in numpy.linalg package for Python implementations.

The BFGS method is one of the most popular quasi-Newton methods that can be applied to unconstrained optimization problems min⁡x∈Rnf(x)\min_{x \in\mathbb{R}^n} f(x). It is also known as the variable metric algorithm as first proposed by Davidon [17]; Yuan [51]. The algorithm maintains the approximate Hessian Hk+1H_{k+1} of the optimization problem. The update rule of the algorithm is

xt+1=xt−ηtHt∇f(xt),x_{t+1} = x_t - \eta_t H_t \nabla f(x_t),

and the update rule of HtH_t is

Ht+1=(1−stytTytTst)Ht(1−ytstTytTst)+ststTytTst.H_{t+1} = \left(1-\frac{s_t y_t^T}{y_t^T s_t}\right)H_t\left(1-\frac{y_t s_t^T}{y_t^T s_t}\right)+\frac{s_t s_t^T}{y_t^T s_t}.

where st=xt+1−xts_t = x_{t+1} - x_t, yt=∇f(xt+1)−∇f(xt)y_t = \nabla f(x_{t+1}) - \nabla f(x_t) and H0H_0 is a predefined initial approximation of the inverse Hessian matrix. We refer readers to Nocedal & Wright [38] for a discussion on how the BFGS update is derived. To optimize the memory usage, the limited memory version of BFGS called L-BFGS (Liu & Nocedal [35]) is used. Since using line search for choosing ηt\eta_t can incur additional function evaluations in each iteration, we use ηt≡1\eta_t \equiv1 and only tune H0H_0 in the numerical simulation.

Both the AM and the BFGS methods employed our numerical simulation can be further strengthened by using a heuristics invented by Barzilai and Borwein (Barzilai & Borwein [9]) to choose the βt\beta_t in AM and H0H_0 in BFGS. In AM, we set

βt=−Δrt−1TΔxt−1Δrt−1TΔrt−1,\beta_t = -\frac{\Delta r_{t-1}^{T}\Delta x_{t-1}}{\Delta r_{t-1}^{T}\Delta r_{t-1}},

which solves min⁡β∥Δxt−1+βΔrt−1∥2\min_{\beta}\|\Delta x_{t-1}+\beta\Delta r_{t-1}\|_2. In BFGS, we set

H0=yt−1Tst−1yt−1Tyt−11H_0 = \frac{y_{t-1}^{T}s_{t-1}}{y_{t-1}^{T}y_{t-1}}\mathbb{1}

to be the initialization of the approximate inverse Hessian in the tt-th iteration (Nocedal & Wright, [38], Pages 143 and 178).

Experimental Details

In this section, we provide details of the numerical experiments.

Hamiltonian Generation

Three types of Hamiltonians are used in our numerical experiments. These include the Ising family of Hamiltonians, the transversal 2-local Hamiltonians in 1D (Transversal1D), and the 2-local Hamiltonians in 1D (Local1D). The figures in the main text demonstrate the results of the experiments on the Local1D Hamiltonian in 6-qubit system.

Ising Hamiltonian The Ising Hamiltonian is a sum of 2-local terms, which can be written as

H=∑i=1naiσz(i)+∑i=1n−1biσz(i)σz(i+1),H = \sum_{i=1}^{n} a_i \sigma_z^{(i)} + \sum_{i=1}^{n-1} b_i \sigma_z^{(i)} \sigma_z^{(i+1)},

where σz(i)\sigma_z^{(i)} is a Pauli ZZ operator acting on the ii-th qubit. The coefficients aia_i and bib_i are randomly generated from the standard normal distribution.

Transversal1D Hamiltonian The transversal 1D Hamiltonian is a sum of 2-local terms, and it can be written as

H=∑p∈{x,y,z}ap∑i=1nσp(i)+∑p,q∈{x,y,z}bp,q∑i=1nσp(i)σq(i+1).H = \sum_{p \in\{x,y,z\}} a_p \sum_{i=1}^{n} \sigma_p^{(i)} + \sum_{p,q \in\{x,y,z\}} b_{p,q} \sum_{i=1}^{n} \sigma_p^{(i)} \sigma_q^{(i+1)}.

The coefficients aja_j and bp,qb_{p,q} are randomly generated from the standard normal distribution. Notice that, in this scenario, there are 12 terms in the Hamiltonian, and each term in the Hamiltonian is a sum of Pauli operators acting on different qubits. Thus, the operator norm of each term is bounded by the number of qubits instead of 1. As a result, in the implementation of our algorithm, we need to normalize the Hamiltonian by dividing the number of qubits.

Local1D Hamiltonian The local 1D Hamiltonian is a sum of 2-local terms, including the Ising Hamiltonian as a special case, and it can be written as

H=∑i=1n∑p∈{x,y,z}ap,iσp(i)+∑i=1n∑p,q∈{x,y,z}bp,q,iσp(i)σq(i+1),H = \sum_{i=1}^{n} \sum_{p \in\{x,y,z\}} a_{p,i} \sigma_p^{(i)} + \sum_{i=1}^{n} \sum_{p,q \in\{x,y,z\}} b_{p,q,i} \sigma_p^{(i)} \sigma_q^{(i+1)},

where σ(i)\sigma^{(i)} is a Pauli operator acting on the ii-th qubit for i≤ni \le n, and σ(n+1)\sigma^{(n+1)} is defined as σ(n+1)=σ(1)\sigma^{(n+1)} = \sigma^{(1)}. The coefficients ap,ia_{p,i} and bp,q,ib_{p,q,i} are randomly generated from the standard normal distribution.

Initialization, Learning Rate, and Stopping Criteria

The initial guess for the parameters in the QIS algorithm and the gradient descent algorithm is set to 0. The learning rate in the gradient descent algorithm is set to the number of terms in the Hamiltonian. In the experiments, we first generate the Hamiltonian and then normalize it by dividing it by the number of qubits. Then, the inverse temperature β\beta is set to 1. Therefore, the optimal solutions and optimal objective values can be directly computed and compared with the results of the algorithms. With these settings, the stopping criteria can be set to the error of the objective value. The stopping criteria for the QIS, gradient descent algorithm, and quasi-Newton accelerations is set to have error at most 10−1210^{-12}. The maximum number of iterations for the quasi-Newton accelerations is set to 40.

Results on Different Hamiltonians

In this section, we provide the results of the numerical experiments on different Hamiltonians. We have conducted experiments on the Ising, Transversal1D, and Local1D Hamiltonians, with different numbers of qubits. The results are shown in the following tables and figures. We first present the results in Table 1 and then provide the figures for each family of Hamiltonians.

QISGDAM-QISL-BFGS-GD
6-qubit-Ising31947976
6-qubit-Transversal1743256257
6-qubit-Local1913237758
7-qubit-Ising37055166
7-qubit-Transversal2006294057
7-qubit-Local2236272157
8-qubit-Ising42162365
8-qubit-Transversal2267331147
8-qubit-Local2525302057

Table 1. Number of steps to achieve 10−710^{-7} precision for different Hamiltonians.

The results of the Ising Hamiltonian are shown in Figure 5 for a 7-qubit system with 13 Hamiltonian terms. In such cases, the QIS algorithm converges to the optimal solution with error 10−910^{-9} in roughly 400 iterations with less loss than the GD algorithm, while the quasi-Newton methods converge to the optimal solution with similar error in less than 20 iterations.

(a) QIS and GD results.

Quasi-Newton methods without BB method

(b) Quasi-Newton methods without BB method.

Quasi-Newton methods with BB method

(c) Quasi-Newton methods with BB method.

Figure 5. Results of the Ising Hamiltonian for 7 qubits.

The results of the Transversal1D Hamiltonian are shown in Figure 6 for a 7-qubit system with 12 terms. In such cases, the QIS algorithm converges to the optimal solution with error 10−710^{-7} in roughly 1000 iterations with less loss than the GD algorithm, while the quasi-Newton methods converge to the optimal solution with similar error in less than 20 iterations.

(a) QIS and GD results.

(b) Quasi-Newton methods without BB method.

(c) Quasi-Newton methods with BB method.

Figure 6. Results of the Transversal1D Hamiltonian for 7 qubits.

The results of the Local1D Hamiltonian are shown in Figure 7 for a 7-qubit system with 96 terms. In such cases, the QIS algorithm converges to the optimal solution with error 10−910^{-9} in roughly 2000 iterations with less loss than the GD algorithm, while the quasi-Newton methods converge to the optimal solution with similar error in less than 40 iterations.

(a) QIS and GD results.

Quasi-Newton methods without BB method

(b) Quasi-Newton methods without BB method.

Quasi-Newton methods with BB method

(c) Quasi-Newton methods with BB method.

Figure 7. Results of the Local1D Hamiltonian for 7 qubits.

Reproducibility Details

The numerical experiments were conducted using Python 3.11.5 in Python scripts. Running the script requires the following packages: numpy and scipy for linear algebra operations, matplotlib for data visualization, sys for outputting results in txt format, time for measuring the runtime of the algorithm, and Qiskit ([42]) for generating Hamiltonians. For reproducibility, we set the random seed to 100 for QIS and GD, and random seed array from 1 to the number of experiments for quasi-Newton accelerations. The average runtime of the script is less than 6 minutes for systems of five to eight qubits (of dimensions 32×3232 \times32 to 256×256256 \times256).

References

  1. [1]Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cognitive Science, 9(1):147–169, 1985.
  2. [3]Anderson, D. G. Iterative Procedures for Nonlinear Integral Equations. Journal of the ACM, 12(4):547–560, 1965.DOI
  3. [4]Anshu, A., Arunachalam, S., Kuwahara, T., and Soleimanifar, M. Sample-efficient learning of interacting quantum systems. Nature Physics, pp. 1–5, 2021.DOI
  4. [5]Arora, S., Hazan, E., and Kale, S. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(6):121–164, 2012.
  5. [9]Barzilai, J. and Borwein, J. M. Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8(1):141–148, 1988.DOI
  6. [10]Berger, A. L., Della Pietra, S. A., and Della Pietra, V. J. A Maximum Entropy Approach to Natural Language Processing. Computational Linguistics, 22(1):39–71, 1996.DOI
  7. [11]Brandão, F. G. S. L. and Kastoryano, M. J. Finite Correlation Length Implies Efficient Preparation of Quantum Thermal States. Communications in Mathematical Physics, 365(1):1–16, 2019.arxiv.org/abs/1609.07877
  8. [12]Bresler, G. Efficiently Learning Ising Models on Arbitrary Graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, STOC ’15, pp. 771–782, New York, NY, USA, 2015. Association for Computing Machinery.arxiv.org/abs/1411.6156
  9. [13]Brezinski, C., Cipolla, S., Redivo-Zaglia, M., and Saad, Y. Shanks and Anderson-type acceleration techniques for systems of nonlinear equations. IMA Journal of Numerical Analysis, 42(4):3058–3093, 2022.arxiv.org/abs/2007.05716
  10. [14]Cranmer, K., Golkar, S., and Pappadopulo, D. Inferring the quantum density matrix with machine learning, 2019.arxiv.org/abs/1904.05903
  11. [15]Csiszár, I. and Shields, P. C. Information Theory and Statistics: A Tutorial. Foundations and Trends® in Communications and Information Theory, 1(4):417–528, 2004.
  12. [16]Darroch, J. N. and Ratcliff, D. Generalized Iterative Scaling for Log-Linear Models. Annals of Mathematical Statistics, 43(5):1470–1480, 1972.DOI
  13. [17]Davidon, W. C. Variable Metric Method for Minimization. SIAM Journal on Optimization, 1(1):1–17, 1991.
  14. [18]Della Pietra, S., Della Pietra, V., and Lafferty, J. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997.
  15. [20]Fang, H.-r. and Saad, Y. Two classes of multесцant methods for nonlinear acceleration. Numerical Linear Algebra with Applications, 16(3):197–221, 2009.DOI
  16. [21]Garza, A. J. and Scuseria, G. E. Comparison of self-consistent field convergence acceleration techniques. The Journal of Chemical Physics, 137(5):054110, 2012.DOI
  17. [22]Globerson, A. and Jaakkola, T. Approximate inference using conditional entropy decompositions. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, pp. 131–138. PMLR, 2007.
  18. [24]Hamilton, L., Koehler, F., and Moitra, A. Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.arxiv.org/abs/1705.11107
  19. [25]Hastings, M. B. Quantum belief propagation: An algorithm for thermal quantum systems. Physical Review B, 76(20):201102, 2007.DOI
  20. [26]Jaynes, E. T. Information Theory and Statistical Mechanics. Physical Review, 106(4):620–630, 1957.DOI
  21. [28]Kindermann, R. and Snell, J. L. Markov random fields and their applications. Number 1 in Contemporary mathematics. American mathematical society, Providence, 1980.DOI
  22. [29]Klivans, A. and Meka, R. Learning Graphical Models Using Multiplicative Weights. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 343–354, 2017.arxiv.org/abs/1706.06274
  23. [30]Kuwahara, T., Kato, K., and Brandão, F. G. S. L. Clustering of Conditional Mutual Information for Quantum Gibbs States above a Threshold Temperature. Physical Review Letters, 124(22):220601, 2020.DOI
  24. [31]Lafferty, J. D., McCallum, A., and Pereira, F. C. N. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML ’01, pp. 282–289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
  25. [32]Leifer, M. S. and Poulin, D. Quantum Graphical Models and Belief Propagation. Annals of Physics, 323(8):1899–1946, 2008.
  26. [34]Liang, G., Yu, B., and Taft, N. Maximum entropy models: convergence rates and applications in dynamic system monitoring. In International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., pp. 168–174, 2004.
  27. [35]Liu, D. C. and Nocedal, J. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1):503–528, 1989.
  28. [36]Malouf, R. A comparison of algorithms for maximum entropy parameter estimation. In proceeding of the 6th conference on Natural language learning - COLING-02, volume 20, pp. 1–7, 2002.DOI
  29. [37]McCallum, A., Freitag, D., and Pereira, F. C. N. Maximum Entropy Markov Models for Information Extraction and Segmentation. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML ’00, pp. 591–598, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
  30. [38]Nocedal, J. and Wright, S. J. Numerical optimization. Springer series in operations research. Springer, New York, 2nd ed edition, 2006.
  31. [39]Ostrowski, A. M. Solution of Equations and Systems of Equations. Academic Press, 2nd edition, 1966.DOI
  32. [40]Petz, D. Geometry of canonical correlation on the state space of a quantum system. Journal of Mathematical Physics, 35(2):780–795, 1994.DOI
  33. [41]Poulin, D. and Hastings, M. B. Markov Entropy Decomposition: A Variational Dual for Quantum Belief Propagation. Physical Review Letters, 106(8):080403, 2011.pubmed.ncbi.nlm.nih.gov/21405554
  34. [42]Qiskit, T. Qiskit: An open-source framework for quantum computing, 2023.
  35. [43]Ravikumar, P., Wainwright, M. J., and Lafferty, J. D. High-dimensional Ising model selection using l1-regularized logistic regression. The Annals of Statistics, 38(3):1287–1319, 2010.
  36. [44]Sun, K., Wang, Y., Liu, Y., Zhao, Y., Pan, B., Jui, S., Jiang, B., and Kong, L. Damped Anderson Mixing for Deep Reinforcement Learning: Acceleration, Convergence, and Stabilization. In Advances in Neural Information Processing Systems, volume 34, pp. 3732–3743. Curran Associates, Inc., 2021.arxiv.org/abs/2110.08896
  37. [45]Toth, A. and Kelley, C. T. Convergence Analysis for Anderson Acceleration. SIAM Journal on Numerical Analysis, 53(2):805–819, 2015.DOI
  38. [46]Vuffray, M., Misra, S., Lokhov, A., and Chertkov, M. Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models. In Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.arxiv.org/abs/1605.07252
  39. [47]Wainwright, M. J. and Jordan, M. I. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends® in Machine Learning, 1(1–2):1–305, 2007.
  40. [51]Yuan, Y.-X. Variable Metric Algorithms. In Engquist, B. (ed.), Encyclopedia of Applied and Computational Mathematics, pp. 1515–1519. Springer, Berlin, Heidelberg, 2015.DOI

Paper details

vlnc:W_vkn26h5j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents