- Home »
- "Quantum advantage with shallow circuits"

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

Collection/Series:

Event Type:

Seminar

Speaker(s):

Event Date:

Wednesday, April 19, 2017 - 13:00 to 14:30

Location:

Time Room

Room #:

294

©2012 Perimeter Institute for Theoretical Physics