Near-linear constructions of exact unitary 2-designs

Richard Cleve, Debbie Leung, Li Liu, Chunhao Wang

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)721-756
Number of pages36
JournalQuantum Information and Computation
Issue number9-10
StatePublished - 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistical and Nonlinear Physics
  • Nuclear and High Energy Physics
  • Mathematical Physics
  • General Physics and Astronomy
  • Computational Theory and Mathematics


Dive into the research topics of 'Near-linear constructions of exact unitary 2-designs'. Together they form a unique fingerprint.

Cite this