Shallow circuits and the quantum-classical boundary

In the last few years there have been demonstrations of quantum advantage using noisy quantum circuits that are believed to go beyond the limits of the classical computers that exist today.  In this talk I will give an overview of a different type of quantum advantage that can be attained by shallow (short-depth) quantum circuits.  I will discuss recent results which establish unconditionally that constant-depth quantum circuits can solve certain linear algebra problems faster than their classical counterparts. We will see that the reason quantum computers solve these problems provably faster (as measured by circuit depth) than classical computers is due to a strong form of quantum nonlocality that is present in their input/output statistics. 

Zoom Link: https://pitp.zoom.us/j/96752851897?pwd=R29GWHovN0MwVXVYWklaNE1QZ1c5dz09