Qu'est-ce que le recuit inversé?

9

Quantum Annealing, (questions connexes Quantum Annealing , ou hamiltonian related ) est le processus utilisé dans Quantum Annealer de D-Waves, dans lequel les paysages énergétiques sont explorés, pour différentes solutions, et en réglant un hamiltonien approprié, en se concentrant sur un possible optimal solution à un problème. Le processus de recuit quantique réduit les "champs magnétiques transversaux" dans l'hamiltonien, en plus d'autres effets quantiques comme la tunnelisation quantique, l'intrication et la superposition, qui à leur tour jouent tous un rôle dans la réduction à zéro à une "vallée" d'une fonction d'onde mécanique quantique. , où réside la solution "la plus probable".

Le processus de recuit inversé, très brièvement, consiste à utiliser des méthodes classiques telles que le recuit simulé, pour trouver une solution et creuser une vallée à l'aide du recuit quantique. Si le hamiltonien utilisé par le Quantum Annealer est déjà dans une "vallée", comme il est passé une solution en premier lieu -La machine D-Wave atteint-elle une autre "vallée" (une meilleure solution?) En utilisant le hamiltonien passé à ça, en premier lieu?

user3483902
la source

Réponses:

4

Jusqu'à récemment, les dispositifs de recuit quantique de D-Wave partaient toujours d'une superposition uniforme sur tous les qubits:N

                                                Hjenjetjeunel=|+0|+1...|+N

où .|+je=12(|0je+|1je)

Supposons donc que vous ayez déjà effectué quelques recuits avec cette configuration et l'un des résultats à faible énergie ressemble à une solution relativement bonne (certains optima locaux) à votre problème d'optimisation. Jusqu'à l'introduction très récente de la fonction de recuit inverse , il était impossible d'utiliser cette solution comme entrée pour le prochain recuit afin d'explorer l'espace local autour de cette solution pour des chaînes de bits avec une énergie encore plus faible. Par conséquent, le recuit inverse nous permet d'initialiser le recuit quantique avec une solution connue (classique) et de rechercher l'espace d'état autour de ces optima locaux.

Lorsque vous explorez des paysages énergétiques complexes (accidentés) de problèmes d'optimisation, vous devez équilibrer l' exploration globale de l'espace d'état avec l' exploitation des optima locaux. Dans le recuit quantique traditionnel (onde D), nous partons d'un champ transversal élevé qui diminue ensuite progressivement comme vous l'avez décrit dans votre question. Le recuit quantique de D-Wave effectuait ainsi une recherche globale (en raison de beaucoup de tunnellisation quantique) au début du programme de recuit lorsque le champ transversal est fort. À mesure que le champ transversal s'affaiblit, la recherche devient de plus en plus locale. En revanche, le recuit inverse commence par une solution classique définie par l'utilisateur, puis augmente progressivement le champ transversal (recuit arrière) pour ensuite diminuer à nouveau le champ transversal (recuit avant).

Cela introduit la nouvelle distance d'inversion des paramètres qui détermine la distance que vous souhaitez recuire vers l'arrière (la force du champ transversal doit devenir). D-Wave a publié les deux tracés suivants dans ce livre blanc D-Wave :

tracés de distance d'inversion

Dans le graphique de gauche, vous pouvez voir que la distance d'inversion est un nouvel hyperparamètre très important puisque sa valeur détermine la probabilité d'obtenir un nouvel état fondamental (région bleue). Si la distance d'inversion est trop faible, vous obtiendrez le même état avec lequel vous avez commencé (région rouge), ce qui serait inutile. Et bien sûr, si vous inversez le recuit pendant trop longtemps, vous effectuez essentiellement un recuit quantique traditionnel et perdez les informations avec lesquelles vous avez commencé. N'oubliez pas que trop de champ transversal signifie que nous effectuons à nouveau une recherche globale!

Le graphique de droite montre essentiellement la même chose en traçant la distance de Hamming contre la distance d'inversion et la probabilité d'obtenir un nouvel état fondamental. Pour votre problème, vous voulez trouver ce point idéal (maxima de la courbe rouge). Pour les grandes distances d'inversion, nous voyons à nouveau que nous obtenons des chaînes de solution qui sont loin de notre état initial en termes de distance de Hamming.

Dans l'ensemble, le recuit inverse est une chose assez nouvelle et, à ma connaissance, il n'y a pas d'articles publiés sur son efficacité. Dans son livre blanc , D-Wave affirme la génération de «nouveaux optima mondiaux jusqu'à 150 fois plus rapides que le recuit quantique avant».

Mark Fingerhuth
la source
2

Quelques articles sont disponibles sur les algorithmes qui peuvent être construits en utilisant le recuit inverse, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta et https://arxiv.org/abs/1609.05875 ( il convient de souligner les précédents travaux sur le système fermé quelque peu liés: https://link.springer.com/article/10.1007/s11128-010-0168-z ). En ce qui concerne les résultats expérimentaux, je pense que les seuls publiquement visibles au moment de la rédaction sont le livre blanc donné dans le post précédent. Cependant, de nouveaux travaux seront présentés à l'AQC 2018 ( https://ti.arc.nasa.gov/events/aqc-18/ ) fin juin et ces discussions sont généralement mises en ligne quelques mois après la conférence.

Nick Chancellor
la source