PIRSA:17040021

"Quantum advantage with shallow circuits"

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

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

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

David Gosset Institute for Quantum Computing (IQC)

DOI 10.48660/17040021
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).