Fractional Quantum Advantage — Stepping Stones to Dramatic Quantum Advantage

  1. A fraction or percentage of dramatic quantum advantage. Such as 50% (half), 90% (almost there), or 10% (a small fraction).
  2. A qualitative degree of quantum advantage. Minimal, substantial or significant, or dramatic.
  3. A symbolic degree. Such as one, two, or three stars, or gold, silver, or bronze.
  4. A fraction or percentage of a qualitative or symbolic degree of quantum advantage. Such as 50% substantial quantum advantage or 75% one-star quantum advantage.
  5. Near quantum advantage. Roughly 90–95% or closer to some qualitative or symbolic degree of quantum advantage. Such as near dramatic quantum advantage, near substantial quantum advantage, or near two-star quantum advantage.
  6. A multiple of classical performance. 2X, 10X, 50X, 100X, 1,000X, 1,000,000X.
  7. Some vague rhetorical characterization. Indicating better than classical, but not the full potential of a quantum speedup.
  1. References
  2. Quantum advantage
  3. Three levels of quantum advantage
  4. Fractional quantum advantage
  5. Broad characterizations of fractional quantum advantage
  6. More modest improvements over classical solutions
  7. Symbolic references to degree of quantum advantage
  8. One, two, and three star quantum advantage
  9. Gold, silver, and bronze levels of quantum advantage
  10. Platinum, stainless steel, and brushed aluminum levels of quantum advantage
  11. Near quantum advantage
  12. How many orders of magnitude faster than a classical computer?
  13. What about factors of 2, 4, 5, 10, 20, 50, 100, 250, 500, and 1,000?
  14. Approximate advantages for various qubit counts
  15. Wall clock problems
  16. Two-hour business process optimization problems
  17. Larger wall clock problems
  18. Some other classifications of relative performance
  19. What is the quantum advantage of your quantum algorithm or application?
  20. What is the net quantum advantage of your quantum algorithm or application?
  21. Be sure to divide net quantum advantage by the number of classical processors used by an application
  22. Raw, net, and final quantum advantage
  23. What fraction of your application performance can really utilize a quantum algorithm effectively?
  24. Full quantum advantage: Generation of true random numbers (TRNG)
  25. Every fraction of quantum advantage counts
  26. Summary and conclusions

References

For reference, some of my previous writing on quantum advantage:

  1. What Is Quantum Advantage and What Is Quantum Supremacy?
    https://jackkrupansky.medium.com/what-is-quantum-advantage-and-what-is-quantum-supremacy-3e63d7c18f5b
  2. What Is Dramatic Quantum Advantage?
    https://jackkrupansky.medium.com/what-is-dramatic-quantum-advantage-e21b5ffce48c
  3. What Is the Quantum Advantage of Your Quantum Algorithm?
    https://medium.com/@jackkrupansky/what-is-the-quantum-advantage-of-your-quantum-algorithm-8f481aefe8d0
  4. Quantum Advantage Now: Generation of True Random Numbers
    https://medium.com/@jackkrupansky/quantum-advantage-now-generation-of-true-random-numbers-237d89f8a7f2

Quantum advantage

There is no generally accepted qualitative or numeric metric for how much of a performance advantage of a quantum solution over a classical solution constitutes true quantum advantage.

  1. Dramatic quantum advantage. My proposed threshold of a factor of a quadrillion advantage over a classical solution.
  2. Fractional quantum advantage. Something less than dramatic quantum advantage.
  • Unless specified otherwise, quantum advantage implies a dramatic quantum advantage.

Three levels of quantum advantage

In the broadest terms, I suggest three levels of quantum advantage:

  1. Minimal quantum advantage. A 1,000X performance advantage over classical solutions. 2X, 10X, and 100X (among others) are reasonable stepping stones.
  2. Substantial or significant quantum advantage. A 1,000,000X performance advantage over classical solutions. 20,000X, 100,000X, and 500,000X (among others) are reasonable stepping stones.
  3. Dramatic quantum advantage. A one quadrillion X (one million billion times) performance advantage over classical solutions. 100,000,000X, a billion X, and a trillion X (among others) are reasonable stepping stones.

Fractional quantum advantage

I do think that we should generously reward all incremental progress towards the lofty holy grail goal of dramatic quantum advantage over classical computing. I refer to such incremental progress as fractional quantum advantage.

  1. 1% minimum quantum advantage would be 0.01 times 1,000X or 10X.
  2. 10% minimum quantum advantage would be 0.10 times 1,000X or 100X.
  3. 50% minimum quantum advantage would be 0.50 times 1,000X or 500X.
  4. 5% substantial or significant quantum advantage would be 0.05 times 1,000,000X or 50,000X.
  5. 25% substantial or significant quantum advantage would be 0.25 times 1,000,000X or 250,000X.
  6. 1% dramatic quantum advantage would be 0.01 times one quadrillion X or ten trillion X.
  7. 0.1% dramatic quantum advantage would be 0.001 times one quadrillion X or one trillion X.
  8. 0.0001% dramatic advantage would be 0.000001 times one quadrillion X or one billion X.

Broad characterizations of fractional quantum advantage

Here are a few broad characterizations of fractional quantum advantage, again they may all be applied to either minimum, substantial, or dramatic quantum advantage, but here I’ll leave out the adjective for brevity:

  1. Near quantum advantage. Very close to 100%, maybe high nineties, maybe even 90% or even 80%. But generally simply close enough for many purposes.
  2. 90–100%
  3. 75–90%
  4. 50–75%
  5. 50%. Halfway to full quantum advantage.
  6. 25–50%
  7. 10–25%
  8. 1–10%
  9. 0.1%
  10. 0.01%
  11. 0.001%

More modest improvements over classical solutions

For more modest improvements over classical solutions:

  1. 1,000,000X
  2. 1,000X
  3. 100X
  4. 50X
  5. 20X
  6. 10X
  7. 4X
  8. 3X (200%)
  9. 2X (100%)
  10. 75%
  11. 50%
  12. 25%

Symbolic references to degree of quantum advantage

Sometimes a simpler form of reference is desirable rather than some detailed numeric specification. Here are three categories of symbolic reference to degree of quantum advantage:

  1. Stars. One, two, and three star quantum advantage.
  2. Prize medal metals. Gold, silver, and bronze levels of quantum advantage.
  3. Alternative metals. Platinum, stainless steel, and brushed aluminum levels of quantum advantage. To more realistically reflect the relative differences.

One, two, and three star quantum advantage

To avoid ambiguity or confusion of terms, the three major levels of quantum advantage could be labeled with star ratings:

  1. One star. Minimal quantum advantage — 1,000X.
  2. Two stars. Substantial or significant quantum advantage — 1,000,000X.
  3. Three stars. Dramatic quantum advantage — one quadrillion X.

Gold, silver, and bronze levels of quantum advantage

An alternative to star levels of quantum advantage would be contest prize medal metals:

  1. Gold. Three stars. Dramatic quantum advantage — one quadrillion X.
  2. Silver. Two stars. Substantial or significant quantum advantage — 1,000,000X.
  3. Bronze. One star. Minimal quantum advantage — 1,000X.

Platinum, stainless steel, and brushed aluminum levels of quantum advantage

A disadvantage of the traditional gold, silver, bronze contest prize medal metal model is that the performance differences between the top three winners can be very modest, so it would be more helpful to have metals which emphasize wider relative distinctions between the levels, such as:

  1. Platinum. Gold. Three stars. Dramatic quantum advantage — one quadrillion X.
  2. Stainless steel. Silver. Two stars. Substantial or significant quantum advantage — 1,000,000X.
  3. Brushed aluminum. Bronze. One star. Minimal quantum advantage — 1,000X.

Near quantum advantage

It will be some time before quantum computers and quantum algorithms and applications achieve true, full, dramatic quantum advantage, so in the spirit of rewarding all progress we should especially reward coming very close to quantum advantage.

  1. Very near 100%. 99.9% or even 99%.
  2. 98%.
  3. 95%.
  4. High 90’s%.
  5. 90% or higher.
  6. Possibly 85%.
  7. Possibly even 80%.
  8. Maybe even 75%. Especially in the early days, when that would be a major accomplishment.
  1. Near dramatic quantum advantage.
  2. Near substantial quantum advantage.
  3. Near minimum quantum advantage.
  4. Near three-star quantum advantage.
  5. Near silver quantum advantage.
  6. Near platinum quantum advantage.
  7. Near stainless steel quantum advantage.
  1. Near dramatic quantum advantage.
  2. Depends on the context. A particular context may make it clear what degree of quantum advantage is being referred to.

How many orders of magnitude faster than a classical computer?

Generally, I would say that true, dramatic quantum advantage is more than a few orders of magnitude (powers of ten) advantage over a classical computer.

What about factors of 2, 4, 5, 10, 20, 50, 100, 250, 500, and 1,000?

Even a quantum solution which is only ten or twenty times faster, or even four or five times faster than a classical solution is still interesting for many niche applications — especially for wall clock problems, as discussed in the next section, but I would call such quantum solutions fractional quantum advantage or partial quantum advantage rather than full dramatic quantum advantage since they aren’t delivering the full, promised potential of quantum computing.

Approximate advantages for various qubit counts

If n qubits will be used in a Hadamard transform to perform a quantum computation in parallel, 2^n parallel computations can be performed, giving an approximate performance advantage of 2^n.

  1. 10 qubits = ~ 1,000 parallel computations.
  2. 20 qubits = ~ 1,000,000 parallel computations.
  3. 30 qubits = ~ one billion parallel computations.
  4. 40 qubits = ~ one trillion parallel computations.
  5. 50 qubits = ~ one quadrillion parallel computations.
  6. 60 qubits = ~ one quintillion parallel computations.
  1. 5 qubits = 32 parallel computations.
  2. 6 qubits = 64 parallel computations.
  3. 7 qubits = 128 parallel computations.
  4. 8 qubits = 256 parallel computations.
  5. 12 qubits = 4K parallel computations.
  6. 16 qubits = 64K parallel computations.
  7. 24 qubits = 16M parallel computations.
  8. 28 qubits = 256M parallel computations.
  1. QV 32 = 5 qubits = 32 parallel computations.
  2. QV 64 = 6 qubits = 64 parallel computations.
  3. QV 128 = 7 qubits = 128 parallel computations.
  4. QV 256 = 8 qubits = 256 parallel computations.
  5. QV 512 = 9 qubits = 512 parallel computations.
  6. QV 1024 = 10 qubits = 1024 parallel computations.
  7. QV 2048 = 11 qubits = 2048 parallel computations.
  8. QV 4096 = 12 qubits = 4096 parallel computations.

Wall clock problems

I define a wall clock problem as a problem which must be solved in some defined time interval, typically measured in hours and possibly minutes, where a solution which takes longer than that designated interval is effectively useless since the organization has a mission critical need which must be met in that time interval or the organization is considered to have failed to fulfill its mission. Taking much longer than that designated interval will incur dramatic pain, anxiety, cost, lost business, unhappy customers, lost opportunity, or some other dramatic and unacceptable outcome.

Two-hour business process optimization problems

Usually we focus attention on using quantum computers to solve really big problems that might take years, decades, or even centuries on a classical computer or even a large cluster of classical computers or a classical supercomputer, but there are some relatively small problems where quantum computers could still deliver a quantum advantage, even if minimal relative to a dramatic quantum advantage. One category of such problems is what I call two-hour optimization problems.

Larger wall clock problems

Nominally, wall clock problems are measured in hours, but the same concept can be applied to problems where the time interval is measured in days, weeks, or even months. For these larger wall clock problems the functional definition is the same — the organization has a mission-critical need and a maximum allowable time interval.

  1. A day or two. Might be meaningful for an application which is run on the weekend, part of a weekly process.
  2. A week or two. Might be meaningful for some design process which occurs over a small number of months.
  3. A month or two. Might be meaningful for some process which occurs over many months or even a year or more.

Some other classifications of relative performance

Alternatively, consider these degrees of quantum advantage:

  1. Below classical. There might in fact be problems which can be more easily solved on a quantum computer, such as simulating physics or chemistry, or generation of true random numbers, but not necessarily faster, just easier.
  2. Near parity with classical. Ditto.
  3. Modestly better than classical. Like 10–50% faster. Generally not of much value, but could still be of value for some wall clock problems, where time is critical.
  4. Moderately better than classical. Like 2X to 20X.
  5. Well above classical. Like 50X to1,000X.
  6. Better than even a massively parallel or distributed classical solution. 10,000X to 1,000,000X. May be easier to manage even if not providing a solution that was not achievable at all using classical methods.
  7. Degrees of advantage over parallel and distributed classical solutions. Comparable to 2, 4, 8, 10, 16, 20, 25, 32, 48, 64, 80, 96, 128, 256, 512, 1K, 2K, 4K, 8K, 16K, 32K, 50K, 64K, 75K, or 100K classical processors in either a massively parallel or distributed classical solution.
  8. Full dramatic quantum advantage. A factor of a quadrillion over the best classical solution.
  9. Amazingly above classical. True quantum supremacy — classical can’t even get the job done with any realistic level of resources and time.

What is the quantum advantage of your quantum algorithm or application?

As should be abundantly clear by now, quantum advantage is not simply a boolean yes or no, but a degree of advantage relative to a classical solution. Quantum algorithm designers and application developers should endeavor to quantify what their actual quantum advantage really is.

  1. 10.
  2. 100.
  3. 1,000.
  4. 10,000.
  5. 100,000.
  6. 1,000,000.
  7. 10,000,000.

What is the net quantum advantage of your quantum algorithm or application?

Just to re-emphasize that the net quantum advantage of a quantum algorithm or application should be used when discussing the quantum advantage of a quantum algorithm or application, not the raw quantum advantage, which must be discounted by the shot count.

Be sure to divide net quantum advantage by the number of classical processors used by an application

Whether dealing with a classical supercomputer or a cluster of classical commodity processors, the proper performance advantage metric is to take the performance advantage of a single quantum computer over a single classical computer and divide by the number of classical processors used in the classical solution.

Raw, net, and final quantum advantage

Just to summarize the preceding three sections, we have three stages of calculating quantum advantage:

  1. Raw quantum advantage. What the quantum algorithm actually does. n qubits in a Hadamard transform produces 2^n quantum states (product states), implying a raw quantum advantage of 2^n. While the comparable classical code sequence evaluates a single linear computation, the quantum circuit accomplishes 2^n evaluations in a single quantum circuit execution.
  2. Net quantum advantage. Discount raw quantum advantage by the number of circuit repetitions (shot count) to yield the net quantum advantage. The shot count indicates how many times the quantum circuit must be run to generate and process enough results to develop a statistically meaningful result, the expectation value. Repetitions are needed in part because quantum computations are noisy (errors), but also because quantum computations are probabilistic by nature even if there were no noise or errors per se.
  3. Final quantum advantage. Divide the net quantum advantage by the number of classical processors required by the classical solution, to get the final quantum advantage, which is the advantage of the quantum solution over the classical solution, not merely a quantum processor to single classical processor comparison.

What fraction of your application performance can really utilize a quantum algorithm effectively?

A typical application has a lot more code than the rather small portion that can be converted from a classical algorithm to a quantum algorithm, so any measurement, calculation, or estimation of overall application performance needs to include the total application, including all of the classical code.

Full quantum advantage: Generation of true random numbers (TRNG)

One very interesting odd case where quantum computers have a functional advantage over classical computers is the generation of true random numbers, known as TRNG — True Random Number Generation.

Every fraction of quantum advantage counts

Achieving true, full, dramatic quantum advantage is a monumental, intimidating goal. Progress towards that lofty goal will be fairly slow.

Summary and conclusions

  1. Full, dramatic quantum advantage is a factor of a quadrillion better than the best classical solution.
  2. A fractional quantum advantage could be a relatively minor advantage, a fairly major advantage, a notable fraction of full dramatic quantum advantage, or anything between.
  3. Minimal quantum advantage. A 1,000X performance advantage over classical solutions. 2X, 10X, and 100X (among others) are reasonable stepping stones.
  4. Substantial or significant quantum advantage. A 1,000,000X performance advantage over classical solutions. 20,000X, 100,000X, and 500,000X (among others) are reasonable stepping stones.
  5. Relatively minor advantages such as 2X to 100X could still be of significant value for wall clock problems where time is limited, so if a classical solution cannot complete the task within that critical time interval, then a quantum solution which can will be a meaningful advantage to the organization regardless of how small a fraction of full dramatic quantum advantage it might be.
  6. The raw quantum advantage of a quantum algorithm or application must be discounted (divided) by the shot count or circuit repetitions which are required to achieve a statistically meaningful quantum result to get the net quantum advantage.
  7. Be sure to divide net quantum advantage by the number of classical processors used by an application, so that the comparison is quantum solution to classical solution — at the application level, not simply quantum algorithm to classical algorithm at the processor level.
  8. We should reward all increments of progress towards dramatic quantum advantage. Every fraction counts. Eventually, some day, all quantum solutions will offer dramatic quantum advantage, but we’re not there yet, not even close.

--

--

Freelance Consultant

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