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
Additional details
- Eprint ID
- 67725
- Resolver ID
- CaltechAUTHORS:20160607-113319489
- Swiss National Science Foundation (SNSF)
- Ministry of Education (Singapore)
- National Research Foundation (Singapore)
- CCF-1111382
- NSF
- CCF-1452616
- NSF
- W911NF-12-1-0486
- Army Research Office (ARO)
- European Union
- N N202 231937
- Ministerstwo Nauki i Szkolnictwa Wyższego (MNiSW)
- National Centre for Research and Development (Poland)
- Created
-
2016-06-07Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field