PIRSA:17040021 Scientific Series Other

DOI10.48660/17040021

Series: Perimeter Institute Quantum Discussions

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}}
}

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).

Resources

Next talk

Related Talks