Quantum-inspired matrix arithmetic framework for
dequantizing quantum machine learning
Dr. Nai Hui Chia
Monday, April 10, 2023, from 12:30–1:30 pm
3301 Exploratory Hall
Fairfax Campus, George Mason University
In this talk, we will discuss 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]. In particular, we will first see classical algorithms for Singular Value Transformation (SVT) that run in time independent of input dimension under suitable quantum-inspired sampling assumptions that can be realized by low-overhead data structures. Our result for SVT is motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén, Su, Low, and Wiebe [STOC’19]. Then, since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, this result, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. Finally, we will discuss applications of this framework, such as recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, semidefinite program solving, low-rank Hamiltonian simulation, and discriminant analysis.
This talk is based on the joint work (link) with Andras Gylian, Tongyang Li, Han-Hsuan Lin, Chunhao
Wang, and Ewin Tang. The work has been published in STOC 2020 and the Journal of ACM.