Analyzing Prospects for Quantum Advantage in Topological Data Analysis
arXiv:2209.13581 · doi:10.1103/PRXQuantum.5.010319
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.
arXiv comment54 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 (24)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum principal component analysis
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Efficient quantum algorithms for simulating sparse Hamiltonians
- A Theory of Trotter Error
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Random Quantum Circuits are Approximate 2-designs
- Even more efficient quantum computations of chemistry through tensor hypercontraction
- Fixed-point quantum search with an optimal number of queries
- Random geometric complexes
- Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Simplicial complexes: spectrum, homology and random walks
- Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
- Towards quantum advantage via topological data analysis
- Quantum algorithm for persistent Betti numbers and topological data analysis
- Fourier Analytic Approach to Phase Estimation
- Finding Small and Large k-Clique Instances on a Quantum Computer
- 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