2025/07/08 by Laura Cui, Cui, Laura, Thomas Schuster +5 · 1 voice · 16 citations
#quant-ph #cs.CC #cs.IT #math-ph
paper · pdf · doi:10.48550/arxiv.2507.06216
We construct ε-approximate unitary k-designs on n qubits in circuit depth O(log k log log n k / ε). The depth is exponentially improved over all known results in all three parameters n, k, ε. We further show that each dependence is optimal up to exponentially smaller factors. Our construction uses O(nk) ancilla qubits and O(nk) bits of randomness, which are also optimal up to log(n k) factors. An alternative construction achieves a smaller ancilla count O(n) with circuit depth O(k log log nk/ε). 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.