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.

  • 1
    $\begingroup$ 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. $\endgroup$ Sep 11, 2018 at 0:58
  • $\begingroup$ I guess you meant “Outperforms the best previously known classical algorithm” $\endgroup$ Sep 11, 2018 at 9:18
  • $\begingroup$ 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. $\endgroup$
    – delete000
    Sep 11, 2018 at 12:24

1 Answer 1


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: 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 / Phys. Rev. A 96, 022329

This is based on the connection between the permanent and quantum optics, shown by 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).


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.