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
    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 Sep 11 at 0:58
  • I guess you meant “Outperforms the best previously known classical algorithm” – Frédéric Grosshans Sep 11 at 9:18
  • 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 Sep 11 at 12:24
up vote 6 down vote accepted

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

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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