Analyzing Prospects for Quantum Advantage in Topological Data Analysis

PRX Quantum, vol. 5

Abstract

Lloyd [Nat. Commun. , 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. Published by the American Physical Society 2024

Authors 10

1. Dominic W. Berry

   Macquarie University

   Affiliation as printed

   School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, Australia

2. Yuan Su

   Google (United States)

   Affiliation as printed

   Google Quantum AI, Venice, California 90291, USA

3. Casper Gyurik Aachen applied Quantum algorithms (aQa)

   Leiden University

   Affiliation as printed

   applied Quantum algorithms (aQa), Leiden University, Leiden 2300 RA, Netherlands

4. Robbie King

   California Institute of Technology · Google (United States)

   Affiliation as printed

   Department of Computing and Mathematical Sciences, Caltech, Pasadena, California 91125, USA

   Google Quantum AI, Venice, California 90291, USA

5. Joao Basso

   Google (United States)

   Affiliation as printed

   Google Quantum AI, Venice, California 90291, USA

6. Alexander Del Toro Barba

   Google (United States)

   Affiliation as printed

   Google Quantum AI, Venice, California 90291, USA

7. Abhishek Rajput

   University of Toronto

   Affiliation as printed

   Department of Computer Science, University of Toronto, Ontario M5S 2E4, Canada

8. Nathan Wiebe

   Pacific Northwest National Laboratory · University of Toronto

   Affiliation as printed

   Department of Computer Science, University of Toronto, Ontario M5S 2E4, Canada

   Pacific Northwest National Laboratory, Richland, Washington 99354, USA

9. Vedran Dunjko Aachen applied Quantum algorithms (aQa)

   Leiden University

   Affiliation as printed

   applied Quantum algorithms (aQa), Leiden University, Leiden 2300 RA, Netherlands

10. Ryan Babbush

    Google (United States)

    Affiliation as printed

    Google Quantum AI, Venice, California 90291, USA