Random Quantum Circuits, Phase Transitions and Complexity - Aram Harrow

Explore the intricacies of random quantum circuits, phase transitions, and complexity in this 41-minute lecture by Aram Harrow at the Institute for Advanced Study. Delve into topics such as the complexity of random quantum circuits, random circuit sampling conjecture, and Haar-random unitaries. Examine the necessity of Haar randomness and investigate pseudo-random unitaries. Discover applications of designs and analyze 1-D random circuits depth T, as well as random circuits in higher dimensions. Study general geometries and the proof of D=1 result. Investigate low-depth circuits, tensor contraction in 1-D, and simulating 2-D circuits. Learn about cheaper tensor contraction and approximate simulation techniques. Evaluate the effectiveness of the algorithm and explore random tensor networks. Conclude with open questions in the field of quantum complexity.

Intro
Complexity of random quantum circuits
random circuit sampling Conjecture
This talk
Haar-random unitaries
Is Haar really necessary?
Pseudo-random unitaries
Applications of designs
1-d random circuits depth T
random circuits in D=2,3,...
General geometries
Proof of D=1 result
low-depth circuits
tensor contraction in 1-D
simulating 2-D circuits
cheaper tensor contraction
Approximate simulation
Does the algorithm work?
random tensor networks
Open questions