EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Analyzing Prospects for Quantum Advantage in Topological Data Analysis

Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, Ryan Babbush

PRX Quantum · 06.02.2024 · 5 (1)

DOI: 10.1103/prxquantum.5.010319 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PRX Quantum, online erschienen am 06.02.2024. Verfasst von Dominic W. Berry und 9 weiteren Autor:innen. Die Arbeit wurde bisher 46-mal zitiert (Crossref) und nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Australian Research Council, US Department of Energy, Office of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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

Förderung

  • Australian Research Council
  • US Department of Energy
  • Office of Science
  • National Science Foundation

Zitieren

APA

Berry, D. W., Su, Y., Gyurik, C., King, R., Basso, J., Barba, A. D. T., Rajput, A., Wiebe, N., Dunjko, V., & Babbush, R. (2024). Analyzing Prospects for Quantum Advantage in Topological Data Analysis. PRX Quantum, 5(1). https://doi.org/10.1103/prxquantum.5.010319

Vancouver

Berry DW, Su Y, Gyurik C, King R, Basso J, Barba ADT, et al. Analyzing Prospects for Quantum Advantage in Topological Data Analysis. PRX Quantum. 2024;5(1). doi:10.1103/prxquantum.5.010319

BibTeX
@article{Berry2024,
  author = {Berry, Dominic W. and Su, Yuan and Gyurik, Casper and King, Robbie and Basso, Joao and Barba, Alexander Del Toro and Rajput, Abhishek and Wiebe, Nathan and Dunjko, Vedran and Babbush, Ryan},
  title = {Analyzing Prospects for Quantum Advantage in Topological Data Analysis},
  journal = {PRX Quantum},
  year = {2024},
  volume = {5},
  number = {1},
  doi = {10.1103/prxquantum.5.010319}
}
Kostenlos starten →