<p>There is at least one example that I can remember, but there are probably more that I am not aware of.</p>

<p>Recently, Maarten Van den Nest and Wolfgang Dürr found a  new <a href="http://arxiv.org/abs/1304.2879">classical algorithm</a> (arXiv:1304.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices.  Their algorithm is completely <em>classical</em>, but several connections to <em>quantum</em> physics are employed in the design (read below). The algorithm was found to be exponentially faster than previously known algorithms that solve the same problem, at the time of writing*.</p>

<p>*I am ignorant of whether better classical or quantum algorithms have been found a posteriori.</p>

<p>So, there are at least <strong>two quantum ingredients</strong> used in the design of the VdND algorithm. On the one hand, the authors use a classical-quantum connection between classical Ising models and <em>topological quantum systems</em> (precisely, some color codes). On the other hand, the authors use classical techniques to <em>simulate quantum systems</em> in the derivation of the algorithm: in their proof, they first write a small quantum algorithm for the problem of interest; then, the authors show how to simulate the former quantum  algorithm efficiently on a classical computer, obtaining a classical algorithm (this is rather remarkable, in my view).</p>

CC BY-SA 3.0
2014-07-26T15:08:33.283Z
2014-07-26T15:24:18.613Z
2014-07-26T15:24:18.613Z
Juan Bermejo Vega
<p><a href="http://arxiv.org/abs/0910.3376">Quantum Proofs for Classical Theorems</a> by Andrew Drucker and Ronald de Wolf is a very nice survey on this topic.</p>

<p>One of the first classical results obtained by thinking about the problem quantumly was a communication complexity lower bound for the inner product function by <a href="http://arxiv.org/abs/quant-ph/9708019">Cleve, van Dam, Nielsen and Tapp</a>. </p>

CC BY-SA 3.0
2014-07-27T18:32:59.307Z
2014-07-28T14:35:00.377Z
2014-07-28T14:35:00.377Z
Martin Schwarz
<p>A couple more links on connections and analogies between quantum physics, quantum computation and (classical) computer science (to the already posted answers).</p>

<p>The survey paper of <a href="http://arxiv.org/abs/0910.3376" rel="nofollow">Drucker and de Wolf</a> is already mentioned.</p>

<p>A <a href="http://quantum.phys.cmu.edu/QIP/simulation.pdf" rel="nofollow">presentation</a> on simulating quantum computers with (classical) probabilistic models (and references thereof).</p>

<p>A somewhat older paper on $PP$, $BQP$ and $PostBQP$ computation classes (arxiv, 2004).
<a href="http://arxiv.org/abs/quant-ph/0412187" rel="nofollow">Quantum Computing, Postselection, and Probabilistic Polynomial-Time</a></p>

<p>Relations between (classical <em>hard</em>) computation and <a href="http://en.wikipedia.org/wiki/Renormalization" rel="nofollow">renormalization techniques</a> in statistical and quantum field theory (arxiv):</p>

<p><a href="http://arxiv.org/abs/0904.4921" rel="nofollow">Renormalization and computation I: motivation and background</a></p>

<p><a href="http://arxiv.org/abs/0908.3430" rel="nofollow">Renormalization and Computation II: Time Cut-off and the Halting Problem</a></p>

<p><a href="http://arxiv-web3.library.cornell.edu/abs/cs/0608053v2" rel="nofollow">Renormalization group approach to the P versus NP question</a></p>

<p>Further connections in this direction in Baez, Stay (arxiv):
<a href="http://arxiv.org/abs/0903.0340" rel="nofollow">Physics, Topology, Logic and Computation: A Rosetta Stone</a></p>

<p>A (thermodynamic) Turing Machine which can compute (quantum) Hadamard transforms (arxiv):
<a href="http://arxiv.org/abs/0904.3273" rel="nofollow">A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks</a></p>

<p>Finally a review on <em>Quantum Annealing and Computation</em> connections (arxiv, 2013):
<a href="http://arxiv.org/abs/1310.1339" rel="nofollow">Quantum Annealing and Computation: A Brief Documentary Note</a></p>

CC BY-SA 3.0
2014-07-29T15:10:19.457Z
2014-07-29T15:10:19.457Z
Nikos M.
<p>To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?</p>

CC BY-SA 3.0
2014-07-25T21:34:40.160Z
cf [classical computing embraces quantum ideas](http://www.simonsfoundation.org/quanta/20121218-classical-computing-embraces-quantum-ideas/) Wolchover/Simons inst
vzn
<ds.algorithms><quantum-computing>
Are there any cases where quantum has given insight for classical algorithms?
hadsed
# Are there any cases where quantum has given insight for classical algorithms?

(Asked by: username_0 on 2014-07-25)

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?

**Tags:** ds.algorithms, quantum-computing
> **Comments:**
> **username_1**: cf [classical computing embraces quantum ideas](http://www.simonsfoundation.org/quanta/20121218-classical-computing-embraces-quantum-ideas/) Wolchover/Simons inst  

---

## 3 answers

### Answer by username_2 on 2014-07-26. Score: 11

There is at least one example that I can remember, but there are probably more that I am not aware of.

Recently, Maarten Van den Nest and Wolfgang Dürr found a new [classical algorithm](http://arxiv.org/abs/1304.2879) (arXiv:1304.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices. Their algorithm is completely *classical*, but several connections to *quantum* physics are employed in the design (read below). The algorithm was found to be exponentially faster than previously known algorithms that solve the same problem, at the time of writing\*.

\*I am ignorant of whether better classical or quantum algorithms have been found a posteriori.

So, there are at least **two quantum ingredients** used in the design of the VdND algorithm. On the one hand, the authors use a classical-quantum connection between classical Ising models and *topological quantum systems* (precisely, some color codes). On the other hand, the authors use classical techniques to *simulate quantum systems* in the derivation of the algorithm: in their proof, they first write a small quantum algorithm for the problem of interest; then, the authors show how to simulate the former quantum algorithm efficiently on a classical computer, obtaining a classical algorithm (this is rather remarkable, in my view).


---

### Answer by username_3 on 2014-07-27. Score: 10

[Quantum Proofs for Classical Theorems](http://arxiv.org/abs/0910.3376) by Andrew Drucker and Ronald de Wolf is a very nice survey on this topic.

One of the first classical results obtained by thinking about the problem quantumly was a communication complexity lower bound for the inner product function by [Cleve, van Dam, Nielsen and Tapp](http://arxiv.org/abs/quant-ph/9708019).


---

### Answer by username_4 on 2014-07-29. Score: 1

A couple more links on connections and analogies between quantum physics, quantum computation and (classical) computer science (to the already posted answers).

The survey paper of [Drucker and de Wolf](http://arxiv.org/abs/0910.3376) is already mentioned.

A [presentation](http://quantum.phys.cmu.edu/QIP/simulation.pdf) on simulating quantum computers with (classical) probabilistic models (and references thereof).

A somewhat older paper on $PP$, $BQP$ and $PostBQP$ computation classes (arxiv, 2004).
[Quantum Computing, Postselection, and Probabilistic Polynomial-Time](http://arxiv.org/abs/quant-ph/0412187)

Relations between (classical *hard*) computation and [renormalization techniques](http://en.wikipedia.org/wiki/Renormalization) in statistical and quantum field theory (arxiv):

[Renormalization and computation I: motivation and background](http://arxiv.org/abs/0904.4921)

[Renormalization and Computation II: Time Cut-off and the Halting Problem](http://arxiv.org/abs/0908.3430)

[Renormalization group approach to the P versus NP question](http://arxiv-web3.library.cornell.edu/abs/cs/0608053v2)

Further connections in this direction in Baez, Stay (arxiv):
[Physics, Topology, Logic and Computation: A Rosetta Stone](http://arxiv.org/abs/0903.0340)

A (thermodynamic) Turing Machine which can compute (quantum) Hadamard transforms (arxiv):
[A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks](http://arxiv.org/abs/0904.3273)

Finally a review on *Quantum Annealing and Computation* connections (arxiv, 2013):
[Quantum Annealing and Computation: A Brief Documentary Note](http://arxiv.org/abs/1310.1339)


---

