Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 68, Issue 2, Pages 989-1015Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3128110
Keywords
Unitary designs; epsilon nets; random quantum circuits; compilation of quantum gates; unitary channels
Funding
- TEAM-NET Project [POIR.04.04.00-00-17C1/18-00]
- Foundation for Polish Science through the IRAP Project - EU within the Smart Growth Operational Programme [2018/MAB/5]
- National Science Centre, Poland, under Grant SONATA BIS [2015/18/E/ST1/00200]
Ask authors/readers for more resources
In this work, quantitative connections between epsilon-nets and approximate unitary t-designs are studied, revealing their relationship in d-dimensional Hilbert space and their applications in quantum computing. The results show near optimality and the potential for new construction methods in quantum computing.
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. In this work we study quantitative connections between these two notions. Specifically, we prove that, for d dimensional Hilbert space, unitaries constituting delta-approximate t-expanders form epsilon-nets for t similar or equal to d(5/2)/epsilon and delta similar or equal to (epsilon(3/2)/d)(d2). We also show that for arbitrary t, epsilon-nets can be used to construct delta-approximate unitary t-designs for delta similar or equal to epsilon t, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary t design necessary to obtain an epsilon-net must grow at least as fast as 1/epsilon (for fixed dimension) and not slower than d(2) (for fixed epsilon). This shows near optimality of our result connecting t-designs and epsilon-nets. We apply our findings 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 et al., 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 compilation of quantum gates and prove a non-constructive 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available