Weak approximate unitary designs and applications to quantum encryption
This work addresses the practical construction of approximate unitary designs for quantum information theory, with an incremental improvement in quantum encryption by adding non-malleability.
The paper tackles the problem of efficiently constructing approximate unitary t-designs, proving that sampling from an exact t-design yields an approximate design with a specified error bound. As an application, it provides a partially derandomized quantum encryption scheme with non-malleability against certain adversaries, matching the key size and security of the quantum one-time pad.
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/ε)$ unitaries from an exact $t$-design provides with positive probability an $ε$-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.