<p>Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened with <a href="https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/" rel="nofollow noreferrer">approximate MAX3LIN</a>: a quanutm algorithm outperforming all previous known classical algorithms motivated a succesfull search for a better classical algorithm. However, as far as I know, in both these cases, the classical algorithms do not look like classical simulation of a quantum evolution.</p>

<p>I know of one paper describing a classical simulation of a quantum system allowing to outperform previously known algorithms
<em>(Full disclosure: the authors are friends of mine)</em>:</p>

<blockquote>
  <p>A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices, by
  L. Chakhmakhchyan, N. J. Cerf, R. Garcia-Patron,
  <a href="https://arxiv.org/abs/1609.02416" rel="nofollow noreferrer">arXiv:1609.02416</a> /
  <a href="https://dx.doi.org/10.1103/PhysRevA.96.022329" rel="nofollow noreferrer"><em>Phys. Rev. A</em> <strong>96</strong>, 022329</a></p>
</blockquote>

<p>This is based on the connection between the permanent and quantum optics, shown by <a href="https://en.wikipedia.org/wiki/Boson_sampling" rel="nofollow noreferrer">boson sampling</a>. In opposition to the usual approach, they look at states who are well known to be easy to simulate (thermal states), and use this simulation to perform a Monte-Carlo computation of the permanent of Hermitian positive semidefinite matrices. For some classes of matrices, this algorithm gives a better approximation than the best previously known algorithm (Gurvits algorithm).</p>

CC BY-SA 4.0
2018-09-11T09:56:12.033Z
2018-09-12T09:49:41.247Z
2018-09-12T09:49:41.247Z
Frédéric Grosshans
<p>Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have to mean different complexity class, it could simply be better scaling.</p>

<p>This question was inspired by the case of <a href="https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/" rel="noreferrer">efficient classical simulation of a quantum recommendation algorithm</a>.</p>

CC BY-SA 4.0
2018-09-11T00:58:35.910Z
Your question as stated doesn't really make sense. A classical simulation of a quantum algorithm is a specific kind of classical algorithm, so it can't be faster than the best classical algorithm. It could *be* the fastest known classical algorithm, but it can't be *better* since that would make it better than itself.
Craig Gidney
CC BY-SA 4.0
2018-09-11T09:18:35.020Z
I guess you meant “Outperforms the best **previously known** classical algorithm”
Frédéric Grosshans
CC BY-SA 4.0
2018-09-11T12:24:10.450Z
I thought of that caveat when I read the question, but expected it would be obvious that one of the two classical algorithms would be a "previously known" non-simulation of quantum algorithm. I know better now.
delete000
<cc.complexity-theory><quantum-computing><quantum-information>
Fast classical simulation of quantum algorithms
delete000
# Fast classical simulation of quantum algorithms

(Asked by: username_0 on 2018-09-10)

Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have to mean different complexity class, it could simply be better scaling.

This question was inspired by the case of [efficient classical simulation of a quantum recommendation algorithm](https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/).

**Tags:** cc.complexity-theory, quantum-computing, quantum-information
> **Comments:**
> **username_1**: Your question as stated doesn't really make sense. A classical simulation of a quantum algorithm is a specific kind of classical algorithm, so it can't be faster than the best classical algorithm. It could *be* the fastest known classical algorithm, but it can't be *better* since that would make it better than itself.  
> **username_2**: I guess you meant “Outperforms the best **previously known** classical algorithm”  
> **username_0**: I thought of that caveat when I read the question, but expected it would be obvious that one of the two classical algorithms would be a "previously known" non-simulation of quantum algorithm. I know better now.  

---

## 1 answers

### Answer by username_2 on 2018-09-11. Score: 8 | Accepted answer

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened with [approximate MAX3LIN](https://lucatrevisan.wordpress.com/2015/05/18/how-many-theoreticians-does-it-take-to-approximate-max-3lin/): a quanutm algorithm outperforming all previous known classical algorithms motivated a succesfull search for a better classical algorithm. However, as far as I know, in both these cases, the classical algorithms do not look like classical simulation of a quantum evolution.

I know of one paper describing a classical simulation of a quantum system allowing to outperform previously known algorithms
*(Full disclosure: the authors are friends of mine)*:

> A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices, by
> L. Chakhmakhchyan, N. J. Cerf, R. Garcia-Patron,
> [arXiv:1609.02416](https://arxiv.org/abs/1609.02416) /
> [*Phys. Rev. A* **96**, 022329](https://dx.doi.org/10.1103/PhysRevA.96.022329)

This is based on the connection between the permanent and quantum optics, shown by [boson sampling](https://en.wikipedia.org/wiki/Boson_sampling). In opposition to the usual approach, they look at states who are well known to be easy to simulate (thermal states), and use this simulation to perform a Monte-Carlo computation of the permanent of Hermitian positive semidefinite matrices. For some classes of matrices, this algorithm gives a better approximation than the best previously known algorithm (Gurvits algorithm).


---

