<p>As claimed by Leslie G. Valiant in a seminal paper <a href="https://people.seas.harvard.edu/~valiant/holographic11-07.pdf" rel="noreferrer">1</a> of his,</p>

<blockquote>
  <p>Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not need quantum computers.</p>
</blockquote>

<p>That's an algorithmic design technique that has been used (by Valiant himself and others) to produce polynomial time algorithms for several problems that are minor variations of important NP-hard problems (more about it on wikipedia <a href="https://en.wikipedia.org/wiki/Holographic_algorithm" rel="noreferrer">2</a>).</p>

CC BY-SA 4.0
2019-02-09T13:50:16.233Z
2019-02-09T13:50:16.233Z
Alessandro Cosentino
<p>There's also a recent work on <a href="https://arxiv.org/abs/1901.03254" rel="noreferrer">low-rank semidefinite programming</a> that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.</p>

CC BY-SA 4.0
2019-02-08T19:39:39.583Z
2019-02-08T19:39:39.583Z
Ewin
<p>The quantum Monte Carlo quantum annealing (QMC-QA<sup>1</sup>) or discrete-time simulated quantum annealing (SQA<sup>2</sup>) algorithm(s) performed better than the tested D-Wave device in <a href="https://arxiv.org/abs/1401.2910" rel="nofollow noreferrer">recent</a> <a href="https://arxiv.org/abs/1705.07452" rel="nofollow noreferrer">studies</a>:</p>

<blockquote>
  <p>We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin.</p>
</blockquote>

<p>Since both the D-Wave device and SQA outperform SA for certain problem instances, this gives the impression that SQA is a sort of quantum-inspired algorithm. The newer study testing the D-Wave 2000Q processor also finds that its performance correlates better with a <a href="https://arxiv.org/abs/1401.7087" rel="nofollow noreferrer">proposed classical model</a> labeled "spin-vector Monte Carlo (SVMC) algorithm" in that study than with SQA:</p>

<blockquote>
  <p>We use this to argue that a key reason for the quantum annealer’s slowdown relative to SQA is its sub-optimally high temperature, which causes it to behave more like SVMC. Thus, the strong performance of SQA on the logical-planted instance class suggests that this class is a good target or basis for the exploration of an eventual quantum speedup using QA hardware.</p>
</blockquote>

<hr>

<p>If we ignore the background D-Wave story, can we still conclude that SQA is a quantum-inspired optimization algorithm that outperforms classical simulated annealing (and maybe other optimization algorithms) for certain problems? It depends. If the goal is actually to find the ground state of some quantum system, then the answer is yes. But if the goal is to have a general purpose optimization algorithm similar to simulated annealing, then the answer is no.</p>

<hr>

<ol>
<li><sub>Martoňák, R., Santoro, G. E. &amp; Tosatti, E. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. <em>Phys. Rev. B</em> <strong>66</strong>, 094203 (2002).  URL <a href="http://link.aps.org/doi/10.1103/PhysRevB.66.094203" rel="nofollow noreferrer">http://link.aps.org/doi/10.1103/PhysRevB.66.094203</a></sub></li>
<li><sub>Santoro, G. E., Martoňák, R., Tosatti, E. &amp; Car, R. Theory of quantum annealing of an Ising spin glass. <em>Science</em> <strong>295</strong>, 2427–2430 (2002). URL <a href="http://dx.doi.org/10.1126/science.1068774" rel="nofollow noreferrer">http://dx.doi.org/10.1126/science.1068774</a>.</sub></li>
</ol>

CC BY-SA 4.0
2019-02-10T19:11:57.550Z
2019-02-10T19:11:57.550Z
Thomas Klimpel
<p>There is a whole body of work to do with quantum inspired evolutionary algorithms(QIEA), with actual algorithms that use quantum computation techniques, see  <a href="https://dl.acm.org/citation.cfm?id=1997732" rel="nofollow noreferrer"> survey (source ACM) </a>. Another quantum inspired algorithm uses it in <a href="https://www.researchgate.net/publication/215635872_Quantum-Inspired_Evolutionary_Algorithm_for_Numerical_Optimization" rel="nofollow noreferrer">numerical optimization</a>. </p>

CC BY-SA 4.0
2019-02-10T06:59:31.897Z
2019-02-10T06:59:31.897Z
user3483902
<p>Take a look at quantum-inspired linear genetic programming. This algorithm aims to induce computer programs in imperative languages. E.g.:</p>

<ul>
<li><p><a href="https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming" rel="nofollow noreferrer">https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming</a></p></li>
<li><p>Quantum-Inspired Linear Genetic Programming as a Knowledge Management System,
August 2013, The Computer Journal 56(9):1043-1062,
Douglas Mota Dias and Marco Aurelio C. Pacheco
<a href="https://doi.org/10.1093/comjnl/bxs108" rel="nofollow noreferrer">https://doi.org/10.1093/comjnl/bxs108</a></p></li>
</ul>

CC BY-SA 4.0
2019-05-02T00:32:45.280Z
2019-05-02T00:32:45.280Z
Douglas Mota Dias
<p>Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:</p>

<ul>
<li><a href="https://arxiv.org/abs/1807.04271" rel="noreferrer">A quantum-inspired classical algorithm for recommendation systems</a></li>
<li><a href="https://arxiv.org/abs/1811.00414" rel="noreferrer">Quantum-inspired classical algorithms for principal component analysis and supervised clustering</a></li>
<li><a href="https://arxiv.org/abs/1811.04909" rel="noreferrer">Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension</a></li>
<li><a href="https://arxiv.org/abs/1811.04852" rel="noreferrer">Quantum-inspired sublinear classical algorithms for solving
low-rank linear systems</a></li>
</ul>

<p>and for Max 3LIN:</p>

<ul>
<li><a href="https://arxiv.org/abs/1505.03424" rel="noreferrer">Beating the random assignment on constraint satisfaction problems of bounded degree</a>.</li>
</ul>

<p>It may be very useful to compile a list of all known classical algorithms inspired from quantum computing. What other examples are known?</p>

<quantum-computing><randomized-algorithms>
List of quantum-inspired algorithms
Juan Miguel Arrazola
# List of quantum-inspired algorithms

(Asked by: username_0 on 2019-02-07)

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:

* [A quantum-inspired classical algorithm for recommendation systems](https://arxiv.org/abs/1807.04271)
* [Quantum-inspired classical algorithms for principal component analysis and supervised clustering](https://arxiv.org/abs/1811.00414)
* [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://arxiv.org/abs/1811.04909)
* [Quantum-inspired sublinear classical algorithms for solving
  low-rank linear systems](https://arxiv.org/abs/1811.04852)

and for Max 3LIN:

* [Beating the random assignment on constraint satisfaction problems of bounded degree](https://arxiv.org/abs/1505.03424).

It may be very useful to compile a list of all known classical algorithms inspired from quantum computing. What other examples are known?

**Tags:** quantum-computing, randomized-algorithms


---

## 5 answers

### Answer by username_1 on 2019-02-09. Score: 6 | Accepted answer

As claimed by Leslie G. Valiant in a seminal paper [1](https://people.seas.harvard.edu/~valiant/holographic11-07.pdf) of his,

> Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not need quantum computers.

That's an algorithmic design technique that has been used (by Valiant himself and others) to produce polynomial time algorithms for several problems that are minor variations of important NP-hard problems (more about it on wikipedia [2](https://en.wikipedia.org/wiki/Holographic_algorithm)).


---

### Answer by username_2 on 2019-02-08. Score: 9

There's also a recent work on [low-rank semidefinite programming](https://arxiv.org/abs/1901.03254) that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.


---

### Answer by username_3 on 2019-02-10. Score: 3

The quantum Monte Carlo quantum annealing (QMC-QA1) or discrete-time simulated quantum annealing (SQA2) algorithm(s) performed better than the tested D-Wave device in [recent](https://arxiv.org/abs/1401.2910) [studies](https://arxiv.org/abs/1705.07452):

> We establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing: we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95% confidence, over the range of problem sizes that we can test. However, we do not find evidence for a quantum speedup: simulated quantum annealing exhibits the best scaling by a significant margin.

Since both the D-Wave device and SQA outperform SA for certain problem instances, this gives the impression that SQA is a sort of quantum-inspired algorithm. The newer study testing the D-Wave 2000Q processor also finds that its performance correlates better with a [proposed classical model](https://arxiv.org/abs/1401.7087) labeled "spin-vector Monte Carlo (SVMC) algorithm" in that study than with SQA:

> We use this to argue that a key reason for the quantum annealer’s slowdown relative to SQA is its sub-optimally high temperature, which causes it to behave more like SVMC. Thus, the strong performance of SQA on the logical-planted instance class suggests that this class is a good target or basis for the exploration of an eventual quantum speedup using QA hardware.

---

If we ignore the background D-Wave story, can we still conclude that SQA is a quantum-inspired optimization algorithm that outperforms classical simulated annealing (and maybe other optimization algorithms) for certain problems? It depends. If the goal is actually to find the ground state of some quantum system, then the answer is yes. But if the goal is to have a general purpose optimization algorithm similar to simulated annealing, then the answer is no.

---

1. Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. *Phys. Rev. B* **66**, 094203 (2002). URL <http://link.aps.org/doi/10.1103/PhysRevB.66.094203>
2. Santoro, G. E., Martoňák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an Ising spin glass. *Science* **295**, 2427–2430 (2002). URL <http://dx.doi.org/10.1126/science.1068774>.


---

### Answer by username_4 on 2019-02-10. Score: 3

There is a whole body of work to do with quantum inspired evolutionary algorithms(QIEA), with actual algorithms that use quantum computation techniques, see  [survey (source ACM)](https://dl.acm.org/citation.cfm?id=1997732) . Another quantum inspired algorithm uses it in [numerical optimization](https://www.researchgate.net/publication/215635872_Quantum-Inspired_Evolutionary_Algorithm_for_Numerical_Optimization).


---

### Answer by username_5 on 2019-05-02. Score: 1

Take a look at quantum-inspired linear genetic programming. This algorithm aims to induce computer programs in imperative languages. E.g.:

* <https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming>
* Quantum-Inspired Linear Genetic Programming as a Knowledge Management System,
  August 2013, The Computer Journal 56(9):1043-1062,
  username_5 and Marco Aurelio C. Pacheco
  <https://doi.org/10.1093/comjnl/bxs108>


---

