Efficient Quantum Pseudorandomness

Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki
Phys. Rev. Lett. 116, 170502 – Published 29 April 2016
PDFHTMLExport Citation

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.

  • Figure
  • Received 14 March 2015

DOI:https://doi.org/10.1103/PhysRevLett.116.170502

© 2016 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & TechnologyStatistical Physics & ThermodynamicsGeneral Physics

Authors & Affiliations

Fernando G. S. L. Brandão1,2, Aram W. Harrow3, and Michał Horodecki4

  • 1Quantum Architectures and Computation Group, Microsoft Research, Redmond 11728, Washington, USA
  • 2Department of Computer Science, University College London, London, WC1E 6BT, United Kingdom
  • 3Center for Theoretical Physics, MIT, Cambridge MA 02139, USA
  • 4National Quantum Information Center of Gdansk, 81-824 Sopot, Poland

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 116, Iss. 17 — 29 April 2016

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×