Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 29, 2016 | Supplemental Material + Submitted + Published
Journal Article Open

Efficient Quantum Pseudorandomness

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.

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.

Attached Files

Published - PhysRevLett.116.170502.pdf

Submitted - 1605.00713

Supplemental Material - supplementary.pdf

Files

PhysRevLett.116.170502.pdf
Files (664.7 kB)
Name Size Download all
md5:9cb2aa91c100f010a736813bac1f9c99
296.5 kB Download
md5:b4807201faca29984efb8cd46d176175
212.8 kB Preview Download
md5:8e2ec7da9f0a1e506b852b2b1bc0530a
155.3 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 18, 2023