Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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).
