【基础沙龙】第36期-王春昊


主讲人:王春昊,博士,德州大学奥斯汀分校计算机系博士后研究员

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

时间:2020年1月14日星期二,10:00-11:00

地点:沙河校区通信楼725室

主讲人简介

王春昊,博士,现德州大学奥斯汀分校计算机系博士后研究员。2009年本科毕业于浙江大学计算机系,2011年硕士毕业于加拿大西门弗雷泽大学计算机系,2018年博士毕业于加拿大滑铁卢大学计算机系。王春昊博士长期从事计算机算法以及量子计算理论研究,目前致力于量子模拟,量子机器学习,量子优化算法,量子计算复杂度等方面的研究,现已有多篇论文被理论量子计算顶级会议QIP接收。

报告摘要

We present an algorithmic framework generalizing quantum-inspired polylogarithmic-time algorithms on low-rank matrices. Our work follows the line of research started by Tang's breakthrough classical algorithm for recommendation systems [STOC'19]. The main result of this work is an algorithm for singular value transformation on low-rank inputs in the quantum-inspired regime, where singular value transformation is a framework proposed by Gilyén et al. [STOC'19] to study various quantum speedups. Since singular value transformation encompasses a vast range of matrix arithmetic, this result, combined with simple sampling lemmas from previous work, suffices to generalize all results dequantizing quantum machine learning algorithms to the authors' knowledge. Via simple black-box applications of our singular value transformation framework, we recover the dequantization results on recommendation systems, principal component analysis, supervised clustering, low-rank matrix inversion, low-rank semidefinite programming, and support vector machines. We also give additional dequantizations results on low-rank Hamiltonian simulation and discriminant analysis.