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• 1 citation
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•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

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

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•1 citation

Riemannian optimization methods for ground states of multicomponent Bose–Einstein condensates

Robert Altmann, Martin Hermann, Daniel Peterseim +1 more

Abstract This paper addresses the computation of ground states of multicomponent Bose–Einstein condensates, defined as the global minimizer of an energy functional on an infinite-dimensional generalised oblique manifold. We establish the existence of the ground state, prove its uniqueness up to scaling and characterize it as the solution to a coupled nonlinear eigenvector problem. By equipping the manifold with several Riemannian metrics, we introduce a suite of Riemannian gradient descent and Riemannian Newton methods. Metrics that incorporate first- or second-order information about the energy are particularly advantageous, effectively preconditioning the resulting methods. For a Riemannian gradient descent method with an energy-adaptive metric, we provide a qualitative global and quantitative local convergence analysis, confirming its reliability and robustness with respect to the choice of the spatial discretization. Numerical experiments highlight the computational efficiency of both the Riemannian gradient descent and Newton methods.

IMA Journal of Numerical Analysis•Apr 17, 2025•1 citation
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.
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.
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 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.
Abstract This paper addresses the computation of ground states of multicomponent Bose–Einstein condensates, defined as the global minimizer of an energy functional on an infinite-dimensional generalised oblique manifold. We establish the existence of the ground state, prove its uniqueness up to scaling and characterize it as the solution to a coupled nonlinear eigenvector problem. By equipping the manifold with several Riemannian metrics, we introduce a suite of Riemannian gradient descent and Riemannian Newton methods. Metrics that incorporate first- or second-order information about the energy are particularly advantageous, effectively preconditioning the resulting methods. For a Riemannian gradient descent method with an energy-adaptive metric, we provide a qualitative global and quantitative local convergence analysis, confirming its reliability and robustness with respect to the choice of the spatial discretization. Numerical experiments highlight the computational efficiency of both the Riemannian gradient descent and Newton methods.