Could random quantum circuits be efficiently approximately simulated?

Question

Google's landmark result last year was to compute a task with a quantum computer that a classical computer could not compute, and they chose random circuit sampling. Part of their justification was complexity-theoretic reasons that, if one can efficiently compute this classically, it collapses the polynomial hierarchy (they cite 1,2,3 for this). Paper 2 in that list says that the hardness result comes from a reduction to computing the permanent of a random matrix.

Based on a quick search, computing an approximation to the permanent seems to be easy for many classes of random matrices. So is it possible there is some classical algorithm that could efficiently approximate the random circuit sampling problem?

Second, is the quantum computer solving this exactly or approximately? I'm not quite sure what that means to approximately sample (since sampling is inherently noisy anyway). That is: if I had a quantum computer that was (up to some noise) sampling from random circuits, and a classical computer efficiently approximating the same task, could you tell the difference?

Answer 1

I can't answer all your questions and I certainly am not an expert, but I have something to say about your first point. According to the first paper linked in my comment (by Aaronson and Chen), the hardness assumptions of BosonSampling hinges on the assumption that there is no $\text{BPP}^{\text{NP}}$ (this is BPP relative to an NP oracle) algorithm for estimating the permanent of an $n\times n$ matrix $A$ with entries from an $N(0,1)$ Gaussian distribution. Now, I am not an complexity theorist so I don't know how $\text{BPP}^{\text{NP}}$ relates to $\#\text{P}$ or $\text{NP}$ but anyways onto computing permanents.

So it turns out that if your matrix has arbitrary number of negative entries then it is even $\#\text{P}$ hard just to determined the sign of the permanent and this fact rules out multiplicative approximations. This is all according to https://arxiv.org/pdf/1711.09457.pdf in which they state that approximating the permanent is worst case $\#\text{P}$ hard. However, they note that the average case hardness (which is what I think your initial question is asking about) is still open, and in fact the authors give a quasipolynomial time algorithm for approximating the permanent for many types of matrices (including $A$). This result, as they remark goes against the belief that it is still $\#\text{P}$ hard to approximate the permanent of $A$ in the average case. In section 1.6.1 they discuss their result in the context of the BosonSampling hardness conjecture (conjecture 4) and other supremacy claims. So it seems that if one could find a polynomial algorithm for this approximation problem then the quantum supremacy argument may collapse.

It also appears that this quasipolynomial time algorithm for approximating permanents of matrices with entries distributed Gaussian $N(0,1)$ has been simplified/improved in https://arxiv.org/pdf/1911.11962.pdf. The authors of this work also show that if their algorithm can be improved from working on matrices with mean at least $1/poly(log(n))$ to mean at least $1/poly(n)$ then this would disprove the hardness conjecture needed for quantum supremacy.