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:2405.12039

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

Emanuel Malvetti, Christian Arenz, Gunther Dirr, Thomas Schulte‐Herbrüggen

Published May 20, 2024• 13 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2405.12039

Related papers

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•5 citations

Regularization of Riemannian optimization: Application to process tomography and quantum machine learning

Felix Soest, Konstantin Beyer, Walter T. Strunz

Gradient descent algorithms on Riemannian manifolds have recently been proposed as a practical tool for optimizing quantum channels. We add rank-penalizing regularization terms to the cost functions of these methods (in the spirit of Lasso), driving the optimization towards channels with as few Kraus operators as possible. For quantum process tomography of rank-deficient channels, regularization both accelerates convergence and improves the fidelity of the solution compared to the unregularized case. For quantum classification tasks, it reduces the channel rank while maintaining classification accuracy, thereby revealing the minimum rank required by the given input data.

arXiv:2404.19659•Apr 30, 2024•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

Quantum Simulation on Riemannian Manifolds

Dylan Herman, Jacob Watkins, Guneykan Ozgul +4 more

We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and $\ell_p$ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.

quant-pharXiv:2610.03673•Oct 5, 2026•0 citations

GRADIENT FLOWS FOR OPTIMIZATION IN QUANTUM INFORMATION AND QUANTUM DYNAMICS: FOUNDATIONS AND APPLICATIONS

THOMAS SCHULTE-HERBRÜGGEN, Steffen J. Glaser, Gunther Dirr +1 more

Many challenges in quantum information and quantum control root in constrained optimization problems on finite-dimensional quantum systems. The constraints often arise from two facts: (i) quantum dynamic state spaces are naturally smooth manifolds (orbits of the respective initial states) rather than being Hilbert spaces; (ii) the dynamics of the respective quantum system may be restricted to a proper subset of the entire state space. Mathematically, either case can be treated by constrained optimization over the reachable set of an underlying control system. Thus, whenever the reachable set takes the form a smooth manifold, Riemannian optimization methods apply. Here, we give a comprehensive account on the foundations of gradient flows on Riemannian manifolds including new applications in quantum information and quantum dynamics. Yet, we do not pursue the problem of designing explicit controls for the underlying control systems. The framework is sufficiently general for setting up gradient flows on (sub)manifolds, Lie (sub)groups, and (reductive) homogeneous spaces. Relevant convergence conditions are discussed, in particular for gradient flows on compact and analytic manifolds. This is meant to serve as foundation for new achievements and further research. Illustrative examples and new applications are given: we extend former results on unitary groups to closed subgroups with tensor-product structure, where the finest product partitioning relates to SUloc(2n) := SU(2) ⊗ ⋯ ⊗ SU(2) — known as (qubit-wise) local unitary operations. Such applications include, e.g., optimizing figures of merit on SUloc(2n) relating to distance measures of pure-state entanglement as well as to best rank-1 approximations of higher-order tensors. In quantum information, our gradient flows provide a numerically favorable alternative to standard tensor-SVD techniques.

arXiv:0802.4195•Reviews in Mathematical Physics•Jul 1, 2010•54 citations

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Ankit Garg, Robin Kothari, Praneeth Netrapalli +1 more

We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function $f:\mathbb{R}^n \to \mathbb{R}$ and its (sub)gradient. Our goal is to find an $ε$-approximate minimum of $f$ starting from a point that is distance at most $R$ from the true minimum. If $f$ is $G$-Lipschitz, then the classic gradient descent algorithm solves this problem with $O((GR/ε)^{2})$ queries. Importantly, the number of queries is independent of the dimension $n$ and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension $n$. In this paper we reprove the randomized lower bound of $Ω((GR/ε)^{2})$ using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using $O(GR/ε)$ quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need $Ω((GR/ε)^2)$ queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.

arXiv:2010.01801•Leibniz international proceedings in informatics•Oct 5, 2020•17 citations
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.
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.
Gradient descent algorithms on Riemannian manifolds have recently been proposed as a practical tool for optimizing quantum channels. We add rank-penalizing regularization terms to the cost functions of these methods (in the spirit of Lasso), driving the optimization towards channels with as few Kraus operators as possible. For quantum process tomography of rank-deficient channels, regularization both accelerates convergence and improves the fidelity of the solution compared to the unregularized case. For quantum classification tasks, it reduces the channel rank while maintaining classification accuracy, thereby revealing the minimum rank required by the given input data.
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 investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and ℓp\ell_pℓp​ balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.
Many challenges in quantum information and quantum control root in constrained optimization problems on finite-dimensional quantum systems. The constraints often arise from two facts: (i) quantum dynamic state spaces are naturally smooth manifolds (orbits of the respective initial states) rather than being Hilbert spaces; (ii) the dynamics of the respective quantum system may be restricted to a proper subset of the entire state space. Mathematically, either case can be treated by constrained optimization over the reachable set of an underlying control system. Thus, whenever the reachable set takes the form a smooth manifold, Riemannian optimization methods apply. Here, we give a comprehensive account on the foundations of gradient flows on Riemannian manifolds including new applications in quantum information and quantum dynamics. Yet, we do not pursue the problem of designing explicit controls for the underlying control systems. The framework is sufficiently general for setting up gradient flows on (sub)manifolds, Lie (sub)groups, and (reductive) homogeneous spaces. Relevant convergence conditions are discussed, in particular for gradient flows on compact and analytic manifolds. This is meant to serve as foundation for new achievements and further research. Illustrative examples and new applications are given: we extend former results on unitary groups to closed subgroups with tensor-product structure, where the finest product partitioning relates to SUloc(2n) := SU(2) ⊗ ⋯ ⊗ SU(2) — known as (qubit-wise) local unitary operations. Such applications include, e.g., optimizing figures of merit on SUloc(2n) relating to distance measures of pure-state entanglement as well as to best rank-1 approximations of higher-order tensors. In quantum information, our gradient flows provide a numerically favorable alternative to standard tensor-SVD techniques.
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:Rn→Rf:\mathbb{R}^n \to \mathbb{R}f:Rn→R and its (sub)gradient. Our goal is to find an εεε-approximate minimum of fff starting from a point that is distance at most RRR from the true minimum. If fff is GGG-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)2)O((GR/ε)^{2})O((GR/ε)2) queries. Importantly, the number of queries is independent of the dimension nnn and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension nnn. In this paper we reprove the randomized lower bound of Ω((GR/ε)2)Ω((GR/ε)^{2})Ω((GR/ε)2) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε)O(GR/ε)O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)2)Ω((GR/ε)^2)Ω((GR/ε)2) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.