Classically-Inspired Quantum Algorithms Considered Harmful and the Need for Quantum-Native Algorithms

We need more quantum-native algorithms — where the quantum algorithm designer starts fresh, with a clean slate, and with no classical baggage to mess up their thinking, fully exploiting the power of quantum computing, most notably, quantum parallelism to achieve an exponential speedup. The goal is to fully exploit all three of the triad of quantum computing resources — superposition, entanglement, and interference — to achieve dramatic and massive quantum parallelism.

The purpose of this short note is twofold:

1. To suggest a new term for a lot of the misguided approaches being pursued for designing quantum algorithms — classically-inspired quantum algorithms.
2. To encourage the design of quantum algorithms which are native to quantum computing — quantum-native algorithms.

Caution: Be careful not to confuse classically-inspired quantum algorithms with quantum-inspired classical algorithms. The two are very different.

Caveat: The concern here is the implementations of classical algorithms, the code, not the math of algorithms per se. After all, there is only one, universal math that functions for both classical and quantum systems. So inspiration from classical math is definitely fair game, such as Shor’s factoring algorithm being inspired or informed by the math of Euler and Miller, such as order-finding and discrete Fourier transforms, as long as the quantum implementation is exploiting massive quantum parallelism rather than incremental or iterative classical algorithms and their classical implementations (code.) And little bits and pieces of a quantum algorithm can come almost directly from classical math or even classical code, as in exponentiation and the inner calculation of quantum Fourier transform in Shor’s factoring algorithm, again as long as the quantum implementation is focused on exploiting massive quantum parallelism rather than incremental or iterative classical algorithms and their classical implementations (code.)

I think most people have gotten the message that they can’t expect to simply recompile their classical code and that it will magically run exponentially faster on a quantum computer.

But we still have a lot of people trying shoe-horn classical programming techniques into quantum computing. I guess the thinking is that given a big enough hammer, one can pound the squarest peg into the roundest hole. Yeah, sure, one can do that, but… somehow the results will always seem… suboptimal.

The overall approach is to identify aspects of the classical algorithm which are at least relatively compatible with quantum computing, and massage them the best you can to create the basic quantum algorithm, and then use a hefty amount of classical glue and Bondo to flesh out the rest of the algorithm as a hybrid of classical and quantum approaches.

Sure, one can certainly do this, but once again, it is a fool’s errand to expect a magical exponential speedup relative to the original classical algorithm.

I propose a new term for the products of this (misguided) process, “classically-inspired quantum algorithms”. Or “classical-inspired quantum algorithms”. Or, “classically-inspired quantum algorithm” or “classical-inspired quantum algorithm” if you prefer a singular.

Generally, I’ll simply refer to classically-inspired quantum algorithms.

I figured the term is likely already in use, but a quick Google search for “classically-inspired quantum algorithms” came up with zero results! Ditto for when I changed classically to classical. I did get one result each when I changed algorithms to algorithm.

So, at least so far, there isn’t much harm with using this new term as I’ve suggested.

There are two main forms of classically-inspired quantum algorithms at present:

1. Variational methods.
2. Monte Carlo Simulation.

To be clear these are both perfectly respectable and very useful approaches for classical computing.

But neither is a serious attempt to fully exploit the primary benefit of quantum computing, quantum parallelism, where a relatively brief calculation is performed in parallel on all values in the solution space, delivering the promised exponential speedup.

Variational methods exploit some degree of parallelism, but nowhere near the full solution space. They generally process only a very small patch of the solution space before they need to resort to an optimization step to restart the search for a solution with a revised starting point. Whether a variational approach provides any advantage over the original classical algorithm is dubious at best. My only point here is that variational methods don’t exploit the full power of quantum parallelism for the full solution space in one fell swoop.

The whole point of Monte Carlo Simulation is to evaluate solutions at random, which virtually guarantees that the optimal solution won’t be found for a very large solution space, or at least not very quickly. No exponential speedup, even on a quantum computer.

Both approaches only work if you apply sufficient tricks and shortcuts, which is fine for classical algorithms, but once again fails to exploit total, massive quantum parallelism.

If the best solution that you can imagine is a variational method or a Monte Carlo Simulation, it’s best to stick to a classical solution, and look to classical techniques such as a better implementation, a simplified implementation, or classical parallelism, including distributed clusters.

There are undoubtedly many other variations of classically-inspired quantum algorithms; variational methods and Monte Carlo Simulation are only most common and serve to highlight the issue here.

There are many ways to skin a quantum cat. All that really matters is that they serve the goal of fully exploiting all three of the triad of quantum computing resources — superposition, entanglement, and interference — to achieve dramatic and massive quantum parallelism.

Exactly what it’s going to take to shift people from classically-inspired quantum algorithms to quantum-native algorithms remains to be seen and is beyond the scope of this brief note, whose purpose is simply to highlight the problem and the need for a solution.

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