PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditions for Global Optimality in Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

arXiv:2609.09731v1cs.ITmath.ITmath.OCquant-ph

TL;DR

Monotonic decrease and numerical stabilization do not establish whether a generalized quantum AB fixed point is globally optimal. The paper gives a necessary-and-sufficient criterion for full-rank fixed points under convex differentiable objectives and linear constraints, and develops certificates for assessing candidate states. Its examples show that AB can reach a global optimum despite differing from MD, or stabilize at a suboptimal fixed point.

  • Problem

    Monotonic objective decrease and numerical stabilization do not guarantee global optimality, and AB fixed points can fail first-order optimality even for convex objectives.

    Source: §I · p. 1

  • Method

    The paper compares AB fixed-point conditions with first-order optimality, characterizes AB–MD update compatibility, and develops feasible-directional-derivative and finite-difference certificates.

    Source: §I · pp. 1–2

  • Results

    The channel-relative-entropy examples show that differing AB and MD trajectories can accompany global success, while an amplitude-damping AB iteration can stabilize at a suboptimal fixed point detected by the certificate.

    Source: §I · p. 2

  • Takeaways & Limitations

    Assessing the terminal state directly with directional-derivative and finite-difference certificates gives an objective-gap upper bound without explicitly computing the objective gradient.

    Source: §VI · p. 13

Abstract

from arXiv · show

Generalized Arimoto--Blahut (AB) algorithms are widely used in information theory and quantum optimization, but monotonic objective decrease and numerical stabilization do not guarantee global optimality. We establish necessary and sufficient conditions for the global optimality of full-rank AB fixed points for convex differentiable objectives under linear constraints. An AB fixed point is globally optimal if and only if the AB update direction and the objective gradient differ by an element of the constraint normal space at that point. The same compatibility condition characterizes agreement between individual AB and mirror-descent (MD) updates, whereas pathwise equivalence requires it along the entire common trajectory. Thus, an AB algorithm may follow a trajectory different from MD and still reach the global optimum. We also develop a posteriori optimality certificates based on feasible directional derivatives, including finite-difference upper bounds on the objective gap that require only objective evaluations. For channel relative entropy between dephasing and depolarizing channels, we analytically identify the global minimizer as the unique full-rank AB fixed point, although pathwise equivalence fails. Numerical experiments illustrate convergence of AB and MD along different trajectories and validate the certificates. By contrast, an amplitude-damping example shows that a monotone AB iteration can stabilize at a suboptimal fixed point, whose nonoptimality is detected by the finite-difference certificate. These results provide structural and computable criteria for assessing global optimality in quantum AB algorithms.

I. INTRODUCTION

The paper asks when a generalized quantum AB fixed point is globally optimal, since monotonic decrease and numerical stabilization alone do not establish optimality. It compares AB and mirror-descent conditions and develops optimality certificates within a framework for quantum-state optimization.

I. INTRODUCTION

  • For convex differentiable objectives under linear constraints, a full-rank AB fixed point is globally optimal exactly when its update direction differs from the objective gradient by an element of the constraint normal space.The paper also motivates this criterion by noting that an AB fixed point may fail the first-order optimality condition even for a convex objective.Source: §I · p. 1

A. Optimization Problem and Mixture Family

  • The optimization framework minimizes f(ρ) = Tr ρΩ(ρ) over density matrices, with a mixture family encoding linear constraints Tr ρHj = cj.The formulation also covers optimization over quantum operations by transforming it to a state-optimization problem on an enlarged Hilbert space using purification.Source: A. Optimization Problem and Mixture… · p. 2

B. Mirror Descent Algorithm

  • Mirror descent uses the objective gradient as its update direction and a Bregman-divergence proximal step, with quantum relative entropy identified as the natural choice.The update is posed over the feasible set M.Source: B. Mirror Descent Algorithm · pp. 2–3

C. Generalized Quantum Arimoto–Blahut Algorithm

III. GLOBAL OPTIMALITY CONDITIONS AND MIRROR-DESCENT EQUIVALENCE

  • Section III characterizes update-level and pathwise AB–MD equivalence, relates full-rank accumulation points to AB fixed points, and develops global-optimality conditions and a posteriori certificates.The certificates use feasible directional derivatives and finite differences to bound the objective gap without explicitly computing the gradient.Source: §I · p. 2, §III · p. 3

A. Geometric Setting and Update Maps

  • The geometric analysis works on the relative interior of the feasible set, where states are full rank, and defines tangent and normal spaces for normalization and linear constraints.It assumes the feasible set contains a positive-definite state and that {I, H1, …, Hk} is linearly independent.Source: A. Geometric Setting and Update Maps · p. 3

B. Update-Level and Pathwise Equivalence

AB and mirror descent have the same proximal-update form but use different directions, Ω(ρ) and ∇f(ρ). Their updates agree when the directions differ only by a normal-space element; matching an entire trajectory requires this compatibility at every common iterate.

B. Update-Level and Pathwise Equivalence

  • Earlier equivalence results rely on conditions including nonnegative DΩ and a global-optimality guarantee, while one condition may be analytically intractable or hard to verify numerically.Without the additional conditions, AB may become trapped in a local minimum.Source: B. Update-Level and Pathwise Equivalence · pp. 3–4
  • At any full-rank state, an AB update equals the MD update if and only if Ω(ρ) − ∇f(ρ) belongs to the constraint normal space.Equivalently, the two update directions have the same feasible tangent component.Source: B. Update-Level and Pathwise Equivalence · pp. 4–5
  • From a shared full-rank initialization, AB and MD iterates agree through step T exactly when the compatibility condition holds at every common iterate before T.Agreement of the update maps throughout the full-rank domain requires the condition at every state in that domain.Source: B. Update-Level and Pathwise Equivalence · p. 5
  • A compatibility failure separates the trajectories from that iterate onward but does not determine whether the AB trajectory later reaches a globally optimal state.Equality of Ω and ∇f is sufficient for update agreement but stronger than necessary.Source: B. Update-Level and Pathwise Equivalence · p. 5

C. Accumulation Points and Fixed Points

Monotone objective values do not ensure that the AB state sequence converges to a single state. Under condition (a1), relative-interior accumulation points are AB fixed points, and uniqueness of the full-rank fixed point yields state convergence.

C. Accumulation Points and Fixed Points

  • Monotone convergence of objective values does not by itself imply convergence of the state sequence to a single state.The analysis distinguishes convergence to an accumulation set from convergence to a particular state.Source: C. Accumulation Points and Fixed Points · pp. 5–6
  • Condition (a1) implies asymptotic regularity, which is sufficient to link trajectory accumulation points to fixed points when the AB update map is continuous.The fixed-point analysis is restricted to accumulation points in the relative interior, the natural domain of the logarithmic update.Source: C. Accumulation Points and Fixed Points · pp. 5–6
  • Under condition (a1), every relative-interior accumulation point of the AB trajectory is an AB fixed point.Asymptotic regularity connects accumulation points to fixed points, but does not by itself imply convergence to one state.Source: C. Accumulation Points and Fixed Points · p. 6
  • If every accumulation point is full-rank and the AB map has a unique full-rank fixed point, the state sequence converges to that fixed point.The uniqueness condition strengthens the accumulation-point result to convergence of the trajectory.Source: C. Accumulation Points and Fixed Points · p. 6

D. Global Optimality of Fixed Points

For convex differentiable objectives under linear constraints, a full-rank AB fixed point is globally optimal exactly when its AB direction and objective gradient differ by a constraint-normal vector. This condition is needed at the fixed point for optimality, but along the trajectory for pathwise equivalence with mirror descent.

D. Global Optimality of Fixed Points

  • A full-rank AB fixed point is globally optimal if and only if Ω(ρ∗) − ∇f(ρ∗) belongs to the constraint normal space.The theorem assumes a convex differentiable objective and a feasible set defined by linear constraints.Source: D. Global Optimality of Fixed Points · p. 7
  • Failure of pathwise equivalence does not rule out global optimality when the terminal AB fixed point satisfies the compatibility condition.The condition need not hold at earlier iterates.Source: D. Global Optimality of Fixed Points · p. 7
  • At an AB fixed point, global optimality is also characterized by vanishing objective directional derivatives in every feasible tangent direction.The equivalent weak-form characterization avoids explicitly forming the objective gradient.Source: D. Global Optimality of Fixed Points · pp. 7–8

E. A Posteriori Optimality Certificates

The paper gives a zero-residual optimality test and an upper bound on suboptimality based on the distance of the objective gradient from the constraint normal space. Convex finite differences along feasible directions estimate the needed derivatives without explicitly computing the gradient.

E. A Posteriori Optimality Certificates

  • A zero residual certifies global optimality exactly when every feasible first-order variation vanishes.For a small nonzero residual, the distance from the objective gradient to the normal space yields a rigorous upper bound on suboptimality.Source: E. A Posteriori Optimality Certificates · p. 8
  • Convexity bounds each feasible directional derivative between backward and forward secant slopes, allowing derivative estimates from objective evaluations.The finite-difference construction uses feasible perturbations ρ ± h_jE_j.Source: E. A Posteriori Optimality Certificates · pp. 8–9
  • The finite-difference estimates yield a suboptimality bound without explicitly calculating the objective gradient.The certificate is based on evaluations along feasible directions.Source: E. A Posteriori Optimality Certificates · p. 8

IV. EXAMPLES

The channel-relative-entropy examples identify global minimizers that are unique full-rank AB fixed points in unconstrained and linearly constrained settings. Numerical experiments show AB and MD reaching those minimizers along different trajectories.

A. Formulation

  • The examples formulate negative quantum relative entropy between channels as a convex optimization problem, with energy constraints defining the feasible mixture family.The feasible set is specified by linear conditions Tr ρ_A H_j = E_j.Source: A. Formulation · p. 9

B. Theoretical Analysis

  • The maximally mixed state is the unique full-rank AB fixed point and global minimizer in the unconstrained example.Any full-rank limit of a convergent AB trajectory must be this state.Source: B. Theoretical Analysis · p. 9
  • In the constrained example, 1/2(I + EH) is both the global minimizer and the unique full-rank AB fixed point.The result applies to the stated linear constraint with H chosen from σx, σy, or σz.Source: B. Theoretical Analysis · p. 10

C. Numerical Comparison of AB and MD

  • Without constraints, AB and MD approach the same global minimizer from the tested initialization while following different trajectories and converging at different rates.Their initial update directions differ because Ω(ρ(0)) − ∇f(ρ(0)) is not in the constraint normal space.Source: C. Numerical Comparison of AB and MD · p. 10
  • With Tr(ρσx) = 0.4, the tested AB and MD trajectories approach the known global minimizer along different paths.At the initial point, Ω(ρ(0)) − ∇f(ρ(0)) is outside span{I, σx}, so the updates differ.Source: C. Numerical Comparison of AB and MD · pp. 10–11
  • For the reported numerical trajectories, condition (a1) is satisfied at every numerically resolved iteration with γ = 1.A negative ratio does not establish failure of (a1); it indicates that the stronger nonnegativity condition (a2) need not hold.Source: C. Numerical Comparison of AB and MD · pp. 10–11

D. A Posteriori Certification

The finite-difference certificate gives conservative, objective-only bounds on AB suboptimality, and the examples show why a converged AB iterate must be assessed at its endpoint. Its scope is full-rank fixed-point optimality; convergence to a globally optimal fixed point requires additional analysis.

D. A Posteriori Certification

  • In both constrained and unconstrained examples, the finite-difference bounds stay above the true objective gap, with smaller tested steps generally producing tighter bounds.The certificate uses objective evaluations along feasible tangent directions and does not require an explicit objective gradient.Source: D. A Posteriori Certification · p. 11, Figure 3 · p. 12, Figure 4 · p. 12

V. COUNTEREXAMPLE

  • The amplitude-damping AB sequence decreases monotonically and stabilizes, yet reaches a strictly higher objective value than MD and is certified nonoptimal by a finite-difference test.The interval for the E_z direction excludes zero, violating the fixed-point optimality condition.Source: §V · pp. 12–13

VI. DISCUSSION

  • AB and MD can follow different trajectories while an AB limit is globally optimal, because optimality requires compatibility only at the terminal fixed point.Pathwise equivalence instead requires compatibility at every common iterate.Source: §VI · p. 13
  • The results characterize full-rank fixed-point optimality and finite-iterate certificates, but do not establish convergence to a globally optimal fixed point.The discussion also identifies rank-deficient boundary points, non-linear-equality feasible sets, and scalable certification as future directions.Source: §VI · p. 13

APPENDIX A PROOF OF COROLLARY 14

The appendices prove optimality and uniqueness claims by combining convexity, symmetry, and tests of the AB direction against feasible displacements. The dephasing–depolarizing fixed-point proof reduces uniqueness to strict positivity of a scalar function.

APPENDIX A PROOF OF COROLLARY 14

  • At a full-rank global minimizer, affine-constraint first-order optimality supplies a subgradient in the constraint normal space, while a normal subgradient implies global minimality by convexity.The positive-semidefinite constraint is inactive at a full-rank point.Source: Appendix A · p. 13

APPENDIX B PROOF OF PROPOSITION 19

  • For the dephasing–depolarizing example, symmetry and convexity establish the maximally mixed state as a global minimizer.The proof uses channel covariance and invariance of quantum relative entropy under isometries.Source: Appendix B · pp. 13–14

APPENDIX C PROOF OF THEOREM 17

  • The unconstrained uniqueness proof shows that the maximally mixed state is the unique full-rank AB fixed point for the specified channel parameters.It reduces the fixed-point problem to strict positivity of T(ρ), derives a radial expression, and proves its coefficients positive.Source: Appendix C · p. 14, A. Scalar Reduction of the Fixed-Point… · p. 14

A. Scalar Reduction of the Fixed-Point Problem

  • A scalar reduction proves uniqueness when a candidate fixed point satisfies a strict inequality against every other feasible full-rank state.The proof uses that AB directions at fixed points are normal to the feasible set, while state differences lie in its tangent space.Source: A. Scalar Reduction of the Fixed-Point… · p. 14

B. Radial Representation of T(ρ)

  • The radial representation keeps the Bloch direction fixed and varies the state radius to express the scalar function used in the uniqueness proof.The derivation splits the relative-entropy expression into two logarithmic terms.Source: B. Radial Representation of T(ρ) · pp. 14–15

C. Closed-Form Expression for T(ρ)

The appendix derives a closed form for T(ρ) by evaluating its two logarithmic contributions along radial directions. Positivity of the resulting Bloch coefficients makes T(ρ) strictly positive away from the maximally mixed state, yielding uniqueness of the full-rank fixed point.

C. Closed-Form Expression for T(ρ)

  • The closed-form calculation evaluates the two terms of T(ρ) separately, using channel symmetries and a block decomposition of the relevant operator.Rotational and reflection symmetries about the Z-axis constrain the Bloch components of the AB direction.Source: C. Closed-Form Expression for T(ρ) · pp. 15–16
  • For the chosen channel parameters, the transverse and Z-direction Bloch coefficients are strictly positive for every full-rank state in the stated radial range.The proof establishes positivity of the transverse coefficient directly and bounds the Z coefficient using monotonicity.Source: D. Strict Positivity of T(ρ) · p. 16
  • For every ρ ≠ I/2, ηz(ρ) > 0; since I/2 is an AB fixed point, Lemma 22 with bρ = I/2 proves it is the unique full-rank fixed point.Source: D. Strict Positivity of T(ρ) · p. 16

APPENDIX D PROOF OF THEOREM 20

For each constrained problem, the appendix verifies the proposed state is an AB fixed point and then establishes strict positivity against every other feasible full-rank state. The scalar uniqueness lemma therefore gives a unique full-rank fixed point.

APPENDIX D PROOF OF THEOREM 20

  • For H in {X, Y, Z}, symmetry establishes the proposed constrained state as an AB fixed point, and strict positivity away from it proves uniqueness among full-rank fixed points.The proof reuses the symmetry decomposition and positive coefficients established in Appendix C.Source: Appendix D · pp. 16–17

APPENDIX E GRADIENT OF THE CHANNEL-RELATIVE-ENTROPY OBJECTIVE

Appendix E derives the channel-relative-entropy gradient by differentiating the objective after writing ρ = X², then recovering ∇f(ρ) through a Sylvester equation. It establishes matrix-differential identities for handling a possibly singular term and differentiating a logarithm.

APPENDIX E GRADIENT OF THE CHANNEL-RELATIVE-ENTROPY OBJECTIVE

  • Writing ρ = X² turns the gradient calculation into differentiating g(X) = f(X²) and recovering ∇f(ρ) from ∇g(X) through a Sylvester equation.For X ≻ 0, the Sylvester map is invertible on Hermitian matrices, so ∇f(ρ) is uniquely determined.Source: Appendix E · p. 17, A. Setting and Proof Strategy · p. 17

A. Setting and Proof Strategy

  • The example has A_N2 ≻ 0 while A_N1 may be singular, so the derivation uses a support logarithm for positive semidefinite operators.The support logarithm is defined on the range of the operator, with the convention 0 log 0 = 0.Source: A. Setting and Proof Strategy · p. 17

B. Two Matrix-Differential Identities

  • The matrix-differential identities address the constant-rank entropy derivative and the Fréchet derivative of log A, including its self-adjointness and eigenbasis form.The logarithm derivative identity is used for the cross term Tr(A_N1 log A_N2).Source: B. Two Matrix-Differential Identities · pp. 17–18

C. Gradient Formula

The gradient formula separates the contributions from differentiating A_N1 and log A_N2. It is obtained by differentiating with respect to X and then solving a Sylvester equation to recover the gradient with respect to ρ.

C. Gradient Formula

  • The proposition separates the gradient contributions from differentiating A_N1 and the cross-term logarithm log A_N2.The proof applies the constant-rank entropy derivative to Tr(A_N1 log A_N1) and differentiates the cross term using the product rule.Source: C. Gradient Formula · p. 18
  • For Hermitian perturbations δX, the output operators vary through δA_N1 and δA_N2, each formed by varying one of the two X factors.The variations use δX ⊗ I_B and the corresponding channel operators Γ_N1 and Γ_N2.Source: C. Gradient Formula · p. 18
  • The numerical gradient procedure computes L, evaluates ∇g(X), and solves the Sylvester equation to obtain ∇f(ρ).The Sylvester equation has a unique solution because x_i + x_j > 0 in an eigenbasis of X.Source: C. Gradient Formula · p. 18
Loading 2609.09731v1…