As per the title: should we merge/synonymise and ? I suppose the terms are used in slightly different contexts, with quantum advantage/supremacy referring to the quest of proving/obtaining strong evidence towards disproving the extended Church-Turing thesis. Speedup is a more generic term.

Nevertheless, I feel like the tags both ultimately refer to the same thing: questions about quantum algorithms that solve some task faster/more efficiently than their classical counterparts, be this advantage quadratic, exponential, proven, empirical, or something else.

Am I missing some good reason to keep these separate?


1 Answer 1

  • "Quantum advantage" could refer to a reduced storage requirement (needing fewer qubits than the number of bits you'd need on a classical computer) even if the speed is worse than on a classical computer.

  • Quantum advantage could also refer to the advantages we get in quantum metrology, meaning that there's no speed-up, but measurements can be made more accurately if we make use of inherently quantum phenomena like entanglement.

  • Quantum advantage could also refer to security advantages of quantum communication protocols that fall under "quantum communication" more than "quantum computing", which is a context where "speed" isn't the pertinent term used.

While I've argued above that the two terms are not the same, the question of whether or not "everything in falls under is an interesting one because speed-up is just a subset of advantage right (or so it would seem)? My answer to that is this: is a tag that can also be used to describe theoretical speed-ups as long as the "asymptotic" cost is less (regardless of how large $N$ has to be to get to the speed-up regime), but there's cases in which there would be zero for practical problems, despite there being a significant "speed-up" theoretically.

Quantum advantage is a term that's been advocated to replace "quantum supremacy". But quantum supremacy is a term almost exclusively used in the context of experimental results that outperform classical computers.

No one was using the term quantum advantage or quantum supremacy when Shor's algorithm was performed on 7 qubits to factor the number 15.

Quantum advantage/supremacy requires more than that: you would need to perform Shor's algorithm on a number big enough that you actually beat the classical computer. But "speed-up" is often used (for example) in association with the theoretical $\mathcal{O}(\sqrt{n})$ cost of Grover vs the classical cost of $\mathcal{O}(n)$.

  • $\begingroup$ I suppose you are right that "quantum advantage" might be taken to mean more things. In my mind it was equivalent to "quantum supremacy", but that's probably not how the terminology is used in general. But the distinction between speed-up and quantum-advantage you propose seems hard to enforce in practice. Keep in mind that most people won't read the tag description at all, and the distinction between the tags you propose wouldn't be obvious from the tag names themselves. Also, questions involving asymptotic aspects would also often be covered with complexity-theory and similar, no? $\endgroup$
    – glS Mod
    May 9, 2021 at 17:14
  • $\begingroup$ Just like you, I also think "quantum advantage" is just a synonym for "quantum supremacy", and in fact it's already a tag synonym. I think both terms can be used not only for quantum computational supremacy but also for quantum communication supremacy or quantum measurement supremacy. As for speed-up: I think complexity-theory would be used for things like BQP vs QMA vs PSPACE, etc. more than for simple runtimes. There's no complexity theory in calculating a runtime. $\endgroup$ May 9, 2021 at 21:00
  • $\begingroup$ ok but now I'm not sure what you're suggesting. I don't think devoting speed-up to cases where there are "theoretical but not practical speedups" works, because most people won't read the tag excerpt and end up using the wrong one. We could then only use quantum-advantage, possibly specifying in the description that it is to be used for any situation involving some kind of speed-up or other "advantage". We can then use specialised tags for things that are commonly referred to as "quantum supremacy" experiments/results (i.e. boson-sampling and such) $\endgroup$
    – glS Mod
    May 10, 2021 at 7:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .