Local Random Quantum Circuits Form Approximate Designs

Watch a technical conference presentation from TQC 2024 exploring how local random quantum circuits (RQC) form approximate unitary designs on arbitrary connected graphs. Delve into mathematical proofs showing that RQCs with O(poly(n,k)) gates can form approximate unitary k-designs across various graph architectures. Learn about new methods for determining spectral gaps of Hamiltonians on arbitrary graphs, including an extension of the finite-size method for frustration-free Hamiltonians and a novel approach based on the Detectability Lemma. Discover how these findings demonstrate that RQCs on graphs with spanning trees of bounded degree and height form k-designs after O(|E|n poly(k)) gates, and for k ≤ 4, circuits on graphs of certain maximum degrees form designs after O(|E|n) gates. Understand the broader implications of these results for quantum computation, including the proof that RQCs on any connected architecture can form approximate designs in quasi-polynomial circuit size.