+++ONLINE KOLLOQUIUM+++ Phase transitions in the complexity of simulating random shallow quantum circuits (MCQST-Kolloquium) (Prof. Aram Harrow)
- Date: Jan 26, 2021
- Time: 14:30
- Speaker: Prof. Aram Harrow
- Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge/Massachusetts, USA
- Location: +++ONLINE KOLLOQUIUM+++
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.