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.03762

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

A. Afham

cs.LGmath.OCquant-phSubmitted Sep 3, 2026• Announced Sep 4, 2026
arXivHTMLPDF

Abstract

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - κ^{-3/2})$, where $κ$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($κ^{3/2}$ versus $κ^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[α, β]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : αI \leq S \leq βI\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

Comments
33 Pages, 3 figures. Comments welcome!

Related papers

Quantum State Tomography via Nonconvex Riemannian Gradient Descent

Ming-Chien Hsu, En-Jui Kuo, Wei-Hsuan Yu +2 more

The recovery of an unknown density matrix of large size requires huge computational resources. State-of-the-art performance has recently been achieved with the factored gradient descent (FGD) algorithm and its variants since they are able to mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite the theoretical guarantee of a linear convergence rate, convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number κ of the ground truth state. Consequently, the total number of iterations needed to achieve the estimation error ϵ can be as large as O(sqrt[κ]ln(1/ϵ)). In this Letter, we derive a quantum state tomography scheme that improves the dependence on κ to the logarithmic scale. Thus, our algorithm can achieve the approximation error ϵ in O(ln(1/κϵ)) steps. The improvement comes from the application of nonconvex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by the numerical results.

arXiv:2210.04717•Physical Review Letters•Jun 13, 2024•13 citations

Riemannian gradient descent-based quantum algorithms for ground state preparation with guarantees

Mahum Pervez, Ariq Haqq, Nathan A. McMahon +1 more

We investigate Riemannian gradient flows for preparing ground states of a desired Hamiltonian on a quantum device. We show that the number of steps of the corresponding Riemannian gradient descent (RGD) algorithm that prepares a ground state to a given precision depends on the structure of the Hamiltonian. Specifically, we develop an upper bound for the number of RGD steps that depends on the spectral gap of the Hamiltonian, the overlap between ground and initial state, and the target precision. In numerical experiments we study examples where we observe for a 1D Ising chain with nearest-neighbor interactions that the RGD steps needed to prepare a ground state scales linearly with the number of spins. For all-to-all couplings a quadratic scaling is obtained. To achieve efficient implementations while keeping convergence guarantees, we develop RGD approximations by randomly projecting the Riemannian gradient into polynomial-sized subspaces. We find that the speed of convergence of the randomly projected RGD critically depends on the size of the subspace the gradient is projected into. Finally, we develop efficient quantum device implementations based on Trotterization and a quantum stochastic drift-inspired protocol. We implement the resulting quantum algorithms on IBM's quantum devices and provide data for small-scale problems.

quant-pharXiv:2512.13401•Dec 16, 2025•0 citations

Riemannian gradient descent for Hartree-Fock theory

Evgueni Dinvay

We present a Riemannian optimization framework for Hartree-Fock theory formulated directly in the Sobolev space $H^1$. The orthonormality constraints are interpreted geometrically via infinite-dimensional Stiefel and Grassmann manifolds endowed with the embedded $H^1$ metric. Explicit expressions for Euclidean and Riemannian gradients, tangent-space projections, and retractions are derived using resolvent operators, avoiding distributional formulations. The resulting algorithms include Riemannian steepest descent and a preconditioned nonlinear conjugate gradient method equipped with Armijo backtracking and Powell-type restarts. Particular attention is given to physically motivated preconditioning based on inversion of the kinetic energy operator. The framework is naturally compatible with adaptive multiwavelet discretizations, where Coulomb-type convolutions can be evaluated efficiently. Numerical experiments demonstrate robust convergence and competitive performance compared to conventional SCF-DIIS schemes. In addition, for small molecules the gradient descent method converges from random initial guesses. The proposed formulation provides a geometrically consistent and discretization-independent perspective on electronic structure optimization and offers a foundation for further developments in infinite-dimensional Riemannian methods for quantum chemistry.

quant-pharXiv:2603.15870•Mar 18, 2026

Randomized Gradient Descents on Riemannian Manifolds: Almost Sure Convergence to Global Minima in and beyond Quantum Optimization

Emanuel Malvetti, Christian Arenz, Gunther Dirr +1 more

We analyze convergence of gradient-descent methods on Riemannian manifolds. In particular, we study randomization of Riemannian gradient algorithms for minimizing smooth cost functions (of Morse-Bott type). We prove that randomized gradient descent methods, where the Riemannian gradient is replaced by a random projection of it, converge to a single local optimum almost surely despite the existence of saddle points. We consider both uniformly distributed and discrete random projections. We also discuss the time required to pass a saddle point. As a major application, we consider ground-state preparation through quantum optimization over the unitary group. In mathematical terms our randomized algorithm applied to the trace function $U \to \operatorname{tr}(AUρU^*)$ almost surely converges to its global minimum. The minimum corresponds to the smallest eigenvalue (ground state) of the selfadjoint operator $A$ (Hamiltonian) if $ρ$ is a rank-one projector (pure state). In this setting, one can efficiently replace the uniform random projections by implementing so-called discrete unitary 2-designs.

arXiv:2405.12039•May 20, 2024•1 citation

Quantum gradient descent and Newton’s method for constrained polynomial optimization

Rebentrost, Frank Patrick, Seth Lloyd

Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.

•Jul 1, 2019•127 citations

Projected Inverse Iteration: An Eigenvalue Approach to Ground-State Computation with Neural Quantum States

Hang Zhang, Victor Armegioiu, Juan Carrasquilla +4 more

Deep learning offers a powerful approach to quantum many-body problems via neural network wavefunctions, but their optimization remains a severe bottleneck. Existing optimization methods, including natural gradient descent and stochastic reconfiguration, suffer from spectral gap-dependent convergence that limits their effectiveness on systems fraught with competing orders and nearly degenerate ground states, such as frustrated magnets and strongly correlated electron materials. Here, we introduce Projected Inverse Iteration (PII) by re-framing the ground-state search as an eigenvalue problem. PII achieves rapid, gap-insensitive convergence while preserving the favorable polynomial computational scaling of stochastic reconfiguration. Demonstrated on challenging two-dimensional spin systems, including the highly frustrated $J_1$-$J_2$ model, PII outperforms standard optimization techniques and presents a promising algorithmic strategy for discovering complex quantum states in the presence of small spectral gaps. More broadly, PII can be interpreted as a novel natural gradient method tailored for eigenvalue problems, opening up its application to related challenges within deep learning.

quant-pharXiv:2606.07825•Jun 9, 2026•0 citations
The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, (1−κ−3/2)(1 - κ^{-3/2})(1−κ−3/2), where κκκ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee (κ3/2κ^{3/2}κ3/2 versus κ5/2κ^{5/2}κ5/2 iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval [α,β][α, β][α,β] is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set {S:αI≤S≤βI}\{S : αI \leq S \leq βI\}{S:αI≤S≤βI} -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.
The recovery of an unknown density matrix of large size requires huge computational resources. State-of-the-art performance has recently been achieved with the factored gradient descent (FGD) algorithm and its variants since they are able to mitigate the dimensionality barrier by utilizing some of the underlying structures of the density matrix. Despite the theoretical guarantee of a linear convergence rate, convergence in practical scenarios is still slow because the contracting factor of the FGD algorithms depends on the condition number κ of the ground truth state. Consequently, the total number of iterations needed to achieve the estimation error ϵ can be as large as O(sqrt[κ]ln(1/ϵ)). In this Letter, we derive a quantum state tomography scheme that improves the dependence on κ to the logarithmic scale. Thus, our algorithm can achieve the approximation error ϵ in O(ln(1/κϵ)) steps. The improvement comes from the application of nonconvex Riemannian gradient descent (RGD). The contracting factor in our approach is thus a universal constant that is independent of the given state. Our theoretical results of extremely fast convergence and nearly optimal error bounds are corroborated by the numerical results.
We investigate Riemannian gradient flows for preparing ground states of a desired Hamiltonian on a quantum device. We show that the number of steps of the corresponding Riemannian gradient descent (RGD) algorithm that prepares a ground state to a given precision depends on the structure of the Hamiltonian. Specifically, we develop an upper bound for the number of RGD steps that depends on the spectral gap of the Hamiltonian, the overlap between ground and initial state, and the target precision. In numerical experiments we study examples where we observe for a 1D Ising chain with nearest-neighbor interactions that the RGD steps needed to prepare a ground state scales linearly with the number of spins. For all-to-all couplings a quadratic scaling is obtained. To achieve efficient implementations while keeping convergence guarantees, we develop RGD approximations by randomly projecting the Riemannian gradient into polynomial-sized subspaces. We find that the speed of convergence of the randomly projected RGD critically depends on the size of the subspace the gradient is projected into. Finally, we develop efficient quantum device implementations based on Trotterization and a quantum stochastic drift-inspired protocol. We implement the resulting quantum algorithms on IBM's quantum devices and provide data for small-scale problems.
We present a Riemannian optimization framework for Hartree-Fock theory formulated directly in the Sobolev space H1H^1H1. The orthonormality constraints are interpreted geometrically via infinite-dimensional Stiefel and Grassmann manifolds endowed with the embedded H1H^1H1 metric. Explicit expressions for Euclidean and Riemannian gradients, tangent-space projections, and retractions are derived using resolvent operators, avoiding distributional formulations. The resulting algorithms include Riemannian steepest descent and a preconditioned nonlinear conjugate gradient method equipped with Armijo backtracking and Powell-type restarts. Particular attention is given to physically motivated preconditioning based on inversion of the kinetic energy operator. The framework is naturally compatible with adaptive multiwavelet discretizations, where Coulomb-type convolutions can be evaluated efficiently. Numerical experiments demonstrate robust convergence and competitive performance compared to conventional SCF-DIIS schemes. In addition, for small molecules the gradient descent method converges from random initial guesses. The proposed formulation provides a geometrically consistent and discretization-independent perspective on electronic structure optimization and offers a foundation for further developments in infinite-dimensional Riemannian methods for quantum chemistry.
We analyze convergence of gradient-descent methods on Riemannian manifolds. In particular, we study randomization of Riemannian gradient algorithms for minimizing smooth cost functions (of Morse-Bott type). We prove that randomized gradient descent methods, where the Riemannian gradient is replaced by a random projection of it, converge to a single local optimum almost surely despite the existence of saddle points. We consider both uniformly distributed and discrete random projections. We also discuss the time required to pass a saddle point. As a major application, we consider ground-state preparation through quantum optimization over the unitary group. In mathematical terms our randomized algorithm applied to the trace function U→tr⁡(AUρU∗)U \to \operatorname{tr}(AUρU^*)U→tr(AUρU∗) almost surely converges to its global minimum. The minimum corresponds to the smallest eigenvalue (ground state) of the selfadjoint operator AAA (Hamiltonian) if ρρρ is a rank-one projector (pure state). In this setting, one can efficiently replace the uniform random projections by implementing so-called discrete unitary 2-designs.
Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Deep learning offers a powerful approach to quantum many-body problems via neural network wavefunctions, but their optimization remains a severe bottleneck. Existing optimization methods, including natural gradient descent and stochastic reconfiguration, suffer from spectral gap-dependent convergence that limits their effectiveness on systems fraught with competing orders and nearly degenerate ground states, such as frustrated magnets and strongly correlated electron materials. Here, we introduce Projected Inverse Iteration (PII) by re-framing the ground-state search as an eigenvalue problem. PII achieves rapid, gap-insensitive convergence while preserving the favorable polynomial computational scaling of stochastic reconfiguration. Demonstrated on challenging two-dimensional spin systems, including the highly frustrated J1J_1J1​-J2J_2J2​ model, PII outperforms standard optimization techniques and presents a promising algorithmic strategy for discovering complex quantum states in the presence of small spectral gaps. More broadly, PII can be interpreted as a novel natural gradient method tailored for eigenvalue problems, opening up its application to related challenges within deep learning.