Quantum supremacy using a programmable superconducting processor was published today. Scott Aaronson posted a few weeks ago a post about this paper and it was clear we will see a Nature or Science paper soon.

The abstract’s wording is less extravagant:

This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy for this specific computational task...

  1. Isn't supremacy a well-defined concept in complexity theory?
  2. Wouldn't Shor's algorithm be considered a QC supremacy?
  3. How can we define supermacy unless it's provable that there is no classical algorithm to solve the problem faster on "traditional" supercomputer besides brute force?

Note: this is an amazing paper and I am seriously asking to understand if the wording of the paper is acceptable by the QC community.

Related: IBM’s response.


3 Answers 3


The term "Quantum Supremacy" was first proposed and used by John Preskill in 2012. He talks about it in this Quanta article and you can find a link to his 2012 paper there as well. It's not a term Google invented in order to hype their work and is, I think, a well understood goal within the larger QC research community. If you want to understand the role complexity theory has played in the pursuit of quantum supremacy then I highly recommend Aaronson and Chen's "Complexity-Theoretic Foundations of Quantum Supremacy Experiments"


You should read the new post by Aaronson, but until then the short answers:

  1. No.
  2. If you can realize it in a real world machine, then it would (if no one finds a fast, classical algorithm until then).
  3. You don't prove anything. It's a practical fact, like AI playing chess better than humans. If a chess genius is born, (s)he might win back the crown for humanity!

Answer to 1), 2) & 3):

  • Complexity theory works with asymptotic and probabilistic cases, not the space and time consumption of specific examples of a given problem type which are mathematically precise concepts that are the basis of P, NP, QP, etc. problem classes. Asymptotically, we know certain problems can be solved in polynomial time on a quantum computer that take exponential time on a classical computer. It is in that mathematically precise sense that Shor's algorithm is superior to any classical algorithm to do the same. But that is not what quantum supremacy means.

Quantum supremacy would require an implementation of Shor's algorithm on a quantum computer that can factor a prime number that no existing implementation of a classical computer can. This makes it very hard to make mathematically precise because it would depend on the quantum computer being a precise (or with bounded, modelable error) implementation of an abstract quantum computer and which generation of classical computer it is up against. The incredible amount of engineering details necessary are not something we can easily make a mathematical model for.

So Quantum Supremacy is based on momentary and practical comparisons of specific problem instances between specific hardwares. And in the end, quantum supremacy might come and go from time to time as classical computers get better along with quantum computers.

General note on the paper:

  • Their work was quite impressive in terms of the difficulty of setting up the physical system (they truly made a step forward in terms of that alone) and there is a sense in which it is true quantum supremacy but it is not what we were hoping for in an intuitive sense. It is almost as if someone said a pile of sand settling is a complex computing system that can outperform current classical computers and then proved it by showing that it can compute where a piece of sand in the pile falls in less time than a classical computer. The paper isn't quite as bad as that. But it just doesn't feel like true supremacy even though it technically is.

They essentially set up a quantum system of 53 entangled qubits and then sampled the system to determine the statistics of the quantum system. To determine the same statistics with a classical system you would have to model 2^53 superimposed states, calculate each of their hamiltonian evolutions and then sample the model. That is not currently possible for 53 qubits on a classical computer. But it doesn't really excite one about quantum supremacy.


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.