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 Pal and Li, Tongyang and Lin, Han-Hsuan and Tang, Ewin and Wang, Chunhao (2022) Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning. Journal of the ACM, 69 (5). pp. 1-72. ISSN 0004-5411. doi:10.1145/3549524.

Full text is not posted in this repository. Consult Related URLs below.

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, 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: ℓ²-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:Article
Related URLs:
URLURL TypeDescription ItemConference Paper
Chia, Nai-Hui0000-0002-4138-7956
Gilyén, András Pal0000-0001-5992-5743
Li, Tongyang0000-0002-0338-413X
Lin, Han-Hsuan0000-0002-5126-0174
Tang, Ewin0000-0002-7451-9687
Wang, Chunhao0000-0002-9983-5774
Additional Information:Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang were supported by Scott Aaronson’s Vannevar Bush Faculty Fellowship from the US Department of Defense. AG was supported by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, and by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907), as well as by the EU’s Horizon 2020 Marie Skłodowska-Curie program 891889 QuantOrder. TL was supported by supported by IBM PhD Fellowship, QISE-NET Triplet Award (NSF grant 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 (NSF grant DGE-1762114). Ewin Tang thanks Craig Gidney for the reference to alias sampling. András Pal Gilyén 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.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Vannevar Bush Faculty FellowshipUNSPECIFIED
Samsung ElectronicsUNSPECIFIED
Marie Curie Fellowship891889
NSF Graduate Research FellowshipDGE-1762114
Department of Energy (DOE)UNSPECIFIED
Issue or Number:5
Record Number:CaltechAUTHORS:20221130-646241700.10
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118181
Deposited By: Research Services Depository
Deposited On:23 Dec 2022 19:44
Last Modified:23 Dec 2022 19:44

Repository Staff Only: item control page