  Recently Bravyi, Gosset and K\"onig (Science 2018) proved an unconditional
separation between the computational powers of small-depth quantum and
classical circuits for a relation. In this paper we show a similar separation
in the average-case setting that gives stronger evidence of the superiority of
small-depth quantum computation: we construct 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 show that any classical circuit with
bounded-fanin gates solving this problem on a non-negligible fraction of the
inputs must have logarithmic depth. Our results are obtained by introducing a
technique to create quantum states exhibiting global quantum correlations from
any graph, via a construction that we call the \emph{extended graph}.
  Similar results have been very recently (and independently) obtained by
Coudron, Stark and Vidick (arXiv:1810.04233), and Bene Watts, Kothari,
Schaeffer and Tal (STOC 2019).
