A Caltech Library Service

Efficient Quantum Pseudorandomness

Brandão, Fernando G. S. L. and Harrow, Aram W. and Horodecki, Michał (2016) Efficient Quantum Pseudorandomness. Physical Review Letters, 116 (17). Art. No. 170502. ISSN 0031-9007. doi:10.1103/PhysRevLett.116.170502.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions (“circuits”) are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:© 2016 American Physical Society. (Received 14 March 2015; published 29 April 2016) We would like to thank Dorit Aharonov, Itai Arad, Winton Brown, Daniel Jonathan, Bruno Nachtergaele, Alex Russell, Tomasz Szarek, and Andreas Winter. F. G. S. L. B. acknowledges support from the Swiss National Science Foundation, via the National Centre of Competence in Research QSIT, and the Ministry of Education and the National Research Foundation, Singapore. A. W. H. was funded by NSF Grants No. CCF-1111382 and No. CCF-1452616 and ARO Contract No. W911NF-12-1-0486. M. H. is supported by the EU QESSENCE grant, by Polish Ministry of Science and Higher Education Grant No. N N202 231937. M. H. also acknowledges the QUASAR grant of the National Centre for Research and Development of Poland for preparing the final version of the Letter. Part of this work was done in the National Quantum Information Center of Gdansk. We thank the Institute Mittag Leffler for its hospitality within the program “Quantum Information Science,” where (another) part of this work was done.
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)UNSPECIFIED
Ministry of Education (Singapore)UNSPECIFIED
National Research Foundation (Singapore)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0486
Ministerstwo Nauki i Szkolnictwa Wyższego (MNiSW)N N202 231937
National Centre for Research and Development (Poland)UNSPECIFIED
Issue or Number:17
Record Number:CaltechAUTHORS:20160607-113319489
Persistent URL:
Official Citation:Efficient Quantum Pseudorandomness Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki Phys. Rev. Lett. 116, 170502
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67725
Deposited By: George Porter
Deposited On:07 Jun 2016 21:46
Last Modified:11 Nov 2021 03:53

Repository Staff Only: item control page