Computer Science Theory Seminar

Nai-Hui ChiaUniversity of Texas at Austin
The Capabilities and Limits of Quantum Algorithms

Monday, March 16, 2020 - 3:45pm
Gates 122

Abstract: 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 the near-term and general 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 general quantum computers are indeed more powerful than near-term quantum computers. Then, I will show our polylog(n)-time classical algorithms for problems thought to have had exponential quantum speedups, including SVM, low-rank linear system, low-rank SDP, and more. Our algorithms are asymptotically as good as quantum ones and thus 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.