  Unitary $t$-designs are the bread and butter of quantum information theory
and beyond. An important issue in practice is that of efficiently constructing
good approximations of such unitary $t$-designs. Building on results by Aubrun
(Comm. Math. Phys. 2009), we prove that sampling $d^t\mathrm{poly}(t,\log d,
1/\epsilon)$ unitaries from an exact $t$-design provides with positive
probability an $\epsilon$-approximate $t$-design, if the error is measured in
one-to-one norm distance of the corresponding $t$-twirling channels. As an
application, we give a partially derandomized construction of a quantum
encryption scheme that has roughly the same key size and security as the
quantum one-time pad, but possesses the additional property of being
non-malleable against adversaries without quantum side information.

Quantum Physics;Cryptography and Security;Functional Analysis;Probability