EUVIMEDEUVIMED entdecken
Crossref

Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang

Journal of the ACM · 31.10.2022 · 69 (5) · 1-72

DOI: 10.1145/3549524 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 27.10.2022. Verfasst von Nai-Hui Chia und 5 weiteren Autor:innen. Die Arbeit wurde bisher 39-mal zitiert (Crossref) und nennt 83 Literaturangaben. Gefördert von: Scott Aaronson’s Vannevar Bush Faculty Fellowship from the US Department of Defense, Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, Institute for Quantum Information and Matter, an NSF Physics Frontiers Center.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ 2 -norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

Förderung

  • Scott Aaronson’s Vannevar Bush Faculty Fellowship from the US Department of Defense
  • Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”
  • Institute for Quantum Information and Matter, an NSF Physics Frontiers Center
  • EU’s Horizon 2020 Marie Skłodowska-Curie program
  • IBM PhD Fellowship, QISE-NET Triplet Award
  • U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program
  • National Science Foundation Graduate Research Fellowship Program

Zitieren

APA

Chia, N., Gilyén, A. P., Li, T., Lin, H., Tang, E., & Wang, C. (2022). Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning. Journal of the ACM, 69(5), 1-72. https://doi.org/10.1145/3549524

Vancouver

Chia N, Gilyén AP, Li T, Lin H, Tang E, Wang C. Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning. Journal of the ACM. 2022;69(5):1-72. doi:10.1145/3549524

BibTeX
@article{Chia2022,
  author = {Chia, Nai-Hui and Gilyén, András Pal and Li, Tongyang and Lin, Han-Hsuan and Tang, Ewin and Wang, Chunhao},
  title = {Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning},
  journal = {Journal of the ACM},
  year = {2022},
  volume = {69},
  number = {5},
  pages = {1--72},
  doi = {10.1145/3549524}
}
Kostenlos starten →