Quantum Algorithm for Estimating Ollivier-Ricci Curvature

2025/12/10 by Nhat A. Nghiem, Nghiem, Nhat A., Linh Nguyen +7
Computer Science · Mathematics · Physics and Astronomy · #FOS: Physical sciences #Geometric Analysis and Curvature Flows #Noncommutative and Quantum Gravity Theories #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2512.09822

openalex publication_date 2025/12/10 · openalex created_date 2025/12/12 · openalex updated_date 2026/08/01

Abstract

We introduce a quantum algorithm for computing the Ollivier Ricci curvature, a discrete analogue of the Ricci curvature defined via optimal transport on graphs and general metric spaces. This curvature has seen applications ranging from signaling fragility in financial networks to serving as basic quantities in combinatorial quantum gravity. For inputs given as a point cloud with pairwise distances, we show that our algorithm can achieve an exponential speedup over the best-known classical methods for two particular classes of problem. Our work is another step toward quantum algorithms for geometrical problems that are capable of delivering practical value while also informing fundamental theory.

Citations

• Quantum Algorithm for Estimating Intrinsic Geometry
• New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
• CurvGAD: Leveraging Curvature for Enhanced Graph Anomaly Detection
• Quantum computing and persistence in topological data analysis
• Recovering Manifold Structure Using Ollivier-Ricci Curvature
• Improved Quantum Power Method and Numerical Integration Using Quantum Singular Value Transformation
• On the Ollivier-Ricci curvature as fragility indicator of the stock markets
• Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• An Intrinsic Approach to Scalar-Curvature Estimation for Point Clouds
• Quantum state preparation without coherent arithmetic
• Verifying the Union of Manifolds Hypothesis for Image Data
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• Improved quantum algorithms for linear and nonlinear differential equations
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Network geometry and market instability
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Testing the Manifold Hypothesis
• Quantum algorithms for supervised and unsupervised machine learning
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of Markov chains on metric spaces
• Simulating physics with computers
• A fast quantum mechanical algorithm for database search
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum theory, the Church–Turing principle and the universal quantum computer

Related

• Quantum Curvature as Key to the Quantum Universe
• Ricci curvature of quantum channels on non-commutative transportation metric spaces
• Quantum Algorithm for Estimating Intrinsic Geometry
• The geometry of quantum computation
• Quantum Algorithm for Computing Distances Between Subspaces