Recuit quantique

Recuit quantique. Le recuit quantique (AQ) est un processus d'optimisation permettant de trouver le minimum global d'une fonction objectif donnée sur un ensemble donné de solutions candidates (états candidats), par un processus utilisant des fluctuations quantiques. Le recuit quantique est principalement utilisé pour des problèmes où l'espace de recherche est discret (problèmes d'optimisation combinatoire) avec de nombreux minima locaux, comme trouver l'état fondamental d'un verre de spin ou résoudre des problèmes QUBO, qui peuvent coder un large éventail de problèmes comme Max-Cut, la coloration des graphiques, SAT ou le problème du voyageur de commerce. Le terme « recuit quantique » a été proposé pour la première fois en 1988 par B. Apolloni, N. Cesa Bianchi et D. De Falco en tant qu'algorithme classique d'inspiration quantique. Il a été formulé sous sa forme actuelle par T. Kadowaki et H. Nishimori (ja) en 1998, bien qu'une variante du temps imaginaire sans cohérence quantique ait été discutée par A. B. Finnila, M. A. Gomez, C. Sebenik et J. D. Doll en 1994.

Contexte théorique

Le recuit quantique part d’une superposition mécanique quantique de tous les états possibles (états candidats) avec des poids égaux. Ensuite, le système évolue selon l’équation de Schrödinger dépendant du temps, une évolution mécanique quantique naturelle des systèmes physiques. Les amplitudes de tous les états candidats continuent de changer, réalisant un parallélisme quantique, en fonction de l'intensité du champ transversal en fonction du temps, ce qui provoque un tunnel quantique entre les états ou essentiellement un tunnel à travers les pics. Si le taux de changement du champ transverse est suffisamment lent, le système reste proche de l'état fondamental de l'hamiltonien instantané (voir aussi calcul quantique adiabatique). Si le taux de changement du champ transversal est accéléré, le système peut quitter temporairement l'état fondamental mais produire une probabilité plus élevée de conclure dans l'état fondamental du problème hamiltonien final, c'est-à-dire le calcul quantique diabatique. Le champ transversal est finalement désactivé et le système devrait avoir atteint l'état fondamental du modèle d'Ising classique qui correspond à la solution du problème d'optimisation initial. Une démonstration expérimentale du succès du recuit quantique pour des aimants aléatoires a été rapportée immédiatement après la proposition théorique initiale. Il a également été prouvé que le recuit quantique fournit un oracle de Grover rapide pour l'accélération de la racine carrée dans la résolution de nombreux problèmes NP-complets.