Abstract

We construct -approximate unitary k-designs on n qubits in circuit depth O(log k log log nk/\epsilon). The depth is exponentially improved over all known results in all three parameters n,k,\epsilon. We further show that each dependence is optimal up to exponentially smaller factors. Our construction uses \tilde{O}(nk) ancilla qubits and O(nk) bits of randomness, which are also optimal up to log(nk) factors. An alternative construction achieves a smaller ancilla count \tilde{O}(n) with circuit depth O(k log log nk/\epsilon). To achieve these efficient unitary designs, we introduce a highly-structured random unitary ensemble that leverages long-range two-qubit gates and low-depth implementations of random classical hash functions. We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries. As an illustration of this framework's versatility, we provide a succinct alternative proof of the existence of pseudorandom unitaries.

Personal information

Laura is a third-year graduate student in physics at Caltech, and is supervised by John Preskill and Fernando Brandão. She is broadly interested in the intersection of quantum information and many-body physics, particularly problems related to the complexity of quantum dynamics.

Reference

https://arxiv.org/abs/2507.06216