Un ordinateur quantique peut résoudre des problèmes d'optimisation plus rapidement que les supercalculateurs classiques, un processus connu sous le nom de « avantage quantique » et démontré par un chercheur de l'USC dans un article récemment publié dans Lettres d'examen physique.
L'étude montre comment le recuit quantique, une forme spécialisée de calcul quantique, surpasse les meilleurs algorithmes classiques actuels lors de la recherche de solutions presque optimales à des problèmes complexes.
« La façon dont le recuit quantique fonctionne consiste à trouver des états de faible énergie dans les systèmes quantiques, qui correspondent à des solutions optimales ou presque optimales aux problèmes résolus », a déclaré Daniel Lidar, auteur correspondant de l'étude et professeur de génie électrique et informatique, de chimie et de physique et d'astronomie à l'USC Viterbi School of Engineering and the USC Dornson College of Letters, Arts and Sciences.
Optimisation approximative
Les scientifiques ont du mal à démontrer l'avantage de mise à l'échelle quantique (où l'avantage quantique augmente à mesure que la taille du problème augmente) grâce à l'utilisation d'un record quantique depuis des années. Le recuit quantique a longtemps été théorisé pour offrir des avantages de calcul pour l'optimisation, mais des preuves définitives des améliorations de mise à l'échelle par rapport aux méthodes classiques ont été insaisissables. Cette étude est en train de se concentrer sur l'optimisation exacte (où l'avantage quantique reste non prouvé) à une optimisation approximative, un domaine avec une large applicabilité dans l'industrie et la science.
Le recuit quantique est un type spécifique de calcul quantique qui peut utiliser des principes de physique quantique pour trouver des solutions de haute qualité à des problèmes d'optimisation difficiles. Plutôt que de nécessiter des solutions optimales exactes, l'étude s'est concentrée sur la recherche de solutions dans un certain pourcentage (≥ 1%) de la valeur optimale.
De nombreux problèmes du monde réel ne nécessitent pas de solutions exactes, ce qui rend cette approche pratiquement pertinente. Par exemple, pour déterminer les actions à mettre dans un fonds commun de placement, il est souvent assez bon pour simplement battre un indice de marché leader plutôt que de battre tous les autres bourses.
Pour démontrer l'avantage de mise à l'échelle quantique algorithmique, les chercheurs ont utilisé un processeur de recuit quantique avantage D-Wave, un type spécialisé de dispositif informatique quantique installé au Institut des sciences de l'information de l'USC. Comme avec tous les ordinateurs quantiques actuels, le bruit joue un rôle majeur dans la gâtation de l'avantage quantique dans le recuit quantique.
Pour surmonter ce problème, l'équipe a mis en œuvre une technique appelée Correction de recuit quantique (QAC) sur le processeur de la Wave D, créant plus de 1 300 Qubits logiques supprimés par des erreurs. Cette suppression d'erreur était essentielle pour atteindre l'avantage plutôt que la température parallèle avec les mouvements de cluster isoénergétiques (PT-ICM), l'algorithme classique de courant le plus efficace pour des problèmes comparables.
Performance «Time-to-Epsilon»
L'étude a démontré l'avantage quantique en utilisant plusieurs méthodes de recherche et s'est concentré sur une famille de problèmes de verre à spin bidimensionnel avec des interactions de haute précision.
« Les problèmes de vitrage sont une classe de défis d'optimisation complexes qui proviennent des modèles de physique statistique des systèmes magnétiques désordonnés », a déclaré Lidar.
Au lieu de rechercher des solutions exactes, les chercheurs ont comparé les performances « Time to-Epsilon », mesurant la rapidité avec laquelle chaque approche pourrait trouver des solutions dans un pourcentage spécifié de la réponse optimale.
Les chercheurs visent à étendre leurs résultats à des problèmes plus denses et plus dimensionnels et à explorer des applications dans l'optimisation du monde réel. Lidar a déclaré que de nouvelles améliorations de la suppression matérielle quantique et d'erreurs pourraient amplifier l'avantage observé.
« Cela ouvre de nouvelles voies pour les algorithmes quantiques dans les tâches d'optimisation où des solutions presque optimales sont suffisantes. »
