Quantum Algorithm for Estimating Ollivier-Ricci Curvature

• URL: http://arxiv.org/abs/2512.09822v1
• Date: Wed, 10 Dec 2025 16:54:02 GMT
• Title: Quantum Algorithm for Estimating Ollivier-Ricci Curvature
• Authors: Nhat A. Nghiem, Linh Nguyen, Tuan K. Do, Tzu-Chieh Wei, Trung V. Phan,
• Abstract summary: 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.<n>This curvature has seen applications ranging from signaling fragility in financial networks to serving as basic quantities in quantum gravity.
• Score: 1.5823330232573694
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Optimizing two-dimensional isometric tensor networks with quantum computers [0.5437050212139087]
  We propose a hybrid quantum-classical algorithm for approximating the ground state of two-dimensional quantum systems.<n>Inspired by the density matrix renormalization group, we optimize tensors sequentially by diagonalizing a series of effective Hamiltonians.<n>We demonstrate our method on the two-dimensional (2D) transverse-field Ising model, achieving ground-state optimization on up to 25 qubits with modest quantum overhead.
  arXiv  Detail & Related papers  (2025-11-17T19:00:03Z)
• Quantum Orthogonal Separable Physics-Informed Neural Networks [0.0]
  This paper introduces Quantum Orthogonal Separable Physics-Informed Neural Networks (QO-SPINNs), a novel architecture for solving Partial Differential Equations.<n>We leverage a quantum algorithm for accelerating matrix multiplication within each layer, achieving a $mathcal O(dlog d/2)$ complexity.<n>We provide a robust and efficient framework for uncertainty quantification (UQ) which, to our knowledge, is the first UQ method specifically designed for Separable PINNs.
  arXiv  Detail & Related papers  (2025-11-16T14:15:19Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Quantum Algorithm for Estimating Intrinsic Geometry [0.09999629695552192]
  We present a quantum algorithm for estimating the intrinsic geometry of a point cloud.<n>These quantities are crucial for dimensionality reduction, feature extraction, and anomaly detection.<n>Our work marks another step toward efficient quantum applications in geometrical data analysis.
  arXiv  Detail & Related papers  (2025-08-08T14:36:59Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Natural Stochastic Pairwise Coordinate Descent [13.986982036653632]
  Variational quantum algorithms, optimized using gradient-based methods, often exhibit sub-optimal convergence performance.<n>Quantum natural gradient descent (QNGD) is a more efficient method that incorporates the geometry of the state space via a quantum information metric.<n>We formulate a novel quantum information metric and construct an unbiased estimator for this metric using single-shot measurements.
  arXiv  Detail & Related papers  (2024-07-18T18:57:29Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning [52.77024349608834]
  Building a quantum analog of classical deep neural networks represents a fundamental challenge in quantum computing. Key issue is how to address the inherent non-linearity of classical deep learning. We introduce the Quantum Path Kernel, a formulation of quantum machine learning capable of replicating those aspects of deep machine learning.
  arXiv  Detail & Related papers  (2022-12-22T16:06:24Z)
• Towards a Quantum Simulation of Nonlinear Sigma Models with a Topological Term [0.0]
  We show that the quantum theory is massless in the strong-coupling regime. We also highlight the limitations of current quantum algorithms, designed for noisy intermediate-scale quantum devices.
  arXiv  Detail & Related papers  (2022-10-07T16:35:03Z)
• Optimization in quantum metrology and entanglement theory using semidefinite programming [0.0]
  We discuss efficient methods to optimize the metrological performance over local Hamiltonians in a bipartite quantum system.<n>We present the quantum Fisher information in a bilinear form and maximize it by an iterative see-saw (ISS) method.<n>We consider a number of other problems in quantum information theory that can be solved in a similar manner.
  arXiv  Detail & Related papers  (2022-06-06T18:01:03Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• The Hintons in your Neural Network: a Quantum Field Theory View of Deep Learning [84.33745072274942]
  We show how to represent linear and non-linear layers as unitary quantum gates, and interpret the fundamental excitations of the quantum model as particles. On top of opening a new perspective and techniques for studying neural networks, the quantum formulation is well suited for optical quantum computing.
  arXiv  Detail & Related papers  (2021-03-08T17:24:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.