Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup

Understand

At its core a $t$-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics.

• We construct new families of quantum circuits on $n$-qubits giving rise to $\varepsilon$-approximate unitary $t$-designs efficiently in $O(n^3t^{12})$ depth.
• These quantum circuits are based on a relaxation of technical requirements in previous constructions.
• In particular, the construction of circuits which give efficient approximate $t$-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M.