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?