CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20160607-113319489

[img] PDF - Published Version
See Usage Policy.

207Kb
[img] PDF - Supplemental Material
See Usage Policy.

151Kb
[img] PDF - Submitted Version
See Usage Policy.

289Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160607-113319489

Abstract

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
http://dx.doi.org/10.1103/PhysRevLett.116.170502DOIArticle
http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.116.170502PublisherArticle
https://arxiv.org/abs/1605.00713arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)UNSPECIFIED
Ministry of Education (Singapore)UNSPECIFIED
National Research Foundation (Singapore)UNSPECIFIED
NSFCCF-1111382
NSFCCF-1452616
Army Research Office (ARO)W911NF-12-1-0486
European UnionUNSPECIFIED
Ministerstwo Nauki i Szkolnictwa Wyższego (MNiSW)N N202 231937
National Centre for Research and Development (Poland)UNSPECIFIED
Record Number:CaltechAUTHORS:20160607-113319489
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160607-113319489
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
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:07 Jun 2016 21:46
Last Modified:30 Jul 2018 15:21

Repository Staff Only: item control page