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.
Taxonomy for milestones in quantum computing performance.

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.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
W. J. Zeng

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}$

More from Medium

Review: Black Opal’s “Control” by Q-CTRL

Analytical gradient of energies with a sophisticated calculation method by quantum computers…

THE TWO ASSUMPTIONS GRAVITY MODEL : An Occam’s Razor Optimized Gravity Conjecture (2.0)

Podcast with Matt Langione, Boston Consulting Group