# Clarifying Quantum Supremacy: better terms for milestones in quantum computation

• Quantum Supremacy: This milestone consists of two results: (1) a mathematical proof that a given problem has a super-polynomial separation* between any possible quantum algorithm and any possible classical algorithm and (2) the exhibition of the solution of this problem by a quantum computer at a performance (size, speed, or efficiency) that is infeasible with any available classical computer. *Note that it suffices for such a proof to be relative to a widely believed assumption such as the polynomial hierarchy not collapsing.
• Weak Quantum Supremacy: The solution of any problem, using a quantum computer, faster, cheaper, or more efficiently than any available classical solution.
• Quantum Advantage: The solution of a valuable problem, using a quantum computer, faster, cheaper, or more efficiently than any available classical solution.
• Strong Quantum Advantage: Quantum Advantage accompanied with a proof — up to widely believed assumptions — that the problem has a super-polynomial separation between any quantum solution and any classical solution. Equivalently, quantum supremacy but for a commercially valuable problem.

## More from W. J. Zeng

Focused on making quantum computers useful asap. http://willzeng.com $\langle sold|\otimes|worn\rangle+|not sold\rangle\otimes|never worn\rangle/\sqrt{2}$

Love podcasts or audiobooks? Learn on the go with our new app.

## W. J. Zeng

Focused on making quantum computers useful asap. http://willzeng.com $\langle sold|\otimes|worn\rangle+|not sold\rangle\otimes|never worn\rangle/\sqrt{2}$