2015/01/31 by Richard Cleve, Debbie Leung, Li Liu +1 · 2 citations
Physics and Astronomy · #quant-ph
published as Quantum Information and Computation, Vol. 16, No. 9 & 10 (2016) 0721-0756 · 30 pages, 10 figures, presentation improved
arxiv created 2016/06/28 · arxiv updated 2017/01/03
A unitary 2-design can be viewed as a quantum analogue of a 2-universal hash function: it is indistinguishable from a truly random unitary by any procedure that queries it twice. We show that exact unitary 2-designs on n qubits can be implemented by quantum circuits consisting of ~O(n) elementary gates in logarithmic depth. This is essentially a quadratic improvement in size (and in width times depth) over all previous implementations that are exact or approximate (for sufficiently strong approximations).