Quantum algorithm for estimating Olivier-Ricci curvature
Abstract
We introduce a quantum algorithm for computing the Ollivier-Ricci curvature, a discrete analog 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 problems. Our work is another step toward quantum algorithms for geometrical problems that are capable of delivering practical value while also informing fundamental theory.
Fields of Study & Subjects
Geometric Analysis and Curvature Flows
Noncommutative and Quantum Gravity Theories
Markov Chains and Monte Carlo Methods
Publication details
- Journal / source
- Physical Review Research
- Publisher
- American Physical Society (APS)
- Volume
- 8
- Issue
- 2
- Publication date
- 3 May 2026
- Language
- EN