A Caltech Library Service

Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

Chia, Nai-Hui and Gilyén, András and Li, Tongyang and Lin, Han-Hsuan and Tang, Ewin and Wang, Chunhao (2020) Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery , New York, NY, pp. 387-400. ISBN 9781450369794.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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, suffices to generalize all recent 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: ℓ²-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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. ET thanks Craig Gidney for the reference to alias sampling. AG is grateful to Saeed Mehraban for insightful suggestions about proving perturbation bounds on partition functions. Part of this work was done while visiting the Simons Institute for the Theory of Computing. We gratefully acknowledge the Institute’s hospitality. NHC, HHL, and CW were supported by Scott Aaronson’s Vannevar Bush Faculty Fellowship from the U.S. Department of Defense. AG acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”; additional support was provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). TL was supported by IBM PhD Fellowship, QISE-NET Triplet Award (NSF DMR-1747426), and the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program. ET was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1762114.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Vannevar Bush FellowshipUNSPECIFIED
Samsung ElectronicsUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Department of Energy (DOE)UNSPECIFIED
NSF Graduate Research FellowshipDGE-1762114
Subject Keywords:quantum machine learning, low-rank approximation, sampling, quantum-inspired algorithms, quantum machine learning, dequantization
Record Number:CaltechAUTHORS:20210226-083945792
Persistent URL:
Official Citation:Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. 2020. Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20), June 22–26, 2020, Chicago, IL, USA. ACM, New York, NY, USA, 14 pages.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108232
Deposited By: Tony Diaz
Deposited On:26 Feb 2021 17:01
Last Modified:26 Feb 2021 17:01

Repository Staff Only: item control page