  We prove under the complexity theoretical assumption of the non-collapse of
the polynomial hierarchy that estimating the output probabilities of random
quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for
any classical computer, where $m$ is the number of gates in the quantum
computation. More precisely, we show that the above problem is
$\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reduction. In the recent
experiments, the quantum circuit has $n-$qubits and the architecture is a
two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$. Indeed for constant
depth circuits estimating the output probabilities to within
$2^{-\Omega(n\log{n})}$ is hard, and for circuits of depth $\sqrt{n}$, for
which the anti-concentration property holds, estimating the output
probabilities to within $2^{-\Omega(n^{3/2}\log n)}$ is hard. We prove these
results from first principles and do not use the standard techniques such as
the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's
result.
