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 man y cases pseudorandom operations can emulate c...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
American Physical Society (APS)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115397 https://orcid.org/0000-0003-3220-7682 |
| _version_ | 1826214824271413248 |
|---|---|
| author | Brandão, Fernando G. S. L. Horodecki, Michał Harrow, Aram W |
| author2 | Massachusetts Institute of Technology. Department of Physics |
| author_facet | Massachusetts Institute of Technology. Department of Physics Brandão, Fernando G. S. L. Horodecki, Michał Harrow, Aram W |
| author_sort | Brandão, Fernando G. S. L. |
| collection | MIT |
| description | 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 man y 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. |
| first_indexed | 2024-09-23T16:12:03Z |
| format | Article |
| id | mit-1721.1/115397 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:12:03Z |
| publishDate | 2018 |
| publisher | American Physical Society (APS) |
| record_format | dspace |
| spelling | mit-1721.1/1153972022-10-02T07:01:35Z Efficient Quantum Pseudorandomness Brandão, Fernando G. S. L. Horodecki, Michał Harrow, Aram W Massachusetts Institute of Technology. Department of Physics Harrow, Aram W 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 man y 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. National Science Foundation (U.S.) (Grant CCF1452616) National Science Foundation (U.S.) (Grant CCF-1111382) United States. Army Research Office (Contract W911NF-12-1-0486) 2018-05-16T15:16:49Z 2018-05-16T15:16:49Z 2016-04 2015-03 2018-05-08T13:46:10Z Article http://purl.org/eprint/type/JournalArticle 0031-9007 1079-7114 http://hdl.handle.net/1721.1/115397 Brandão, Fernando G. S. L., et al. “Efficient Quantum Pseudorandomness.” Physical Review Letters, vol. 116, no. 17, Apr. 2016. © 2016 American Physical Society https://orcid.org/0000-0003-3220-7682 http://dx.doi.org/10.1103/PHYSREVLETT.116.170502 Physical Review Letters Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf American Physical Society (APS) APS |
| spellingShingle | Brandão, Fernando G. S. L. Horodecki, Michał Harrow, Aram W Efficient Quantum Pseudorandomness |
| title | Efficient Quantum Pseudorandomness |
| title_full | Efficient Quantum Pseudorandomness |
| title_fullStr | Efficient Quantum Pseudorandomness |
| title_full_unstemmed | Efficient Quantum Pseudorandomness |
| title_short | Efficient Quantum Pseudorandomness |
| title_sort | efficient quantum pseudorandomness |
| url | http://hdl.handle.net/1721.1/115397 https://orcid.org/0000-0003-3220-7682 |
| work_keys_str_mv | AT brandaofernandogsl efficientquantumpseudorandomness AT horodeckimichał efficientquantumpseudorandomness AT harrowaramw efficientquantumpseudorandomness |