Existe-t-il des exemples de cas où la simulation classique d'un algorithme quantique pour un problème surpasse le meilleur algorithme classique précédemment connu pour ce problème? "Surperformances" ne signifie pas nécessairement une classe de complexité différente, il pourrait simplement s'agir d'une meilleure mise à l'échelle.
Cette question s'inspire du cas de la simulation classique efficace d'un algorithme de recommandation quantique .
Réponses:
Votre question a été inspirée par le récent progrès classique inspiré de l'algorithme de recommandation quantique. Notez que ce n'est pas la première fois qu'une telle chose se produit. En 2015, des développements similaires se sont produits avec approximativement MAX3LIN : un algorithme de quanutm surpassant tous les précédents algorithmes classiques connus a motivé une recherche réussie d'un meilleur algorithme classique. Cependant, autant que je sache, dans ces deux cas, les algorithmes classiques ne ressemblent pas à une simulation classique d'une évolution quantique.
Je connais un article décrivant une simulation classique d'un système quantique permettant de surpasser les algorithmes précédemment connus (Divulgation complète: les auteurs sont mes amis) :
Ceci est basé sur la connexion entre l'optique permanente et l'optique quantique, montrée par l' échantillonnage des bosons . Contrairement à l'approche habituelle, ils examinent des états bien connus pour être faciles à simuler (états thermiques) et utilisent cette simulation pour effectuer un calcul Monte-Carlo de la matrice permanente de matrices semi-finies positives hermitiennes. Pour certaines classes de matrices, cet algorithme donne une meilleure approximation que le meilleur algorithme précédemment connu (algorithme Gurvits).
la source