When will we know that quantum supremacy has been reached?

Question

The term "quantum supremacy" - to my understanding - means that one can create and run algorithms to solve problems on quantum computers that can't be solved in realistic times on binary computers. However, that is a rather vague definition - what would count as "realistic time" in this context? Does it have to be the same algorithm or just the same problem? Not being able to simulate quantum computers of certain sizes surely can't be the best measure.

Answer 1

The term quantum supremacy doesn't necessarily mean that one can run algorithms, as such, on a quantum computer that are impractical to run on a classical computer. It just means that a quantum computer can do something that a classical computer will find difficult to simulate.

You might ask (and rightly so) what I might possibly mean by talking about something done by a quantum computer which is not an algorithm. What I mean by this is that we can have a quantum computer perform a process which

• does not necessarily have very well-understood behaviour — in particular, there are very few things we can prove about that process;

• in particular, that process does not 'solve' any problem of practical interest — the answer to the computation doesn't necessarily answer a question that you are interested in.

When I say that the process doesn't necessarily have well-understood behaviour, this does not mean that we don't know what the computer is doing: we will have a good description of the operations that it does. But we won't necessarily have an acute understanding of the cumulative effect on the state of the system of those operations. (The very promise of quantum computation was originally proposed because quantum mechanical systems are difficult to simulate, which meant that it might be able to simulate other systems which are difficult to simulate.)

---

You might ask what the point is of having a quantum computer do something which is difficult to simulate if the only reason is only that it is difficult to simulate. The reason of this is: it demonstrates a proof of principle. Suppose that you can build quantum systems with 35 qubits, with 40 qubits, with 45 qubits, 50 qubits, and so forth — each built according to the same engineering principles, each of them simulatable in practise, and each behaving the way that the simulation predicts (up to good tolerances), but where each simulation is much more resource-intensive than the last. Then once you have a system on 55 or 60 qubits that you can't simulate with the world's largest supercomputer, you could argue that you have an architecture that builds reliable quantum computers (based on the sizes you can simulate), and which can be used to build quantum computers large enough that no known simulation technique can predict their behaviour (and where perhaps no such technique is even possible).

This stage in itself is not necessarily useful for anything, but it is a necessary condition to being able to solve interesting problems on a quantum computer more quickly than you can on a classical computer. The fact that you can't necessarily solve 'interesting' problems at this stage is one reason why people are sometimes dissatisfied with the term 'supremacy'. (There are other reasons to do with political connotations, which are justified in my opinion but off-topic here.) Call it "quantum ascendancy", if you prefer — meaning that it marks a point at which quantum technologies are definitely becoming significant in power, while not yet in any danger of replacing the mobile phone in your pocket, desktop computers, or even necessarily industrial supercomputers — but it is a point of interest in the developmental curve of any quantum computational technology.

---

But the bottom line is that, yes, "quantum supremacy" is precisely about "not being able to simulate quantum computers of certain sizes", or at least not being able to simulate certain specific processes that you can have them perform, and this benchmark depends not only on quantum technology but on the best available classical technology and the best available classical techniques. It is a blurry boundary which, if we are being serious about things, we will only be confident that we have passed a year or two after the fact. But it is an important boundary to cross.

Answer 2

The term quantum supremacy, as introduced by Preskill in 2012 (1203.5813), can be defined by the following sentence:

We therefore hope to hasten the onset of the era of quantum supremacy, when we will be able to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers.

Or, as wikipedia rephrases it, quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.

It should be noted that this is not a precise definition in the mathematical sense. What you can make precise statements on is how the complexity of a given problem scales with the dimension of the input (say, the number of qubits to be simulated, if one is dealing with a simulation problem). Then, if it turns out that quantum mechanics allows solving the same problem more efficiently (and, crucially, you are able to prove it), then there is room for a quantum device to demonstrate (or rather, provide evidence towards) quantum supremacy (or quantum advantage, or however you prefer to call it, see for example the discussion in the comments here).

---

So, in light of the above, when exactly can one claim to have reached the quantum supremacy regime? At the end of the day, there is no single magic number that brings you from the "classically simulatable regime" to the "quantum supremacy regime", and this is more of a continuous transition, in which one gathers more and more evidence towards the statements that quantum mechanics can do better than classical physics (and, in the process, provide evidence against the Extended Church-Turing thesis).

On the one hand, there are regimes which obviously fall into the "quantum supremacy regime". This is when you manage to solve a problem with a quantum device that you just cannot solve with a classical device. For example, if you manage to factorize a huge number that would take the age of the universe to compute with any classical device (and assuming someone managed to prove that Factoring is indeed classical hard, which is far from a given), then it seems hard to refute that quantum mechanics does indeed allow to solve some problems more efficiently than classical devices.

But the above is not a good way to think of quantum supremacy, mostly because one of the main points of quantum supremacy is as an intermediate step before being able to solve practical problems with quantum computers. Indeed, in the quest for quantum supremacy, one relaxes the requirement of trying to solve useful problems and just tries to attack the principle that at least for some tasks, quantum mechanics does indeed provide advantages.

When you do this and ask for the simplest possible device that can demonstrate quantum supremacy, things start to get tricky. You want to find the threshold above which quantum devices are better than classical ones, but this amounts to compare two radically different kinds of devices, running radically different kinds of algorithms. There is no easy (known?) way to do this. For example, do you take into account how expensive it was to build the two different devices? And what about comparing a general purpose classical device with a special purpose quantum one? Is that fair? What about validating the output of the quantum device, is that required? Also, how strict do you require your complexity results to be? A proposed reasonable list of criteria for a quantum supremacy experiment, as given by Harrow and Montanaro (nature23458, paywalled), is$^1$:

1. A well-defined computational problem.
2. A quantum algorithm solving the problem which can run on a near-term hardware capable of dealing with noise and imperfections.
3. A number of computational resources (time/space) allowed to any classical competitor.
4. A small number of well-justified complexity-theoretic assumptions.
5. a verification method that can efficiently distinguish between the performances of the quantum algorithm from any classical competitor using the allowed resources.

To better understand the issue one may have a look at the discussions around D-Wave's claims in 2005 of a "$10^8$ speedup" with their device (which holds only when using appropriate comparisons). See for example discussions on this Scott Aaronson's blog post and references therein (and, of course, the original paper by Denchev et al. (1512.02206)).

Also regarding the exact thresholds separating the "classical" from the "quantum supremacy" regime, one may have a look at the discussions around the number of photons required to claim quantum supremacy in a boson sampling experiment. The reported number was initially around 20 and 30 (Aaronson 2010, Preskill 2012, Bentivegna et al. 2015, among others), then briefly went as low as seven (Latmiral et al. 2016), and then up again as high as ~50 (Neville et al. 2017, and you may have a look at the brief discussion of this result here).

There are many other similar examples that I didn't mention here. For example there is the whole discussion around quantum advantage via IQP circuits, or the number of qubits that are necessary before one cannot simulate classically a device (Neill et al. 2017, Pednault et al. 2017, and some other discussions on these results). Another nice review I didn't include above is this Lund et al. 2017 paper.

(1) I'm using here the rephrasing of the criteria as given in Calude and Calude (1712.01356).