Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Average-Case Quantum Advantage with Shallow Circuits   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).

30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
36
The categories of this paper are: cmp-lg
19
The categories of this paper are: eess
4
The categories of this paper are: cond-mat
25
The categories of this paper are: patt-sol
15
The categories of this paper are: nucl-ex
2
The categories of this paper are: math
0
The categories of this paper are: hep-ph
35
The categories of this paper are: mtrl-th
5
The categories of this paper are: gr-qc
18
The categories of this paper are: econ
16
The categories of this paper are: stat
20
The categories of this paper are: acc-phys
26
The categories of this paper are: bayes-an