Efficient Quantum Pseudorandomness

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 ce...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2016-04, Vol.116 (17), p.170502-170502, Article 170502
Main Authors: Brandão, Fernando G S L, Harrow, Aram W, Horodecki, Michał
Format: Article
Language:English
Subjects:
Circuits
Construction
Cryptography
Design engineering
Dynamics
Evolution
Pseudorandom
Transformations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0031-9007
1079-7114
DOI:10.1103/PhysRevLett.116.170502