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 quantum computers. In this talk, I will address the following two questions: 1) What is the power of near-term quantum computers? 2) What speedup can general quantum computers achieve for problems in machine learning and data analysis? We will first see that a general quantum computer is strictly more powerful than small-depth quantum computers in the presence of classical computers. Then, I will show quantum-inspired classical algorithms for problems including SVM, low-rank linear system, low-rank SDP, and more. Our algorithms running in time polylog(n) are asymptotically as good as existing quantum ones. This result also implies that existing quantum machine learning algorithms have not achieved exponential quantum speedups. Finally, I will discuss polynomial quantum speedups for fundamental problems in data analysis and their limits under plausible assumptions in complexity theory.
Nai-Hui Chia is a postdoctoral researcher at the Department of Computer Science at the University of Texas at Austin under the supervision of Dr. Scott Aaronson since 2018. He obtained his Ph.D. from the Pennsylvania State University under the supervision of Dr. Sean Hallgren in 2018 and his B.S. from National Taiwan University in 2010. His research interests lie in quantum algorithms, complexity theory, and quantum cryptography.
Faculty Host: Michael Forbes