Get to know your Duncan Hall neighbors! Join Rice CS for coffee & a series of talks on algorithms & machine learning at Rice.
Coffee & Food for Thought: Algorithms & ML
Duncan Hall Room 3092
Presenter: Nai-Hui Chia, Rice CS Assistant Professor
Title: Quantum-inspired matrix arithmetic framework for dequantizing quantum machine learning
Wed, Jan 25, 2023, 2-3pm
Duncan Hall 3092
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 realised 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 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.
Bio: Nai-Hui Chia is an Assistant Professor in the Department of Computer Science at Rice University. Before that, he was an Assistant Professor in the Luddy School of Informatics, Computing, and Engineering at Indiana University Bloomington from 2021 to 2022, a Hartree Postdoctoral Fellow in the Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland from 2020 to 2021, supervised by Dr Andrew Childs, and a Postdoctoral Fellow at UT Austin from 2018 to 2020, working under the supervision of Dr. Scott Aaronson. he received his PhD in Computer Science and Engineering at Penn State University, where he was fortunate to have Dr Sean Hallgren as his advisor.
Feb 1, 2023
Associate Professor, Rice CS
Feb 8, 2023
Associate Professor, Computational Applied Mathematics and Operations Research
Feb 15, 2023
Rice CS PhD Student
Feb 22, 2023
Rice CS PhD Student
Mar 1, 2023
ECE PhD student
Mar 8, 2023
CS PhD student
Jan 18, 2023: Jingfeng Wu, A Fine-Grained Characterization for the Implicit Regularization of SGD in Least Square Problems
Jan 11, 2023, Thamar Solorio, Data Augmentation in Sequence Labelling Tasks
Jan 4, 2023: Samson Zhou, Theoretical Foundations of Modern Data Science
Nov 30, 2022: Sebastian Perez-Salazar, IID Prophet Inequalities with Limited Flexibility
Nov 16, 2022: Anshumali Shrivastava, Probabilistic Hash Functions and Hash Tables: A New Paradigm for Efficient AI Training and Inference
Nov 2, 2022: César A. Uribe, Hyperfast Second-Order Local Solvers for Efficient Statistically Preconditioned Distributed Optimization
Oct 26, 2022: Xia (Ben) Hu, Towards Effective & Efficient Interpretation of Deep Neural Networks: Algorithms & Applications
Oct 19, 2022: Vaibhav Unhelkar, Enabling Humans and Robots to Predict the Other’s Behavior from Small Datasets
Oct 12, 2022: Arlei Silva, Link Prediction with Autocovariance