Other Than Generating Random Numbers and Greater Performance, There Isn’t Anything That a Quantum Computer Can Compute That a Classical Computer Can’t Compute

35 min readMar 15, 2023

The only real benefit of a quantum computer is quantum parallelism, the ability to execute a computation over a very wide range of distinct values in one fell swoop. In other words, a great performance advantage over a classical solution. There is the one special advantage of the ability to generate and operate on true random numbers, but other than that, there is nothing that a quantum computer can do or compute or compute better that a classical computer can’t compute, even if more slowly. Despite this fact, there continue to be dubious claims of quantum computers getting better results even without relying on better performance. This informal paper explores the nuances of this key attribute of quantum computing.

Sure, a quantum computer can compute in less than a second, or mere seconds or minutes or hours what would take a classical computer years, decades, or centuries to compute, but in the end, the results of the computation will be the same, except that a higher error rate and the fact that quantum computation is inherently probabilistic by nature means that frequently a quantum computer won’t get the correct answer at all, so the overall parallel computation must be repeated a significant number of times in order to statistically weed out all of the incorrect results. But if all goes well, the quantum result should match the classical result — if the classical computer could ever manage to finish the computation if quantum parallelism is sufficiently high.

This all relies on a true apples to apples comparison of algorithms — the classical and quantum algorithms have to both be focused on calculating the same result. But, for a variety of reasons, to be explored in this informal paper, the two algorithms may not be focused on calculating the same result.

Caveat: My comments here are all focused only on general-purpose quantum computers. Some may also apply to special-purpose quantum computing devices, but that would be beyond the scope of this informal paper. For more on this caveat, see the section on analog quantum computing devices as well as my informal paper:

Topics discussed in this informal paper:

In a nutshell
Motivation for this informal paper
Beware of claims that a quantum computer can produce better results
Functional benefit vs. performance advantage
No, capacity is not a functional advantage
Beware of illusions of functional benefits that turn out to not be all that they claim to be
Be sure to do an apples to apples comparison
If there is a functional difference, then it’s not an apples to apples comparison and the quantum and classical algorithms are not comparable
Reasons for discrepancies between classical and quantum results
Be careful not to compare a great quantum algorithm to a mediocre classical algorithm
Make sure to use the same count of distinct values to assure an apples to apples comparison
Sorry I don’t have a mathematical proof
Based on current vision for quantum computing
May not be true for some radical revision of the current vision for quantum computing
Won’t be true if and when we can design a quantum computer which can fully simulate human intelligence
Tight integration of quantum sensors or quantum imaging with a quantum computer might be a functional advantage that a classical computer cannot match
Special case for approximations
Quantum-inspired classical algorithms
Back-filling the classical algorithm based on improvements made in the quantum algorithm
Little data with a big solution space
Very good at searching for needles in haystacks
Quantum parallelism
Quantum advantage
The secret sauce of quantum computing is quantum parallelism
Superposition, entanglement, and interference are what enable quantum parallelism
Is the physics of a quantum computer any different? No, not really for the most part, other than superconductors
No, there isn’t any magic in a quantum computer, just physics and clever engineering and algorithms
Combinatorial explosion — moderate number of parameters but very many combinations
What can’t a quantum computer compute?
Quantum computers are not a good fit for Big Data
Analog quantum computing devices may indeed compute values that classical solutions may not be able to compute, but there are issues
Only interested in practical applications, not extreme or contrived computer science experiments
Beware of hype, fraud, shams, exaggerations, and false, inaccurate, or misleading comparisons
Generating true random numbers — the only true functional advantage a quantum computer has over a classical computer
Alternative titles
Conclusions

In a nutshell

Your classical algorithm isn’t necessarily going to be much faster on a quantum computer. Not all application problems have faster quantum solutions.
Your classical algorithm may not even be able to run on a quantum computer. Lack of control structures, data types, I/O, database and network access, and lack of general support for Big Data.
A quantum computer simply can’t compute better results than a classical computer. With the exceptions of generating true random numbers and greater performance.
A quantum computer offers a performance advantage but not a functional advantage. And even the performance advantage might not always be achievable. And the exception that generating true random numbers is a functional advantage of quantum computers.
No, capacity is not a functional advantage. Function refers to what is computed, the final result. Capacity and performance are joined at the hip, but performance of a classical computer will suffer long before capacity becomes an issue, so, generally, capacity will never be the limiting factor giving a quantum computer an advantage — it will always be a performance advantage, and definitely not a functional advantage.
The secret sauce of quantum computing is quantum parallelism. That’s it. That’s all. That’s what enables the performance advantage.
Quantum advantage. Expresses how much more powerful a quantum solution is compared to a classical solution.
Superposition, entanglement, and interference are what enable quantum parallelism. They offer no other functional effect or benefit, although superposition does enable generation of true random numbers as well.
Is the physics of a quantum computer any different? No, not really for the most part, other than superconductors. Physics is the same… everywhere in the universe. Quantum computers don’t have any special physics — other than superconductors.
No, there isn’t any magic in a quantum computer, just physics and clever engineering and algorithms. Can’t bypass or exceed the laws of physics. Only an exponential performance advantage at best. And the generation of true random numbers, which some might consider magic, but it’s the simplest form of magic.
Any perceived functional advantage of a quantum computer is just an illusion. With a little work, the illusion can be eliminated. With the exception of generating true random numbers.
The quantum result may not be comparable to the classical result due to any number of technical factors which amount to failure to achieve an apples to apples comparison. All of thos technical factors can be overcome, but it requires diligence and potentially some hard work.
Be sure to do an apples to apples comparison. Eliminate any technical differences that are not necessary and may be causing a difference in the results.
Be careful not to compare a great quantum algorithm to a mediocre classical algorithm. The classical algorithm may need to be updated or even completely redesigned to perform a true apples to apples comparison. Make sure it’s the algorithms that you are comparing, not the skills and quality of the teams designing the algorithms.
Make sure to use the same count of distinct values to assure an apples to apples comparison. That could account for a different result.
Sorry I don’t have a mathematical proof, but that’s not really needed. Just look at the computations which can be performed by rotations of the Bloch sphere or by multiplying unitary transformation matrices. There’s nothing there that a classical computer can’t compute.
Based on the current vision for quantum computing. The thesis of this informal paper is based not just on current, existing, and near-term quantum computers, but the general vision of general-purpose quantum computing extending out well beyond the next five to ten years.
May not be true for some radical revision of the current vision for quantum computing. Once we go out further into the future, to ten or fifteen or even twenty years or further, there is no telling what the vision for quantum computing might evolve into, and whether the thesis of this informal paper will or will not still be true.
Won’t be true if we design a quantum computer which can fully simulate human intelligence. By definition, that will require capabilities beyond the standard Turing machine model of classical computing. But this won’t be possible with the current vision for quantum computing.
Tight integration of quantum sensors or quantum imaging with a quantum computer might be a functional advantage that a classical computer cannot match. The quantum computer could directly operate on the quantum state of the quantum sensors. There is no way for a classical computer to directly operate on the quantum state of quantum sensors. Whether such tight integration would be both theoretically valid and practical remains to be seen. Much research would be required.
There may indeed be special cases when approximations are involved. Methods for approximation could indeed differ between quantum and classical algorithms. But generally, even these can be eliminated, with a little care.
Quantum-inspired classical algorithms have some potential.
Back-filling the classical algorithm based on improvements made in the quantum algorithm may have some potential.
Little data with a big solution space is the ideal use case for quantum computing. Evaluate a relatively simple computation over a very large solution space. Searching for a needle in a huge haystack.
Analog quantum computing devices may indeed compute values that classical solutions may not be able to compute, but there are issues. Generally, this informal paper only applies to general-purpose quantum computers, not specialized quantum computing devices, some of which operate in an analog mode.
Only interested in practical applications, not extreme or contrived computer science experiments. You can almost always come up with contrived computer science experiments which can show whatever conclusion you want to show. Rather, stay focused on practical real-world applications.
Beware of hype, fraud, shams, exaggerations, and false, inaccurate, or misleading comparisons. Generally, don’t believe everything that you read. Always check with more reliable sources.

Motivation for this informal paper

The main motivation for this informal paper is that I have seen reports that even without a performance advantage, current quantum computers are sometimes able to compute a better result than a classical solution. This simply doesn’t make any sense — there’s no good reason to expect that absent a performance advantage that a quantum computer could conceivably achieve a better result than a classical solution.

Generally, the only way that the quantum result could be better or even merely different than the classical result (absent a performance advantage) would be that an apples to apples comparison is not being performed — something must be different in the quantum and classical algorithms to explain the difference.

And any difference must be a mistake since there really isn’t anything that a quantum computer can compute better than a classical computer, except for the one exception of generating and using true random numbers. And the difference of the potential performance advantage, but that is not a functional advantage (different result) unless the classical solution is unable to run long enough to achieve a final result.

Beware of claims that a quantum computer can produce better results

The ultimate goal for quantum computing is to generate results much faster, dramatically faster than is possible on even the fastest classical computers. As this informal paper highlights, there should not be any significant functional difference in the results that can be achieved on a quantum computer compared to the results that can be achieved on a classical computer. The only significant difference should be performance.

Faster, yes, but functionally better, no.

There are exceptions, as will be discussed later, but as long as a true apples to apples comparison is done of a quantum algorithm and its comparable classical algorithm, the results should be the same, or at least very close.

Functional benefit vs. performance advantage

Just to clarify terminology, the whole thrust of this informal paper is to distinguish performance advantage — quantum advantage — from functional advantage (or functional benefit) — a difference in the results of a quantum computation which have some sort of functional benefit, such as a more accurate number.

Performance advantage is of course the whole point of pursuing quantum computing.

But along the way, some people have perceived that they can achieve some sort of function benefit distinct from any performance advantage. Typically this occurs when people are unable to achieve a meaningful quantum performance advantage due to the limitations of near-term quantum computing hardware. Or they are not performing a true apples to apples comparison.

This informal paper will examine and discuss perceived functional benefits — and why they aren’t typically as real as they are claimed.

No, capacity is not a functional advantage

No, capacity is not a functional advantage for a quantum computer. Function refers to what is computed, the final result.

Capacity and performance are joined at the hip. They’re generally not separable.

But performance of a classical computer will suffer long before capacity becomes an issue.

A classical loop can run for a very long time, but you can only append data to memory or storage for a finite amount of time before you run out of memory or storage. But it will take a lot of iterations of the loop to use up that memory or storage. And generally we’re interested in compute-intensive algorithms and applications rather than vast amounts of intermediate data.

So, generally, capacity will never be the limiting factor giving a quantum computer an advantage — it will always be a performance advantage.

And it definitely won’t be a functional advantage since it doesn’t involve a difference in what is computed as the final result.

Beware of illusions of functional benefits that turn out to not be all that they claim to be

As will be discussed, it is indeed very possible to give the illusion that there is some functional benefit (non-performance benefit) of a quantum algorithm compared to a classical algorithm, but mere appearance is not sufficient to demonstrate actual functional advantage.

As will be discussed there are any number of factors that can offer the illusion of advantage but turn out to not be significant functional advantage after all once you start digging into the details.

Be sure to do an apples to apples comparison

We can’t really compare the classical and quantum solutions to an application problem unless we are doing a true apples to apples comparison of algorithms — the classical and quantum algorithms have to both be focused on calculating the same result. But, for a variety of reasons, the two algorithms may not be focused on calculating the same result at all.

Some reasons that the comparison does not end up being an apples to apples comparison:

An elite team laser-focused on exploiting quantum computing can easily outperform a less-motivated classical team. Their quantum algorithm may in fact be functionally superior, not because that same functional benefit cannot be achieved in a classical algorithm, but simply because the quality of the team or available resources and time is greater than the quality, resources, or time of the team who designed the classical algorithm. The goal is to compare the best that the technologies can support, not the quality of the teams themselves.
Quantum team may be forced to take shortcuts or implement limited functionality due to limits of existing quantum hardware. They are able to get better results than a great classical approach because they are implementing a subset of the functionality that the classical team implemented. It’s best to retrofit those same identical shortcuts and limits to functionality in the classical solution so that it is a true apples to apples comparison.
The quantum team may have been given simplified functionality to implement for a more focused application problem relative to a more general and more functional task originally assigned to the classical team. Not an apples to apples comparison.
If you run your classical and quantum implementations of the same algorithm for the same input and same parameters, you should get the same result. But, the quantum results are probabilistic, so you need to look at the expected value from a batch of repeated executions rather than individual results.

If there is a functional difference, then it’s not an apples to apples comparison and the quantum and classical algorithms are not comparable

Just to reiterate that there should be no functional difference between the results from classical and quantum algorithms. The comparison needs to be restricted to apples to apples comparisons. If the results differ significantly, the comparison is not valid.

The goal is not to achieve different results, but to achieve the same results much faster, dramatically faster.

Reasons for discrepancies between classical and quantum results

We can’t really compare the classical and quantum solutions for an application problem unless we are doing a true apples to apples comparison of algorithms — the classical and quantum algorithms have to both be focused on calculating the same result. But, for a variety of reasons, the two algorithms may not be focused on calculating the same result.

Here are some of the ways that classical and quantum algorithms can end up delivering different results, even if superficially identical results are expected:

Solving somewhat or even subtly different application problems. It might be intentional, such as an evolution or change in interest or focus, or it might be unintentional, such as a miscommunication, misunderstanding, or simple mistake. If the two algorithms are clearly (or not so clearly) implementing somewhat or subtly different functionality, it should be no surprise if the functional results might differ.
Really are fundamentally distinct algorithms. Not an apples to apples comparison.
Differing assumptions. The algorithms may be basically the same, but use different assumptions. In particular, the quantum algorithm may be based on simplifying assumptions which might end up speeding up the quantum algorithm, but end up producing somewhat different results.
Inputs not perfectly identical. Maybe the algorithms are actually the same, but different input data is used. This may end up simplifying and speeding up the calculation.
Maybe different input parameters. Even with identical input data, different input parameters might be used. Again, this may end up simplifying and speeding up the calculation. For example, better tuning of ansatz values. Extra effort may be exerted by the quantum team to compensate for otherwise poor results due to limitations of current quantum hardware.
Different number of distinct values evaluated. Since a quantum computer can take advantage of quantum parallelism and evaluate a very large number of distinct values simultaneously, that gives it an inherent performance advantage over a classical computer which must evaluate each distinct value one at a time (or a few in parallel using threads, multiple cores, or distributed computing), so that it will be common for the classical solution to evaluate a much more limited number of distinct values, which can result in a different final result than the quantum solution after evaluating a much larger number of distinct values. But if the count of distinct values is a parameter, this is essentially the same as saying that the input parameters should be identical — if run for the same number of distinct values, the quantum and classical solutions should arrive at the same final result.
Differences in precision of calculations. Such as expensive and slow floating point in the classical algorithm. Again, the quantum algorithm may benefit from simplifying assumptions about required precision. And the classical algorithm may be intended to be more general.
Special vs. general solution. The classical algorithm may be intended to be more general, while the quantum algorithm may be tailored to the needs of a specific application or niche requirements.
Different limitations. Classical computers are quite general, quantum computers not so much. Near-term and NISQ hardware can force limitations that functionally wouldn’t normally be considered — and likely weren’t needed for the classical implementation.
Different functional effects. The original intent might well be for the quantum algorithm to be functionally identical, but it might not work out that way. Differences might be incidental, unintentional, intentional but believed to be insignificant, or a willingness to settle for a specialized and higher performance quantum solution.
Differences in buildup of subtle errors. Each stage of the algorithm might have the possibility of introducing subtle errors, even for classical algorithms, but the specific errors might not be functionally identical between the classical and quantum algorithms.
Use of Monte Carlo simulation or other approximate methods. The classical result is to be expected to be only an approximation, while the quantum solution may indeed evaluate all possible values to achieve the theoretically best result. A judgment call will be needed to judge whether the approximated result is good enough or not. If the solution space is set to be small enough, the Monte Carlo solution can actually hit all possible values, at least in a statistical sense. But, if the classical solution is a Monte Carlo Simulation, this is probably an apples to apples comparison almost by definition. Better to compare the quantum algorithm to a brute force classical algorithm which efficiently evaluates all possible solutions in a deterministic manner, to get a fair comparison — that achieves the same functional results for both algorithms.
A quantum-inspired classical algorithm would be a more appropriate comparison. Regardless of where the functional differences arise with an existing classical algorithm, a quantum-inspired classical implementation of the quantum algorithm has a great chance of eliminating any functional differences in the results. And if this does happen, it clearly demonstrates that there is no functional benefit to the quantum algorithm. There may indeed still be a significant performance advantage for the quantum algorithm, but that of course is the essential goal anyway.

Be careful not to compare a great quantum algorithm to a mediocre classical algorithm

In some cases it may indeed appear that a quantum algorithm is producing a better result than a classical algorithm. As noted above, be careful not to compare two fundamentally distinct algorithms — an apples to apples comparison is necessary to claim a valid functional advantage. Also as noted previously, a quantum algorithm produced by an elite team laser-focused on exploiting quantum computing can easily outperform a less-motivated classical team.

It can take some effort to assure that the classical algorithm has all the care and attention that the quantum algorithm was given.

Yes, a great quantum algorithm can indeed produce better results than a mediocre classical algorithm, so first you need to assure that the classical algorithm is updated to take advantage of all of the assumptions and limitations utilized by the quantum algorithm, so that a true apples to apples comparison can be made.

Make sure to use the same count of distinct values to assure an apples to apples comparison

Just to emphasize that although a dramatically higher count of distinct values can dramatically improve quantum results, any performance comparison must use the same count of distinct values for both the classical and quantum algorithms, thus assuring identical functional results, or at least close.

It is to be expected that a classical algorithm may not be able to implement higher counts of distinct values, since that’s the whole point of pursuing a quantum solution. But comparisons can be made using significantly smaller counts of distinct values.

For example, both classical and quantum algorithms could be tested for 1,000 and a million distinct values to confirm that they are comparable — that they get identical or near-identical functional results.

But then the quantum algorithm could be run for a billion, a trillion, or a quadrillion distinct values or more — all executed in parallel, courtesy of quantum parallelism — even though such counts of distinct values are not practical for classical algorithms.

The performance at 1,000 and a million distinct values can then be compared — and extrapolated to much higher counts of distinct values — to ascertain the essential performance advantage, the quantum advantage, of the quantum algorithm for production-scale applications.

If the quantum algorithm achieves different functional results at different counts of distinct values — which is to be expected, the quantum algorithm designer must then do some analysis to determine what functional result is considered acceptable, and use the count of distinct values needed to achieve that result as the basis for computing the performance advantage — the quantum advantage — for the quantum algorithm over the classical algorithm.

But this process is only valid if the classical and quantum algorithms are first confirmed to be comparable at counts of distinct values which the classical algorithm is actually able to execute in a reasonable amount of time. Then the performance advantage, based on count of distinct values, can be correctly determined (extrapolated.)

Sorry I don’t have a mathematical proof

Yes, it would be better if I could offer a mathematical proof that a classical computer can compute anything that a quantum computer can compute — other than random numbers and performance, but I don’t think one is needed at this stage.

Just look at the computations which can be performed by rotations of the Bloch sphere or by multiplying unitary transformation matrices. There’s nothing there that a classical computer can’t compute.

Based on current vision for quantum computing

The thesis of this informal paper is based not just on current, existing, and near-term quantum computers, but the general vision of general-purpose quantum computing extending out well beyond the next five to ten years.

The thesis of this informal paper will still be true once we achieve the vision of a practical quantum computer, maybe five years from now, or maybe three to seven years from now.

May not be true for some radical revision of the current vision for quantum computing

But once we go out further into the future, to ten or fifteen or even twenty years or further, there is no telling what the vision for quantum computing might evolve into.

Twenty or 25 years from now, the vision for quantum computing may have changed so radically that the thesis of this paper is no longer valid. It may indeed still be valid, but just as likely it might no longer be valid. We just can’t know or even reasonably speculate at this stage.

But as long as the current vision for quantum computing remains roughly as it is today, the thesis of this informal paper remains valid.

There may indeed be architectural changes or changes to the programming model which could change enough to invalidate the thesis of this informal paper, but there are likely plenty of architectural and programming model changes which would be significant and meaningful, but not sufficient to invalidate the thesis of this informal paper.

Won’t be true if and when we can design a quantum computer which can fully simulate human intelligence

It is relatively widely accepted that the standard Turing machine model of classical computing simply won’t ever be able to fully simulate full human intelligence. Ever.

At least some of us accept that some form of quantum effects will be needed to capture the full richness of human intelligence.

That said, it also seems virtually certain that the current vision for quantum computing will be woefully insufficient to fully simulate human intelligence. Not today. Not tomorrow. Not two or three years from now. Not five years from now. Not even ten years from now. And likely not even twenty or 25 years from now.

I do personally believe that some sort of advanced vision for quantum computing will indeed be capable of fully simulating human intelligence, eventually, but how exactly such an advanced quantum computer might function is anybody’s guess at this stage.

At that stage, the thesis of this informal paper would indeed fail — that such an advanced quantum computer would indeed be able to compute things (human intelligence) that a classical computer could not compute.

But for now, we are stuck with the current vision for quantum computing far out into the future, during which time the thesis of this informal paper will remain true.

Tight integration of quantum sensors or quantum imaging with a quantum computer might be a functional advantage that a classical computer cannot match

An interesting exception to the thesis of this informal paper would be the tight integration of quantum sensors or quantum imaging with the qubits of a quantum computer so that the quantum computer can directly operate on the quantum state of the quantum sensors.

It is quite possible that this would enable computations which are not possible with a classical computer, for the simple reason that there is no way to directly operate on the quantum state of quantum sensors from a classical computer.

But, this is a purely speculative proposal at this stage. Whether it is indeed both theoretically valid and practical remains to be seen. Much research would be required.

And, it’s certainly not a capability at present or on the near-term horizon.

So, for now, the thesis of this informal paper remains valid, pending further developments.

Special case for approximations

Generally, a fairly accurate result is needed, such as an error of only 1% or 2%, 0.1%, 0.0001%, or even smaller, but sometimes somewhat larger errors can be perfectly acceptable, such as 5%, 10%, or even 20% or 25%. Sometimes just a ballpark number is needed — an order of magnitude.

Sometimes a strictly deterministic classical solution might be required.

Sometimes a statistical approximation of a strictly deterministic solution is sufficient.

It could be that even with a relatively large number of distinct values, a classical algorithm can’t arrive at an acceptable approximation.

It could be that an extremely large number of distinct values, only possible with a quantum algorithm, is the only way to get an acceptable approximation.

It might be a fielder’s choice whether the classical solution is an acceptable approximation, or whether a quantum solution is required. Even then, it will be a fielder’s choice how close the approximation needs to be. Different applications and even different users of the same application may make distinct fielder’s choices.

In short, in such approximation cases, where a definitive functional result is not necessarily known, it won’t make a lot of sense to try to require the classical and quantum solutions to be identical for any particular count of distinct values.

Even so, generally, even these kinds of distinctions can be eliminated, with a little care. And maybe greater effort.

The classical and quantum algorithms can still be compared for smaller counts of distinct values to confirm that they are at least roughly comparable. Then the net performance advantage can be calculated (extrapolated) based on the final count of distinct values which produces the approximate result which is acceptable to the particular application or even to a particular user of that application.

But then it’s not a functional benefit over a classical solution anyway. It’s still a performance advantage, but just more difficult to assess what the particular advantage will be since it will vary between applications and even potentially between users.

Quantum-inspired classical algorithms

Sometimes what is lacking in classical algorithms is a healthy dose of creativity and cleverness. Quantum algorithms frequently have the benefit that it takes great creativity and cleverness to implement just about any solution on a quantum computer. That creativity and cleverness comes from serious outside-the-box thinking that normally doesn’t occur when designing typical classical algorithms.

Quantum-inspired classical algorithms are based on taking that creativity and cleverness and outside-the-box thinking from designing a quantum algorithm and applying it to a new approach to a classical algorithm. Sometimes, that’s all it takes to design a much better classical algorithm — a little outside-the-box thinking. Or a lot.

In summary, the process is as follows:

Design a quantum algorithm. A great quantum algorithm. Fully exploiting quantum parallelism.
Identify the elements of creativity, cleverness, and outside-the-box thinking used in the quantum algorithm.
Design a classical algorithm exploiting that same creativity, cleverness, and outside-the-box thinking as used in the quantum algorithm.

That’s the theory, but it’s more complex than that. Several distinct approaches can be used for the design of the new classical algorithm:

A direct, brute force implementation. For example, take the quantum parallelism and implement it as a flattened or iterative computation over each of the distinct values, one at a time. Even though this may be suboptimal, it will still be a reasonable benchmark for comparison against a quantum solution.
Exploit classical parallelism. Evaluate the distinct values in parallel to the extent possible on a classical computer, as multiple threads, separate computing cores, or using distributed computing.
Use Monte Carlo simulation to approximate a solution. Evaluate only a subset of the distinct values that quantum parallelism is evaluating in parallel. Not likely to achieve the same exact final functional result, but could achieve a semi-decent approximation. Classical parallelism can be exploited as well to increase the number of distinct values evaluated in a given amount of time.

In theory, those first two approaches should give the exact same result as the quantum algorithm — or an even better result if there are limitations in the quantum hardware which prevent an ideal quantum computation, or if an insufficient number of circuit repetitions are used to statistically derive a valid expectation value.

The third approach, could indeed produce a different result than the quantum algorithm, so a judgment call will be needed to judge whether the approximated result is good enough or not.

Back-filling the classical algorithm based on improvements made in the quantum algorithm

Even if a full quantum-inspired approach is not taken to implement a wholly-new classical algorithm, the creativity, cleverness, outside-the-box thinking, or simply general insight which comes from designing the quantum algorithm may suggest some interesting improvements to optimize an existing classical algorithm to achieve some potentially interesting level of performance improvement or accuracy of the final result value.

The improvement may make the classical results good enough or reduce the performance advantage of the quantum algorithm. Or maybe not. It’s at least a viable alternative to consider.

Little data with a big solution space

The ideal use case for a quantum computer has these qualities:

A small amount of input data.
A fairly simple calculation.
Apply that simple calculation to a very large solution space. Many possible values. The calculation will be replicated for each value in that large solution space, in parallel. Very quickly.
Producing a small amount of output.

Quantum computers have no ability to access files or databases, so they have no access to Big Data per se. The big solution space is the analog to Big Data in quantum computing.

Very good at searching for needles in haystacks

Essentially, a quantum computer is very good at searching for needles in haystacks. Very large haystacks, much bigger than even the largest classical computers could search. And doing it much faster.

Back to little data with a big solution space model, the huge solution space is the haystack to be searched and the solution is the needle to be found.

Quantum parallelism

As mentioned at the start, quantum parallelism is the secret sauce of quantum computing and involves evaluating a vast number of alternative solutions all at once. A single modest computation is executed once but operating on all possible values at the same time.

Essentially, a quantum computer is very good at searching for needles in haystacks. Very large haystacks, much bigger than even the largest classical computers could search. And doing it much faster.

And it was just mentioned that the optimal use of a quantum computer is for little data with a big solution space. A small amount of input data with a fairly simple calculation which will be applied to a very large solution space, producing a small amount of output.

But a difficulty with quantum parallelism is that it is not automatic — the algorithm designer must cleverly deduce what aspect of the application can be evaluated in such a massively parallel manner.

And the ugly truth is that not all algorithms can exploit quantum parallelism or exploit it fully.

Ultimately the degree of quantum parallelism is not guaranteed and will vary greatly between applications and algorithms and even depending on the input data.

The ultimate goal of quantum parallelism is quantum advantage…

Quantum advantage

Quantum advantage expresses how much more powerful a quantum solution is compared to a classical solution. It is typically expressed as either how many times faster the quantum computer is, or how many years, decades, centuries, millennia, or even millions or billions or trillions of years a classical computer would have to run to do what a quantum computer can do in mere seconds, minutes, or hours.

Ultimately, the goal is not simply to do things faster, but to make the impossible possible. To make the impractical practical. Many computations are too expensive today to be practical on a classical computer. Quantum parallelism is the means by which this is accomplished.

For more on quantum advantage, see my informal paper:

The secret sauce of quantum computing is quantum parallelism

Just to emphasize the point clearly, the secret sauce of a quantum computer is quantum parallelism, where a vast number of alternative solutions are evaluated simultaneously, all at once. A single modest computation executed once but operating on all possible values at the same time.

Superposition, entanglement, and interference are what enable quantum parallelism

People talk a lot about superposition, entanglement, and interference, but the net effect is to enable quantum parallelism.

To be clear, superposition, entanglement, and interference offer no other functional effect or benefit other than to enable quantum parallelism, the performance advantage of quantum computing.

And superposition enables generation of true random numbers as well. This quantum effect effectively flips the coin to generate a random bit value.

Is the physics of a quantum computer any different? No, not really for the most part, other than superconductors

For the most part, the physics of a classical computer are virtually identical to the physics of a quantum computer. One exception is superconductivity, but that enables quantum computing without performing any other function per se. Physics, quantum mechanics and quantum physics in particular, is the same… everywhere in the entire universe, although I’m not so sure what really happens at that level in the singularity of a black hole.

Superconductivity merely enables pairs of electrons to travel in a loop endlessly without friction or loss of energy. It lets transmon qubits do their thing without excess heat distorting the delicate quantum effects that a quantum algorithm is attempting to control and read out.

The quantum effects of quantum mechanics and quantum physics are the same, regardless of the system, including:

Quantum systems.
Quantum state.
Wave functions.
Basis states.
Probability amplitudes.
Superposition.
Entanglement.
Interference.
Measurement.

The only real difference is that in a classical computer, in a transistor, there are enough atoms that all of the quantum effects get statistically averaged away so that the results are deterministic rather than probabilistic as they are in qubits.

But whether we’re talking about a baseball, a glass of water, a bullet, or a qubit, quantum effects are… everywhere and always occurring.

What makes a quantum computer, or a qubit in particular, different is that it is a very carefully isolated quantum system so that quantum effects from other qubits or from external matter and energy in general are prevented from affecting the qubit state, and carefully controlled laser or microwave pulses can be used to control, manipulate, or read the quantum state of the qubit.

And as already noted, superposition, entanglement, and interference are utilized for either quantum parallelism, the performance advantage of quantum computing, or generation of random numbers, but not for any other functional effect different from what can be accomplished on a classical computer.

Manipulation of qubit quantum state with rotations of the Bloch sphere or multiplication of unitary transformation matrices won’t accomplish anything that a classical computer cannot accomplish — other than the generation of true random numbers, and quantum parallelism for a performance advantage.

No, there isn’t any magic in a quantum computer, just physics and clever engineering and algorithms

Sorry, but despite all of the wild promises, a quantum computer simply can’t bypass or exceed the laws of physics.

Even for its legitimately promised performance advantage, it’s only an exponential performance advantage at best.

There are plenty of interesting real world problems that we would like to solve with a quantum computer, but unfortunately too many of them require much more than a mere exponential advantage.

In short, despite the extravagant promises, quantum computing simply doesn’t have any magic to offer beyond that exponential speedup, at best.

And the generation of true random numbers. Some might consider that magic, but it’s the simplest form of magic.

Combinatorial explosion — moderate number of parameters but very many combinations

Another way of characterizing the sweet spot for quantum computing is applications which have a moderate number of parameters but a huge number of combinations or permutations of those parameters. What is called a combinatorial explosion.

The combinations of parameters can be evaluated in parallel with one simple computation, far faster than any classical computer or even any large classical supercomputer or large distributed computing cluster.

What can’t a quantum computer compute?

Quantum computers offer some awesome features, but they lack most of the features of a general purpose Turing machine which are offered by all classical computers. A quantum computer is more of a specialized coprocessor than a general purpose computer. Some of the basic features of a classical computer can be mimicked by a quantum computer, but unless your algorithm exploits quantum parallelism to a dramatic degree, it will generally not gain any significant advantage over a classical computer.

A few of the constraints on quantum computers:

No support for control structures. No conditionals, looping, function calls, or recursion.
No rich data types. Even integer and real numbers are not built in. No ability to process raw text.
Very limited algorithm size. Nothing that might take tens of thousands of lines of code.
No support for Big Data.
No support for I/O.
No support for database access.
No support for accessing network services.
No high-level programming model.
No high-level programming languages. For the quantum algorithms themselves, that is.

For more detail, see my paper:

Quantum computers are not a good fit for Big Data

Curiously, quantum computers have no ability to access files, databases, or network services, or any other source of Big Data, so Big Data is not the kind of haystack that a quantum algorithm can search. As just mentioned in little data with a big solution space, searching a huge solution space is the analog to Big Data for quantum computing. But it’s not Big Data in the classical sense.

None of the Three V’s of Big Data are appropriate for quantum computing — volume, velocity, variety.

The classical portion of a quantum application can indeed access files, databases, network services, and other sources of Big Data, but then only relatively small amounts of that data can be processed on any given invocation of a quantum algorithm, which greatly limits the value of quantum computing for processing that Big Data. Any quantum parallelism would be limited to the small amount of data contained in each chunk.

In fact, a quantum computer would only have value if the classical computing time to process a single element or chunk of Big Data was huge, which is generally not the case. Generally with Big Data the time cost comes from the large volume of data to be processed, not the time to process an individual item or modest chunk of data.

Analog quantum computing devices may indeed compute values that classical solutions may not be able to compute, but there are issues

Analog quantum computing devices, such as software-configurable physics experiments, such as neutral-atom quantum computing devices in analog mode, boson sampling devices, photonic quantum computers, and quantum annealing devices, may indeed compute values that classical computers may not be able to compute. Emphasis on may — better results are not assured.

Also, analog computations may not have the level of precision required for some computations.

And they might not have the range of magnitude for desired calculations.

In truth, so-called analog mode might better be referred to as physical simulation rather than computation since all that is happening is that a physics simulation plays out and then the final physical state is measured. No actual computation is actually occurring.

In fact, my comments here are all focused only on general-purpose quantum computers, which excludes analog quantum computing devices, by definition. Some may also apply to special-purpose quantum computing devices, but that would be beyond the scope of this informal paper. For more on this caveat, see my informal paper:

Only interested in practical applications, not extreme or contrived computer science experiments

It’s always possible to come up with contrived computer science experiments which show a clear or even dramatic benefit for classical or quantum solutions. The important thing is to make sure to stay focused on practical applications — classical and quantum solutions to production-scale practical real-world problems.

Beware of hype, fraud, shams, exaggerations, and false, inaccurate, or misleading comparisons

It is very easy for a wide range of claims to be made about the capabilities and performance of quantum computers, but such claims are not always what they seem.

Always look for confirming evidence, such as independent third-party benchmarks, to substantiate all capability and performance claims.

And carefully read any and all fine print to understand what caveats apply to the claims. Even if a claim is nominally substantiated, it may still be less than it superficially seems to be.

And if there is no fine print, a distinct lack of transparency and technical disclosure, that mere fact should set off alarm bells.

And the ultimate concern, a false comparison, a failure to do an apples to apples comparison is likely to be more common than not.

And, generally, don’t believe everything that you read. Always check with more reliable sources.

Generating true random numbers — the only true functional advantage a quantum computer has over a classical computer

As indicated at the outset, there is one functional advantage of a quantum computer over a classical computer, which is the ability to generate and operate on true random numbers.

For a general discussion of generating true random numbers with a quantum computer, see my informal paper:

Alternative titles

For my own reference, here are alternative titles which I considered for this informal paper:

Other than generating random numbers and greater performance, is there anything that a quantum computer can do that a classical computer can’t do?
Other than generating random numbers and greater performance, there isn’t anything that a quantum computer can do that a classical computer can’t do
Other than generating random numbers and greater performance, is there anything that a quantum computer can compute that a classical computer can’t compute?
Other than generating random numbers and greater performance, there isn’t anything that a quantum computer can compute that a classical computer can’t compute
Generating random numbers and greater performance are the only advantages of a quantum computer over a classical computer
A quantum computer has no advantage of over a classical computer other than generating random numbers and greater performance
No, other than generating random numbers and greater performance, there isn’t anything that a quantum computer can compute that a classical computer can’t compute
No, other than generating random numbers and greater performance, there is nothing that a quantum computer can compute that a classical computer can’t compute

And a couple of short, but less accurate titles:

There Isn’t Anything That a Quantum Computer Can Compute That a Classical Computer Can’t Compute
A Quantum Computer Can’t Compute Anything That a Classical Computer Can’t Compute

Conclusions

Your classical algorithm isn’t necessarily going to be much faster on a quantum computer. Not all application problems have faster quantum solutions.
Your classical algorithm may not even be able to run on a quantum computer. Lack of control structures, data types, I/O, database and network access, and lack of general support for Big Data.
A quantum computer simply can’t compute better results than a classical computer. With the exceptions of generating true random numbers and greater performance.
A quantum computer offers a performance advantage but not a functional advantage. And even the performance advantage might not always be achievable. And the exception that generating true random numbers is a functional advantage of quantum computers.
No, capacity is not a functional advantage. Function refers to what is computed, the final result. Capacity and performance are joined at the hip, but performance of a classical computer will suffer long before capacity becomes an issue, so, generally, capacity will never be the limiting factor giving a quantum computer an advantage — it will always be a performance advantage, and definitely not a functional advantage.
The secret sauce of quantum computing is quantum parallelism. That’s it. That’s all. That’s what enables the performance advantage.
Quantum advantage. Expresses how much more powerful a quantum solution is compared to a classical solution.
Superposition, entanglement, and interference are what enable quantum parallelism. They offer no other functional effect or benefit, although superposition does enable generation of true random numbers as well.
Is the physics of a quantum computer any different? No, not really for the most part, other than superconductors. Physics is the same… everywhere in the universe. Quantum computers don’t have any special physics — other than superconductors.
No, there isn’t any magic in a quantum computer, just physics and clever engineering and algorithms. Can’t bypass or exceed the laws of physics. Only an exponential performance advantage at best.
Any perceived functional advantage of a quantum computer is just an illusion. With a little work, the illusion can be eliminated. With the exception of generating true random numbers.
The quantum result may not be comparable to the classical result due to any number of technical factors which amount to failure to achieve an apples to apples comparison. All of thos technical factors can be overcome, but it requires diligence and potentially some hard work.
Be sure to do an apples to apples comparison. Eliminate any technical differences that are not necessary and may be causing a difference in the results.
Be careful not to compare a great quantum algorithm to a mediocre classical algorithm. The classical algorithm may need to be updated or even completely redesigned to perform a true apples to apples comparison. Make sure it’s the algorithms that you are comparing, not the skills and quality of the teams designing the algorithms.
Make sure to use the same count of distinct values to assure an apples to apples comparison. That could account for a different result.
Sorry I don’t have a mathematical proof, but that’s not really needed. Just look at the computations which can be performed by rotations of the Bloch sphere or by multiplying unitary transformation matrices. There’s nothing there that a classical computer can’t compute.
Based on the current vision for quantum computing. The thesis of this informal paper is based not just on current, existing, and near-term quantum computers, but the general vision of general-purpose quantum computing extending out well beyond the next five to ten years.
May not be true for some radical revision of the current vision for quantum computing. Once we go out further into the future, to ten or fifteen or even twenty years or further, there is no telling what the vision for quantum computing might evolve into, and whether the thesis of this informal paper will or will not still be true.
Won’t be true if we design a quantum computer which can fully simulate human intelligence. By definition, that will require capabilities beyond the standard Turing machine model of classical computing. But this won’t be possible with the current vision for quantum computing.
Tight integration of quantum sensors or quantum imaging with a quantum computer might be a functional advantage that a classical computer cannot match. The quantum computer could directly operate on the quantum state of the quantum sensors. There is no way for a classical computer to directly operate on the quantum state of quantum sensors. Whether such tight integration would be both theoretically valid and practical remains to be seen. Much research would be required.
There may indeed be special cases when approximations are involved. Methods for approximation could indeed differ between quantum and classical algorithms. But generally, even these can be eliminated, with a little care.
Quantum-inspired classical algorithms have some potential.
Back-filling the classical algorithm based on improvements made in the quantum algorithm may have some potential.
Little data with a big solution space is the ideal use case for quantum computing. Evaluate a relatively simple computation over a very large solution space. Searching for a needle in a huge haystack.
Analog quantum computing devices may indeed compute values that classical solutions may not be able to compute, but there are issues. Generally, this informal paper only applies to general-purpose quantum computers, not specialized quantum computing devices, some of which operate in an analog mode.
Only interested in practical applications, not extreme or contrived computer science experiments. You can almost always come up with contrived computer science experiments which can show whatever conclusion you want to show. Rather, stay focused on practical real-world applications.
Beware of hype, fraud, shams, exaggerations, and false, inaccurate, or misleading comparisons. Generally, don’t believe everything that you read. Always check with more reliable sources.

For more of my writing: List of My Papers on Quantum Computing.