##### Department of Mathematics,

University of California San Diego

****************************

### Quantum computing colloquium

## Nai-Hua Chia

#### UT Austin

## The Capabilities and Limits of Quantum Algorithms

##### 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 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.

Host: James McKernan

### March 19, 2020

### 11:00 AM

### https://ucsd.zoom.us/j/363302151

****************************