(Edited to make the argument and the question more precise)

An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a classical sampler that outputs a probability $q_x$, $x \in \{0,1\}^{2^n}$ that approximates an output probability $p_x$ of a quantum device up to an additive error $$|p_z - q_z| \le \epsilon,$$ then uses Stockmeyer's counting to improve $q_x$ to a multiplicative approximate $\tilde{q}_x$ $$|p_z - \tilde{q}_z| \le \frac{p_z}{\mathrm{poly}(n)}$$ using a $\mathrm{BPP^{NP}}$ machine. This last step works only on a constant fraction of circuits i.e. on average, and relies on "anti-concentration", a separate property of the probabilities $p_z$.

If multiplicatively approximate $p_x$ is #P-hard on average, then the polynomial hierarchy collapses to the third level (known to contain $\mathrm{BPP^{NP}}$) by the fact that $\mathrm{PH \subset P^{\#P}}$. Thus, we conclude that no such classical sampler exists because we don't believe in PH collapse.

My question is the following: we know that there exists a quantum circuit whose single output probability $p_0$ is #P-complete to compute exactly ("strongly simulate") yet the probabilities can be sampled efficiently ("weakly simulate") on a classical computer. (In fact, this kind of quantum circuits are no more powerful than a BPP machine.) Is there anything close to a "quantum supremacy" argument (albeit there is nothing quantum here) that would apply to a worst-case hard problem that is nevertheless easy to approximate like this? My guess is that there can be none. But what exactly prevents this kind of argument? Is it the lack of anti-concentration, or worst-to-average case reduction, or something more general?

  • $\begingroup$ It might help if you sketch the argument more precisely - it might also make it easier to pinpoint where it goes wrong. $\endgroup$ Commented Aug 23, 2019 at 22:38
  • $\begingroup$ @NorbertSchuch Thanks for the suggestion. I have edited the question. $\endgroup$ Commented Aug 25, 2019 at 12:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.