Quantum Computing Seminar: Quantum-inspired matrix arithmetic framework for dequantizing quantum machine learning

Speaker: Nai-Hui Chia, Rice University

Title: Quantum-inspired matrix arithmetic framework for dequantizing quantum machine learning 

Abstract:  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. 

Time:  Monday, April 10, 2023, 12:30pm – 1:30pm

Place:  Exploratory Hall, room 3301

Zoom and In-person

Flyer