Random unitaries in extremely low depth

Abstract

Random unitaries form the backbone of numerous components of quantum technologies, and serve as indispensable toy models for complex processes in quantum many-body physics. In all of these applications, a crucial consideration is in what circuit depth a random unitary can be generated. I will present recent work, in which we show that local quantum circuits can form random unitaries in exponentially lower circuit depths than previously thought. We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over n qubits in log n depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in poly log n depth, and in all-to-all-connected circuits in poly log log n depth. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.