Analyzing Prospects for Quantum Advantage in Topological Data Analysis

Abstract

Lloyd et al. were first to demonstrate the promise of quantum algorithms for computing Betti numbers, a way to characterize topological features of data sets. Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that super-quadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for super-polynomial advantage. We then introduce and analyze specific problem examples which have parameters in the regime where super-polynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances.

54 pages, 7 figures. Added a number of theorems and lemmas to clarify findings and also a discussion in the main text and new appendix about variants of our problems with high Betti numbers that are challenging for recent classical algorithms

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Fixed-point quantum search with an optimal number of queries
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Fourier Analytic Approach to Phase Estimation
• A (simple) classical algorithm for estimating Betti numbers

Cited by in corpus (24)

• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Benchmarking quantum computers
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Clique Homology is QMA1-hard
• The topology of data hides in quantum thermal states
• Quantum topological data analysis via the estimation of the density of states
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Achieving the volume-law entropy regime with random-sign Dicke states
• Nonlinear Spectroscopy via Generalized Quantum Phase Estimation
• Efficient explicit circuit for quantum state preparation of piecewise continuous functions
• Optimal Coherent Quantum Phase Estimation via Tapering
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Quantum state preparation via piecewise QSVT
• Provable quantum speedups for computing persistence in topological data analysis
• Towards Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
• Vortex Detection from Quantum Data
• Quantum community detection via deterministic elimination
• Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
• Quantum phase estimation with optimal confidence interval using three control qubits
• Holey graphs: very large Betti numbers are testable