Despite having become a fairly mature field with enormous sums of money dumped into research and development, there does not as yet exist a formal proof that quantum computation actually provides an advantage. Having learned a bit about quantum circuits, quantum error correcting codes, and all the related basics of quantum information theory in university, the only arguments that were presented to me for quantum supremacy were:
- The existence of Shor's algorithm,
- The seeming infeasibility of simulating quantum systems with classical computers,
Neither of which are I find particularly compelling, especially when compared to the evidence for $P \neq NP$ for example.
My question is, what are the current "best" arguments for quantum advantage, assuming an ideal quantum computer (either by direct evidence for an advantage, or against the implications there being no advantage)? Given the lack of a hard proof, I am being deliberately vague in my use of the word "best".
I would hope that given the billions of dollars dumped into the field, that there would be extremely strong conjectures and circumstantial evidence of quantum advantage being real/its negation being false.
Edit: By "ideal quantum computer", I mean a quantum computer in the abstract, similar to how we might consider an abstract turing machine or other classical computer model as opposed to any specific physical architecture with all the related engineering concerns.
Best Answer
The short answer is that if you are looking for theoretical evidence in the form of provable theorems, the situation is not very satisfactory. But I would argue that the heuristic evidence is pretty strong.
Let's first think about what would constitute a compelling argument. The "gold standard" would presumably be a proof that $\mathsf{BQP}\ne \mathsf{P}$, but of course we are far away from that; we cannot even prove that $\mathsf{P} \ne \mathsf{PSPACE}$. For a long time, it was not even known that there was an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{PH}$ (where $\mathsf{PH}$ denotes the polynomial hierarchy); it was a big theoretical breakthrough by Raz and Tal to prove such an oracle separation. You could argue that the Raz–Tal result provides some evidence that $\mathsf{BQP} \not\subseteq \mathsf{PH}$ in the "real world," but it's at best very weak, since people have proved relativized versions of all kinds of things that we believe are false. If you're skeptical, you could even argue that the difficulty of finding an oracle separation is evidence that the opposite is true in the real world!
Recent quantum supremacy experiments have focused on sampling problems. Here, the gold standard would be showing that $\mathsf{SampBQP}\ne\mathsf{SampBPP}$. Again, an unconditional proof is beyond reach, but you might hope we could prove, say, that if $\mathsf{SampBQP}=\mathsf{SampBPP}$ then $\mathsf{PH}$ collapses. But not only is this not known; Aaronson and Chen, in Complexity-theoretic foundations of quantum supremacy experiments (which by the way I highly recommend for a general discussion of the topic of quantum supremacy), showed that there is an oracle relative to which $\mathsf{SampBQP}=\mathsf{SampBPP}$ but $\mathsf{PH}$ does not collapse. So even proving this conditional result seems difficult (because it would require non-relativizing techniques).
In another answer, JoshuaZ mentions $\mathsf{BosonSampling}$, which has indeed gotten a lot of attention recently. A polynomial-time exact classical simulation of $\mathsf{BosonSampling}$ would indeed collapse $\mathsf{PH}$ (Carlo Beenakker alludes to this fact in his answer), but arguably an exact simulation is not a realistic computational problem to be considering, since in practice we can only implement approximate sampling. Aaronson and Arkhipov had to introduce additional assumptions to prove the hardness of approximate sampling, and if you're a skeptic, you can question those additional assumptions, which certainly haven't been vetted as much as (say) the non-collapse of $\mathsf{PH}$. Indeed, as Aaronson explains on his blog, Kalai and others have obtained interesting partial results about classical algorithms for $\mathsf{BosonSampling}$, so it probably isn't the most convincing candidate right now for a skeptic. Random circuit sampling, which was the basis for Google's experiment, fares a little better, because AFAIK there are no nontrivial classical algorithmic results; Aaronson and Gunn prove some hardness results in this direction, but again have to introduce extra assumptions beyond the "standard" ones. See also On the Complexity and Verification of Quantum Random Circuit Sampling by Bouland et al.
Stepping back from the question of what we can prove, however, I would say that the random circuit sampling problem is intuitively pretty convincing. Perhaps you're skeptical of Shor's algorithm because you think that factoring and discrete log are "structured" problems that might have a classical algorithm that we haven't discovered yet. Fair enough, but by the same intuition, it's not so plausible that there would be a classical algorithm for random circuit sampling, because of the lack of structure. The Google experiment, IMO, provides pretty convincing evidence that quantum computers can solve this problem, not just in theory but in practice. So you just have to decide whether you believe that there really is a classical algorithm for this problem that we just haven't discovered yet.