26 January 2021
from 14:30 to 16:00
MCQST Colloquium | Aram Harrow - Associate Professor of Physics, Center for Theoretical Physics, MIT
Address / Location
The MCQST Colloquium Series features interdisciplinary talks given by visiting international speakers. The monthly colloquial covers topics spanning all MCQST research units and will be broadcasted live, being made available to audiences worldwide. The main goal of the series is to create the framework for idea exchange, to strengthen links with QST leading groups worldwide, as well as to act as an integral part of the local educational environment.
On 26 January 2021, we are excited to invite you to attend the colloquium offered by Aram Harrow, Associate Professor of Physics at the Center for Theoretical Physics at MIT.
Phase transitions in the complexity of simulating random shallow quantum circuits
The appeal of quantum computing is based on the fact that simulating N quantum systems on a classical computer takes time exponential in N. This exponential hardness is known to hold even for shallow quantum circuits, meaning unitary dynamics that run for a constant amount of time. We show that when the quantum circuits are made of random gates on a 2D geometry, they are not always exponentially hard to simulate. Instead, we give evidence for a phase transition in computational difficulty as the depth and local dimension are varied. Our evidence consists of (1) fast classical simulations of random circuits on a 400x400 grid of qubits, (2) a mapping to the order/disorder transition in an associated stat mech model, and (3) a proof that some circuit families are easy to simulate approximately but hard to simulate exactly. Our algorithms are based on tensor network contraction and mapping the 2D random unitary circuit to a 1D process consisting of alternating rounds of random local unitaries and weak measurements.
This is based on https://arxiv.org/abs/2001.00021 which is joint work with John Napp, Rolando La Placa, Alexander Dalzell, and Fernando Brandao.
The MCQST Colloquium takes place online via zoom.
If you would like to get more information about future talks you can alternatively also sign up to one of the following mailing lists:
You can register here for the mailing lists:
If you already receive mails from [wiss-mpq], there is no need to register to [Mpq-colloquium-stream].