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?

  • 3
    $\begingroup$ maybe the answer is hidden somewhere in scottaaronson.com/papers/quantumsupre.pdf ? $\endgroup$
    – Condo
    Oct 27 '20 at 15:56
  • $\begingroup$ Probably you're right, though I was hoping I could just get a quick answer from an expert before slogging through 66 pages of dense complexity theory :) $\endgroup$
    – Sam Jaques
    Oct 28 '20 at 9:44
  • 1
    $\begingroup$ If you can commit a couple of hours of YouTube lectures, Adam Bouland gave an excellent set of lectures t the Israeli Institute of Advanced Studies just on this topic. Quantum algorithms shine when calculating the difference of two functions - e.g. permanents of matrices with entries in $\mathbb{C}$, not just in $\{0,1\}$. $\endgroup$
    – Mark S
    Oct 28 '20 at 23:44

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.

  • $\begingroup$ @Sam Jaques I'lladd that you shouldn't except my answer with the hope that someone with expertise in this area can fully answer your question ;) $\endgroup$
    – Condo
    Oct 28 '20 at 19:23
  • 1
    $\begingroup$ Gaussian probability distributions generally (with the help of diagonal loading) make belief propagation efficiently solvable (arxiv.org/abs/0811.2518). If one encodes the permanent as a graphical model (which you apparently can, see arxiv.org/abs/0908.1769), with the Gaussian probability distribution on the matrix entries 'moved' to the variables, then shouldn't one be able to get to $1/\exp(n)$ accuracy? $\endgroup$
    – botsina
    Nov 8 '20 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.