Analyzing Prospects for Quantum Advantage in Topological Data Analysis
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909109810364416 |
|---|---|
| author | Berry, Dominic W. Su, Yuan Gyurik, Casper King, Robbie Basso, Joao Barba, Alexander Del Toro Rajput, Abhishek Wiebe, Nathan Dunjko, Vedran Babbush, Ryan |
| author_facet | Berry, Dominic W. Su, Yuan Gyurik, Casper King, Robbie Basso, Joao Barba, Alexander Del Toro Rajput, Abhishek Wiebe, Nathan Dunjko, Vedran Babbush, Ryan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_13581 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Analyzing Prospects for Quantum Advantage in Topological Data Analysis Berry, Dominic W. Su, Yuan Gyurik, Casper King, Robbie Basso, Joao Barba, Alexander Del Toro Rajput, Abhishek Wiebe, Nathan Dunjko, Vedran Babbush, Ryan Quantum Physics 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. |
| title | Analyzing Prospects for Quantum Advantage in Topological Data Analysis |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2209.13581 |