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 for be local observables of, say, an -qubit quantum system. What the state of the system would likely be given only the local marginal information ? 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 where is a quantum Hamiltonian parameterized by a vector of real numbers . That is, given as input the average values encoding local information, the parameter vector of the Hamiltonian is uniquely determined by and the computation of from is an example of the backward mapping problems.
Maximum entropy problem
Dual problem
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 where is a diagonal matrix whose entries are the mean values of operators related to over the Gibbs state and is the Hessian of the log-partition function. This connection to the Hessian matrix 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 where is the Hessian of the log-partition function and is the step size of GD. In a sense, the Jacobian of the QIS update rule, , 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.

Figure 1. The maximum entropy problem and its dual problem. Here, is the von Neumann entropy of .
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 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 , we define as . We sometimes extend this notation to the case when is a vector of matrices and write, for example, to mean the summation . For matrices , define . We use or to mean is a positive semidefinite matrix. A density matrix is a positive semidefinite matrix of unit trace. The set of density matrices on Hilbert space is denoted .
Suppose is a finite-dimensional Hilbert space and is a real convex function. We use to denote the domain of , the interval on which takes well-defined finite values. Then extends to all Hermitian operators in as where is the spectral decomposition of . Denote the interior and boundary of as and respectively. It is easy to see that the domain of matrix function is , and the interior of the domain is . For a subset of Hermitian matrices, we use to denote the closure of .
Given convex function as above, the Bregman divergence for matrices is , where and . An important case we focus on in this paper is . In this case, the matrix Bregman divergence becomes the Kullback-Leibler divergence defined for non-normalized matrices . When are positive semidefinite matrices of trace 1, it recovers the Kullback-Leibler relative entropy . We will need the matrix Bregman-Legendre projection and Bregman-Legendre conjugate for convex function defined as , . For , and we omit and write it as .
In this paper, we consider spin Hamiltonians only and write them as where ’s are local terms acting on at most constant number of neighboring qubits according to certain interaction geometry. For example, a term acting on the first two qubits is for Pauli operator . We often use to represent the Gibbs state of the Hamiltonian for inverse temperature specified in the context or otherwise. Here 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 , define the linear family of quantum states as . Define the exponential family as . We introduce the new notation playing the role of in the previous discussion as we will need certain normalization conditions. In the end, we will choose so is a scaled linear shift of such that and .
We note that, in Ji (2022), the algorithms are designed for non-normalized matrices and, therefore, there is no need to explicitly normalize in the update. Here, we perform explicit normalization to work with normalized quantum states and their von Neumann entropy. For , the normalization is equivalent to a linear update in the summation of the exponential function where . 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 is in the span of the ’s. This will be the case if the assumption on is that . The second is to perform the normalization explicitly as we did in the algorithm. This approach is advantageous as it works for all ’s satisfying even if is not in the span of ’s.
An important special case of the algorithm is when and where is the dimension. Then, the minimization over the linear family is now exactly the maximum entropy problem as in Figure 1 with , , and . When all the operators ’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: such that .
Input: and .
Output: such that
Initialize .
for , do
Compute .
for do
.
end for
Update parameters .
end for
Algorithm 1: Quantum iterative scaling algorithm.
To give some intuition behind the QIS algorithm, we define and note that the update in the QIS algorithm is simply , which is zero when the linear family constraint is satisfied by . In this case, the algorithm stops updating in the -th direction as expected. Otherwise, if the difference between the current mean value and the target value is big, so will be the update . 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 , where is the Gibbs state for Hamiltonian . Therefore, in gradient descent, the update in each step is , where 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 , and the update of the GD algorithm . For and in , the QIS update is more aggressive than the dual gradient descent for learning rate while still guarantees the convergence. This effect is more evident when the two numbers and 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 . As a comparison, we will also analyze the convergence rate of the GD
Require: such that .
Input: and .
Output: such that
Initialize .
for , do
Compute .
for do
.
end for
Update parameters .
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 and , we define the corresponding Gibbs state as , and for an operator , we use to mean the average value of with respect to . Define diagonal matrix . Finally, define to be the Hessian of the log-partition function with 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 of Algorithm 1 for is given by for and defined above with .
Theorem 4.2. The Jacobian of the iterative update map of Algorithm 2 is given by where 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 . Hence, we need to prove bounds on the spectral radius. In Anshu et al. [4], a non-trivial lower bound on 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 and be matrices defined above. We have .
We are now able to state the convergence rate of the QIS and GD algorithms.
Theorem 4.4. For Hamiltonian where conditions of Theorem D.1 are satisfied and are traceless terms with norm , the QIS algorithm with and the GD algorithm with the same choices of and solve the Hamiltonian inference problem with geometric convergence rate .
Proof of Theorem 4.4. We consider the QIS algorithm first, which is the more difficult case. By Theorem 4.1, . Hence, we can bound the spectral radius as
Here, the second line follows from the fact that and have the same set of eigenvalues and the third step follows as is Hermitian. By definition, is a diagonal matrix whose -th entry is . Theorem 4.3 then implies that has eigenvalues in and
The Hamiltonian is . Define , and . We have where . We compute
By Theorem D.1, we have . 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 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 may differ for each .
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 in QIS iteration is a contraction, we can set the mixing parameter 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 . The update in the BFGS algorithm has the form , where is the step size which can usually be found by line search, and 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 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 of the inverse Jacobian matrix is generally not symmetric. In contrast, BFGS is an optimization method and constructs a symmetric approximation 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 . Here, the local terms, denoted as , consist of tensor products of local Pauli operators, and the parameters are the values to be learned. These Hamiltonians were then utilized to create Gibbs states . We feed the Gibbs states and their corresponding local average values to the algorithms. In this way, we know the ground truth about the values of '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 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 (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 .
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 and the target value . Therefore it requires the ability to prepare for the trial parameter 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 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 and exponential family defined in § 3. When is the maximally mixed state , 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:
subject to: .
Exponential family minimization
minimize:
subject to: .
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 and its natural logarithm.
for defined as
In fact, we have
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
where the second line follows from Equation (2). This completes the proof of Equation (3).
Now, for , the update in the algorithm is
Hence, for and defined in Equation (4),
For the second line, we used Equation (3). Equivalently, the Jacobian matrix
for matrices and defined in the statement of the theorem. The Jacobian of the QIS iteration can be written as
This completes the proof the theorem.
Proof of Theorem 4.2. In an iteration of the algorithm, we have
The Jacobian of each iteration has entry
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 is differentiable at the neighborhood of a fixed point . For an iterative algorithm . A sufficient condition for to be a point of attraction is the spectral radius . Moreover, if is an attraction point, the geometric convergence rate of the iterative algorithm is given by
Bounds on the Hessian Matrix
Theorem C.1 (Duhamel’s formula). Let be a matrix-valued function. Then
Define matrices
In other words, is a diagonal matrix and is the Hessian of the partition function . In the following, let . We use for the Frobenius inner product on matrices, i.e., , and for the BKM inner product
Proposition C.2. The -th diagonal entry of is
and the -th entry of is
We recall the Petz monotonicity theorem as follows.
Theorem C.3 (Theorem 2.2 and Equation (4.2) in [40]). Let and be finite-dimensional Hilbert spaces, and let be completely positive and trace-preserving. Let be its Hilbert--Schmidt adjoint. For every density operator and every , it holds that
In finite dimensions, all the operators under consideration are bounded.
Theorem C.4. For and defined above, we have .
Proof. Fix an arbitrary , and define
Complete the measurement by defining the quantum-to-classical channel
The map is CPTP because each and . Define
and let . The Hilbert--Schmidt adjoint satisfies
Applying Theorem C.3 to the CPTP map gives
Since the coefficient of outcome 0 in is zero, that outcome contributes nothing, and Theorem C.2 gives
For the other side, the same proposition gives
Therefore, for every , and hence .
We now derive the upper Hessian bound in Theorem 4.3. Let
By Theorem C.2, . Thus, for the diagonal matrix defined in § 4,
For the Hessian , we have
Thus, in matrix form,
where is real. Using , we obtain
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 be an -local Hamiltonian over a finite dimensional lattice. For a given inverse temperature , there are constants depending on the geometric property of the lattice such that
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 is a contraction and we are interested in finding the fix-point . The standard fix-point iterative algorithm is to compute for , until a stopping criteria is met. In Anderson mixing, a relatively small history size is chosen and we define . In our numerical implementation, we use . Define the residual and two matrices storing the historical information
where is the forward difference operator and . Then, the Anderson accelerated iteration can be written succinctly as where
Here, is the mixing parameter.
It is pointed out in Fang & Saad [20] that approximates the inverse of the Jacobian of 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 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 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 . It is also known as the variable metric algorithm as first proposed by Davidon [17]; Yuan [51]. The algorithm maintains the approximate Hessian of the optimization problem. The update rule of the algorithm is
and the update rule of is
where , and 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 can incur additional function evaluations in each iteration, we use and only tune 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 in AM and in BFGS. In AM, we set
which solves . In BFGS, we set
to be the initialization of the approximate inverse Hessian in the -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
where is a Pauli operator acting on the -th qubit. The coefficients and 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
The coefficients and 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
where is a Pauli operator acting on the -th qubit for , and is defined as . The coefficients and 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 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 . 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.
| QIS | GD | AM-QIS | L-BFGS-GD | |
| 6-qubit-Ising | 319 | 479 | 7 | 6 |
| 6-qubit-Transversal | 1743 | 2562 | 5 | 7 |
| 6-qubit-Local | 1913 | 2377 | 5 | 8 |
| 7-qubit-Ising | 370 | 551 | 6 | 6 |
| 7-qubit-Transversal | 2006 | 2940 | 5 | 7 |
| 7-qubit-Local | 2236 | 2721 | 5 | 7 |
| 8-qubit-Ising | 421 | 623 | 6 | 5 |
| 8-qubit-Transversal | 2267 | 3311 | 4 | 7 |
| 8-qubit-Local | 2525 | 3020 | 5 | 7 |
Table 1. Number of steps to achieve 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 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.

(b) Quasi-Newton methods without 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 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 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.

(b) Quasi-Newton methods without 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 to ).
References
- [1]Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cognitive Science, 9(1):147–169, 1985.
- [3]Anderson, D. G. Iterative Procedures for Nonlinear Integral Equations. Journal of the ACM, 12(4):547–560, 1965.DOI
- [4]Anshu, A., Arunachalam, S., Kuwahara, T., and Soleimanifar, M. Sample-efficient learning of interacting quantum systems. Nature Physics, pp. 1–5, 2021.DOI
- [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.
- [9]Barzilai, J. and Borwein, J. M. Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8(1):141–148, 1988.DOI
- [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
- [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
- [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
- [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
- [14]Cranmer, K., Golkar, S., and Pappadopulo, D. Inferring the quantum density matrix with machine learning, 2019.arxiv.org/abs/1904.05903
- [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.
- [16]Darroch, J. N. and Ratcliff, D. Generalized Iterative Scaling for Log-Linear Models. Annals of Mathematical Statistics, 43(5):1470–1480, 1972.DOI
- [17]Davidon, W. C. Variable Metric Method for Minimization. SIAM Journal on Optimization, 1(1):1–17, 1991.
- [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.
- [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
- [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
- [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.
- [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
- [25]Hastings, M. B. Quantum belief propagation: An algorithm for thermal quantum systems. Physical Review B, 76(20):201102, 2007.DOI
- [26]Jaynes, E. T. Information Theory and Statistical Mechanics. Physical Review, 106(4):620–630, 1957.DOI
- [28]Kindermann, R. and Snell, J. L. Markov random fields and their applications. Number 1 in Contemporary mathematics. American mathematical society, Providence, 1980.DOI
- [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
- [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
- [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.
- [32]Leifer, M. S. and Poulin, D. Quantum Graphical Models and Belief Propagation. Annals of Physics, 323(8):1899–1946, 2008.
- [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.
- [35]Liu, D. C. and Nocedal, J. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1):503–528, 1989.
- [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
- [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.
- [38]Nocedal, J. and Wright, S. J. Numerical optimization. Springer series in operations research. Springer, New York, 2nd ed edition, 2006.
- [39]Ostrowski, A. M. Solution of Equations and Systems of Equations. Academic Press, 2nd edition, 1966.DOI
- [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
- [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
- [42]Qiskit, T. Qiskit: An open-source framework for quantum computing, 2023.
- [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.
- [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
- [45]Toth, A. and Kelley, C. T. Convergence Analysis for Anderson Acceleration. SIAM Journal on Numerical Analysis, 53(2):805–819, 2015.DOI
- [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
- [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.
- [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







