Epsilon-nets, unitary designs and random quantum circuits

Michał\ Oszmaniec, Adam Sawicki, Michał\ Horodecki

Published 2020-07-21Version 1

Epsilon-nets and approximate unitary $t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. The former constitute subsets of unitary channels that are epsilon-close to any unitary channel. The latter are ensembles of unitaries that (approximately) recover Haar averages of polynomials in entries of unitary channels up to order $t$. In this work we establish quantitative connections between these two seemingly different notions. Specifically, we prove that, for a fixed dimension $d$ of the Hilbert space, unitaries constituting $\delta$-approximate $t$-expanders form $\epsilon$-nets in the set of unitary channels for $t\simeq\frac{d^{5/2}}{\epsilon}$ and $\delta\simeq(\epsilon/C)^{\frac{d^2}{2}}$, where $C$ is a numerical constant. Conversely, we show that $\epsilon$-nets with respect to this metric can be used to construct $\delta$-approximate unitary $t$-expanders for $\delta\simeq\epsilon t$. We further apply our findings in conjunction with the recent results of [Varju, 2013] in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in [Brandao-Harrow-Horodecki, 2016]. Importantly, our gate sets need not to be symmetric (i.e. contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider a problem of compilation of quantum gates and prove a non-constructive version of the Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.