Phase Transitions in the Complexity of Simulating Random Shallow Quantum Circuits

Explore the complexity of simulating random shallow quantum circuits in this 32-minute conference talk by Aram Harrow from the Massachusetts Institute of Technology. Delve into the phase transitions in computational difficulty as depth and local dimension vary in 2D quantum circuits with random gates. Learn about fast classical simulations on large qubit grids, mappings to statistical mechanics models, and proofs of simulation complexity. Discover tensor network contraction techniques and the mapping of 2D random unitary circuits to 1D processes. Gain insights into approximate simulations, algorithm effectiveness, and open questions in the field of quantum computing simulation.

Intro
quantum computers
How hard is it to simulate a quantum computer?
the simulation frontier
easier quantum simulation
quantum circuits
noisy dynamics?
random circuit sampling
tensor contraction in 1-D
simulating 2-D circuits
effective 1-D dynamics
cheaper tensor contraction
Approximate simulation
Does the algorithm work?
Open questions