Dear quanta,
I am speaking tomorrow at Harvard on my recent paper with John, Rolando +
Caltech people on simulating 2D random circuits. Below is the announcement.
-aram
----
Hi All,
Here is the notice for the Mathematical Picture Language Seminar on
Tuesday, January 28 at 3:30 p.m.
I attach the flyer, and include the details below in case you don’t want to
access the attachment:
3:30 PM
Tuesday, January 28, 2020
Harvard University
Mathematical Picture Language Seminar
Jefferson 356
“Phase transitions in the complexity of simulating random shallow quantum
circuits”
Aram Harrow, MIT
*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.
This is based on
https://arxiv.org/abs/2001.00021
<https://urldefense.proofpoint.com/v2/url?u=https-3A__arxiv.org_abs_2001.00021&d=DwMFaQ&c=WO-RGvefibhHBZq3fL85hQ&r=nlqvXX6Jmbu52yOuosGBtKKs0OQ7eTClhH721mPk7Mc&m=kGIohRcNpDIpUlmt_9jyhIpX7x3_CYyIT4oro3EOmmw&s=rR9hIouMMGwBvXjKrW30QCHVDv7xmCYgSnoqKoAeGg8&e=>
which is joint work with John Napp, Rolando La Placa, Alexander Dalzell,
and Fernando Brandao.
Barbara Drauschke, assistant to A. Jaffe
617-495-2895
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip