Trois mille mètres au-dessus du niveau de la mer, une paroi verticale. L'escaladeur classique grimpe par une seule voie, pas à pas, et se retrouve souvent coincé dans un minimum local, une petite niche d'où il n'y a pas de passage vers le haut. L'escaladeur quantique, lui, agit autrement : il est capable de sauter par-dessus une gorge et d'atterrir dans un bassin d'énergie voisin, où la voie est meilleure.
Le paysage énergétique est le graphe de l'énergie de toutes les configurations possibles du système. Pour un problème d'optimisation, chaque point du paysage correspond à une solution, et sa hauteur à sa qualité. Les problèmes NP-difficiles, comme la recherche de l'état fondamental du modèle d'Ising, ont un paysage accidenté avec de nombreux minima locaux. Les heuristiques classiques, comme le recuit simulé, imitent le refroidissement d'un métal : le système refroidit lentement, cherchant à atteindre le minimum d'énergie, mais il se coince souvent dans des creux peu profonds.
L'algorithme Qjump fonctionne de manière itérative. À partir d'une solution courante, une chaîne de bits, le circuit quantique génère de nombreux candidats en « sautant » dans les bassins d'énergie voisins. Le circuit se compose d'une couche d'encodage, de plusieurs couches d'opérateurs de coût et de mélange, inspirées de QAOA, et de mesures. Les paramètres du circuit ne sont pas optimisés de manière variationnelle, mais sont tirés de valeurs précalculées pour un QAOA profond, ce qui élimine le problème des plateaux stériles. Après l'échantillonnage quantique, l'ordinateur classique effectue une recherche locale, une descente gloutonne, pour chaque candidat et choisit la meilleure solution.
Les expériences ont été menées sur un processeur supraconducteur de 104 qubits avec une précision médiane des portes à deux qubits de 99,5 %. Sur les 20 instances difficiles sélectionnées, Qjump a trouvé en moyenne le minimum global 2,23 fois plus souvent que le recuit simulé, à temps fixe. En extrapolant vers du matériel futur avec une fréquence d'échantillonnage de 0,4 MHz et un contrôle rapide via FPGA, l'estimation du temps jusqu'à la solution a montré une accélération de 2,34 fois. Pour des systèmes plus petits, l'avantage était moindre : 0,98 fois pour 60 qubits et 1,56 fois pour 84 qubits. Cela indique une amélioration avec la taille du problème. QAOA avec recherche locale s'est révélé presque inefficace pour ces problèmes.
Qjump a montré que les schémas hybrides, où le processeur quantique n'est utilisé que pour « sauter » à travers le paysage et l'ordinateur classique pour l'optimisation précise, peuvent être une voie pratique vers l'avantage quantique sur les dispositifs quantiques intermédiaires bruités. Auparavant, on ne savait pas si de tels dispositifs sans correction d'erreurs pouvaient surpasser les heuristiques classiques. Maintenant, il existe un mécanisme concret de division du travail qui réduit les exigences sur la profondeur des circuits et la qualité des qubits. Cela élargit l'applicabilité des processeurs quantiques existants pour des problèmes d'optimisation dès aujourd'hui : logistique, planification, finance.
L'escaladeur quantique ne remplace pas l'escaladeur classique. Il ne fait que sauter par-dessus les gorges, tandis que la descente classique perfectionne la solution. Ensemble, ils atteignent des sommets inaccessibles séparément.
Pour sélectionner les instances difficiles, les chercheurs ont généré 4000 configurations aléatoires de connexions et de champs, puis n'ont gardé que les 20 sur lesquelles le recuit simulé classique fonctionnait le moins bien. Cela garantit que la comparaison était équitable : l'algorithme quantique a été testé sur les cas les plus difficiles.