[2019-12-13] Dr. Nai-Hui Chia, UT Austin, "The capabilities and limits of quantum algorithms"

Poster:Post date:2019-11-28
Title: The capabilities and limits of quantum algorithms
Date: 2019-12-13 3:40pm-5:00pm
Location: R102, CSIE
Speaker: Dr. Nai-Hui Chia, UT Austin
Hosted by: Prof. Hsuan-Tien Lin


Quantum computing has notable impacts on computer science in recent years. While quantum computers are about to achieve so-called "quantum supremacy" (i.e., solving some classically-intractable computational tasks), it is the right time to understand the capabilities and limits of near-term and general quantum computers.
In this talk, I will address the following two questions: 1) what quantum resources are needed for general quantum algorithms? 2) What problems in machine learning and data analysis can have quantum speedups, and what are the limits? We will first see that a general quantum computer is indeed more powerful than a hybrid classical-quantum computer that only has limited quantum circuit depth relative to an oracle. Then, I will show polylog(n) classical algorithms for problems thought to have had exponential quantum speedups with input/output formats analogous to existing quantum algorithms, including SVM, low-rank linear system, recommendation system, and more. This implies that existing quantum machine learning algorithms have not achieved exponential speedups. Finally, I will discuss polynomial quantum speedups for fundamental problems in data analysis and their limits under plausible assumptions in complexity theory.
 I am a postdoctoral fellow at UT Austin working under the supervision of Dr.Scott Aaronson. Before that, I received my Ph.D. in computer science and engineering at Penn State University, where I was fortunate to have Dr. Sean Hallgren as my advisor. My research interests include quantum algorithms, complexity, and quantum cryptography.
Last modification time:2019-11-29 AM 9:32

cron web_use_log