Środowiskowe Seminarium z Informacji i Technologii Kwantowych

Epsilon-nets and approximate unitary t-designs are natural notions that capture properties of general unitary operations relevant for numerous applications in quantum information and quantum computing. The former constitute subsets of unitary channels that are epsilon-close to every target 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. We 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 any from set of universal two-qudit gates in the parallel and sequential local architectures considered by [Brandao-Harrow-Horodecki, 2016]. Importantly, we do not require that the gate set is symmetric (i.e. contains gates together with their inverses) and consists of gates having algebraic entries. Second, we consider a problem of compilation of quantum gates and prove a non-constructive version of Solovay-Kitaev theorem for general universal gate sets.