SPEAKER: Associate Professor François Le Gall
AFFILIATION: Nagoya University, Japan
TITLE: Average-Case Quantum Advantage with Shallow Circuits
SESSION CHAIR: Dr. Yuval Sanders, Macquarie University, Australia
ABSTRACT: In 2018, Bravyi, Gosset and König proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this talk I will describe similar separations that give even stronger evidence of the superiority of small-depth quantum computation. The first part of the talk will describe the average-case separation from ArXiv:1810.12792, which constructs a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a “shallow” quantum circuit) and shows that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. The second part of the talk will discuss further recent developments.
