What Is Quantum Advantage and What Is Quantum Supremacy?

  1. quantum advantage. A quantum computer can perform a particular computation significantly faster than even the best classical computer. And in some cases, a quantum computer can perform computations which no classical computer can perform at all — also referred to as quantum supremacy.
  2. quantum supremacy. A quantum computer is able to compute a solution to a particular problem when no classical computer is able to do so at all or in any reasonable amount of time. Does not imply either an advantage or supremacy for any other problems beyond the particular problem or niche of closely related problems. Alternatively, quantum advantage across a wide range of applications and computations. Or, possibly simply a synonym for quantum advantage.
  1. quantum advantage. At least in the context of a particular application of interest, a quantum computer can perform a computation significantly faster than even the best classical computer or no classical computer may be able to perform the computation at all — or at least not in some reasonable amount of time or with a reasonable number of classical computers in a distributed or networked configuration. Note that a quantum advantage in one or more applications does not necessarily imply an overall quantum advantage in any other application or across all applications. The central essence of quantum advantage is quantum parallelism which enables quantum algorithms to execute with a computational complexity which is polynomial in contrast with classical algorithms which tend to have a greater (worse) computational complexity which is superpolynomial, such as exponential. Or in general, the computational complexity of an algorithm on a quantum computer grows significantly more slowly than for the best comparable algorithm on the best classical computer as the size of the input or complexity of the problem to be solved grows — Big-O for a quantum algorithm on a quantum computer is much smaller than Big-O for the best algorithm on a classical computer. May sometimes be used as a synonym for quantum supremacy, quantum preeminence, or quantum ascendency. May refer to a specific characterization of how much faster or better a quantum computer can execute a particular algorithm compared to a comparable algorithm on a classical computer — the specific advantage. See also: quantum speedup. May also refer to the eventual advantage and promise of quantum computers, as opposed to capabilities which are available today or likely will be in the fairly near-term future.
  2. quantum supremacy. A quantum computer is able to compute a solution to a problem when no classical computer is able to do so — or at least not in some reasonable amount of time or with a reasonable number of classical computers. Implies quantum advantage. Does not imply either an advantage or supremacy for any other problems beyond the particular problem or niche of closely related problems. Alternatively, quantum advantage across a broad range of applications and categories of computations, rather than limited to a particular problem or niche of closely related problems. May also be merely a synonym for quantum advantage unless clear from context. A synonym for quantum computational supremacy, quantum preeminence, or quantum ascendency. See the Wikipedia Quantum supremacy article and the Characterizing Quantum Supremacy in Near-Term Devices paper by Boixo, et al. Also see the definition and discussion in the Quantum computing and the entanglement frontier paper by Preskill.

Breadth of quantum supremacy

  1. Single, particular, niche problem or application — of theoretical, non-practical interest only.
  2. Single, particular, niche problem or application — of practical, real-world interest.
  3. Narrow niche of related problems or applications. Of practical, real-world interest, by definition. Be sure to clearly identify the niche. Ditto for all of the remaining distinctions.
  4. General niche of related problems or applications.
  5. Broad niche of related problems or applications.
  6. Multiple niches of problems or applications.
  7. Many niches of problems or applications.
  8. Narrow category of related problems or applications. Be sure to clearly identify the category.
  9. General category of related problems or applications.
  10. Broad category of related problems or applications.
  11. Multiple categories of problems or applications.
  12. Many categories of problems or applications.
  13. All categories of problems or applications.

Single vs. multiple classical computers

  • Cost is a real issue. A single quantum computer may be very expensive, while a single classical computer is now a very cheap commodity. It may make more sense to compare any advantage or supremacy on a cost or cost-adjusted basis. So, we could compare a single $1.5 million dollar quantum computer to a distributed network of 1,000 $1,500 classical computers.
  • Distributed computing is now the accepted paradigm for high-performance classical computing. So-called fat nodes — a single machine with lots of memory and processors — are now less common and even discouraged in many contexts. A supercomputer these days is really usually a very large number of commodity processors wired together. Any computationally-intense application which is a candidate for quantum computing would tend to have its classical equivalent implemented by a significant number of relatively cheap distributed or networked classical processors — anywhere from 4 to 8, 16 to 64, 256, or 1,024 or even more.
  1. Comparable total system cost.
  2. A reasonable number of machines for a single application — excluding the mega-huge Internet giants such as Google, Apple, Facebook, and Microsoft.

Computational complexity

Hybrid mode execution

Big O notation

Polynomial vs. exponential complexity

  • 10² is 100 operations.
  • 100² is 10,000 operations.
  • 1000² is 1,000,000 operations. One million.
  • 10³ is 1,000 operations — 10 times 100.
  • 100³ is 1,000,000 operations. One million — 100 times 10,000.
  • 1000³ is 1,000,000,000 operations. One billion — 1,000 times 1,000,000.
  • 2¹⁰ is 1,024 operations.
  • 2¹⁰⁰ is 10 followed by 29 zeros operations. That’s a huge number. That’s why a quantum computer with an algorithm of polynomial complexity is needed
  • 2¹⁰⁰⁰ is 10 followed by 300 zeros operations. That’s way beyond huge. Only a quantum computer could handle that.
  • 2²⁰ is about one million operations. Not such a big deal
  • 2³⁰ is about one billion operations. A moderate deal, doable, but likely requires more than one machine.
  • 2⁴⁰ is about one trillion operations. Still technically feasible, but likely requiring a larger network of computers and/or a very long running time.
  • 2⁵⁰ is about one quadrillion operations. The realm of petaflops, the realm of the largest supercomputers.
  • 2⁶⁰ is about a million quadrillion. 1,000 of the largest classical supercomputers.
  • 2⁷⁰ is about a billion quadrillion. A million of the largest classical supercomputers.
  • 2⁸⁰ is about a trillion quadrillion. A billion of the largest classical supercomputers.
  • 2⁹⁰ is about a quadrillion quadrillion. A trillion of the largest classical supercomputers. Or, 1,000 of the largest classical supercomputers running for a billion seconds — 32 years. Imaginable, yes, but not very likely to happen. Really need a quantum computer.
  • 2¹⁰⁰ … a million of the fastest classical supercomputers running for 32 years. Or, 1,000 of those machines running for 32,000 years.
  • 2¹¹⁰ … a million of the fastest classical supercomputers running for 32,000 years. Certainly feels beyond imaginable.
  • 2²⁷⁵ is roughly the number of atoms in the universe. Don’t even think about trying it on even the largest imaginable network of largest classical supercomputers.
  • 3¹⁰ is about 59,000 operations.
  • 3¹⁰⁰ is about 5 followed by 47 zeros operations.
  • 3¹⁰⁰⁰ is … too big for even Google to figure out!
  • 3⁶⁴⁶ is about 1 followed by 308 zeros.

Quadratic complexity (quadratic speedup)

  • sqrt(100) is 10. 10 times faster than sequentially processing all items.
  • sqrt(10000) is 100. 100 times faster.
  • sqrt(1,000,000) is 1,000. 1,000 times faster.
  • sqrt(1,000,000,000,000) is 1,000,000. A million times faster.

What applications might be the most ripe for quantum advantage?

When will quantum advantage and quantum supremacy be achieved?

--

--

--

Freelance Consultant

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

Recommended from Medium

Research Paper About Human Behavior

Where to find Sulforaphane ?

Time Ltd.

The Infinite Lifecycles Of The Immortal Jellyfish

Amazing Biotechnology Gadgets Around the World

The Maine Coon Cat is a strong and cute cat. No breed has a…

#Charles eugene hill. — Aug 15, 2020

Advantages Of Positive Displacement Pumps in Drilling

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
Jack Krupansky

Jack Krupansky

Freelance Consultant

More from Medium

Qiskit 101 — How I began my quantum computing journey?

Qiskit banner

What I Learned From Fire Opal…

Quantum Entanglement

Quantum computing: Genius or dangerous?