Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40203

Generalized Reimpell-Werner Iteration

Shihao Ru, Bikun Li, Weibo Gao, Liang Jiang

quant-phmath-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum measurements and channels determine how information is extracted, encoded, and transmitted in quantum protocols. Optimizing their performance often requires numerical methods that remain practical as Hilbert space dimensions increase. The Reimpell-Werner iteration offers a practical approach to these tasks through repeated matrix updates that respect the constraints. Here, we generalize this iteration to linear objectives with arbitrary Hermitian cost matrices. We prove that the iterates converge to a global optimum whenever the initialization satisfies suitable support overlap conditions. For each fixed problem, choice of iteration parameters, and admissible initialization, $\mathcal{O}(1/\varepsilon)$ iterations suffice asymptotically to bring the objective value within $\varepsilon$ of the optimum. These results provide a rigorous foundation for the iteration and broaden the class of optimization problems to which its convergence guarantees apply.

AI Summary

The paper addresses global convergence of the Reimpell–Werner (RW) iteration for channel optimization and the Ježek–Řeháček–Fiurášek (JRF) iteration for measurement optimization. It generalizes RW to the SDP $\max_{X\succeq0}\{\operatorname{tr}(CX):\operatorname{tr}_A X\preceq D\}$ for arbitrary Hermitian $C$ and PSD $D$. A slack matrix and a common spectral shift make the augmented cost positive semidefinite without changing the optimization problem. Under explicit initial-support conditions, satisfied by positive-definite seeds, every update is well defined and the matrix iterates converge to a global optimum. The limiting normalizer yields the unique dual optimizer of the support-reduced, normalized problem. Specializations establish convergence of the original RW iteration and of JRF for arbitrary finite mixed-state ensembles under the stated support conditions. The proof combines polar normalization on a Stiefel manifold, a Łojasiewicz gradient inequality, and a spectral argument establishing limiting dual feasibility and closing the duality gap. For each fixed instance, shift, and admissible seed, objective accuracy $\varepsilon$ requires asymptotically $O(1/\varepsilon)$ iterations; a computable dual certificate requires $O(1/\varepsilon^2)$. Half-gradient-exponent cases have logarithmic bounds. Explicit slow families have objective iteration exponents approaching one and unbounded matrix-error exponents as dimension grows. The bounds have instance-dependent constants and onset, so they do not establish complexity as dimension varies. Runtime comparisons exclude reference-bound construction and iterative certificate evaluation. Extension to general linear constraints remains open because the normalization exploits partial-trace structure; optimal shift and initialization choices are also unresolved.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
24 pages, 2 figures, 1 table

Related papers

Iterative quantum optimization with an adaptive problem Hamiltonian for the shortest vector problem

Yifeng Rocky Zhu, David Joseph, Cong Ling +1 more

Quantum optimization algorithms hold the promise of solving classically hard, discrete optimization problems in practice. The requirement of encoding such problems in a Hamiltonian realized with a finite (and currently small) number of qubits, however, poses the risk of finding only the optimum within the restricted space supported by this Hamiltonian. We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.

arXiv:2204.13432•Physical Review A•Aug 29, 2022•7 citations

Quantum gradient algorithm for general polynomials

Pan Gao, Keren Li, Shijie Wei +2 more

Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of $O(poly(d))$ for the $d$-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in $O(poly(logd))$. Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.

arXiv:2004.11086•Physical Review A•Apr 1, 2021•17 citations

Iterative Optimization of Quantum Error Correcting Codes

Michael Reimpell, Reinhard F. Werner

We introduce a convergent iterative algorithm for finding the optimal coding and decoding operations for an arbitrary noisy quantum channel. This algorithm does not require any error syndrome to be corrected completely, and hence also finds codes outside the usual Knill-Laflamme definition of error correcting codes. The iteration is shown to improve the figure of merit "channel fidelity" in every step.

arXiv:quant-ph/0307138•Physical Review Letters•Mar 2, 2005•116 citations

Conditions for Global Optimality in Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

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.

cs.ITCross-listedarXiv:2609.09731•Sep 10, 2026•0 citations

An Algorithm for Global Maximization of Secrecy Rates in Gaussian MIMO Wiretap Channels

Sergey L. Loyka, Charalambos D. Charalambous

Optimal signaling for secrecy rate maximization in Gaussian MIMO wiretap channels is considered. While this channel has attracted a significant attention recently and a number of results have been obtained, including the proof of the optimality of Gaussian signalling, an optimal transmit covariance matrix is known for some special cases only and the general case remains an open problem. An iterative custom-made algorithm to find a globally-optimal transmit covariance matrix in the general case is developed in this paper, with guaranteed convergence to a global optimum. While the original optimization problem is not convex and hence difficult to solve, its minimax reformulation can be solved via the convex optimization tools, which is exploited here. The proposed algorithm is based on the barrier method extended to deal with a minimax problem at hand. Its convergence to a global optimum is proved for the general case (degraded or not) and a bound for the optimality gap is given for each step of the barrier method. The performance of the algorithm is demonstrated via numerical examples. In particular, 20 to 40 Newton steps are already sufficient to solve the sufficient optimality conditions with very high precision (up to the machine precision level), even for large systems. Even fewer steps are required if the secrecy capacity is the only quantity of interest. The algorithm can be significantly simplified for the degraded channel case and can also be adopted to include the per-antenna power constraints (instead or in addition to the total power constraint). It also solves the dual problem of minimizing the total power subject to the secrecy rate constraint.

arXiv:1504.03725•IEEE Transactions on Communications•Apr 17, 2015•45 citations

Quantum-Channel Matrix Optimization for Holevo Bound Enhancement

Hong Niu, Chau Yuen, Alexei Ashikhmin +1 more

Quantum communication holds the potential to revolutionize information transmission by enabling secure data exchange that exceeds the limits of classical systems. One of the key performance metrics in quantum information theory, namely the Holevo bound, quantifies the amount of classical information that can be transmitted reliably over a quantum channel. However, computing and optimizing the Holevo bound remains a challenging task due to its dependence on both the quantum input ensemble and the quantum channel. In order to maximize the Holevo bound, we propose a unified projected gradient ascent algorithm to optimize the quantum channel given a fixed input ensemble. We provide a detailed complexity analysis for the proposed algorithm. Simulation results demonstrate that the proposed quantum channel optimization yields higher Holevo bounds than input ensemble optimization.

quant-pharXiv:2602.17065•International Conference on Communications•Feb 20, 2026•0 citations
Quantum measurements and channels determine how information is extracted, encoded, and transmitted in quantum protocols. Optimizing their performance often requires numerical methods that remain practical as Hilbert space dimensions increase. The Reimpell-Werner iteration offers a practical approach to these tasks through repeated matrix updates that respect the constraints. Here, we generalize this iteration to linear objectives with arbitrary Hermitian cost matrices. We prove that the iterates converge to a global optimum whenever the initialization satisfies suitable support overlap conditions. For each fixed problem, choice of iteration parameters, and admissible initialization, O(1/ε)\mathcal{O}(1/\varepsilon)O(1/ε) iterations suffice asymptotically to bring the objective value within ε\varepsilonε of the optimum. These results provide a rigorous foundation for the iteration and broaden the class of optimization problems to which its convergence guarantees apply.
The paper addresses global convergence of the Reimpell–Werner (RW) iteration for channel optimization and the Ježek–Řeháček–Fiurášek (JRF) iteration for measurement optimization. It generalizes RW to the SDP max⁡X⪰0{tr⁡(CX):tr⁡AX⪯D}\max_{X\succeq0}\{\operatorname{tr}(CX):\operatorname{tr}_A X\preceq D\}maxX⪰0​{tr(CX):trA​X⪯D} for arbitrary Hermitian CCC and PSD DDD. A slack matrix and a common spectral shift make the augmented cost positive semidefinite without changing the optimization problem.
Under explicit initial-support conditions, satisfied by positive-definite seeds, every update is well defined and the matrix iterates converge to a global optimum. The limiting normalizer yields the unique dual optimizer of the support-reduced, normalized problem. Specializations establish convergence of the original RW iteration and of JRF for arbitrary finite mixed-state ensembles under the stated support conditions. The proof combines polar normalization on a Stiefel manifold, a Łojasiewicz gradient inequality, and a spectral argument establishing limiting dual feasibility and closing the duality gap.
For each fixed instance, shift, and admissible seed, objective accuracy ε\varepsilonε requires asymptotically O(1/ε)O(1/\varepsilon)O(1/ε) iterations; a computable dual certificate requires O(1/ε2)O(1/\varepsilon^2)O(1/ε2). Half-gradient-exponent cases have logarithmic bounds. Explicit slow families have objective iteration exponents approaching one and unbounded matrix-error exponents as dimension grows.
The bounds have instance-dependent constants and onset, so they do not establish complexity as dimension varies. Runtime comparisons exclude reference-bound construction and iterative certificate evaluation. Extension to general linear constraints remains open because the normalization exploits partial-trace structure; optimal shift and initialization choices are also unresolved.
Quantum optimization algorithms hold the promise of solving classically hard, discrete optimization problems in practice. The requirement of encoding such problems in a Hamiltonian realized with a finite (and currently small) number of qubits, however, poses the risk of finding only the optimum within the restricted space supported by this Hamiltonian. We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.
Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of O(poly(d))O(poly(d))O(poly(d)) for the ddd-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in O(poly(logd))O(poly(logd))O(poly(logd)). Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.
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.
Optimal signaling for secrecy rate maximization in Gaussian MIMO wiretap channels is considered. While this channel has attracted a significant attention recently and a number of results have been obtained, including the proof of the optimality of Gaussian signalling, an optimal transmit covariance matrix is known for some special cases only and the general case remains an open problem. An iterative custom-made algorithm to find a globally-optimal transmit covariance matrix in the general case is developed in this paper, with guaranteed convergence to a global optimum. While the original optimization problem is not convex and hence difficult to solve, its minimax reformulation can be solved via the convex optimization tools, which is exploited here. The proposed algorithm is based on the barrier method extended to deal with a minimax problem at hand. Its convergence to a global optimum is proved for the general case (degraded or not) and a bound for the optimality gap is given for each step of the barrier method. The performance of the algorithm is demonstrated via numerical examples. In particular, 20 to 40 Newton steps are already sufficient to solve the sufficient optimality conditions with very high precision (up to the machine precision level), even for large systems. Even fewer steps are required if the secrecy capacity is the only quantity of interest. The algorithm can be significantly simplified for the degraded channel case and can also be adopted to include the per-antenna power constraints (instead or in addition to the total power constraint). It also solves the dual problem of minimizing the total power subject to the secrecy rate constraint.
Quantum communication holds the potential to revolutionize information transmission by enabling secure data exchange that exceeds the limits of classical systems. One of the key performance metrics in quantum information theory, namely the Holevo bound, quantifies the amount of classical information that can be transmitted reliably over a quantum channel. However, computing and optimizing the Holevo bound remains a challenging task due to its dependence on both the quantum input ensemble and the quantum channel. In order to maximize the Holevo bound, we propose a unified projected gradient ascent algorithm to optimize the quantum channel given a fixed input ensemble. We provide a detailed complexity analysis for the proposed algorithm. Simulation results demonstrate that the proposed quantum channel optimization yields higher Holevo bounds than input ensemble optimization.