Quantum Topological Data Analysis with Linear Depth and Exponential Speedup

Abstract

Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of $O(n^4/({\epsilon }^2\delta ))$ (where $n$ is the number of data points, $\epsilon$ is the error tolerance, and $\delta$ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of $O(n\log (1/(\delta \epsilon )))$. Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.

arXiv comment27 pages

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Supervised learning with quantum enhanced feature spaces
• Quantum machine learning in feature Hilbert spaces
• Fermionic quantum computation
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient Learning for Deep Quantum Neural Networks
• Toward the first quantum simulation with quantum speedup
• Statistical topological data analysis using persistence landscapes
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• The Clique Density Theorem
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Hodge Laplacians on graphs
• Fast estimation of approximate matrix ranks using spectral densities
• Term Grouping and Travelling Salesperson for Digital Quantum Simulation
• Review of a Quantum Algorithm for Betti Numbers
• Random simplicial complexes
• Spectral gaps of simplicial complexes without large missing faces
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Spectral gaps, missing faces and minimal degrees

Cited by in corpus (5)

• The Future of Quantum Computing with Superconducting Qubits
• Quantum algorithm for persistent Betti numbers and topological data analysis
• Topological data analysis and machine learning
• The topology of data hides in quantum thermal states
• Quantum-Enhanced Topological Data Analysis: A Peep from an Implementation Perspective