Abstract
Lloyd et al. [Nat. Commun. 7, 10138 (2016)] 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 superquadratic 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 superpolynomial advantage. We then introduce and analyze specific problem examples which have parameters in the regime where superpolynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances.
- Received 26 April 2023
- Revised 26 September 2023
- Accepted 22 December 2023
DOI:https://doi.org/10.1103/PRXQuantum.5.010319
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
It is a long-standing challenge to find practical applications where quantum computers can provide dramatic speedups over classical computing. A recently proposed application is in topological data analysis (TDA). This can be used for a wide variety of tasks, such as predicting financial crashes and analyzing neural networks, so has the potential to greatly expand the applicability of quantum computers. Moreover, it can be mapped to a Hamiltonian, making it a natural problem to solve on quantum computers. Prior work suggested a large speedup but did not give examples where that speedup could be achieved.
We develop more advanced techniques to provide better performance in nearly every step of quantum algorithms for TDA. This includes more advanced techniques for state preparation and amplitude estimation that can be applied more generally in other quantum algorithms. We determine the number of Toffoli gates needed for estimating computation time on fault-tolerant quantum computers. We then consider a particular class of graphs where there is a large speedup. For these graphs we estimate that TDA would be feasible on quantum computers but intractable with standard classical techniques. TDA therefore joins a small group of other applications (factoring and quantum chemistry) where this has been demonstrated.
This work raises interesting open questions for application to real-world data. The next step is to examine real-world examples to find cases where there is a large speedup.
