Generalized Reimpell-Werner Iteration

Technical Summary: Generalized Reimpell–Werner Iteration

Problem Statement
Quantum information protocols rely heavily on optimizing measurements and channels to extract, encode, and transmit information. Key tasks include minimum error state discrimination, optimizing entanglement fidelity, quantifying quantum resources (such as coherence and imaginarity), and local energy extraction. These problems are naturally formulated as Semidefinite Programs (SDPs) involving a linear objective function over positive semidefinite (PSD) matrices subject to partial trace constraints.

While standard SDP solvers can approach global optima, their computational cost scales poorly with increasing Hilbert space dimensions. Iterative methods, such as the Ježek–Řeháček–Fiurášek (JRF) iteration for measurements and the Reimpell–Werner (RW) iteration for channels, offer a more practical alternative by exploiting the specific algebraic structure of these constraints. However, existing convergence guarantees for these methods have limitations:

1. Scope: The original RW iteration is restricted to positive semidefinite (PSD) cost matrices. Many quantum tasks, such as local energy extraction or certain game-theoretic benchmarks, involve Hermitian cost matrices with both positive and negative eigenvalues.
2. Convergence: While monotonicity of the objective value is established, global convergence to an optimum for general high-rank initializations has remained an open question, particularly for the JRF iteration with mixed state ensembles. Previous results often required specific initialization conditions (e.g., linearly independent pure ensembles) or relied on stability tests and random perturbations to avoid non-optimal fixed points.

Methodology
The authors propose a Generalized Reimpell–Werner (RW) Iteration that extends the original framework to arbitrary Hermitian cost matrices under partial trace inequality constraints.

• Shift and Slack Formulation: To handle indefinite (non-PSD) cost matrices $C$, the authors introduce a scalar shift $s \geq 0$ and a slack matrix $S \succeq 0$. They define a shifted cost matrix $\tilde{C} = C + sI_{AB}$ and reformulate the constraint $\text{tr}_A X \preceq D$ as an equality $\text{tr}_A X + S = D$ (assuming normalized $D=I_B$). This augmentation ensures the shifted objective remains equivalent to the original while allowing the use of PSD update rules.
• Iterative Update: The generalized iteration updates the primal variable $X$ and the slack $S$ simultaneously via congruence transformations involving the shifted cost matrix and a normalizer $Y^{(k)}$. The update rule is:
  $$Y^{(k)} := \left[ \text{tr}_A(\tilde{C} X^{(k)} \tilde{C}) + s^2 S^{(k)} \right]^{1/2}$$
  $$X^{(k+1)} := (I_A \otimes Y^{(k)})^{-1} \tilde{C} X^{(k)} \tilde{C} (I_A \otimes Y^{(k)})^{-1}$$
  $$S^{(k+1)} := s^2 (Y^{(k)})^{-1} S^{(k)} (Y^{(k)})^{-1}$$
• Support Conditions: The convergence analysis relies on a specific "support overlap" condition for the initialization. Specifically, the kernel of the initial seed pair $(X^{(0)}, S^{(0)})$ must have trivial intersection with the support of the shifted cost matrix and the shift term. This condition is satisfied by any positive definite initialization and allows for singular seeds under specific conditions.
• Geometric Framework: The proof maps the iteration to a gradient ascent on a real analytic manifold (the Stiefel manifold) using a reshaping technique (Penrose diagram). This allows the application of the Łojasiewicz gradient inequality to establish convergence.

Key Contributions and Results

1. Generalization to Hermitian Costs: The paper successfully generalizes the RW iteration to handle arbitrary Hermitian cost matrices, thereby unifying the treatment of tasks with indefinite objectives (e.g., energy extraction) with standard PSD tasks (e.g., state discrimination).
2. Global Convergence Theorem: The authors prove that the iterates converge to a global optimum provided the initialization satisfies the explicit support condition. This resolves the open problem regarding the global convergence of the JRF iteration for arbitrary mixed state ensembles under suitable initialization.
   • The limiting pair $(X^{(\infty)}, S^{(\infty)})$ achieves the optimal primal value.
   • The limiting normalizer determines the unique dual optimizer of the normalized problem.
   • The duality gap closes at the fixed point.
3. Iteration Complexity Bounds: The paper quantifies the convergence rate. For a fixed problem and admissible initialization:
   • Objective Gap: $O(1/\varepsilon)$ iterations are sufficient to bring the objective value within $\varepsilon$ of the optimum. In the best case (e.g., diagonal cost matrices), this improves to $O(\log(1/\varepsilon))$.
   • Certificate and Matrix Error: Bounds are also established for the dual certificate gap and the Frobenius distance to the optimal matrix, showing similar dependence on the Łojasiewicz exponent $\theta \in [1/2, 1)$.
4. Specializations:
   • When $s=0$ and $C \succeq 0$, the method reduces to the original RW iteration.
   • The JRF iteration is shown to be a block-diagonal specialization of the generalized RW iteration.
   • The framework covers applications including entanglement fidelity optimization, state discrimination/exclusion, coherence robustness, and local energy extraction.

Significance and Claims
The paper claims to provide a rigorous foundation for the Reimpell–Werner and JRF iterations, moving beyond empirical observations or restricted convergence proofs. By establishing global convergence under explicit, verifiable support conditions, the work broadens the class of optimization problems to which these efficient iterative methods can be applied with guaranteed performance.

The authors emphasize that their method avoids the computational expense of large linear systems encountered in interior-point methods (like Clarabel) or cone projections (like SCS). Numerical simulations (Figure 1) indicate that the generalized RW and JRF implementations achieve significantly lower median runtimes than standard SDP solvers for state discrimination and entanglement fidelity tasks, particularly as system dimensions increase.

The work does not claim to solve general linear constraints beyond partial traces, noting that the tensor structure is essential to their normalization scheme. Furthermore, while the convergence is guaranteed, the specific rate (linear vs. sublinear) depends on the problem instance's geometry, with some constructed cases exhibiting polynomial rather than geometric convergence.