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.
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.
The D-Wave quantum computer is designed to solve a specific class of problems - The Quadratic Unconstrained Binary Optimization (QUBO) problem. One of the key processes in this pathway to the solution consists in embedding the problem graph into a hardware graph. It is a nontrivial task to determine whether a problem graph is minor embeddable in a hardware graph. One method that singles out cases where minor embeddability fails requires calculation of the tree-width of both the problem and the hardware graphs. The latter computation is known to be NP-Complete. In this paper, we propose a novel, fast approximation to tree-width based on the differential geometric concept of Ollivier-Ricci curvature. This latter runs in linear time and thus could significantly reduce the overall complexity of determining whether a QUBO problem is solvable on the D-Wave architecture.
Adiabatic Quantum Processes have been known to solve combinatorial optimization problems intractable by classical computational methods by exploiting the adiabatic theorem. The solution of the optimization problem is encoded in the ground state of a final Hamiltonian, which in turn can be targeted by adiabatically transitioning from the known ground state of an easy-to-prepare Hamiltonian to the ground state of the problem Hamiltonian. Our focus is to characterize topologically the minimum gap between the ground state and the first excited state, which is the bottleneck of the process in terms of its speed. Since the gap occurs at topologically steep ascent/descent of the ground/first excited states, it is proposed to utilize the curvature uniformization process of the Ricci flow to identify such gaps as areas of heavy curvature transport. Our results indicate that such gaps can be detected automatically in various Adiabatic Quantum Processes.
This manuscript explores the Riemannian geometry of quantum state manifolds and its physical implications. We establish that quantum state manifolds, as submanifolds of Hilbert space, possess intrinsic Riemannian geometry characterized by a metric tensor derived from the Hilbert space inner product. This geometric framework reveals fundamental connections: the distance between nearby states scales with quantum fluctuations, curvature indicates state robustness, and geometric phase transitions occur in many-body systems. We review historical developments from early quantum geometry to modern quantum information geometry, and present methodologies for computing geometric quantities and their physical interpretations. Results include distance-fluctuation relations for coherent states, curvature calculations for SU(2) manifolds, and applications to quantum optimization and metrology via the quantum Fisher information metric. The discussion interprets geometric quantities in terms of uncertainty principles, state robustness, and quantum criticality, while outlining future research directions in quantum chaos-geometry correlations, non-associative geometry, and geometric quantum algorithm design. We conclude that Riemannian geometry provides a powerful framework for understanding and exploiting the structure of quantum state space, with applications across quantum information processing, metrology, and foundational physics.
Non-convex optimization is an essential problem in the field of machine learning. Optimization methods for non-convex problems can be roughly di- vided into first-order methods and second-order methods, depending on the or- der of the derivative to the objective function they used. Generally, to find the local minima, the second-order methods are applied to find the effective direction to escape the saddle point. Specifically, finding the Negative Curvature is considered as the subroutine to analyze the characteristic of the saddle point. However, the calculation of the Negative Curvature is expensive, which prevents the practical usage of second-order algorithms. In this thesis, we present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove that our algorithm could produce the target state corresponding to the negative curvature direction with query complexity O ̃(polylog(d) ε^(-1)), where d is the dimension of the optimization function. The quantum negative curvature finding algorithm is exponentially faster than any known classical method, which takes time at least O(dε^(-1/2)). Moreover, we propose an efficient quantum algorithm to achieve the classical read-out of the target state. Our classical read-out algorithm runs exponentially faster on the degree of d than existing counterparts.
This paper proposes a novel theoretical framework based on discrete geometricflow and quantum state evolution to study topological phase transitions and theemergence of low-energy effective physics in quantum geometry. We construct discrete geometric dynamics on a three-dimensional periodic point cloud, driving edgelength evolution via the discrete Ricci flow equation, and attach a four-dimensionallocal Hilbert space to each edge, representing the quantum state of the system usingmatrix product states (MPS). Numerical simulations show that during the evolution of the discrete Ricci flow, the system undergoes a topological phase transitionat a specific curvature threshold, manifested as a jump in Betti numbers detectedby persistent homology. After the phase transition, the geometric mean curvature and the low-energy spectral gap of the quantum system synchronously entera plateau region, exhibiting a stable inverse relationship: ¯ ∆ = Λ/∥ ¯R∥+δ, whereΛ is an O(1) constant and δ is a small correction. This result, for the first timeat the numerical level, realizes a complete causal chain from pure geometric evolution to the generation of quantum low-energy parameters, providing a computableexample for the idea that ”geometric flow is renormalization group flow”.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.