PIRSA:21120007

Quantum Algorithms for Classical Sampling Problems

Wild, D. (2021). Quantum Algorithms for Classical Sampling Problems . Perimeter Institute. https://pirsa.org/21120007

Wild, Dominik. Quantum Algorithms for Classical Sampling Problems . Perimeter Institute, Dec. 01, 2021, https://pirsa.org/21120007 

          @misc{ pirsa_PIRSA:21120007,
            doi = {10.48660/21120007},
            url = {https://pirsa.org/21120007},
            author = {Wild, Dominik},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum Algorithms for Classical Sampling Problems },
            publisher = {Perimeter Institute},
            year = {2021},
            month = {dec},
            note = {PIRSA:21120007 see, \url{https://pirsa.org}}
          }

Dominik Wild

Max Planck Institute of Quantum Optics

Talk number
PIRSA:21120007
Collection
Talk Type
Subject
Abstract

Sampling from classical probability distributions is an important task with applications in a wide range of fields, including computational science, statistical physics, and machine learning. In this seminar, I will present a general strategy of solving sampling problems on a quantum computer. The entire probability distribution is encoded in a quantum state such that a measurement of the state yields an unbiased sample. I will discuss the complexity of preparing such states in the context of several toy models, where a polynomial quantum speedup is achieved. The speedup can be understood in terms of the properties of classical and quantum phase transitions, which establishes a connection between computational complexity and phases of matter. To conclude, I will comment on the prospects of applying this approach to challenging, real-world tasks.