In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15):

"If [...] the QAOA outperforms all known classical algorithms then it will achieve Quantum Supremacy in an algorithmic sense."

To support this, they prove that any classical (stochastic) algorithm that produces a similar (up to a small multiplicative error) output distribution as QAOA, cannot do this in poly-time (or in other words: sampling from the QAOA distribution cannot be done efficiently on classical computer).

Can someone explain how this point supports their supremacy claim?

I mean, according to their proof it is still possible that a (potentially not yet known) classical algorithm can have a completely different output distribution that however might have even a much higher probability for the correct answer.

Of course, this also depends on the definition of quantum supremacy but for me quantum supremacy would mean that no classical algorithm can exist at all that solves the problem in a better way than a quantum algorithm. So, is this just a different understanding of the supremacy term in the sense that they mean that supremacy is reached once all known classical algorithms are beaten?


2 Answers 2


"but for me quantum supremacy would mean that no classical algorithm can exist at all that solves the problem in a better way than a quantum algorithm."

If that were the case, then "quantum supremacy" would almost not exist at all.

Even Shor's algorithm for factoring numbers in polynomial time would not be considered "superior" to what classical computation can do because it is still unknown whether or not classical computers can factor numbers in polynomial time.

But the word "quantum supremacy" should be avoided for exactly the confusion you're undergoing here. It's better to be specific about what you mean. Instead of using a buzz word like "quantum supremacy", you can just say "no known classical algorithm can do this calculation as efficiently". Or in the case of the Deutsch problem, where a perfect quantum computer needs to evaluate the blackbox function only once, and a classical computer would need to evalue it twice, then you can say "the quantum computer can solve the problem with a small number of evaluations of the blackbox which is impossible to match by a classical computer."

  • 1
    $\begingroup$ I get your point and it makes sense. But then it is not yet clear to me what the authors want to say. If QAOA outperforms all known classical algorithms for a certain problem, it is obviously superior. Why is it required to prove that the output distribution can classically not be sampled. From the result that OAOA outperforms all known algorithms, it is clear that there is no (known) classical algorithm that has a similar output distribution. $\endgroup$ Feb 8, 2021 at 22:13
  • 1
    $\begingroup$ @NepomukHirsch That's true, but as the first author Ed Farhi has noted in several of his talks in the years after that 2016 paper of his that you cited, 12 authors came up with a better classical algorithm for this problem after the 2016 paper so we have "classical supremacy" because not only is the quantum algorithm not much better from a "complexity theory" standpoint, it's also harder to run such an algorithm in hardware, so classical computers have the advantage here. $\endgroup$ Feb 8, 2021 at 22:17
  • 2
    $\begingroup$ @BrockenDuck that's a separate question. You can ask it and put a link to this answer in the question. If you let me know here, I will answer your question. But I'm busy until tomorrow, so you can ask tomorrow if you want. $\endgroup$ Feb 9, 2021 at 17:35
  • 1
    $\begingroup$ I disagree with this. Theoretical claims of quantum supremacy are made when there is a proof (or at least strong reasons to believe) that the given problem can be solved more efficiently with a quantum device than with any classical one. As you correctly mention, Shor is indeed not one such example. Things like boson sampling or sampling from random circuits of certain kinds are. This is the way the terminology is used e.g. in arxiv.org/abs/1809.07442. That said, there might be claims of "quantum supremacy" made even in lack of such requirements; do you know of some such references? $\endgroup$
    – glS
    Feb 10, 2021 at 9:37
  • 1
    $\begingroup$ @gIS So why do you "disagree" with the answer? $\endgroup$ Feb 10, 2021 at 13:51

Demanding that quantum computational supremacy be achieved only when we can prove that no classical algorithm can run with the same asymptotic speed is presently out of reach, not so much of the scientists and engineers, but of the complexity theorists.

For example because Feynman proved that $\mathsf{BQP}$ is contained in $\mathsf{PP}$, and because we don't yet know how to unconditionally separate, e.g., $\mathsf{P}$ from $\mathsf{PP}$, almost all proposals/approaches to proving quantum computational supremacy in the asymptotic sense must rest on assumptions about the limitations of classical computational algorithms. Often when speaking freely these hypotheses are unstated or unrepeated. Indeed, the Farhi and Harrow paper states in the abstract that the results are conditioned "based on reasonable complexity theoretic assumptions".

I would argue that running Shor's algorithm to factor, say, RSA-2048 would be evidence of quantum computational supremacy, with the hidden assumption that there is no polynomial-time factoring algorithm.

But the reason that Shor's algorithm is not seen as an ideal candidate in the near term for showing quantum computational supremacy is not because we don't know whether a classical algorithm exists; it's rather that the overhead required for factoring is too large now, absent fully scalable fault tolerant quantum computers.

That is, one of the motivations of Preskill starting the program of showing quantum computational supremacy was to provide a goal achievable with the near-term, noisy, intermediate-scale quantum (NISQ) devices. The QAOA approach in the Farhi-Harrow paper may be achievable with such a NISQ device; however, it nonetheless has to rely on reasonable complexity-theoretic assumptions.


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.