What are the strongest arguments for a genuine quantum computing advantage?

Question

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:

1. The existence of Shor's algorithm,
2. 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.

Answer 1

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.

Answer 2

The question as posed assumes an "ideal" quantum computer, I presume meaning a fully fault tolerant device. (Which does not yet exist.) There is one other limitation that needs to be resolved, which is whether or not it is possible to efficiently encode classical data in the amplitudes of a quantum state. If this is possible, then exponential speed-up follows quite naturally from the fact that the number of qubits needed to store the data is only logarithmic in the size of the dataset.

There is much doubt whether this efficient encoding will be possible, and more meaningful approaches assume only classical access to the data. In the context of classification problems a quantum advantage was recently proven in A rigorous and robust quantum speed-up in supervised machine learning.

The proof is at the same level of rigor as the proof of the exponential speed-up of Shor's algorithm, both rely on the complexity of the discrete log problem (compute logarithms in a cyclic group), which is believed to require a superpolynomial amount of time on a classical computer.

If only the abstract properties of computation are considered, then the conjecture that PostBPP $\neq$ PostBQP is enough to show that classical computers cannot exactly simulate quantum computers in polynomial time. This conjecture follows from the non-collapse of the polynomial hierarchy, which is at the same level of plausibility as P $\neq$ NP.

For more on this, see Quantum computational supremacy by Harrow and Montanaro, and Complexity-Theoretic Foundations of Quantum Supremacy Experiments by Aaronson and Chen.

---

_{Since the OP refers to *"billions of dollars dumped into the field*", let me point out that these investments are made with a very practical expectation: There are problems that matter (in chemistry, drug design, materials science, optimisation, ...) which we have not been able to solve on a classical computer. If some company offers cloud access to a device that will deliver an answer, then customers will come, even if there is no mathematical proof that the problem is unsolvable on a classical computer.}

---

Addendum in response to the comment of the OP that "given all the money put into solving engineering concerns, at least some of that surely might have been put into theorists investigating if classical counterparts exist." This is actually happening. In parallel to the development of quantum algorithms, there is a "dequantization" effort: find the essential feature of the quantum algorithm that provides the speed-up relative to the existing classical algorithms, and then see if this same feature can be reproduced without relying on quantum superposition and entanglement.

Ewin Tang's work is a notable example, see A quantum-inspired classical algorithm for recommendation systems, as described in this blog. We are learning which algorithms can be dequantized and for which this is unlikely, see Towards quantum advantage via topological data analysis.

Answer 3

One major piece of evidence is not in the context of problems which are decision problems (which return a yes/no answer), or function problems, but rather distribution problems, where one wants to sample from some given probability distribution. One of the best examples of this is Boson Sampling, where one has some system which does splitting and a few other things to non-interacting bosons (for most purposes these can be assumed to be photons), and one wants to sample from the distribution. Then Scott Aaronson and Alex Arkhipov showed that subject to two plausible conjectures a classical system being able to make even a good approximation of this unless the polynomial hiearchy collapses.

In this context, the two conjectures are the Permanent-of-Gaussians Conjecture, which says that it is $\#P$-hard to approximate the permanent of a matrix $A$ of independent $N$ (0, 1) Gaussian entries, with high probability; and the second is the the Permanent Anti-Concentration Conjecture, which says that roughly speaking, with high probability, a random matrix has a large permanent. The permanent is arising in this context because roughly speaking it plays a role with bosons similar to the role the determinant plays with fermions. But the upshot is that under pretty plausible assumptions a classical computer cannot with high probability simulate the output a pretty simple quantum system.

There has been a bit of work following up on the above result getting other results of a similar fashion. But a lot of that is technical. As far as I'm aware both of the two conjectures are still open, but they seem to be believed to be probably true.

Answer 4

• As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the Strong Exponential Time Hypothesis (a by-now moderately accepted generalization of $\mathsf{P} \neq \mathsf{NP}$).
• Regarding "sampling problems", here is what I might regard as the simplest/best evidence: The Deutsch--Josza Algorithm gives an efficient quantum algorithm $Q$ with the following property: On input a classical circuit $C$, we have $\Pr[Q(C) = 1] = 0$ if $C$'s truth-table is exactly 50% $1$'s, and $\Pr[Q(C) = 1] > 0$ if $C$'s truth-table is not exactly 50% $1$'s. Now suppose that for every efficient quantum algorithm (in particular, $Q$) there were an efficient randomized classical algorithm $A$ that had "approximately the same output distribution" as $Q$; say, for all outputs $y$, $$\Pr[Q = y] \text{ is within a factor of 1000 of }\Pr[A = y].$$ Then we would also have that $\Pr[A(C) = 1] > 0$ iff $C$'s truth-table is not exactly 50% $1$'s, which is equivalent to "$\mathsf{co}\text{-}\mathsf{C}_=\mathsf{P} = \mathsf{NP}$", which was shown (Ogihara and Toda, early '90s) to imply $\mathsf{PH}$ collapses to the second level (indeed, to $\mathsf{AM}\cap \mathsf{co}\text{-}\mathsf{AM}$). Indeed, the above "factor-$1000$ approximation" is a red herring; one only needs the weaker "approximate sampling" condition that the classical algorithm outputs each outcome with positive probability iff the quantum algorithm does.

Answer 5

In addition to Shor's algorithm and to Grover algorithm let me mention two important pieces of information that abstract quantum computer have for some specific goals superior computational powers.

1. The ability of quantum computers, and even quantum circuits of bounded depth to perform sampling tasks that goes beyond the polynomial hierarchy! (Evidence that ${\bf QuantumSampling \not \subset PH}$.)

2. The evidence that the class of decision problems that quantum computers can solve goes beyond the polynomial hierarchy! (Evidence that ${\bf BQP \not \subset PH}$)

The first item is a long story related to early works of Terhal and DiVincenzo (2004), Aaronson and Arkhipov (2013) and Bremner, Jozsa, and Shepherd (2011). Related also to Boson Sampling.

The second item (with a weaker type of evidence) is related to a 2018 work by Raz and Tal.

${\bf QuantumSampling}$ (which is one aspect of the power of quantum computers that reflects the power of quantum computers for sampling) may be in a sense stronger than ${\bf BQP}$ (The power of quantum computers for decision problems) since it is a plausible conjecture that ${\bf QuantumSampling \not \subset P^{BQP}}$. (And even ${\bf QuantumSampling} \not \subset {\bf PH^{BQP}}$.)