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.