1. Bibliographic Information

1.1. Title

Quantum thermodynamics and semi-definite optimization

1.2. Authors

Nana Liu, Michele Minervini, Dhrumil Patel, and Mark M. Wilde.

• Nana Liu: Affiliated with the Institute of Natural Sciences and School of Mathematical Sciences, Shanghai Jiao Tong University, China. Her research likely involves theoretical physics, quantum information, and mathematical aspects of quantum systems.
• Michele Minervini: Affiliated with the School of Electrical and Computer Engineering, Cornell University, United States. His background is probably in electrical engineering, computer engineering, and quantum computing.
• Dhrumil Patel: Affiliated with the School of Computer Science, Cornell University, United States. His expertise would be in computer science, algorithms, and potentially quantum algorithms.
• Mark M. Wilde: Affiliated with the School of Electrical and Computer Engineering, Cornell University, United States. A prominent researcher in quantum information theory, quantum computing, and quantum thermodynamics.

1.3. Journal/Conference

This paper is a preprint, published on arXiv.org.

• arXiv.org: A free, open-access server for preprints in physics, mathematics, computer science, quantitative biology, quantitative finance, statistics, electrical engineering and systems science, and economics. Papers on arXiv are not peer-reviewed by arXiv itself, though many are later published in peer-reviewed journals. Its reputation is as a crucial platform for rapid dissemination of research and early feedback within the scientific community.

1.4. Publication Year

2025 (Dated: May 13, 2025 for the v2 version. The abstract states "Published at (UTC): 2025-05-07T15:40:15.000Z"). This indicates it is a very recent or forthcoming work.

1.5. Abstract

In quantum thermodynamics, the goal often involves finding the minimum energy of a system given its Hamiltonian (energy operator) and a set of non-commuting charges (conserved quantities like particle number). Simultaneously, in optimization theory, semi-definite programs (SDPs) deal with optimizing a linear function over the cone of positive semi-definite operators intersected with an affine space. Despite their distinct origins and terminology, this paper reveals that these two problems are mathematically equivalent.

The paper adopts Jaynes' mindset from quantum thermodynamics, proposing that minimizing free energy (instead of just energy) offers an elegant solution. This leads to a dual chemical potential maximization problem which is concave in its parameters. This concavity allows the use of efficient gradient ascent methods (including stochastic gradient ascent) for quick convergence to optimal chemical potential values. At low temperatures, this minimum free energy closely approximates the true minimum energy.

The authors then demonstrate how this Jaynes-inspired gradient-ascent approach can be leveraged in both first-order and second-order classical and hybrid quantum-classical algorithms for energy minimization and, by extension, for solving SDPs. These algorithms come with guarantees on their runtimes. The paper concludes by providing a physical justification, rooted in quantum thermodynamics, for the effectiveness of various algorithms like the matrix multiplicative weights update method and the matrix exponentiated gradient update method, and their quantum counterparts, which were developed decades after Jaynes' seminal work.

1.6. Original Source Link

https://arxiv.org/abs/2505.04514v2 PDF Link: https://arxiv.org/pdf/2505.04514v2.pdf Publication Status: Preprint on arXiv.

2. Executive Summary

2.1. Background & Motivation

The paper addresses a fundamental connection between two seemingly disparate fields: quantum thermodynamics and semi-definite optimization (SDO).

• Core Problem:

  1. In quantum thermodynamics, a key task is to determine the minimum energy of a quantum system described by a Hamiltonian (operator representing total energy) and a list of non-commuting charges (operators representing conserved quantities like particle number or electric charge). These charges have specified expectation values.
  2. In optimization theory, semi-definite programs (SDPs) are a class of optimization problems where a linear objective function is optimized subject to linear matrix inequality (LMI) constraints, meaning variables must be positive semi-definite matrices.

• Importance and Challenges:

  • Intertwined Nature: The postulates of quantum mechanics inherently involve positive semi-definite operators for states, measurements, and quantum channels (via Choi matrices). This means many quantum mechanical problems, like calculating minimum energy or optimal communication probabilities, can naturally be formulated as SDPs. SDPs have become indispensable in quantum information science, many-body physics, and quantum communication.
  • Differing Motivations & Terminology: Despite the deep mathematical connection, these problems arise from very different intellectual traditions (physics vs. operations research/computer science) and are expressed using highly specialized and distinct terminology, obscuring their underlying mathematical equivalence.
  • Gap in Prior Research: While SDPs have significantly advanced quantum mechanics, the reverse question—can quantum mechanics offer insights into SDO?—has mostly been addressed by developing quantum algorithms for SDPs on quantum computers. The gap is in using physical intuition and thermodynamic principles to understand and develop SDP solvers, rather than just porting classical algorithms to quantum hardware.

• Paper's Entry Point / Innovative Idea: The paper's innovation lies in leveraging Jaynes' mindset from quantum thermodynamics. Instead of directly minimizing energy, they propose minimizing free energy at a finite (but low) temperature. This thermodynamic perspective allows for a natural reformulation of the problem into a dual chemical potential maximization problem that is concave. This concavity is key because it enables the use of efficient gradient-based optimization methods, which are guaranteed to converge. This approach provides a physical intuition for existing and new SDP algorithms.

2.2. Main Contributions / Findings

The paper makes several significant contributions:

1. Mathematical Equivalence: It rigorously establishes that the problem of minimizing energy in quantum thermodynamics (with conserved charges) and semi-definite programs (SDPs) are mathematically identical, bridging a gap between physics and optimization communities.
2. Jaynes-Inspired Dual Formulation: By adopting Jaynes' statistical-mechanical perspective, the paper shows that minimizing free energy (at low temperature, which approximates minimum energy) transforms into a dual chemical potential maximization problem. This dual problem has a concave objective function.
3. Efficient Optimization Strategy: The concavity of the dual problem is a crucial finding, as it guarantees that standard gradient ascent (or stochastic gradient ascent) methods can efficiently find the optimal chemical potentials. The optimal states are identified as grand canonical thermal states (also known as non-Abelian thermal states or quantum Boltzmann machines).
4. Classical and Hybrid Quantum-Classical Algorithms: The paper develops both first-order and second-order classical and hybrid quantum-classical (HQC) algorithms for energy minimization. These algorithms are directly applicable to solving general SDPs through simple reductions.
5. Runtime Guarantees: The proposed algorithms come with explicit runtime guarantees (or sample complexity for HQC algorithms), demonstrating their efficiency. For instance, the sample complexity of the HQC algorithm for SDPs scales polynomially with key parameters.
6. Physical Justification for Existing Algorithms: The Jaynes-inspired approach provides a deep physical motivation for why established SDP algorithms, such as the matrix multiplicative weights (MMW) update method and the matrix exponentiated gradient (MEG) update method (and their quantum generalizations), perform well. It grounds their success in quantum thermodynamic principles.
7. Second-Order Methods and Information Geometry: It is shown that the Hessian matrix of the objective function for chemical potential maximization is equal to the negative of the Kubo-Mori information matrix. This connection implies that Newton's method (a second-order optimization technique) is equivalent to natural gradient ascent in the Kubo-Mori geometry, aligning the optimization path with the information-geometric curvature of the state space.

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

• Quantum Mechanics Postulates: The fundamental rules governing the behavior of matter and energy at the atomic and subatomic level.
  • Quantum State: A description of a quantum system. In this paper, a quantum state is represented by a density matrix $\rho$. A density matrix is a positive semi-definite operator with trace equal to one ($\rho \ge 0, \mathrm{Tr}[\rho]=1$). This ensures probabilities are non-negative and sum to one.
  • Observable: A measurable physical quantity (like energy, momentum, position, spin, or charge) in quantum mechanics. Observables are represented by Hermitian operators (or Hermitian matrices for finite-dimensional systems).
  • Hamiltonian (H): A specific Hermitian operator that represents the total energy of a quantum system. Its eigenvalues are the possible energy values.
  • Conserved Charges (Q_i): Hermitian operators representing quantities that are conserved during the system's evolution (e.g., particle number, electric charge). They are called non-commuting charges if their operators do not commute, meaning the order of measuring them matters.
  • Expectation Value ($\langle \mathcal{O} \rangle_\rho$): The average value of a measurement of an observable $\mathcal{O}$ on a quantum system in state $\rho$. It is calculated as $\mathrm{Tr}[\mathcal{O}\rho]$.
• Optimization Theory:
  • Semi-definite Program (SDP): A convex optimization problem where the objective function is linear, and the constraints are linear matrix inequalities (LMIs), meaning some matrix variable must be positive semi-definite. SDPs generalize linear programs (LPs) and quadratic programs (QPs).
  • Cone of Positive Semi-definite Operators: The set of all Hermitian matrices whose eigenvalues are all non-negative. This set forms a convex cone.
  • Affine Space: A geometric structure that generalizes the notion of Euclidean space. In SDPs, it often refers to linear equality constraints on the matrix variables.
  • Convex Optimization: A subfield of optimization that studies the problem of minimizing convex functions over convex sets. Key properties include that any local minimum is a global minimum, and efficient algorithms often exist.
  • Concave Function: A function whose negative is convex. Maximizing a concave function is equivalent to minimizing a convex function.
  • Gradient Ascent: An iterative optimization algorithm used to find local maxima of a function. It takes steps proportional to the gradient of the function at the current point, moving in the direction of steepest increase.
  • Stochastic Gradient Ascent (SGA): A variant of gradient ascent where the gradient is approximated using a small batch of data (or a single data point) rather than the entire dataset. This is particularly useful for large datasets or when exact gradient computation is costly, introducing stochasticity (randomness) in the updates.
  • Lipschitz Constant (L) / Smoothness Parameter: A measure of how rapidly a function's gradient can change. A function is L-smooth if its gradient is L-Lipschitz continuous, meaning the change in the gradient is bounded by $L$ times the change in the input. This parameter is crucial for determining step sizes and convergence rates in gradient-based optimization.
  • Hessian Matrix: A square matrix of second-order partial derivatives of a scalar-valued function. It describes the local curvature of a function. For a concave function, its Hessian is negative semi-definite.
• Quantum Thermodynamics: The study of thermodynamic phenomena in quantum systems.
  • Free Energy (F): A thermodynamic potential that measures the "useful" or "process-initiating" work obtainable from an isothermal, isobaric thermodynamic system. In quantum mechanics, it's typically defined as $F = \langle H \rangle_\rho - T S(\rho)$, where $H$ is the Hamiltonian, $T$ is the temperature, and $S(\rho)$ is the von Neumann entropy.
  • Von Neumann Entropy ($S(\rho)$): The quantum mechanical analog of classical Shannon entropy, measuring the amount of uncertainty or mixedness in a quantum state $\rho$. It is defined as $S(\rho) = -\mathrm{Tr}[\rho \ln \rho]$.
  • Lagrangian Duality: A technique in optimization theory where a constrained optimization problem (the primal problem) is transformed into an unconstrained problem (the dual problem) involving Lagrange multipliers. The dual problem provides a lower bound on the primal problem's optimal value. For convex problems (or concave maximization), strong duality often holds, meaning the primal and dual optimal values are equal.
  • Chemical Potential ($\mu$): In thermodynamics, chemical potential measures the change in free energy when an additional particle is added to a system. In this context, the chemical potential vector acts as Lagrange multipliers for the conserved charge constraints.
  • Quantum Relative Entropy ($D(\omega \| \tau)$): A measure of distinguishability between two quantum states $\omega$ and $\tau$. It is defined as $D(\omega \| \tau) = \mathrm{Tr}[\omega (\ln \omega - \ln \tau)]$. It is always non-negative and is zero if and only if $\omega = \tau$. It plays a role similar to Kullback-Leibler divergence in classical information theory.
  • Grand Canonical Thermal State / Non-Abelian Thermal State / Quantum Boltzmann Machine: These are terms for a specific type of quantum state $\rho_T(\mu)$ that minimizes free energy in the presence of non-commuting charges. They have the form $\rho_T(\mu) \propto \exp\left(-\frac{1}{T}(H - \mu \cdot Q)\right)$, where $\mu \cdot Q = \sum_i \mu_i Q_i$. They are analogous to Gibbs states in classical statistical mechanics but generalized for non-commuting operators.
  • Kubo-Mori Information Matrix ($I^{KM}(\mu)$): A metric tensor from quantum information geometry that measures the "distance" between infinitesimally different parameterized quantum states. It is related to the Fisher information matrix and describes the curvature of the manifold of quantum states. Its elements are given by the second derivative of the log-partition function.
  • Natural Gradient Ascent: An optimization method that takes into account the geometry of the parameter space. Instead of simply moving in the direction of steepest ascent in Euclidean space, it moves in the direction of steepest ascent with respect to a chosen Riemannian metric (e.g., Fisher information metric, Kubo-Mori metric). This can lead to faster convergence.

3.2. Previous Works

The paper extensively references prior work, differentiating itself by offering a thermodynamics-inspired perspective.

• Jaynes' Seminal Work (1957, 1962): E. T. Jaynes' papers on information theory and statistical mechanics [42-44] are foundational. He proposed unifying information theory with statistical mechanics, demonstrating that thermodynamic ensembles can be derived from maximizing entropy subject to constraints (e.g., fixed expectation values of conserved quantities). The paper explicitly states that Jaynes already observed the conversion of entropy maximization to a dual optimization problem solved by gradient ascent. This paper extends Jaynes' idea from entropy maximization to free energy minimization for non-commuting charges.
• Quantum Information and Thermodynamics (Recent Works): The paper cites recent work [45-51] that has seen Jaynes' framework resurface, particularly concerning quantum systems with non-commuting charges and topics like non-Abelian thermal states and quantum Boltzmann machines. This shows the relevance of the problem in modern quantum research.
• SDP Solvers on Quantum Computers: Previous work has focused on developing algorithms for solving SDPs on quantum computers.
  • Guaranteed Runtimes [30-36]: Algorithms like those by Brandao and Svore (2017) [30], van Apeldoorn and Gilyén (2019) [31] (AG19), and Kerenidis and Prakash (2020) [34] provide theoretical speedups for SDPs on quantum computers. The paper specifically compares its sample complexity to AG19.
  • Heuristic Approaches [37-41]: Other quantum algorithms for SDPs are based on heuristics, often variational quantum algorithms (VQAs) like Variational Quantum Eigensolver (VQE) variants [38, 40, 41]. The paper's HQC algorithm is noted to be broadly similar to HQC algorithms for generative modeling [56] and quantum Boltzmann machine learning [49, 53-55].
• Classical SDP Solvers (Operations Research/Computer Science):
  • Interior-Point Methods [23-25]: A class of algorithms for convex optimization that traverse the interior of the feasible region to find an optimal solution. These are often considered state-of-the-art for SDPs.
  • Matrix Exponentiated Gradient (MEG) Update Method [26]: An algorithm for online learning and convex optimization problems, particularly those involving Bregman divergences. The paper notes its relation to parameterized thermal states but points out that MEG is not motivated by quantum thermodynamics.
  • Matrix Multiplicative Weights (MMW) Update Method [27-29]: A widely used algorithm in online learning, linear optimization, and game theory (especially zero-sum games). It is a matrix generalization of the multiplicative weights update method. The paper highlights that MMW also involves parameterized thermal states but lacks a thermodynamic motivation.

3.3. Technological Evolution

The field has evolved from:

• Theoretical Foundations: Jaynes' work (1950s-60s) laid theoretical groundwork for connecting information theory and statistical mechanics. SDPs emerged from operations research and mathematical programming (1980s-90s) as powerful tools for convex optimization.
• Quantum Information Science (QIS) Emergence: The rise of QIS in the late 20th and early 21st centuries revealed the inherent SDP structure in quantum mechanics, making SDPs crucial for analyzing quantum states, channels, and measurements.
• Classical SDP Algorithm Development: Driven by practical applications in combinatorial optimization, finance, scheduling, and machine learning, fast classical algorithms for SDPs (like interior-point, MEG, MMW) were developed.
• Quantum SDP Algorithm Development: With the advent of quantum computing, researchers began exploring quantum algorithms for SDPs, aiming for quantum speedups. This led to both exact (with runtime guarantees) and heuristic (variational) quantum approaches.
• This Paper's Contribution: This work represents an evolution where quantum thermodynamics is not just a subject for SDPs but also a source of inspiration for designing SDP algorithms. It flips the perspective from "SDPs for quantum mechanics" to "quantum mechanics for SDPs" in a new way, focusing on physical intuition rather than just quantum computational resources.

3.4. Differentiation Analysis

The core differences and innovations of this paper's approach, compared to existing methods, are:

• Physical Intuition as Design Principle: Unlike MEG and MMW which stem from Bregman divergences or zero-sum games, this paper directly uses quantum thermodynamic principles (minimizing free energy via Lagrangian duality) to derive its optimization framework. This provides a natural, physically motivated explanation for why parameterized thermal states are optimal and why gradient ascent is a suitable optimization strategy.
• Concavity-Guaranteed Convergence: The key insight of transforming the free energy minimization problem into a concave chemical potential maximization problem guarantees that standard gradient ascent methods will converge to the global optimum. This is a strong theoretical guarantee often sought in optimization.
• Unified Framework for Energy Minimization and SDPs: The paper provides a clear, unified framework that tackles quantum energy minimization and general SDPs as essentially the same mathematical problem. This broadens the applicability of the thermodynamic approach.
• Hybrid Quantum-Classical (HQC) Focus with Guarantees: While HQC algorithms (like VQAs) are common for quantum optimization, this paper's HQC algorithm (Algorithm 2) for energy minimization and SDPs comes with convergence guarantees to an approximate globally optimal solution, unlike many heuristic VQAs that can suffer from local minima. The guarantees are derived from the underlying concavity.
• Second-Order Methods and Information Geometry: The explicit derivation of the Hessian's relation to the Kubo-Mori information matrix opens the door for efficient second-order optimization methods (like Newton's method or natural gradient ascent) that leverage the geometric properties of the state space, potentially leading to faster convergence than first-order methods.
• Sample Complexity Comparison: The paper provides a detailed sample complexity analysis for its HQC algorithm and directly compares it to the state-of-the-art AG19 quantum MMW algorithm for SDPs, showing a quadratic improvement in dependence on the dual radius parameter $r$ in certain regimes. This demonstrates a concrete algorithmic advantage from the thermodynamic perspective.

4. Methodology

The core methodology of this paper establishes a deep connection between quantum thermodynamics and semi-definite optimization (SDP). It leverages Jaynes' statistical-mechanical framework to transform an intractable energy minimization problem into a tractable chemical potential maximization problem. This transformation enables efficient gradient-based optimization, leading to both classical and hybrid quantum-classical (HQC) algorithms for solving SDPs.

4.1. Principles

The core idea is to solve the difficult problem of finding the minimum energy of a quantum system (which is mathematically equivalent to SDPs) by instead minimizing its free energy at a low but finite temperature.

1. Approximation by Free Energy: Directly minimizing energy can be hard. Physical systems operate at finite temperatures. Minimizing free energy ($F = \langle H \rangle_\rho - T S(\rho)$) at a sufficiently low temperature $T$ provides an excellent approximation to the minimum energy.
2. Lagrangian Duality and Concavity: The free energy minimization problem is a constrained optimization. By applying Lagrangian duality and quantum relative entropy, this problem can be transformed into a dual chemical potential maximization problem. A crucial insight is that the objective function of this dual problem is concave with respect to the chemical potential parameters.
3. Gradient-Based Optimization: The concavity of the dual problem allows for efficient optimization using gradient ascent methods. These methods are guaranteed to converge to the global maximum, making the problem solvable. The optimal states are found to be grand canonical thermal states.
4. Reduction to SDPs: The paper shows that general SDPs can be systematically reduced to energy minimization problems (with conserved charges), extending the applicability of the thermodynamic approach to a wide class of optimization problems.

4.2. Core Methodology In-depth

4.2.1. Energy Minimization Problem in Quantum Thermodynamics

The paper starts by defining the fundamental energy minimization problem in quantum thermodynamics. A quantum system is characterized by:

• A Hamiltonian $H$: A $d \times d$ Hermitian matrix representing the system's energy.

• A tuple of non-commuting conserved charges $(Q_1, \ldots, Q_c)$: Each $Q_i$ is a $d \times d$ Hermitian matrix representing a conserved quantity (like particle number).

• A constraint vector $q = (q_1, \ldots, q_c) \in \mathbb{R}^c$: Specifies the desired expectation values of the conserved charges.

  The state of the system is a density matrix $\rho \in \mathcal{D}_d$, where $\mathcal{D}_d$ is the set of $d \times d$ density matrices: $ \mathcal{D}d := { \rho \in \mathbb{M}d : \rho \geq 0, ~ \mathrm{Tr}[\rho] = 1 } $ Here, $\mathbb{M}_d$ denotes the set of $d \times d$ matrices with entries in $\mathbb{C}$. The expectation value of an observable $\mathcal{O}$ in a state $\rho$ is defined as: $ \langle \mathcal{O} \rangle\rho \equiv \mathrm{Tr}[\mathcal{O}\rho] $ The energy minimization problem is to find the minimum energy $\langle H \rangle_\rho$ subject to the constraints on conserved charges: $ E(\mathcal{Q}, q) := \operatorname*{min}{\rho \in \mathcal{D}d} \left{ \langle H \rangle\rho : \langle Q_i \rangle_\rho = q_i \forall i \in [c] \right} $ where $\mathcal{Q} \equiv (H, Q_1, \ldots, Q_c)$ and $[c] := \{1, \ldots, c\}$. This is a constrained optimization problem.

4.2.2. Approximation by Free Energy Minimization

Finding an exact analytical solution to $E(\mathcal{Q}, q)$ is generally difficult. The paper proposes to approximate it by minimizing the free energy at a strictly positive temperature $T > 0$. The free energy $F_T(\mathcal{Q}, q)$ is defined as: $ F_T(\mathcal{Q}, q) := \operatorname*{min}{\rho \in \mathcal{D}d} \left{ \langle H \rangle\rho - T S(\rho) : \langle Q_i \rangle\rho = q_i \forall i \in [c] \right} $ where $S(\rho)$ is the von Neumann entropy: $ S(\rho) := - \operatorname{Tr}[\rho \ln \rho] $ The free energy minimization problem provides an approximation to the energy minimization problem, which becomes exact as $T \to 0$. The relationship between $E(\mathcal{Q}, q)$ and $F_T(\mathcal{Q}, q)$ is bounded by: $ E(\mathcal{Q}, q) \geq F_T(\mathcal{Q}, q) \geq E(\mathcal{Q}, q) - T \ln d $ This implies that to achieve an error $\delta > 0$ (i.e., $|F_T(\mathcal{Q}, q) - E(\mathcal{Q}, q)| \le \delta$), the temperature $T$ should be set such that $T \ln d = \delta$, or $T = \delta / \ln d$. This means temperature should be inversely proportional to $\ln d$ (where $d$ is the dimension of the Hilbert space, often $d=2^n$ for an $n$-qubit system).

4.2.3. Chemical Potential Maximization (Dual Problem)

The key step is to transform the free energy minimization problem into its dual form using Lagrangian duality and quantum relative entropy. This transformation yields a chemical potential maximization problem. The free energy $F_T(\mathcal{Q}, q)$ can be expressed as: $ F_T(\mathcal{Q}, q) = \operatorname*{sup}_{\mu \in \mathbb{R}^c} \left{ \mu \cdot q - T \ln Z_T(\mu) \right} $ where $\mu = (\mu_1, \ldots, \mu_c) \in \mathbb{R}^c$ is the chemical potential vector (which acts as Lagrange multipliers for the charge constraints). $Z_T(\mu)$ is the partition function: $ Z_T(\mu) := \mathrm{Tr} \left[ e^{ - \frac{1}{T}(H - \mu \cdot Q) } \right] $ with the shorthand $\mu \cdot Q \equiv \sum_{i \in [c]} \mu_i Q_i$. The optimal state $\rho$ for free energy minimization is the unique grand canonical thermal state $\rho_T(\mu^*)$: $ \rho_T(\mu) := \frac{e^{ - \frac{1}{T}(H - \mu \cdot Q) }}{Z_T(\mu)} $ where $\mu^*$ is the optimal chemical potential vector. This state is also known as a non-Abelian thermal state or quantum Boltzmann machine. The objective function $f(\mu) = \mu \cdot q - T \ln Z_T(\mu)$ is concave in $\mu$. This concavity is crucial for efficient optimization.

The overall idea is depicted in Figure 1: +---------------------------------------+ | Energy Minimization Problem | E(Q,q) = min_rho { <H>_rho : <Q_i>_rho = q_i } +---------------------------------------+ | (1) Approx. by Free Energy Minimization at low T V +---------------------------------------+ | Free Energy Minimization Problem | F_T(Q,q) = min_rho { <H>_rho - T S(rho) : <Q_i>_rho = q_i } +---------------------------------------+ | (2) Lagrangian Duality & Quantum Relative Entropy V +---------------------------------------+ | Chemical Potential Maximization Problem | max_mu { mu . q - T ln Z_T(mu) } | (Concave in mu) +---------------------------------------+ | (3) Gradient Ascent V +---------------------------------------+ | Optimal Chemical Potential (mu*) | -> Optimal State (rho_T(mu*)) | -> Approx. Minimum Energy +---------------------------------------+

该图像是求解量子热力学能量最小化问题的示意图。图中展示了能量最小化 E(Q, q) = ext{min}_{ ho ext{ in } ext{D}_d} raket{H}_ ho 和自由能最小化 F_T(Q, q) = ext{min}_{ ho ext{ in } ext{D}_d} raket{H}_ ho - TS( ho) 的关系。通过对偶性，可以转化为化学势最大化问题。该方法可通过梯度上升法有效求解。

FIG. 1. Depiction of the main idea behind solving an energy minimization problem in quantum thermodynamics, specified by a Hamiltonian $H$ and a tuple $( Q _ { 1 } , \ldots , Q _ { c } )$ of conserved non-commuting charges with respective expected values $( q _ { 1 } , \ldots , q _ { c } )$ . The goal is to determine the minimum energy $E ( \mathcal { Q } , q )$ of the system. Inspired by the fact that physical systems operate at a strictly positive temperature $T > 0$ , we instead minimize the free energy $F _ { T } ( \mathcal { Q } , \boldsymbol { q } )$ of the system at a low temperature $T$ . By employing Lagrangian duality and quantum relative entropy, we can rewrite the free energy minimization problem as the dual problem of chemical potential maximization. This latter problem is concave in the chemical potential vector $\mu$ and thus can be solved quickly by gradient ascent. The approach leads to classical and hybrid quantumclassical algorithms for energy minimization. See Section II for details.

4.2.4. Solution using Gradient Ascent (Algorithm 1: Classical Approach)

Since the objective function $f(\mu) = \mu \cdot q - T \ln Z_T(\mu)$ is concave, it can be maximized efficiently using gradient ascent. The elements of the gradient are given by: $ \frac{\partial}{\partial \mu_i} \left( \boldsymbol{\mu} \cdot \boldsymbol{q} - T \ln Z_T(\boldsymbol{\mu}) \right) = q_i - \langle Q_i \rangle_{\rho_T(\boldsymbol{\mu})} $ The gradient ascent algorithm iteratively updates $\mu$ in the direction of the gradient. The algorithm, which assumes knowledge of a smoothness parameter $L$ and an upper bound $r$ on $\| \mu^* \|$, is presented as Algorithm 1. Algorithm 1 takes observables ($H$, $Q_i$), constraint values ($q_i$), smoothness parameter $L$, Hilbert space dimension $d$, desired error $\varepsilon$, and radius $r$ as input. It initializes $\mu^0 = (0, \ldots, 0)$, sets a learning rate $\eta$, and iterates $M$ times. In each iteration $m$, it updates $\mu^m$ using the gradient: $ \mu^m \leftarrow \mu^{m-1} + \eta (q - \langle Q \rangle_{\rho_T(\mu^{m-1})}) $ The term $q - \langle Q \rangle_{\rho_T(\mu^{m-1})}$ is a vector where the $i$-th component is $q_i - \langle Q_i \rangle_{\rho_T(\mu^{m-1})}$. The temperature $T$ is set to $T \leftarrow \varepsilon / (4 \ln d)$, and the number of steps $M$ is chosen to ensure convergence to an $\varepsilon$-approximate solution. The output is an estimate of the minimum energy.

Algorithm 1 First-order classical algorithm for energy minimization 1: Input: • Observables $H$ and $(Q_i)_{i \in [c]}$ • Constraint values $(q_i)_{i \in [c]}$ • Smoothness parameter $L$ • Hilbert space dimension $d$ • Desired error $\varepsilon > 0$ • Radius $r$: An upper bound on $\| \mu^* \|$, where $\mu^*$ is the optimal solution to (14) for $T = \varepsilon/(4 \ln d)$ 2: Set $T \leftarrow \varepsilon/(4 \ln d)$ 3: Initialize $\mu^0 \leftarrow (0, \ldots, 0)$ 4: Set learning rate $\eta \in (0, 1/L]$ 5: Choose $M = \lceil L r^2 / \varepsilon \rceil$ 6: for $m = 1$ to $M$ do 7: $\mu^m \leftarrow \mu^{m-1} + \eta (q - \langle Q \rangle_{\rho_T(\mu^{m-1})})$ 8: end for 9: return $\mu^M \cdot q + \langle H - \mu^M \cdot Q \rangle_{\rho_T(\mu^M)}$ The output of Algorithm 1, denoted $\tilde{E}$, is an $\varepsilon$-approximate estimate of $E(\mathcal{Q}, q)$. The total error is a sum of three sources:

1. Error from approximating $E(\mathcal{Q}, q)$ by $F_T(\mathcal{Q}, q)$ at temperature $T$. This error is bounded by $T \ln d$.
2. Error from gradient ascent not reaching the exact global maximum of $F_T(\mathcal{Q}, q)$. This depends on $L$, $r$, and $M$.
3. Error from outputting $\tilde{E}$ instead of $f(\mu^M) = \mu^M \cdot q - T \ln Z_T(\mu^M)$. This error is $T S(\rho_T(\mu^M))$, which is also bounded by $T \ln d$. By setting $T = \varepsilon/(4 \ln d)$ and $M = \lceil L r^2 / (2\varepsilon) \rceil$, the total error can be controlled to be $\varepsilon$. The number of steps $M$ is given by: $ M = \left\lceil \left( \frac{2}{T} \sum_{i \in [c]} |Q_i|^2 \right) \frac{r^2}{\varepsilon} \right\rceil = \left\lceil \frac{8 r^2 \ln d}{\varepsilon^2} \sum_{i \in [c]} |Q_i|^2 \right\rceil $ The step size $\eta$ is set as: $ 0 < \eta \leq \frac{1}{L} = \frac{T}{2 \sum_{i \in [c]} |Q_i|^2} = \frac{\varepsilon}{8 (\ln d) \sum_{i \in [c]} |Q_i|^2} $

4.2.5. Analysis of the Smoothness Parameter (L)

The smoothness parameter $L$ is a Lipschitz constant for the gradient of $f(\mu)$. It effectively bounds how much the gradient can change. For a concave function, $L$ can be taken as an upper bound on the largest singular value of the Hessian matrix of $f(\mu)$. The Hessian matrix elements of $f(\mu)$ are given by: $ \frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = - I_{ij}^{\mathrm{KM}}(\mu) $ where $I_{ij}^{\mathrm{KM}}(\mu)$ is the Kubo-Mori information matrix element: $ I_{ij}^{\mathrm{KM}}(\mu) = \frac{1}{T} \int_0^1 ds ~ \mathrm{Tr}[\rho_T(\mu)^s Q_i \rho_T(\mu)^{1-s} Q_j] - \frac{1}{T} \langle Q_i \rangle_{\rho_T(\mu)} \langle Q_j \rangle_{\rho_T(\mu)} $ An upper bound on the magnitude of the Hessian matrix elements is: $ \left| \frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) \right| \leq \frac{2}{T} |Q_i| |Q_j| $ Using this, the smoothness parameter $L$ can be set as: $ L = \frac{2}{T} \sum_{i \in [c]} |Q_i|^2 $ This $L$ value is then used in Algorithm 1 to determine the number of iterations $M$ and the learning rate $\eta$.

4.2.6. Semi-definite Optimization (SDP) as Energy Minimization

The paper shows how to reduce a general SDP to an energy minimization problem, thus allowing the same Jaynes-inspired gradient-ascent approach to solve SDPs. A standard SDP form is: $ \alpha := \operatorname*{min}{X \geq 0} \left{ \mathrm{Tr}[CX] : \mathrm{Tr}[A_i X] = b_i \ \forall i \in [c] \right} $ where $C$ and $A_i$ are $d \times d$ Hermitian matrices, and $b_i \in \mathbb{R}$. If one of the constraints is $\mathrm{Tr}[X]=1$, then the SDP is directly equivalent to the energy minimization problem (7) with identifications $C=H$, $A_i=Q_i$, and $b_i=q_i$. For a general SDP without the $\mathrm{Tr}[X]=1$ constraint, a reduction is applied. First, a constraint $\mathrm{Tr}[X] \leq R$ is added, where $R > 0$ is a guess for the trace of an optimal solution. This defines $\alpha_R$: $ \alpha_R := \operatorname*{min}{X \geq 0} \left{ \mathrm{Tr}[CX] : \mathrm{Tr}[X] \leq R, \mathrm{Tr}[A_i X] = b_i \ \forall i \in [c] \right} $ As $R \to \infty$, $\alpha_R \to \alpha$. The paper then uses two Lemmas to reduce this SDP to an energy minimization problem.

Lemma 1 ([32]): The following equality holds: $ \alpha_R = R \cdot \operatorname*{min}{\rho \in \mathcal{D}{d+1}} \left{ \langle C' \rangle_\rho : \langle A'i \rangle\rho = b'i \forall i \in [c] \right} $ where C' := C \oplus [0], A'_i := A_i \oplus [0], and $b'_i := b_i/R$. This reduction effectively embeds the original $d \times d$ matrices into $(d+1) \times (d+1)$ matrices and normalizes the constraint values. This transformation makes the problem an energy minimization of the form (7) on a larger Hilbert space of dimension $d+1$, with the added constraint $\mathrm{Tr}[\rho]=1$. The output of Algorithm 1 then needs to be scaled by $R$. The error tolerance for Algorithm 1 becomes $\varepsilon/R$, and the dimension is $d+1$, which modifies the number of steps $M$ to: $ M = \left\lceil 8 \left( \frac{R r}{\varepsilon} \right)^2 \ln (d+1) \sum{i \in [c]} |A_i|^2 \right\rceil $

Lemma 3: This lemma provides an alternative reduction more amenable to quantum computer implementation. The following equality holds: $ \alpha_R = R \cdot \operatorname*{min}{\rho \in \mathcal{D}{2d}} \left{ \langle C' \rangle_\rho : \langle A'i \rangle\rho = b'_i \ \forall i \in [c] \right} $ where $C' := C \otimes |0\rangle\langle0|$, $A'_i := A_i \otimes |0\rangle\langle0|$, and $b'_i := b_i/R$. This reduction effectively doubles the dimension of the system ($d \to 2d$) by embedding the original system into a larger system with an ancilla qubit in state $|0\rangle$. This transformation also makes the problem an energy minimization of the form (7) on a larger Hilbert space of dimension 2d.

The overall idea for solving SDPs is depicted in Figure 2: $$+---------------------------------------+ | General SDP | min_X>=0 { Tr[CX] : Tr[A_i X] = b_i } +---------------------------------------+ | (1) Reduction [32, Footnote 3] | (Add Tr[X] <= R, then scale) V +---------------------------------------+ | Scaled Energy Minimization Problem | R * min_rho { <C'>_rho : <A'_i>_rho = b'_i } | (on D_{d+1} or D_{2d}) +---------------------------------------+ | (2) Apply Jaynes-inspired Gradient Ascent V +---------------------------------------+ | Solution to SDP | (Sample-efficient if R not too large) +---------------------------------------+$$

该图像是示意图，展示了解决一般半正定优化问题（SDP）的主要思想。图中包含了从标准SDP到经过修改的SDP的转变过程及其对应的自由能最小化和化学势最大化问题，表现出热力学与优化的关系。关键的公式包括 $\alpha_R = \min_{X \geq 0} \text{Tr}[CX]$ 以及 $\alpha_{R,T} = \min_{\rho \in D_{d+1}} \langle C' \rangle_\rho - TS(\rho)$，阐明了优化算法的样本效率。

FIG. 2. Depiction of the main idea behind solving a general semi-definite optimization problem (abbreviated SDP), specified by the tuple of $d \times d$ Hermitian matrices $( C , A _ { 1 } , \ldots , A _ { c } )$ . The reduction from [32, Footnote 3] allows for reducing a general SDP to an energy minimization problem, where $R \geq 0$ is a guess on the trace of an optimal solution to the original SDP. The resulting algorithm is sample-efficient as long as $R$ does not grow too quickly with $d$ . See Section IV for details.

4.2.7. Hybrid Quantum-Classical (HQC) Algorithms (Algorithm 2)

The classical Algorithm 1 can be promoted to an HQC algorithm by using a quantum computer for certain steps. The HQC algorithm (Algorithm 2) is a stochastic gradient ascent (SGA) algorithm because quantum computers provide estimates (with inherent stochasticity) of expectation values.

Setup and Assumptions:

• The Hilbert space dimension is $d=2^n$, meaning the system involves $n$ qubits.
• Observables $H$ and $Q_i$ are efficiently measurable on a quantum computer. This is typically true if they can be written as succinct linear combinations of Pauli matrices (or Pauli strings). $ \mathcal{H} = \sum_{\vec{\jmath}} h_{\vec{\jmath}} \sigma_{\vec{\jmath}} $ $ Q_i = \sum_{\vec{\jmath}} a_{i, \vec{\jmath}} \sigma_{\vec{\jmath}} $ where $\vec{\jmath} = (j_1, \ldots, j_n) \in \{0,1,2,3\}^n$ is a multi-index, $\sigma_{\vec{\jmath}} = \sigma_{j_1} \otimes \cdots \otimes \sigma_{j_n}$ is a Pauli string (with $\sigma_0=I, \sigma_1=X, \sigma_2=Y, \sigma_3=Z$), and $h_{\vec{\jmath}}, a_{i, \vec{\jmath}} \in \mathbb{R}$ are coefficients. Efficient measurability requires that the number of non-zero terms in these sums is polynomial in $n$, and their 1-norms ($\|h\|_1 = \sum |h_{\vec{\jmath}}|$, $\|a_i\|_1 = \sum |a_{i, \vec{\jmath}}|$) are polynomial in $n$.
• The parameterized thermal state $\rho_T(\mu)$ can be prepared on a quantum computer. This is a crucial subroutine for HQC algorithms and is an active area of research.

Approach (Algorithm 2): Algorithm 2 is a projected stochastic gradient ascent (SGA) algorithm. It iteratively updates the chemical potential vector $\mu$.

• Stochastic Gradient: Instead of computing the exact gradient $q_i - \langle Q_i \rangle_{\rho_T(\mu)}$, Algorithm 2 estimates $\langle Q_i \rangle_{\rho_T(\mu)}$ using a quantum computer via a subroutine estimate_obs (Algorithm 3 in Appendix F2). The estimated gradient $\overline{g}(\mu^m)$ is then used for the update.
• Projection: The update step includes a projection $\Pi_\mathcal{X}$ onto a Euclidean ball $\mathcal{X}$ of radius $r$. This ensures that $\mu$ stays within a bounded search space, where $r \ge \|\mu^*\|$ is an assumed upper bound on the optimal solution's norm. $ \boldsymbol{\mu}^{m+1} = \Pi_{\mathcal{X}} \big( \boldsymbol{\mu}^m + \eta \overline{g}(\boldsymbol{\mu}^m) \big) $ The projection operator is defined as: $ \Pi_{\mathcal{X}}(y) := \operatorname*{argmin}_{x \in \mathcal{X}} |y - x|_2 $
• Unbiased Estimator: The stochastic gradient $\overline{g}(\mu)$ must be unbiased, meaning its expectation value equals the true gradient: $\mathbb{E}[\overline{g}(\mu)] = \nabla_\mu f(\mu) = q - \langle Q \rangle_{\rho_T(\mu)}$. Algorithm 3 (detailed below) provides such an unbiased estimator.
• Bounded Variance: The stochastic gradient must also have bounded variance: $\mathbb{E}[\|\overline{g}(\mu) - \nabla f(\mu)\|^2] \leq \sigma^2$ for some constant $\sigma^2$. This bound is crucial for SGA convergence analysis.

Algorithm for Stochastic Gradient Estimation (Algorithm 3): The estimate_obs subroutine (Algorithm 3) is used to estimate expectation values like $\langle Q_i \rangle_{\rho_T(\mu)}$ and $\langle H - \mu \cdot Q \rangle_{\rho_T(\mu)}$. Given a chemical potential vector $\mu$, Pauli coefficients $(a_{\vec{\jmath}})_{\vec{\jmath}}$, desired accuracy $\varepsilon$, and error probability $\delta$:

1. It calculates the number of samples $N$ needed using Hoeffding's inequality: $N \leftarrow \lceil 2 \|a\|_1^2 \ln(2/\delta) / \varepsilon^2 \rceil$.
2. For $N$ repetitions: a. Sample a multi-index $\vec{\jmath}$ with probability $a_{\vec{\jmath}}/\|a\|_1$. b. Prepare the thermal state $\rho_T(\mu)$. c. Measure the Pauli string $\sigma_{\vec{\jmath}}$ on $\rho_T(\mu)$, obtaining an outcome $b_n \in \{0,1\}$ (corresponding to eigenvalues $\pm 1$). d. Compute $Y_n \leftarrow \|a\|_1 (-1)^{b_n}$.
3. The estimate is the average: $\overline{Y} \leftarrow \frac{1}{N} \sum_{n=0}^{N-1} Y_n$. This $\overline{Y}$ is an unbiased estimator of $\langle Q_i \rangle_{\rho_T(\mu)}$.

Algorithm 2 Hybrid quantum-classical algorithm for energy minimization 1: Input: • Observables $H$ and $(Q_i)_{i \in [c]}$ (as given in (40)-(41)) • Constraint values $(q_i)_{i \in [c]}$ • Hilbert space dimension $d$ • Accuracy $\varepsilon > 0$ • Error probability $\delta \in (0, 1)$ • Radius $r$: An upper bound on $\|\mu^*\|$, where $\mu^*$ is the optimal solution to (14) for $T = \varepsilon/(4 \ln d)$ 2: Set $T \leftarrow \varepsilon/(4 \ln d)$ 3: Initialize $\mu^0 \leftarrow (0, \ldots, 0)$ 4: Set learning rate $\eta$ as in (51) [see below] 5: Set number of iterations, $M$, as in (52) [see below] 6: for $m = 1$ to $M$ do 7: for $i = 1$ to $c$ do 8: $\tilde{Q}_i \leftarrow \mathsf{estimate\_obs}(\mu^{m-1}, (a_{i, \vec{\jmath}})_{\vec{\jmath}}, \varepsilon, \delta)$ 9: $\overline{g}_i(\mu^{m-1}) \leftarrow q_i - \tilde{Q}_i$ 10: end for 11: Update: $\mu^m \leftarrow \Pi_{\mathcal{X}}(\mu^{m-1} + \eta \overline{g}(\mu^{m-1}))$ 12: end for 13: Set $\overline{\mu^M} \leftarrow \frac{1}{M} \sum_{m=1}^M \mu^m$ 14: Set $g_{\vec{\jmath}} \leftarrow h_{\vec{\jmath}} - \sum_{i \in [c]} [\overline{\mu^M}]_i a_{i, \vec{\jmath}}$, for all $\vec{\jmath}$ 15: $\tilde{G} \leftarrow \mathsf{estimate\_obs}(\overline{\mu^M}, (\overline{g_{\vec{\jmath}}})_{\vec{\jmath}}, \varepsilon/4, \delta)$ 16: return Output $\overline{\mu^M} \cdot q + \tilde{G}$

Convergence of HQC Algorithm (Theorem 2): The SGA algorithm (Algorithm 2) converges to an $\varepsilon$-approximate globally optimum solution. The choices for learning rate $\eta$ and number of iterations $M$ are: $ \eta := \left[ \frac{8 \ln d}{\varepsilon} \sum_{i \in [c]} |a_i|1^2 + \frac{\sigma}{r} \sqrt{\frac{M}{2}} \right]^{-1} $ $ M := \left\lceil \frac{16 r^2}{\varepsilon^2} \left( 2 \sigma^2 + 8 (\ln d) \sum{i \in [c]} |a_i|1^2 \right) \right\rceil $ where $\sigma^2$ is the bounded variance of the stochastic gradient: $ \sigma^2 := c \varepsilon^2 + \delta \sum{i \in [c]} |a_i|1^2 $ The sample complexity (total number of thermal-state samples needed) of Algorithm 2 to reach an $\varepsilon$-approximate estimate $\hat{E}$ of the optimal energy $E(\mathcal{Q}, q)$ with success probability $\geq 1 - \delta$ is given by: $ O \left( \frac{r^2 \ln(1/\delta) \ln d}{\varepsilon^4} \left[ \operatorname*{max}\left{ \sum{i \in [c]} |a_i|_1^2, |h|_1 \right} \right]^2 \right) $ This sample complexity is polynomial in $\varepsilon^{-1}$, $c$, $r$, $\|h\|_1$, and $\|a_i\|_1$. For Pauli coefficients that are polynomial in $n$ (number of qubits), the sample complexity scales polynomially with $n$ and $\varepsilon^{-1}$.

Extension to SDPs: Using Lemma 3, the HQC algorithm (Algorithm 2) can be applied to solve general SDPs. The reduction in Lemma 3 doubles the system dimension ($d \to 2d$, or $n \to n+1$ qubits) and requires the energy minimization problem to be solved to an error of $\varepsilon/R$. The sample complexity for solving SDPs of the general form (32) by Algorithm 2 is: $ O \left( \frac{r^2 R^4 n \ln(1/\delta)}{\varepsilon^4} \left[ \operatorname*{max}\left{ \sum_{i \in [c]} |A_i|^2, |C| \right} \right]^2 \right) $ This shows polynomial overhead from the trace factor $R$ and the single-qubit extension.

4.2.8. Second-Order Stochastic Gradient Ascent

The paper also discusses second-order methods (like Newton's method) for potentially faster convergence. This requires estimating the Hessian matrix of $f(\mu)$. The Hessian elements can be expressed using a quantum channel $\Phi_\mu$: $ \Phi_\mu(\cdot) := \int_{-\infty}^\infty dt p(t) e^{-i(H - \mu \cdot Q)t/T} (\cdot) e^{i(H - \mu \cdot Q)t/T} $ where p(t) is a high-peak-tent probability density defined as $p(t) := \frac{2}{\pi} \ln|\coth(\frac{\pi t}{2})|$. The Hessian elements are then: $ \frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = \frac{1}{T} \left( \langle Q_i \rangle_{\rho_T(\mu)} \langle Q_j \rangle_{\rho_T(\mu)} - \frac{1}{2} \langle {\Phi_\mu(Q_i), Q_j} \rangle_{\rho_T(\mu)} \right) $ This expression is equal to the negative of the Kubo-Mori information matrix: $ \frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = - I_{ij}^{\mathrm{KM}}(\mu) $ The ability to estimate these Hessian elements (using quantum circuits like the one depicted in Figure 3) enables Newton's method. For concave functions, Newton's method can offer faster local convergence. Moreover, the equivalence of Hessian with Kubo-Mori information matrix means Newton's step is equivalent to a natural gradient step with respect to the Kubo-Mori metric, where the update rule is: $ \boldsymbol{\mu}^{m+1} = \boldsymbol{\mu}^m - \eta \Delta_m $ where $\Delta_m$ is the solution to $I^{\mathrm{KM}}(\mu^m) \Delta_m = \overline{g}(\mu^m)$. This means the gradient is rescaled by the inverse of the Kubo-Mori information matrix to align with the steepest descent direction in the information geometry.

An example of a quantum circuit for estimating elements of the Hessian (specifically, the anticommutator term) is provided as Algorithm 4 in Appendix H. The circuit involves controlled unitary operations ($e^{i(H-\mu\cdot Q)t/T}$), Hadamard gates, and measurements of a control qubit and the system register. Time t and Pauli strings $\sigma_{\vec{\ell}}, \sigma_{\vec{k}}$ are sampled probabilistically.

该图像是一个量子电路示意图，展示了量子态 $|1\rangle$ 经 Hadamard 门操作后，如何与其他量子门结合，以实现特定的量子操作。整体流程中包含了 $e^{i(H-\mu\cdot Q)t/T}$ 的演变，表明哈密顿量与化学势之间的关联，进一步连接到后续的测量操作。

FIG. 3. $- { \scriptstyle \frac { 1 } { 2 } } \left. \left\{ \Phi _ { \mu } { \bigl ( } Q _ { i } { \bigr ) } , Q _ { j } \right\} \right. _ { \rho _ { T } { \bigl ( } \mu { \bigr ) } }$ $t$ is sampled independently at random from the probability density p ( t ) in (61), while $o _ { \vec { \ell } }$ and $\sigma _ { \vec { k } }$ are sampled with probabilities $a _ { i , \vec { \ell } } / \left| \right| a _ { i } \left| \right| _ { 1 }$ and $a _ { j , \vec { k } } / \lVert a _ { j } \rVert _ { 1 }$ , respectively. For details of the algorithm, see Appendix H.

5. Experimental Setup

The paper primarily focuses on the theoretical framework and algorithmic guarantees rather than empirical experimental results on specific datasets. Therefore, this section describes the theoretical comparison framework and the "evaluation metrics" used for analyzing the proposed algorithms.

5.1. Datasets

No specific empirical datasets are used or described in the paper for validating the method's performance. The theoretical analysis applies to general quantum systems described by Hamiltonians and conserved charges, or general SDPs defined by Hermitian matrices.

• Problem Instances: The "data" implicitly refers to the parameters defining the energy minimization problem ($\mathcal{Q}=(H, Q_1, \ldots, Q_c)$ and $q$) or the SDP ($C, A_1, \ldots, A_c, b_1, \ldots, b_c$).
• Motivation: The choice of these abstract problem instances is effective for validating the generality and theoretical efficiency (i.e., sample complexity or runtime guarantees) of the proposed algorithms across a broad range of quantum and optimization problems.

5.2. Evaluation Metrics

The primary evaluation metric used in this paper is sample complexity, which quantifies the efficiency of hybrid quantum-classical (HQC) algorithms.

• Conceptual Definition: Sample Complexity: In the context of HQC algorithms or stochastic optimization, sample complexity refers to the total number of times a quantum computer needs to prepare a specific quantum state and perform measurements (sampling) to achieve a desired accuracy $\varepsilon$ with a certain success probability ($1-\delta$). It is a measure of the quantum resource cost or query complexity to the quantum oracle. Lower sample complexity implies a more efficient algorithm.

• Mathematical Formula (for HQC energy minimization, Theorem 2): $ O \left( \frac{r^2 \ln(1/\delta) \ln d}{\varepsilon^4} \left[ \operatorname*{max}\left{ \sum_{i \in [c]} |a_i|_1^2, |h|_1 \right} \right]^2 \right) $

  • Symbol Explanation:
    • $O(\cdot)$: Big-O notation, indicating the asymptotic upper bound on the growth rate.
    • $r$: An upper bound on the norm of the optimal chemical potential vector $\|\mu^*\|$. It represents the size of the search space for $\mu$.
    • $\ln(1/\delta)$: Logarithm of the inverse error probability. $\delta$ is the probability of failure to achieve the desired accuracy.
    • $\ln d$: Logarithm of the Hilbert space dimension. For $n$ qubits, $d=2^n$, so $\ln d = n \ln 2 \propto n$.
    • $\varepsilon$: The desired accuracy for the estimated minimum energy.
    • $\sum_{i \in [c]} \|a_i\|_1^2$: Sum of the squared 1-norms of the Pauli-coefficient vectors for the charge observables $Q_i$. It reflects the complexity of the charge operators.
    • $\|h\|_1$: The 1-norm of the Pauli-coefficient vector for the Hamiltonian $H$. It reflects the complexity of the Hamiltonian.
    • $c$: The number of conserved charges (or constraints).

• Mathematical Formula (for HQC SDP solving, derived from Theorem 2): $ O \left( \frac{r^2 R^4 n \ln(1/\delta)}{\varepsilon^4} \left[ \operatorname*{max}\left{ \sum_{i \in [c]} |A_i|^2, |C| \right} \right]^2 \right) $

  • Symbol Explanation:
    • $O(\cdot)$, $r$, $n$ (from $\ln d$), $\ln(1/\delta)$, $\varepsilon$: Same as above, but with $n$ representing the number of qubits in the original $d \times d$ system. Note that the dimension is effectively 2d (or $n+1$ qubits) due to Lemma 3's reduction.
    • $R$: The scaling factor introduced in the SDP reduction, representing a guess on the trace of an optimal solution to the original SDP.
    • $\sum_{i \in [c]} \|A_i\|^2$: Sum of the squared operator norms of the constraint matrices $A_i$ in the SDP.
    • $\|C\|$: The operator norm of the objective matrix $C$ in the SDP.
    • $c$: The number of constraints in the SDP.

5.3. Baselines

The paper's method is primarily compared against other quantum algorithms for SDPs, particularly those based on the matrix multiplicative weights (MMW) approach. It also draws connections to classical MMW and matrix exponentiated gradient (MEG) methods.

• AG19 Quantum MMW Algorithm [31]: This is considered the state-of-the-art quantum algorithm for solving SDPs based on the MMW approach.

  • Why representative: It represents a leading quantum algorithm with theoretical runtime guarantees for SDPs. It is an iterative method and its sample complexity is well-characterized in prior work.
  • Sample Complexity of AG19: $ O \left( \frac{r^4 R^4 \ln(1/\delta) \ln d}{\varepsilon^4} \right) $
    • Symbol Explanation: The symbols $r$, $R$, $\ln(1/\delta)$, $\ln d$ (or $n$), and $\varepsilon$ are consistent with the definitions above. Note the dependence on $r^4$ and independence from $c$.

• Matrix Multiplicative Weights (MMW) Update Method [27-29]: A classical algorithm for online learning and linear optimization, which can also solve SDPs.

  • Why representative: It's a widely used and well-understood algorithm. The paper points out that MMW and MEG implicitly use updates related to parameterized thermal states, providing a physical motivation for their success.

• Matrix Exponentiated Gradient (MEG) Update Method [26]: Another classical online learning algorithm related to Bregman divergences.

  • Why representative: Similar to MMW, it's a known convex optimization algorithm that involves parameterized thermal states.

    The comparisons are theoretical, focusing on sample complexity scaling with various parameters ($r, R, \varepsilon, \delta, d, c, \|A_i\|, \|C\|$).

6. Results & Analysis

The paper's main "results" are theoretical, focusing on the derivation of its Jaynes-inspired gradient-ascent approach and the sample complexity guarantees for its hybrid quantum-classical (HQC) algorithms when applied to energy minimization and semi-definite programs (SDPs). The analysis then compares these complexities to existing quantum SDP solvers.

6.1. Core Results Analysis

The central finding is the derivation of Algorithm 2 (the HQC algorithm for energy minimization and, by extension, SDPs) and its sample complexity guarantees. The core results are:

1. Concavity and Convergence Guarantees: The paper rigorously shows that the dual chemical potential maximization problem is concave. This is a strong theoretical result because it implies that gradient-based optimization (specifically stochastic gradient ascent used in Algorithm 2) is guaranteed to converge to the global optimum, rather than getting stuck in local minima, which is a common challenge for variational quantum algorithms.

2. Sample Complexity for HQC Energy Minimization (Theorem 2): The sample complexity of Algorithm 2 for energy minimization is polynomial in $r$, $\ln(1/\delta)$, $\ln d$ (or $n$), and polynomial in the 1-norms of the Pauli-coefficient vectors for the Hamiltonian $H$ and charge operators $Q_i$. It scales as $O(\varepsilon^{-4})$. This means that given efficient preparation of thermal states and measurable observables, the algorithm can find an $\varepsilon$-approximate solution with a feasible number of quantum samples.

3. Sample Complexity for HQC SDP Solving: When extended to general SDPs via Lemma 3's reduction, the sample complexity of Algorithm 2 is given by: $ O \left( \frac{r^2 R^4 n \ln(1/\delta)}{\varepsilon^4} \left[ \operatorname*{max}\left{ \sum_{i \in [c]} |A_i|^2, |C| \right} \right]^2 \right) $ This expression shows that the algorithm maintains a polynomial dependence on $n$, $\varepsilon^{-1}$, and the operator norms of the SDP matrices. The factors $r^2$ and $R^4$ arise from the properties of the dual problem and the SDP reduction, respectively.

4. Second-Order Methods: The paper demonstrates that the Hessian matrix of the objective function for chemical potential maximization is precisely the negative of the Kubo-Mori information matrix. This deep connection to quantum information geometry is significant. It implies that second-order optimization methods (e.g., Newton's method) are equivalent to natural gradient ascent in the Kubo-Mori metric. Such methods, when implementable, often lead to faster convergence rates than first-order methods because they leverage the curvature information of the objective function.

Comparison with AG19 Quantum MMW Algorithm:

The paper provides a direct theoretical comparison of its HQC algorithm (Algorithm 2) for solving SDPs with the AG19 quantum MMW algorithm [31], after aligning problem settings (e.g., bounding operator norms to 1 for fair comparison).

The sample complexity of Algorithm 2 scales as: $ O \left( \frac{r^2 c^2 R^4 \ln (1/\delta) \ln d}{\varepsilon^4} \right) $ (Here, the $\operatorname*{max}$ term is simplified to $c^2$ assuming $\|A_i\|$ and $\|C\|$ are bounded by 1, and the number of constraints $c$ is the dominant factor).

The sample complexity of the AG19 quantum MMW algorithm scales as: $ O \left( \frac{r^4 R^4 \ln (1/\delta) \ln d}{\varepsilon^4} \right) $

Analysis of Advantages and Disadvantages:

• Advantage of Algorithm 2: Algorithm 2 exhibits a quadratic improvement in the dependence on the dual radius parameter $r$ ($r^2$ vs. $r^4$). This means for problems where $r$ is large, Algorithm 2 offers a strictly better sample complexity. This could be particularly advantageous for SDPs with large dual radii.
• Advantage of AG19: The AG19 algorithm is independent of the number of constraints $c$, whereas Algorithm 2 has a $c^2$ dependence.
• Trade-off:

  • For combinatorial problems like MAXCUT, where $r$ often scales linearly with $c$ (i.e., $r \propto c$), both algorithms achieve comparable performance regarding $c$ (e.g., $r^2 c^2 \propto c^4$ for Algorithm 2, and $r^4 \propto c^4$ for AG19).

  • However, if $r$ is significantly larger than $c$ (i.e., $r \gg c$), Algorithm 2 provides a strictly better sample complexity.

    This comparison highlights that the Jaynes-inspired approach offers a competitive, and in some regimes, superior, theoretical performance for SDP solving on quantum computers.

6.2. Data Presentation (Tables)

The paper presents Algorithm 1 and Algorithm 2 as code blocks. Algorithm 3 and Algorithm 4 are presented within the Appendix. I will transcribe these algorithms as they appear in the paper.

The following is Algorithm 1 from the original paper: Algorithm 1 First-order classical algorithm for energy minimization 1: Input: • Observables $H$ and $(Q_i)_{i \in [c]}$ • Constraint values $(q_i)_{i \in [c]}$ • Smoothness parameter $L$ • Hilbert space dimension $d$ • Desired error $\varepsilon > 0$ • Radius $r$: An upper bound on $\| \mu^* \|$, where $\mu^*$ is the optimal solution to (14) for $T = \varepsilon/(4 \ln d)$ 2: Set $T \leftarrow \varepsilon/(4 \ln d)$ 3: Initialize $\mu^0 \leftarrow (0, \ldots, 0)$ 4: Set learning rate $\eta \in (0, 1/L]$ 5: Choose $M = \lceil L r^2 / \varepsilon \rceil$ 6: for $m = 1$ to $M$ do 7: $\mu^m \leftarrow \mu^{m-1} + \eta (q - \langle Q \rangle_{\rho_T(\mu^{m-1})})$ 8: end for 9: return $\mu^M \cdot q + \langle H - \mu^M \cdot Q \rangle_{\rho_T(\mu^M)}$

The following is Algorithm 2 from the original paper: Algorithm 2 Hybrid quantum-classical algorithm for energy minimization 1: Input: • Observables $H$ and $(Q_i)_{i \in [c]}$ (as given in (40)-(41)) • Constraint values $(q_i)_{i \in [c]}$ • Hilbert space dimension $d$ • Accuracy $\varepsilon > 0$ • Error probability $\delta \in (0, 1)$ • Radius $r$: An upper bound on $\|\mu^*\|$, where $\mu^*$ is the optimal solution to (14) for $T = \varepsilon/(4 \ln d)$ 2: Set $T \leftarrow \varepsilon/(4 \ln d)$ 3: Initialize $\mu^0 \leftarrow (0, \ldots, 0)$ 4: Set learning rate $\eta$ as in (51) 5: Set number of iterations, $M$, as in (52) 6: for $m = 1$ to $M$ do 7: for $i = 1$ to $c$ do 8: $\tilde{Q}_i \leftarrow \mathsf{estimate\_obs}(\mu^{m-1}, (a_{i, \vec{\jmath}})_{\vec{\jmath}}, \varepsilon, \delta)$ 9: $\overline{g}_i(\mu^{m-1}) \leftarrow q_i - \tilde{Q}_i$ 10: end for 11: Update: $\mu^m \leftarrow \Pi_{\mathcal{X}}(\mu^{m-1} + \eta \overline{g}(\mu^{m-1}))$ 12: end for 13: Set $\overline{\mu^M} \leftarrow \frac{1}{M} \sum_{m=1}^M \mu^m$ 14: Set $g_{\vec{\jmath}} \leftarrow h_{\vec{\jmath}} - \sum_{i \in [c]} [\overline{\mu^M}]_i a_{i, \vec{\jmath}}$, for all $\vec{\jmath}$ 15: $\tilde{G} \leftarrow \mathsf{estimate\_obs}(\overline{\mu^M}, (\overline{g_{\vec{\jmath}}})_{\vec{\jmath}}, \varepsilon/4, \delta)$ 16: return Output $\overline{\mu^M} \cdot q + \tilde{G}$

The following is Algorithm 3 from the original paper (Appendix F2): Algorithm 3 estimate_obs($\mu$, $(a_{\vec{\jmath}})_{\vec{\jmath}}$, $\varepsilon$, $\delta$) 1: Input: • chemical potential vector $\mu \in \mathbb{R}^c$, • non-negative coefficients $(a_{\vec{\jmath}})_{\vec{\jmath}}$ for the Pauli strings $(\sigma_{\vec{\jmath}})_{\vec{\jmath}}$ • accuracy $\varepsilon > 0$, • error probability $\delta \in (0, 1)$ 2: $N \leftarrow \lceil 2 \|a\|_1^2 \ln(2/\delta) / \varepsilon^2 \rceil$ 3: for $n = 0$ to $N - 1$ do 4: Sample a multi-index $\vec{\jmath}$ with probability $a_{\vec{\jmath}}/\|a\|_1$ 5: Prepare a register in the state $\rho_T(\mu)$, measure $\sigma_{\vec{\jmath}}$, and store the measurement outcome $b_n$ 6: Set $Y_n \leftarrow \|a\|_1 (-1)^{b_n}$ 7: end for 8: return $\overline{Y} \leftarrow \frac{1}{N} \sum_{n=0}^{N-1} Y_n$

The following is Algorithm 4 from the original paper (Appendix H), which contains a table-like structure:

6.3. Ablation Studies / Parameter Analysis

The paper does not present explicit ablation studies or sensitivity analyses for hyper-parameters in the traditional experimental sense. However, the theoretical analysis inherently involves how key parameters affect the sample complexity and convergence.

• Temperature ($T$) and Error Approximation: The choice of temperature $T = \varepsilon / (4 \ln d)$ is critical. It directly controls the approximation error between minimum energy and minimum free energy. A lower temperature reduces this error but might increase the difficulty of thermal state preparation or the number of gradient ascent steps.

• Radius ($r$) and Scaling Factor ($R$): The parameters $r$ (upper bound on $\|\mu^*\|$) and $R$ (guess on $\mathrm{Tr}[X]$ for SDPs) are significant. The sample complexity of Algorithm 2 depends quadratically on $r$ and quarticly on $R$ ($r^2 R^4$). Accurate estimation of $r$ and $R$ is crucial for tight runtime guarantees. If $R$ grows too quickly, the algorithm might become inefficient.

• Accuracy ($\varepsilon$) and Error Probability ($\delta$): The sample complexity scales as $\varepsilon^{-4}$ and logarithmically with $\ln(1/\delta)$. This indicates that achieving very high accuracy comes at a significant sampling cost, a common characteristic of stochastic algorithms.

• Smoothness Parameter ($L$): The parameter $L$ (which depends on $T$ and operator norms) directly influences the number of iterations $M$ in Algorithm 1 ($M \propto L/\varepsilon$). A larger $L$ (steeper change in gradient) requires more steps for convergence.

• Number of Constraints ($c$) and Operator Norms ($\|A_i\|_1$, $\|C\|_1$): The sample complexity for SDPs depends on $c^2$ and the operator norms of the matrices involved. This means problems with many complex constraints will be more demanding.

  These theoretical dependencies implicitly show how the choice and inherent properties of these parameters affect the algorithm's performance.

7. Conclusion & Reflections

7.1. Conclusion Summary

This paper establishes a profound and mathematically rigorous link between quantum thermodynamics and semi-definite optimization (SDP). It demonstrates that the seemingly distinct problems of energy minimization in quantum systems with non-commuting charges and SDPs are fundamentally equivalent.

The core innovation lies in adopting Jaynes' statistical-mechanical perspective. By minimizing free energy (at low temperatures) instead of directly minimizing energy, the problem is recast into a dual chemical potential maximization problem. This dual problem is shown to have a concave objective function, a property that guarantees efficient optimization using gradient ascent methods. The optimal states for this problem are identified as grand canonical thermal states (or quantum Boltzmann machines).

Leveraging this framework, the authors develop both classical (Algorithm 1) and hybrid quantum-classical (HQC) (Algorithm 2) first-order algorithms for energy minimization. These algorithms are shown to be generalizable to solve standard SDPs through a simple reduction. Crucially, Algorithm 2 comes with sample complexity guarantees, demonstrating polynomial scaling with relevant parameters. Furthermore, the paper highlights the potential for second-order methods by showing that the Hessian matrix of the objective function corresponds to the negative of the Kubo-Mori information matrix, linking Newton's method to natural gradient ascent in quantum information geometry. This work not only provides new algorithmic approaches but also offers a powerful physical intuition for the success of existing SDP solvers like matrix multiplicative weights (MMW) and matrix exponentiated gradient (MEG) methods.

7.2. Limitations & Future Work

The authors acknowledge several limitations and propose promising avenues for future research:

• Assumption of Quasi-local Operators for Strong Concavity: While the dual objective function is generally concave, strong concavity can lead to faster convergence rates. Existing results show strong concavity for quasi-local operators (operators acting on only a few qubits), but this assumption does not hold for the general case considered (arbitrary Pauli string decompositions). Further investigation is needed to establish strong concavity more broadly or identify specific problem classes where it applies.
• Imperfect Thermal State Preparation: The analysis of the HQC algorithm (Algorithm 2) assumes perfect thermal state preparation. In practice, quantum devices have limitations, leading to imperfect state preparation and bias in gradient estimators. While the stochastic gradient framework can accommodate this by adjusting variance bounds, the efficiency of low-temperature thermal state preparation remains a significant challenge for practical quantum advantage.
• Low-Temperature Thermalization Challenge: Achieving the low temperatures (inversely proportional to the number of qubits) required for accurate energy minimization is difficult with current thermal state preparation methods. This poses a barrier to demonstrating quantum advantage for large systems.
• Rigorous Analysis of Second-Order Methods: While a second-order approach is proposed, a detailed sample complexity analysis is still needed. Quantifying the trade-offs between the computational overhead of Hessian estimation and solving linear systems (for Newton steps) versus the improved sample efficiency is crucial to determine when these methods offer a practical advantage, especially for a small number of constraints $c$.
• Generalization to Broader SDP Classes: The current framework focuses on equality-constrained SDPs. Extending it to SDPs with inequality constraints (which naturally leads to non-negative chemical potentials) and other nonlinear objective functions is a natural next step to expand the method's practical utility.
• Exploring Generalized Divergences: The Umagaki relative entropy was key to the duality connection. Investigating if generalized divergences (e.g., Rényi relative entropies) could play similar roles might offer new insights and alternative optimization algorithms.
• Continuous-Variable Constraints: Extending the framework to handle continuous-variable constraints would broaden its applicability to systems described by differential equations.
• Continuous-Time Dynamics and Game Theory: Generalizing the training process to continuous time could connect the work to dynamical systems like replicator dynamics in the quantum regime, linking quantum thermodynamics, dynamical systems, and game theory via SDPs.
• Quantum Advantage Conditions: A thorough investigation is needed to identify specific problem classes where classical simulation of thermal states is intractable, but quantum computers can efficiently prepare them at the required low temperatures, thereby demonstrating a clear quantum advantage.

7.3. Personal Insights & Critique

This paper offers a refreshing perspective on semi-definite optimization by grounding it in quantum thermodynamics. The Jaynes-inspired approach is elegant and provides a deep physical intuition for mathematical constructs that might otherwise seem arbitrary in pure optimization theory.

• Inspiration and Transference:

  • Unified View: The paper's strength lies in its unifying theme. It elegantly bridges two complex fields, demonstrating that fundamental principles from one can inspire powerful solutions in another. This cross-disciplinary approach is highly inspiring and suggests that physical intuition can be a potent tool for algorithm design in diverse areas.
  • Concavity as a Gift: The concavity of the dual chemical potential maximization problem is a "gift" from the thermodynamic formulation. For many quantum optimization problems, non-convexity is a major hurdle. Identifying structures that yield concave (or convex) objectives is invaluable for guaranteed convergence.
  • Information Geometry Connection: The link between the Hessian and the Kubo-Mori information matrix is particularly insightful. This suggests that optimal learning paths in parameterized quantum states are inherently tied to the geometry of quantum information. This could inspire new quantum machine learning algorithms that are "naturally" aligned with the underlying quantum mechanics.
  • Generalizability: The reduction from SDPs to energy minimization problems is powerful. It means that any future improvements in quantum thermodynamic energy minimization algorithms can directly benefit SDP solvers, and vice-versa. This kind of mapping is highly valuable for interdisciplinary research.

• Potential Issues & Areas for Improvement:

  • Practicality of Low-Temperature Thermal State Preparation: The main practical bottleneck for realizing quantum advantage from this work appears to be the efficient preparation of thermal states at extremely low temperatures ($T \propto 1/\ln d$). While there has been progress in thermal state preparation (as cited), achieving polylogarithmic temperature (i.e., very low for large $n$) is still an open and hard problem. The theoretical sample complexity is promising, but state preparation cost could dominate in practice.

  • Dependence on 'r' and 'R': The sample complexity depends on $r^2$ and $R^4$. If the dual radius $r$ or the trace guess $R$ grows very rapidly with problem size (e.g., exponentially), the polynomial scaling might still be prohibitive. Better ways to bound or adaptively estimate $r$ and $R$ would enhance practical utility.

  • Overhead of Quantum Measurements: While Algorithm 3 provides an unbiased estimator, the actual measurement process on quantum hardware involves shot noise and other errors. The Hoeffding bound is a classical statistical bound; practical quantum error mitigation might be needed.

  • Second-Order Methods Complexity: The paper proposes second-order methods but defers the sample complexity analysis. While theoretically faster, Hessian estimation and matrix inversion can introduce significant classical and quantum overheads, especially for large $c$. A detailed trade-off analysis is critical to determine their utility.

  • "Temperature as a Hyperparameter": The temperature $T$ is used as a parameter to control the approximation error. In a practical setting, tuning this $T$ (or $\varepsilon_1$) might behave like a hyperparameter for performance, similar to the learning rate or number of iterations. This interplay needs careful empirical exploration.

    Overall, this paper provides a robust theoretical foundation and a fresh perspective that could significantly influence the design of future quantum algorithms for optimization. Its strength lies in its rigorous theoretical backing and the elegant connections it draws between seemingly disparate fields, offering a blueprint for physically inspired algorithm development.