Algorithme quantique avec un seul qubit pour résoudre le problème du vendeur

L’état quantique d’un qubit idéal est décrit par un point à la surface de la sphère de Bloch (un état quantique pur). Mais l’état d’un qubit réel est décrit par une distribution de probabilité située autour d’un point à l’intérieur de la sphère de Bloch (un état quantique de type mélange décrit par une matrice de densité). Les algorithmes pour ordinateurs quantiques supposent que tous les qubits sont idéaux, bien qu’aucun ne le soit. Il est publié sur arXiv qu’en utilisant un seul qubit idéal, un algorithme peut être implémenté pour résoudre le problème du voyageur de commerce (TSP), déterminant le chemin le plus court entre n villes, ce qui est un problème NP-difficile. Le TSP est cartographié dans un problème discret de type brachistochrone (courbe du chemin le plus rapide) où les villes sont des états dans la sphère de Bloch et le chemin entre elles est donné par des rotations (transformations unitaires) en superposition quantique. Pour n villes où vous devez postuler 2 (n−1) (2 + (n−2)²) = O(n³) rotations unitaires (36 pour n = 4, et 532 pour n = 8); Le problème est qu’ils doivent être ajustés presque parfaitement. On ne sait pas si l’algorithme offre un avantage quantique, car il n’a pas encore été possible d’estimer combien de mesures quantiques sont nécessaires dans l’étape finale (on ne sait donc pas si l’algorithme appartient à la classe BQP). Les résultats ont été obtenus à partir de simulations classiques d’un qubit idéal pour 4 à 9 villes (problèmes triviaux à résoudre sur ordinateur).

En principe, la mise en œuvre physique de l’algorithme ne nécessite que des qubits de haute qualité dans lesquels peuvent être appliqués des opérateurs unitaires simulant des rotations arbitraires sur la sphère de Bloch avec une haute fidélité. Malheureusement, les qubits réels actuels (NISQ) sont trop éloignés d’un qubit idéal pour permettre une telle implémentation pour n > 10. À propos, il vaut peut-être la peine de clarifier la différence entre le problème d’optimisation TSP (TSP-OPT), qui est NP-difficile, et le problème de décision (TSP-DEC), qui est NP-complet. Comme je l’ai déjà mentionné, le TSP-OPT consiste à trouver le chemin entre les villes qui minimise la distance (ou toute autre fonction de coût) ; tandis que le TSP-DEC consiste à déterminer, compte tenu d’un certain coût, s’il existe ou non une solution au problème au moindre coût. Si, dans les prochaines années, il s’avère que le nouvel algorithme est en BQP, nous disposerons d’un nouvel algorithme NP-dur qui pourra être résolu efficacement sur un ordinateur quantique. Mais attention, même si cet algorithme finit par être une solution en temps polynomial à TSP-OPT, il ne fera rien pour affecter la conjecture selon laquelle les ordinateurs quantiques ne sont pas efficaces pour résoudre les problèmes NP-complets.

L’utilité pratique du nouvel algorithme est nulle. Cependant, de grands progrès technologiques sont réalisés vers un qubit idéal (avec une efficacité supérieure à 99 % pendant 24 heures). On s’attend à ce que ces avancées rendent possible la mise en œuvre du nouvel algorithme. Ce qui n’enlève rien à l’intérêt de cette nouvelle réalisation. L’article est Kapil Goswami, Gagan Anekonda Veereshi,…, Rick Mukherjee, « Résoudre le problème du voyageur de commerce à l’aide d’un seul qubit », arXiv : 2407.17207. [quant-ph] (24 juillet 2024), deux : https://doi.org/10.48550/arXiv.2407.17207.

Aujourd’hui, on peut résoudre un problème TSP-OPT avec des centaines de villes sur un PC (la solution sera quasi optimale, puisqu’elle sera basée sur des heuristiques) ; sur un superordinateur, il sera possible de résoudre des dizaines de milliers de villes (dans certains cas jusqu’à près de cent mille). Dans un ordinateur quantique actuel, un problème avec une douzaine de villes ne peut être résolu (dans les ordinateurs à recuit quantique de Systèmes D-Wave avec 5436 qubits physiques, équivalent à 73 qubits logiques, le record a posé problème avec 10 villes) ; un problème ridicule pour votre PC (rappelez-vous que les ordinateurs quantiques actuels ne sont qu’une promesse pour l’avenir).

Le problème TSP-OPT consiste à trouver le cycle hamiltonien le plus court qui traverse toutes les villes (c’est-à-dire qui les traverse toutes, une fois pour chacune, de la première jusqu’au retour à la première). Ce problème peut être implémenté comme un problème de type brachistochrone discret, lorsque la fonction de coût entre deux villes mesure le temps nécessaire pour parcourir la distance qui les sépare. Sur un ordinateur classique, un tel problème nécessite de parcourir l’arbre de tous les cycles hamiltoniens possibles (comme le montre la figure de gauche) et de choisir le cycle qui nécessite le minimum de temps (figure de droite). Le graphique de gauche illustre que cet algorithme présente beaucoup de parallélisme, il semble donc naturel d’essayer de tirer parti du parallélisme quantique associés à des superpositions cohérentes.

Le problème TSP-OPT en tant que problème de type brachistochrone discret peut être implémenté dans la sphère de Bloch associée à un qubit. Un état du qubit est un point sur la sphère et une opération unitaire sur le qubit correspond à une rotation dudit point vers un autre point de la sphère. Les villes sont codées sous forme de points sur la sphère, soit P_je la ième ville. Le coût du trajet entre les villes i et j est codé avec le temps associé à la transition entre lesdits états, τ_ii–jjtal que cos(oh t_ii–jj) = 〈P_je|P_jj〉. Le problème TSP est symétrique lorsque le coût entre deux villes ne dépend pas de la direction, τ_ii–jj =t_jj–iiet est asymétrique sinon, τ_ii–jj ≠t_jj–ii.

Afin d’attribuer un coût arbitraire entre deux villes, un point intermédiaire P est introduit_jetel que le coût est la somme des coûts, τ_ii–jj =t_ii-ij +t_je–jjdéterminé par 〈P_je|P_je> Et p_je|P_jj〉. Le chemin entre deux états est donné par une rotation dans la sphère de Bloch, décrite par une transformation unitaire ; la transition entre P_je Et P_jj nécessite deux transformations unitaires, une entre P_je Et P_jemer P_je = U^toi_ii-ij P_jeet un autre entre P_je Et P_jjmer P_jj = U^d_je–jj P_je. Ainsi une solution au problème pour quatre villes (illustrée sur la figure), soit c₁ → c₂ → c₃ → c₄ → c₁correspondra à la séquence de transformations unitaires (indiquées par des flèches) entre les états P suivants₁₁ → P₁₂ → P₂₂ → P₂₃ → P₃₃ → P₃₄ → P₄₄ → P₄₁ → P₁₁. Pour n villes où vous devez postuler 2 (n−1) transformations unitaires.

Le principe de superposition de la physique quantique permet d’appliquer une transformation unitaire qui est une combinaison linéaire de plusieurs transformations unitaires (ce qu’on appelle habituellement parallélisme quantique). Nous pouvons donc postuler à P₁₁ une transformation unitaire de type U^toi P₁₁ = (un_11–12 Tu^toi_11–12 + un_11–13 Tu^toi_11–13 + un_11–14 Tu^toi_11–14) P₁₁ce qui donnera lieu à une combinaison linéaire d’états α_11–12 |P₁₂ 〉+ un_11–13 |P₁₃〉+ un_11–14 |P₁₄〉. De cette manière, une seule opération quantique est appliquée qui correspond au niveau classique à (n−1) opérations. Une fois ces transformations appliquées (qui dans une simulation classique sont triviales à mettre en œuvre, mais qui dans une réalisation physique nécessitent une fidélité exquise), une série de mesures quantiques de l’état doit être effectuée dans l’avant-dernière étape de l’algorithme afin d’estimer les coefficients qui multiplient la superposition d’états 〈P_i1|P_j1〉.

Les mesures quantiques finales constituent l’étape la plus incertaine de tout l’algorithme. L’article ne présente aucune estimation du nombre de mesures quantiques qu’il faudra effectuer pour obtenir une estimation de ces coefficients avec une fidélité suffisante en fonction du nombre de villes. Pour quelques villes représentées par des États bien séparés sur la sphère de Bloch (comme dans tous les exemples présentés dans l’article), peu de mesures quantiques sont nécessaires. Mais lorsque le nombre de villes augmente et qu’il y a une accumulation d’états dans la sphère de Bloch (le pire des cas pour l’algorithme), il peut arriver que le nombre de mesures augmente de façon exponentielle. Dans ce cas, l’algorithme ne présenterait aucun avantage quantique (il ne serait pas efficace dans le pire des cas).

En utilisant les valeurs desdites mesures quantiques de 〈P_i1|P_j1〉 une matrice de coefficients est obtenue pour un système linéaire d’équations. Sa solution nous permet de déterminer le cycle hamiltonien optimal qui résout le problème TSP. Vous ne comprenez peut-être pas tous les détails, mais ce que j’aimerais que vous compreniez, c’est que (1) vous devez utiliser des états quantiques de très haute fidélité dans la sphère de Bloch, (2) vous devez appliquer des transformations unitaires arbitraires avec une très haute précision, et (3) Il est nécessaire d’effectuer un grand nombre de moyennes quantiques qui estiment les chevauchements entre les états avec une très grande précision. Tout cela nécessite un qubit idéal, très éloigné des qubits réels actuels. Les résultats de simulation pour 4 à 9 villes (bien séparées dans la sphère de Bloch) sont prometteurs ; bien que la solution optimale ne soit pas toujours obtenue et que l’erreur augmente avec le nombre de villes. Comme l’illustre cette figure, les résultats pour entre 4 et 6 villes sont acceptables pour des problèmes de TSP symétriques, mais pour des problèmes asymétriques, notamment entre 7 et 9 villes, ils laissent à désirer.

Bref, un article plus intéressant comme idée de concept que pour ses résultats. Avec la rapidité avec laquelle le domaine de l’informatique quantique progresse, je suis sûr que cet algorithme connaîtra de grandes améliorations dans les années à venir (et peut-être que certains permettront sa mise en œuvre physique avec la technologie qubit NISQ). De plus, il y aura des avancées au niveau théorique, qui permettront de clarifier si le nouvel algorithme est efficace ou non (je dois avouer que j’ai de sérieux doutes quant à son efficacité pour un grand nombre de villes). Il faudra être conscient des avancées sur ce dossier.