Random Unitaries in Extremely Low Depth | Quantum Colloquium

We address a fundamental question in quantum computation and many-body physics: Can short-time quantum dynamics generate unitaries that are indistinguishable from truly random exponentially complex unitaries? Two notions of indistinguishability widely studied in the literature are approximate unitary designs, which cannot be distinguished by any algorithm making a bounded number of queries, and pseudorandom unitaries (PRUs), which remain indistinguishable even under polynomial-time quantum algorithms.

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. Similarly, we construct PRUs in 1D circuits in polylog(n) depth, and in all-to-all-connected circuits in log log(n) depth. In all three cases, the depth scaling is optimal and improves exponentially over known results. These shallow quantum circuits, despite creating only short-range entanglement and having low complexity, are indistinguishable from unitaries of exponential complexity.

Our results have broad implications: (1) we prove that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, (2) we demonstrate a superpolynomial quantum advantage in learning low-complexity physical systems, (3) we establish that causal structure (lightcone) is unlearnable without time-reversal capability, and (4) we prove quantum hardness for recognizing phases of matter with topological order.

Joint work with Thomas Schuster and Jonas Haferkamp (https://arxiv.org/abs/2407.07754).

Panel Discussion: Jeongwan Haah (Stanford), Tony Metger (ETH Zurich), and Ryan O'Donnel (CMU). Moderated by Umesh Vazirani (Simons Institute, UC Berkeley).