11
$\begingroup$

I have a question concerning "quantum-inspired" algorithms. There seem to be several types of algorithms that fall into this category. Some examples are:

I know this is still a new and growing field but does anyone have a reference or resource that discusses things like all the different types of quantum-inspired algorithms, their applicability, advantages/disadvantages, practicalities, which ones are actually in use today etc.?

If none exists, then maybe we can slowly start making this thread a good resource by a collection of answers :)

This question is a more fleshed out version of this previous question: What are quantum inspired algorithms?

Thanks!

Updates

27 Oct 2022: A recent preprint came out showing how to perform a Fourier Transform using Tensor Networks with results indicating that it is faster than the FFT algorithm on "many classes of functions." Could it be a promising candidate for a legitimate and practically useful quantum-inspired algorithm?

9 Sep 2023: I found this paper where the authors discuss some examples which they separate into 3 categories (Fig 3.). I think their categorization is in a slightly different context to the question I asked, but still some nice food for thought!

$\endgroup$
2
  • $\begingroup$ Please see this Quanta magazine article for some more discussion. Anything the article links to, and/or anything linking thereto, might satisfy some of your desirables. $\endgroup$ May 25, 2022 at 17:54
  • $\begingroup$ Thanks for the link Mark! The article dates back to 2018 and mentions "a boom in quasi-quantum classical algorithms". However it mainly discusses that quantum algorithms face the challenge of performing better than the current state of the art (regular) classical algorithms. Unfortunately the only mentions of quantum-inspired algorithms are IBM's simulation of the supremacy experiment and Calude's quantum-inspired algorithm, which they later removed from the article as there is "a strong debate... as to whether the quasi-quantum algorithm solves the same problem that the original algorithm" $\endgroup$ May 25, 2022 at 19:10

1 Answer 1

4
+25
$\begingroup$

My reply is by no means an answer to your question. However, I still would like to drop in my 2 cents.

The notion of "quantum-inspired" algorithms has no formal definition and has a rather broad and interpretable meaning.

I've seen some papers that called their work "quantum" just because some classical part of their algorithm was remotely "inspired" or "motivated" by some quantum process. See this for example. The authors pitch their classical algo as "quantum-based".

Now, there are more "quantumy" classical algorithms which actually attempt to solve problems by classically simulating/approximating quantum processes. A good example would be a Simulated Bifurcation Machine. This is a more "quantum-inspired" algo than my first reference. The machine actually works and can handle complex problems. A number of people in the industry work on different hardware- and software-based implementations.

Then, there is, of course, Digital annealing, which is inspired by D-Wave's Quantum annealing. Basically, it is another CMOS-based Ising machine. It was tested and benchmarked. The thing seems to work alright.

We also have quantum-inspired graph neural networks for solving combinatorial problems. In this work, quantum-inspiredness is reflected in the treatment of a neural network. The neural network is conceptualized as an ansatz. According to the results in the paper, it works and can generalize to larger problems. But overall, it seems a bit impractical.

Also, the references in the OP post suggest that we can cook up "quantum-inspired" algorithms by introducing some concepts from quantum theory and then adding randomness together with sampling techniques. It seems like a good general recipe, and all the references above support this idea.

Some quantum algorithms can be simulated efficiently on classical hardware (Gottesman-Knill theorem). So any such a quantum algorithm can be "retailored" into a classical algorithm and branded as "quantum-inspired".

Overall, the concept of "quantum-inspired" algorithms is no different from the concept of "biologically-inspired" algorithms (e.g. evolutionary and swarm algorithms, neural nets etc) or any other "X-inspired" stuff. If you are very creative... You can come up with biologically-quantum-inspired algorithm... Again, see my first reference for that kind of stuff.

Although my answer is heavily biased toward optimization problems, hopefully, I could convince you that the word "quantum-inspired" is used quite liberally and sometimes intentionally misused for various reasons. Also, it is worth pointing out that the majority of "quantum-inspired" algorithms are heuristics and, as a result, possess many trade-offs.

$\endgroup$
3
  • $\begingroup$ Thanks for your perspective! I think I agree with it and I appreciate the interesting examples! I was wondering if there are any with benchmarks on problems that are of practical relevance? Because in principle (maybe aside from Ewin's dequantization algorithms which are a bit special), any quantum-inspired algorithm which performs "better" (either provably or heuristically) compared to the state-of-the-art should be implementable today giving great performance improvements, right? I imagine that would make some spash! $\endgroup$ Oct 27, 2022 at 8:03
  • 1
    $\begingroup$ @RajivKrishnakumar Most of the algorithms and papers that are shared actually solve or include benchmarking results of industry-level problems. Knowing how to solve these problems faster is of practical importance in many fields of science and industry. Quantum-inspired algorithms like SBM and Digital Annealer are implemented and deployed today. $\endgroup$
    – MonteNero
    Nov 16, 2022 at 23:26
  • 1
    $\begingroup$ As for your second question... there is no one magic-bullet algorithm that is better than everything else. This is due to the No Free Lunch theorem, which roughly speaking states that the better performance on one class of problems is offseted by a worse performance on a different class of problems. So if there is a "splash", it will happen in a very localized and small domain. But if it is localized and small, you will not hear about this splash unless you are part of that domain. $\endgroup$
    – MonteNero
    Nov 16, 2022 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.