paper

Near-linear constructions of exact unitary 2-designs

arXiv:1501.04592

Abstract

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).

arXiv comment30 pages, 10 figures, presentation improved

References in corpus (15)

Cited by in corpus (9)