8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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"

| cite | improve this answer | |
$\endgroup$
13
$\begingroup$

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!
| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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. So it is not a mathematically precise concept like the NP or QP problem classes. 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 perfectly precise (or with bounded, modelable error) implementation of an abstract quantum computer and the same with the classical computer. The incredible amount of engineering details necessary are not something we can easily make a mathematical model for. 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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