Pseudo-random quantum states and operations


Harrow, A. (2008). Pseudo-random quantum states and operations . Perimeter Institute. https://pirsa.org/08040049


Harrow, Aram. Pseudo-random quantum states and operations . Perimeter Institute, Apr. 28, 2008, https://pirsa.org/08040049


          @misc{ pirsa_08040049,
            doi = {10.48660/08040049},
            url = {https://pirsa.org/08040049},
            author = {Harrow, Aram},
            keywords = {Quantum Information},
            language = {en},
            title = {Pseudo-random quantum states and operations },
            publisher = {Perimeter Institute},
            year = {2008},
            month = {apr},
            note = {PIRSA:08040049 see, \url{https://pirsa.org}}

Aram Harrow Massachusetts Institute of Technology (MIT) - Department of Physics


The idea of pseudo-randomness is to use little or no randomness to simulate a random object such as a random number, permutation, graph, quantum state, etc... The simulation should then have some superficial resemblance to a truly random object; for example, the first few moments of a random variable should be nearly the same. This concept has been enormously useful in classical computer science. In my talk, I\'ll review some quantum analogues of pseudo-randomness: unitary k-designs, quantum expanders (and their new cousin, quantum tensor product expanders), extractors. I\'ll talk about relations between them, efficient constructions, and possible applications. Some of the material is joint work with Matt Hastings and Richard Low.