Quantum Algorithm for Estimating Intrinsic Geometry

• URL: http://arxiv.org/abs/2508.06355v1
• Date: Fri, 08 Aug 2025 14:36:59 GMT
• Title: Quantum Algorithm for Estimating Intrinsic Geometry
• Authors: Nhat A. Nghiem, Tuan K. Do, Tzu-Chieh Wei, Trung V. Phan,
• Abstract summary: 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.
• Score: 0.09999629695552192
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: High-dimensional datasets typically cluster around lower-dimensional manifolds but are also often marred by severe noise, obscuring the intrinsic geometry essential for downstream learning tasks. We present a quantum algorithm for estimating the intrinsic geometry of a point cloud -- specifically its local intrinsic dimension and local scalar curvature. These quantities are crucial for dimensionality reduction, feature extraction, and anomaly detection -- tasks that are central to a wide range of data-driven and data-assisted applications. In this work, we propose a quantum algorithm which takes a dataset with pairwise geometric distance, output the estimation of local dimension and curvature at a given point. We demonstrate that this quantum algorithm achieves an exponential speedup over its classical counterpart, and, as a corollary, further extend our main technique to diffusion maps, yielding exponential improvements even over existing quantum algorithms. Our work marks another step toward efficient quantum applications in geometrical data analysis, moving beyond topological summaries toward precise geometric inference and opening a novel, scalable path to quantum-enhanced manifold learning.

Related papers

• Quantum Algorithm for Estimating Ollivier-Ricci Curvature [1.5823330232573694]
  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.
  arXiv  Detail & Related papers  (2025-12-10T16:54:02Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  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)
• qLUE: A Quantum Clustering Algorithm for Multi- Dimensional Datasets [0.6597195879147555]
  qLUE is a quantum clustering algorithm that scales linearly in both the number of points and their density. We show that qLUE is a promising route to handle complex data analysis tasks.
  arXiv  Detail & Related papers  (2024-06-29T08:10:09Z)
• Quantum Algorithm for Computing Distances Between Subspaces [0.0]
  We provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance. Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.
  arXiv  Detail & Related papers  (2023-08-29T16:46:20Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. We propose a quantum approach to defining Betti kernels, which is based on constructing Betti curves with increasing order.
  arXiv  Detail & Related papers  (2023-07-14T14:48:52Z)
• 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)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Quantum-enhanced algorithms for classical target detection in complex environments [0.0]
  Quantum computational approaches to some classic target identification and localization algorithms, especially for radar images, are investigated. Algorithm is inspired by recent approaches to quantum machine learning, but requires significant extensions. Application regimes where quantum efficiencies could enable significant overall algorithm speedup are identified.
  arXiv  Detail & Related papers  (2020-07-29T21:07:31Z)
• Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
  We review and extend the application of deep learning to quantum geometric control problems. We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems. Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
  arXiv  Detail & Related papers  (2020-06-19T19:12:14Z)

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.