Near-linear constructions of exact unitary 2-designs

Richard Cleve; Debbie Leung; Li Liu; Chunhao Wang

Near-linear constructions of exact unitary 2-designs

Richard Cleve, Debbie Leung, Li Liu, Chunhao Wang

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

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 Õ (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 language	English (US)
Pages (from-to)	721-756
Number of pages	36
Journal	Quantum Information and Computation
Volume	16
Issue number	9-10
State	Published - 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

Cite this

@article{30008808b57f4cb4b2bbfd86b5b5dcce,

title = "Near-linear constructions of exact unitary 2-designs",

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

author = "Richard Cleve and Debbie Leung and Li Liu and Chunhao Wang",

note = "Publisher Copyright: {\textcopyright} Rinton Press.",

year = "2016",

language = "English (US)",

volume = "16",

pages = "721--756",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Sciendo",

number = "9-10",

}

TY - JOUR

T1 - Near-linear constructions of exact unitary 2-designs

AU - Cleve, Richard

AU - Leung, Debbie

AU - Liu, Li

AU - Wang, Chunhao

N1 - Publisher Copyright: © Rinton Press.

PY - 2016

Y1 - 2016

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

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

UR - http://www.scopus.com/inward/record.url?scp=84975260929&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975260929&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84975260929

SN - 1533-7146

VL - 16

SP - 721

EP - 756

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 9-10

ER -

Near-linear constructions of exact unitary 2-designs

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this