<p>The term "Quantum Supremacy" was first proposed and used by John Preskill in 2012. He talks about it <a href="https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/" rel="nofollow noreferrer">in this Quanta article</a> 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 <a href="https://arxiv.org/abs/1612.05903" rel="nofollow noreferrer">Aaronson and Chen's "Complexity-Theoretic Foundations of Quantum Supremacy Experiments"</a></p>

CC BY-SA 4.0
2019-10-25T02:36:33.703Z
2019-10-25T02:36:33.703Z
Logan Mayfield
<p>You should read the <a href="https://www.scottaaronson.com/blog/?p=4372" rel="noreferrer">new post by Aaronson</a>, but until then the short answers:</p>

<ol>
<li>No.</li>
<li>If you can realize it in a real world machine, then it would (if no one finds a fast, classical algorithm until then).</li>
<li>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!</li>
</ol>

CC BY-SA 4.0
2019-10-25T19:11:49.787Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/100293/discussion-between-stella-biderman-and-vs).
Stella Biderman
CC BY-SA 4.0
2019-10-24T08:58:43.200Z
2019-10-24T08:58:43.200Z
domotorp
<p>Answer to 1), 2) &amp; 3):</p>
<ul>
<li>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.</li>
</ul>
<p>Quantum supremacy would require an <em>implementation</em> of Shor's algorithm on a quantum computer that can factor a prime number that no <em>existing</em> 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.</p>
<p>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.</p>
<p>General note on the paper:</p>
<ul>
<li>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.</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2019-10-29T23:22:12.767Z
2023-02-24T20:31:53.953Z
2023-02-24T20:31:53.953Z
CognizantApe
<p><a href="https://www.nature.com/articles/s41586-019-1666-5" rel="nofollow noreferrer">Quantum supremacy using a programmable superconducting processor</a> was published today. Scott Aaronson posted a few weeks ago a <a href="https://www.scottaaronson.com/blog/?p=4317" rel="nofollow noreferrer">post</a> about this paper and it was clear we will see a Nature or Science paper soon. </p>

<p>The abstract’s wording is less extravagant:</p>

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

<ol>
<li>Isn't supremacy a well-defined concept in complexity theory?</li>
<li>Wouldn't Shor's algorithm be considered a QC supremacy?</li>
<li>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?</li>
</ol>

<p>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.</p>

<p>Related: IBM’s <a href="https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/" rel="nofollow noreferrer">response</a>. </p>

<cc.complexity-theory><quantum-computing>
Is the wording of Google's QC Supremacy valid?
0x90
# Is the wording of Google's QC Supremacy valid?

(Asked by: username_0 on 2019-10-24)

[Quantum supremacy using a programmable superconducting processor](https://www.nature.com/articles/s41586-019-1666-5) was published today. Scott Aaronson posted a few weeks ago a [post](https://www.scottaaronson.com/blog/?p=4317) 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](https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/).

**Tags:** cc.complexity-theory, quantum-computing

---

## 3 answers

### Answer by username_1 on 2019-10-25. Score: 3 | Accepted answer

The term "Quantum Supremacy" was first proposed and used by John Preskill in 2012. He talks about it [in this Quanta article](https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/) 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"](https://arxiv.org/abs/1612.05903)


---

### Answer by username_2 on 2019-10-24. Score: 13

You should read the [new post by Aaronson](https://www.scottaaronson.com/blog/?p=4372), 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!

> **Comments:**
> **username_3**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/100293/discussion-between-stella-biderman-and-vs).  

---

### Answer by username_4 on 2019-10-29. Score: 4

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.


---

