Fractional Quantum Advantage — Stepping Stones to Dramatic Quantum Advantage

21 min readSep 22, 2021

Achieving quantum advantage over classical computing is the holy grail goal of quantum computing, but that’s a very steep hill to climb. 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, but I generally refer to dramatic quantum advantage as being a factor of a quadrillion to emphasize that the advantage needs to be much more than a relatively minor advantage. That said, 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. This informal paper will explore various formulations for expressing fractional quantum advantage.

To put it most simply, anything less than a dramatic quantum advantage (factor of a quadrillion) would be considered a fractional quantum advantage.

In summary, a fractional quantum advantage could be specified in one of several ways:

A fraction or percentage of dramatic quantum advantage. Such as 50% (half), 90% (almost there), or 10% (a small fraction).
A qualitative degree of quantum advantage. Minimal, substantial or significant, or dramatic.
A symbolic degree. Such as one, two, or three stars, or gold, silver, or bronze.
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.
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.
A multiple of classical performance. 2X, 10X, 50X, 100X, 1,000X, 1,000,000X.
Some vague rhetorical characterization. Indicating better than classical, but not the full potential of a quantum speedup.

Topics discussed in this informal paper:

References
Quantum advantage
Three levels of quantum advantage
Fractional quantum advantage
Broad characterizations of fractional quantum advantage
More modest improvements over classical solutions
Symbolic references to degree of quantum advantage
One, two, and three star quantum advantage
Gold, silver, and bronze levels of quantum advantage
Platinum, stainless steel, and brushed aluminum levels of quantum advantage
Near quantum advantage
How many orders of magnitude faster than a classical computer?
What about factors of 2, 4, 5, 10, 20, 50, 100, 250, 500, and 1,000?
Approximate advantages for various qubit counts
Wall clock problems
Two-hour business process optimization problems
Larger wall clock problems
Some other classifications of relative performance
What is the quantum advantage of your quantum algorithm or application?
What is the net quantum advantage of your quantum algorithm or application?
Be sure to divide net quantum advantage by the number of classical processors used by an application
Raw, net, and final quantum advantage
What fraction of your application performance can really utilize a quantum algorithm effectively?
Full quantum advantage: Generation of true random numbers (TRNG)
Every fraction of quantum advantage counts
Summary and conclusions

References

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

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.

I generally refer to dramatic quantum advantage as being a factor of a quadrillion to emphasize that the advantage needs to be much more than a relatively minor advantage.

Unfortunately, that leaves us with quantum advantage without any qualifying adjectives being a fairly vague term, indicating at least some performance advantage, but unclear how much. It could be either:

Dramatic quantum advantage. My proposed threshold of a factor of a quadrillion advantage over a classical solution.
Fractional quantum advantage. Something less than dramatic quantum advantage.

The short answer is that it is context dependent — and can be either, but my recommendation is that:

Unless specified otherwise, quantum advantage implies a dramatic quantum advantage.

That won’t work in all situations, but is still the least-problematic approach.

I will still occasionally refer to quantum advantage with no descriptive qualifier, but only when I am referring to the general concept of an advantage over classical computing without trying to imply a specific advantage. For example, advising quantum algorithm designers to quantify the quantum advantage of their quantum algorithms — not implying that it must be a dramatic quantum advantage and allowing that it could be only a fractional quantum advantage.

Three levels of quantum advantage

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

Minimal quantum advantage. A 1,000X performance advantage over classical solutions. 2X, 10X, and 100X (among others) are reasonable stepping stones.
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.
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.

To put it most simply, anything less than a dramatic quantum advantage would be considered a fractional quantum advantage.

For more on those three levels of quantum advantage and my conception of dramatic quantum advantage in particular, see my paper:

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.

To put it most simply, anything less than a dramatic quantum advantage would be considered a fractional quantum advantage.

Achieving minimal, substantial or significant, or dramatic quantum advantage will be incredible feats, not easily achieved. As such, it may be worth acknowledging partial achievement of those three major milestones, which I suggest could be called fractional quantum advantage, measured as a percentage or decimal fraction of the milestone metric, or a simple integer factor of advantage over a classical solution.

For example,

1% minimum quantum advantage would be 0.01 times 1,000X or 10X.
10% minimum quantum advantage would be 0.10 times 1,000X or 100X.
50% minimum quantum advantage would be 0.50 times 1,000X or 500X.
5% substantial or significant quantum advantage would be 0.05 times 1,000,000X or 50,000X.
25% substantial or significant quantum advantage would be 0.25 times 1,000,000X or 250,000X.
1% dramatic quantum advantage would be 0.01 times one quadrillion X or ten trillion X.
0.1% dramatic quantum advantage would be 0.001 times one quadrillion X or one trillion X.
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:

Near quantum advantage. Very close to 100%, maybe high nineties, maybe even 90% or even 80%. But generally simply close enough for many purposes.
90–100%
75–90%
50–75%
50%. Halfway to full quantum advantage.
25–50%
10–25%
1–10%
0.1%
0.01%
0.001%

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:

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

Dramatic quantum advantage would be three-star, gold, or platinum.

Minimal quantum advantage would be one-star, bronze, or brushed aluminum.

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:

One star. Minimal quantum advantage — 1,000X.
Two stars. Substantial or significant quantum advantage — 1,000,000X.
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:

Gold. Three stars. Dramatic quantum advantage — one quadrillion X.
Silver. Two stars. Substantial or significant quantum advantage — 1,000,000X.
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:

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

Stainless steel is easily recognized as reasonably substantial and of solid practical utility, but nowhere close to the value of a platinum.

And brushed aluminum is easily recognized as minimal but of a workable utility value for less-demanding applications, but nowhere near as substantial as stainless steel or of the extreme value of platinum.

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.

How close is very close or near? It’s a vague concept. Possibilities include:

Very near 100%. 99.9% or even 99%.
98%.
95%.
High 90’s%.
90% or higher.
Possibly 85%.
Possibly even 80%.
Maybe even 75%. Especially in the early days, when that would be a major accomplishment.

For now, I would go with 90% as the presumed default. Maybe in a few years that might be raised to 95%. And maybe to 98% in seven years.

That said, I’m okay with people using a lower threshold for near, for now, such as 80%.

The prefix term near could be applied to the qualitative or symbolic degrees of quantum advantage, such as:

Near dramatic quantum advantage.
Near substantial quantum advantage.
Near minimum quantum advantage.
Near three-star quantum advantage.
Near silver quantum advantage.
Near platinum quantum advantage.
Near stainless steel quantum advantage.

Without any other qualifiers, what would near quantum advantage mean? Some possibilities:

Near dramatic quantum advantage.
Depends on the context. A particular context may make it clear what degree of quantum advantage is being referred to.

For now, I would presume that near quantum advantage refers to near dramatica quantum advantage. Although I don’t expect that to be very useful in the near term.

Near minimum quantum advantage might become useful within the next two years, or maybe it might take three or four years. It would be useful as the near-term goal even if it takes a few years to actually achieve.

And that would be equivalent to near one-star quantum advantage, near bronze quantum advantage, and near brushed aluminum quantum advantage.

And the actual quantum advantage would be 90% of 1,000X or 900 X.

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.

A factor of a quadrillion (10¹⁵) or a quintillion (10¹⁸) or more would clearly be a dramatic advantage, but a factor of a million (10⁶), a billion (10⁹), or even a trillion (10¹²) would be reasonably impressive, and constitute a fractional quantum advantage, even if not quite a dramatic quantum advantage.

If one can match or exceed the advantage of a quantum solution simply by adding ten, a hundred, or even 1,000 classical machines (10³), that’s not what we mean by a true, dramatic quantum advantage since those are tasks easily accomplished by any competent IT staff today — no quantum computer required.

Still, factors of 10¹, 10², 10³, 10⁴, and 10⁵ are interesting advantages over classical computing even if not even close to a dramatic quantum advantage.

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.

Be aware that an algorithm may use some ancilla qubits besides the qubits used in the Hadamard transform, so fewer qubits may be used than the processor supports.

Also, limited qubit connectivity may significantly reduce the number of available qubits which can be utilized for parallel computations under a Hadamard transform.

Some common examples:

10 qubits = ~ 1,000 parallel computations.
20 qubits = ~ 1,000,000 parallel computations.
30 qubits = ~ one billion parallel computations.
40 qubits = ~ one trillion parallel computations.
50 qubits = ~ one quadrillion parallel computations.
60 qubits = ~ one quintillion parallel computations.

Some smaller examples corresponding to what can be implemented using current quantum computers:

5 qubits = 32 parallel computations.
6 qubits = 64 parallel computations.
7 qubits = 128 parallel computations.
8 qubits = 256 parallel computations.
12 qubits = 4K parallel computations.
16 qubits = 64K parallel computations.
24 qubits = 16M parallel computations.
28 qubits = 256M parallel computations.

For current quantum computers, their Quantum Volume (QV) gives a rough indication of the total number of parallel computations which can effectively be performed. Some examples:

QV 32 = 5 qubits = 32 parallel computations.
QV 64 = 6 qubits = 64 parallel computations.
QV 128 = 7 qubits = 128 parallel computations.
QV 256 = 8 qubits = 256 parallel computations.
QV 512 = 9 qubits = 512 parallel computations.
QV 1024 = 10 qubits = 1024 parallel computations.
QV 2048 = 11 qubits = 2048 parallel computations.
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.

The point here is that if a quantum solution can complete within that designated time interval while no economical classical solution can, then there is a clear quantum advantage, even if fairly minimal in absolute terms.

In fact, I would go so far as to suggest that there is quantum supremacy since no classical solution can do the job acceptably. Granted the classical solution might take only moderately longer and the quantum solution might have only a seemingly minor relative advantage, the mere fact that it is a wall clock problem which cannot be acceptably solved with a classical solution indicates quantum supremacy. The actual quantum advantage might be relatively small, but enough to make all of the difference in the world to the organization employing it.

That said, such narrow constraints might be relatively atypical — generally a few hours won’t matter, but the point of wall clock problems is that they are the cases where even relatively small amounts of time can matter a lot.

Once we have separated out wall clock problems, we can focus on the remaining problems where actual quantum advantage is expected to be very large with even a factor of a thousand or a million being towards the low end of expectations and a factor of a billion, a trillion, or even more are what will be targeted with quantum solutions.

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.

Imagine a business process optimization problem such as vehicle routing which has a 2-hour window to run every day to plan out the business needs of that day, but the best classical solution takes 4 hours, meaning it doesn’t fit in the two-hour window and therefore is flat out unacceptable, so a mere 2X advantage for a quantum solution is a big win. Or if the best classical solution took 3 hours, even a mere 50% quantum advantage would be a big win.

But these are extreme examples. After all, there are always a thousand tricks to get a 50% to 2X improvement for any classical solution, especially with cheap commodity clusters of machines and a smarter, more elite technical team. That said, it could well be that the three or four-hour classical solution is in fact the best optimization that the best classical team could muster, so I suspect that there are indeed plenty of such two-hour optimization problems out there.

A bigger benefit would come if a more sophisticated optimization algorithm which provides more functional features but might take a full eight hours or a full day or two or even a week or month to run a classical solution, while a quantum solution could get the job done well within that required 2-hour window. That might mean a quantum advantage of 10X to 300X.

In any case, an actual quantum advantage far short of 1,000,000X or even short of 1,000X might be sufficient.

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.

Some possible time intervals:

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

Many design applications may take a lengthy amount of time, but a quantum solution (or the classical equivalent) which can complete in 10–20% or 1–2% of the total time may be completely acceptable.

These might be problems where a classical solution takes great amounts of time — days, weeks, months, or even theoretically years if you actually tried to implement it — but a quantum solution is still acceptable even if it still takes hours, days, weeks, or even a month. But a quantum solution in seconds or a few minutes won’t necessarily provide much of an advantage over a solution in a few hours or even a few days.

A full dramatic quantum advantage of a quadrillion speedup may not be necessary. A speedup of 1,000X, 100X, or even 10X may be sufficient. Or maybe a speedup in the 1,000,000X may actually be needed, but still well-short of a full, dramatic quantum advantage or even a billion X.

The point is that the difference in wall clock time between a quantum and classical solution must be very meaningful to the organization. A mere raw performance advantage with no tangible business value is no real advantage to the organization.

Some other classifications of relative performance

Alternatively, consider these degrees of quantum advantage:

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.
Near parity with classical. Ditto.
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.
Moderately better than classical. Like 2X to 20X.
Well above classical. Like 50X to1,000X.
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.
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.
Full dramatic quantum advantage. A factor of a quadrillion over the best classical solution.
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.

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 since quantum computations are inherently both noisy and probabilistic. And they are probabilistic by nature even if all noise and errors were to be eliminated.

Once discounted by the shot count, the raw quantum advantage becomes the net quantum advantage.

Characterizing the shot count is especially problematic as the size of the input data grows. Shot count will almost certainly also grow as input size grows, but at what rate is unclear.

Some common shot count discount factors:

10.
100.
1,000.
10,000.
100,000.
1,000,000.
10,000,000.

In truth, there’s no upper limit, other than the fact that at some point the computation itself is likely to break down and fail to deliver statistically meaningful results regardless of the shot count.

For more on this topic, see my paper:

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.

The reason for this division is that we’re trying to compare solution to solution — compare the quantum solution to the classical solution.

Start with the net quantum advantage, the raw quantum advantage divided by the shot count needed to get a statistically meaningful result. See the discussion in the preceding section.

The net quantum advantage divided by the processor count gives the final quantum advantage.

For example, if a quantum computer has a net quantum advantage of 1,000X compared to a single classical processor, and the classical solution uses 10 classical processors, then the final quantum advantage would be only 1,000 divided by 10 or 100X.

Or, if the net quantum advantage was one billion, and 10,000 classical processors are used, then the final quantum advantage would be only one billion divided by 10,000 or 100,000X.

Or, if the net quantum advantage was one million, and 1,000 classical processors are used, then the final quantum advantage would be only one million divided by 1,000 or 1,000X.

This is an example of why it’s a great reason to use a quadrillion as the threshold for dramatic quantum advantage, 1,000,000X as the threshold for substantial or significant quantum advantage, and a threshold of 1,000X for minimal quantum advantage.

To reiterate, quantum advantage should be a quantum solution to classical solution comparison — at the application level, not a quantum processor to classical processor comparison — at the algorithm and processor level.

Raw, net, and final quantum advantage

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

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.
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.
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.

Generally, quantum advantage without any qualifying adjective (raw, net, final) would be presumed to refer to the final quantum advantage, unless the specific context suggests otherwise.

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.

If only 1% of the performance of a classical application is in the classical code which is converted to a quantum algorithm, then even the greatest impact of a great quantum algorithm (dramatic quantum advantage) will by definition result in no more than a 1% performance advantage. That’s not worth the effort to implement a quantum solution.

If 10% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 10% performance advantage. Again, not particularly worthwhile.

If 25% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 25% performance advantage. Again, not particularly worthwhile.

If 50% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 2X performance advantage. May or may not be worthwhile.

If 75% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 4X performance advantage.

If 80% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 5X performance advantage.

If 90% of the application performance was in the code being converted to a quantum algorithm, the resulting advantage would be no more than a 10X performance advantage.

And those advantage numbers were based on a virtually infinite and instantaneous speed for the quantum algorithm. If the quantum code was only 2X the classical code it replaced and that classical code was 50% of the overall application performance, the net overall application advantage would be only a 25% improvement, rather than the 2X cited earlier.

So, be alert as to what fraction of the overall runtime of the original application really is in the specific classical code which is being replaced with quantum code. Unless the lion share of the total application runtime (over 80%) is spent in the specific classical code being replaced by a quantum algorithm, it may not be worthwhile to go with a quantum solution.

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.

Classical computers, based on Turing Machines which can only compute mathematically computable functions, can only generate or compute pseudo-random numbers since a true random number is not computable in a mathematical sense.

You can add special hardware to a classical computer to gather entropy from the environment to generate true random numbers, but a quantum computer can trivially generate true random numbers using a Hadamard gate to put a qubit into a superposition of 0 and 1 and then measuring that qubit, randomly producing a 0 or 1 with virtually equal probability. Do that for as many random bits as you need.

This is not an example of fractional quantum advantage since it is full quantum advantage that is available on even the simplest of current real quantum computers.