Department Colloquia

The Physics Department Colloquia are held on Tuesdays at 4 p.m. in Abelson 333 and on Zoom unless otherwise noted. To request a Zoom link, please email jthorne@brandeis.edu.

Spring 2022

Phase Transitions in the Complexity of Simulating Random Shallow Quantum Circuits

January 18, 2022

Aram Harrow, MIT

Host: Aram Apyan

Abstract: 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.
TBD

January 25, 2022

Tyler Maunu, Brandeis University

Host: Aram Apyan

TBD

February 1, 2022

JiJi Fan, Brown University

Host: Aram Apyan

February 15, 2022

Baylor Fox-Kember, Brown University

Host: Aram Apyan

TBD

March 22, 2022

Matthew Lister, Purdue University

Host: Aram Apyan