PIRSA:17040021

Video URL

https://pirsa.org/17040021

"Quantum advantage with shallow circuits"

Gosset, D. (2017). "Quantum advantage with shallow circuits". Perimeter Institute for Theoretical Physics. https://pirsa.org/17040021

Gosset, David. "Quantum advantage with shallow circuits". Perimeter Institute for Theoretical Physics, Apr. 19, 2017, https://pirsa.org/17040021 

          @misc{ scivideos_PIRSA:17040021,
            doi = {10.48660/17040021},
            url = {https://pirsa.org/17040021},
            author = {Gosset, David},
            keywords = {Other Physics},
            language = {en},
            title = {"Quantum advantage with shallow circuits"},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2017},
            month = {apr},
            note = {PIRSA:17040021 see, \url{https://scivideos.org/pirsa/17040021}}
          }

David Gosset Institute for Quantum Computing (IQC)

Talk numberPIRSA:17040021
DOI10.48660/17040021
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe an explicit (i.e., non-oracular) computational problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. This is joint work with Sergey Bravyi and Robert Koenig (arXiv:1704.00690).