34
$\begingroup$

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.

$\endgroup$
9
  • 9
    $\begingroup$ There is also Grover's algorithm. $\endgroup$
    – Alex M.
    Dec 9, 2021 at 8:57
  • 2
    $\begingroup$ The fact that "billions of dollars" have been "dumped into the field" is probably more a reflection of the practical advantages of a quantum computer: with Shor's algorithm they have a great hope of breaking existing cryptography systems based on integer factorization (whether or not those systems are theoretically classically secure). $\endgroup$ Dec 9, 2021 at 14:35
  • 2
    $\begingroup$ Let me put it this way: suppose someone came up with an efficient (classical!) factorization algorithm, whose correctness relied on the truth of the Riemann Hypothesis. Would that cause a redoubled effort to prove the RH? Or would it more likely lead to people trying to implementing the algorithm and break codes in practice? $\endgroup$ Dec 9, 2021 at 16:43
  • 1
    $\begingroup$ I agree with Sam Hopkins that practical considerations dominate when it comes to funding. Suppose I have an important problem, and I know that Method A solves it. To justify spending money on implementing Method A, I don't really need powerful evidence that no other method can possibly work. I might spend some money trying to come up with Method B, but it's always a murky question how much effort to invest in something that might or might not work, vs. something that you're confident will work. It's sort of a multi-armed bandit problem. $\endgroup$ Dec 9, 2021 at 17:08
  • 2
    $\begingroup$ @Chuu We already know mathematically that Shor's Algorithm breaks RSA encryption specifically, though not other types of encryption. This is still important because much of internet encryption relies on RSA for various reasons. Other types of classical encryption exist which don't seem vulnerable to Shor's Algorithm but they're often impractical, and we don't know if they're vulnerable to different (possibly undiscovered) quantum algorithms. Because of this, much research is going into post-quantum cryptography, classical schemes that can resist quantum computers. $\endgroup$ Dec 11, 2021 at 14:57

5 Answers 5

27
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ I checked with Scott Aaronson to see if I missed anything. He said the only thing he would add is that chemists and physicists have been searching fruitlessly for efficient (classical) simulations of quantum behavior for nearly a century, so that provides some empirical support for $\mathsf{PromiseBPP} \ne \mathsf{PromiseBQP}$. I also want to mention that Gil Kalai, who is famously skeptical of QC, finds random circuit sampling convincing. I believe the only reason he doesn't accept that Google's experiment establishes quantum supremacy is that he suspects they made a mistake somewhere. $\endgroup$ Dec 10, 2021 at 21:58
  • 1
    $\begingroup$ "since people have proved relativized versions of all kinds of things that we believe are false" Minor note- you actually have a stronger statement here. We've proven relativized versions of things we know are false. IP=PSPACE is true in the non-relativized situation, but we can give oracles where it is false. (I don't know of a natural example where A != B, but they are equal in the relativized context, but it wouldn't surprise me if we have those also.) $\endgroup$
    – JoshuaZ
    Dec 11, 2021 at 13:54
  • $\begingroup$ @JoshuaZ Good point! My favorite example of a nonrelativizing separation is Vinodchandran's result that for all $k$, $\mathsf{PP} \not\subseteq \mathsf{SIZE}(n^k)$. Aaronson showed that there is an oracle $A$ such that $\mathsf{PP}^A \subseteq \mathsf{SIZE}^A(n)$. $\endgroup$ Dec 11, 2021 at 16:56
  • 2
    $\begingroup$ Timothy, my work (with Kindler) is about classical algorithms for noisy Boson Sampling. (Boson Sampling is genuinly very hard even to approximate.) $\endgroup$
    – Gil Kalai
    Dec 15, 2021 at 19:10
  • $\begingroup$ Regarding Shor's algorithm, I found the paper arxiv.org/abs/2104.11616 very interesting in this regard. Is their algorithm classical, quantum, or something else entirely? $\endgroup$ Dec 15, 2021 at 20:42
16
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yeah I did mean a fully fault tolerant etc. quantum computer. I wanted my question to focus on the abstract properties of computation, not on the engineering difficulties its presents (though there are apparently deep theoretical discussions around that too). Also, good point about the "billions of dollars", though presumably one could imagine a lot of that money being diverted into finding classical equivalents. $\endgroup$ Dec 9, 2021 at 9:53
  • $\begingroup$ I added a pointer to work on finding classical equivalents, not an activity that absorbs "billions of dollars", but still a vigorous reseach effort. $\endgroup$ Dec 9, 2021 at 20:16
  • $\begingroup$ I also saw a recent paper covering the quantum advantage of topological data analysis. However, computing Betti numbers in finite-dimensional chain complexes is nothing else than linear algebra, computing ranks of matrices. Isn't that boiling down in claiming quantum supremacy for the Gauss algorithm? $\endgroup$
    – Bizfold
    Jul 6, 2023 at 10:00
15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$
  • 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.
$\endgroup$
2
  • 1
    $\begingroup$ Can you please elaborate on the first item? ETH implies...what exactly? That $\mathsf{BQP}\ne\mathsf{P}$? $\endgroup$ Dec 15, 2021 at 18:20
  • 3
    $\begingroup$ Sorry: I originally wrote 'Exponential Time Hypothesis' here, but that was wrong; I should have written 'Strong Exponential Time Hypothesis' -- I have edited my answer to reflect this. The sum total of all I mean by this first bullet point is that it is a moderately accepted hypothesis ("SETH") that SAT cannot be solved in $2^{.99n}$ time by, say, a randomized classical algorithm. Yet there is a quantum algorithm that solves SAT in $1.42^n$ time. $\endgroup$ Dec 15, 2021 at 18:30
4
$\begingroup$

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}}$.)

enter image description here

$\endgroup$

Your Answer

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

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