Speaker
Description
What computational problems can be solved efficiently with quantum computers, but not with classical computers? One of the most well understood examples of a problem that exhibits such a quantum computational advantage is sampling from quantum circuits. Based on a growing body of theoretical evidence, the problem of sampling from deep, random quantum circuits is now believed to be classically intractable, yet implementable with today's 'NISQ' hardware. However, much less is known about sampling problems beyond the particular regime of deep random circuits. In this talk, I will explore the boundaries of computational advantage in circuit sampling in different regimes, focusing on shallow circuits and the effects of noise. I will describe a sharp transition that occurs as a function of the circuit depth, which separates a classically simulable phase from a putatively complex, non-simulable phase. I will present a precise, statistical description of the quantum states generated by these circuits in the shallow, non-simulable regime, which both accounts for the hardness of classical simulations, and also predicts a dramatic susceptibility to noise. Based on this structural characterisation of shallow circuit sampling, I will argue that even a very small noise rate - scaling with the system size n as log(n)/n - renders the output distribution classically simulable. This highlights the extreme sensitivity of circuit sampling problems to noise, and sheds light on the complexity of simulating quantum many-body dynamics more generally.