Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Ce papier démontre que l'utilisation de codages qudits (entiers) plutôt que de codages qubits (binaires) conventionnels pour les algorithmes quantiques variationnels réduit considérablement les exigences en ressources et le temps d'exécution des simulations tout en obtenant des performances d'optimisation comparables ou supérieures sur des problèmes réalistes de gestion de flottes de véhicules électriques.

L'essentiel

Imaginez que vous êtes le gestionnaire d'une petite flotte de taxis électriques. Vous avez deux grandes tâches à accomplir chaque jour :

1. Recharger les véhicules : Vous devez décider quand les brancher (pour les recharger) ou leur permettre de renvoyer de l'énergie au réseau (décharge) afin d'économiser de l'argent.
2. Assigner les trajets : Vous devez décider quel véhicule effectue le trajet de quel client.

C'est un casse-tête. Si vous assignez le mauvais véhicule à un trajet, ou si vous le rechargez au mauvais moment, vous risquez de vous retrouver sans batterie ou de violer les règles du réseau électrique. Résoudre parfaitement ce casse-tête est très difficile pour les ordinateurs, surtout lorsque l'on ajoute les règles de la physique quantique au mélange.

Ce document est un rapport de chercheurs de l'Institut de recherche Honda et de l'Université de Leiden qui ont posé une question simple : « Est-ce que cela a de l'importance comment nous traduisons ce casse-tête dans le langage d'un ordinateur quantique ? »

Ils ont testé deux « langages » (encodages) différents pour voir lequel aide l'ordinateur quantique à résoudre le problème plus rapidement et plus efficacement.

Les deux langages : « Qubits » contre « Qudits »

Pour comprendre leur expérience, imaginez que vous essayez de décrire une liste de trajets à un robot.

1. L'ancienne méthode : Le langage « Qubit » (L'interrupteur binaire)
Imaginez un interrupteur lumineux. Il est soit ALLUMÉ, soit ÉTEINT.

• Dans cette méthode, les chercheurs ont utilisé un interrupteur séparé pour chaque combinaison possible d'un véhicule et d'un trajet.
• Si vous avez 3 véhicules et 2 trajets, vous avez besoin de 6 interrupteurs. Si un interrupteur est ALLUMÉ, cela signifie que « le Véhicule 1 effectue le Trajet A ». S'il est ÉTEINT, ce n'est pas le cas.
• Le problème : Cela crée une pièce immense et encombrée remplie d'interrupteurs. L'ordinateur doit vérifier des millions de combinaisons, dont la plupart sont absurdes (comme « le Véhicule 1 effectue le Trajet A » ET « le Véhicule 2 effectue le Trajet A » en même temps). L'ordinateur perd du temps à vérifier ces scénarios impossibles.

2. La nouvelle méthode : Le langage « Qudit » (Le cadran multi-positions)
Imaginez un variateur d'intensité lumineuse ou un cadran pouvant pointer vers de nombreux chiffres, pas seulement 0 ou 1.

• Dans cette méthode, au lieu d'utiliser de nombreux interrupteurs, ils ont utilisé un seul cadran pour chaque trajet.
• Si le cadran pointe vers « 1 », cela signifie que « le Véhicule 1 effectue ce trajet ». S'il pointe vers « 2 », cela signifie « le Véhicule 2 ». S'il pointe vers « 0 », cela signifie « aucun véhicule n'effectue ce trajet ».
• L'avantage : C'est beaucoup plus direct. Vous n'avez pas besoin de vérifier si deux véhicules se disputent le même trajet ; le cadran ne peut physiquement pas pointer vers deux véhicules à la fois. Cela réduit la « pièce » que l'ordinateur doit parcourir.

L'expérience : Une course contre la montre

Les chercheurs ont exécuté une simulation de leur ordinateur quantique (une « simulation par vecteur d'état », qui équivaut à un essai pratique parfait et sans bruit) pour observer comment ces deux langages se comportaient. Ils ont configuré de nombreux scénarios aléatoires avec différents nombres de véhicules, de trajets et de créneaux horaires.

Voici ce qu'ils ont découvert :

• L'espace de recherche a rétréci : La méthode « Qudit » (cadran) a réduit la taille de l'espace de recherche de manière exponentielle. Imaginez essayer de trouver une aiguille dans une botte de foin. La méthode Qubit vous donnait une botte de foin de la taille d'une montagne. La méthode Qudit vous donnait une botte de foin de la taille d'une boîte à chaussures.
• Des résultats plus rapides : Parce que la « boîte à chaussures » était beaucoup plus petite, la simulation s'est exécutée beaucoup plus rapidement. La méthode Qudit a pris considérablement moins de temps pour trouver une solution.
• Une meilleure qualité : Surprenamment, la méthode Qudit ne s'est pas contentée d'être plus rapide ; elle a trouvé des solutions meilleures ou équivalentes. Les solutions qu'elle a trouvées étaient plus proches de la réponse parfaite, et les résultats étaient plus cohérents (moins « tremblotants » ou aléatoires).
• Le problème de la « profondeur » : Ils ont essayé de faire « réfléchir » plus intensément l'ordinateur quantique en ajoutant plus de couches (profondeur) à l'algorithme. Habituellement, réfléchir plus intensément aide. Mais ici, la méthode Qubit s'est embrouillée et a performé pire à mesure qu'elle devenait plus profonde, probablement parce qu'elle avait trop de variables à jongler et que l'ordinateur a cessé d'optimiser trop tôt. La méthode Qudit est restée stable et robuste, même lorsque le problème devenait plus complexe.

La conclusion

Le document conclut que pour les problèmes impliquant la planification et l'attribution de choses (comme les véhicules électriques aux trajets), utiliser l'approche Qudit (cadran) est un choix beaucoup plus intelligent que l'approche traditionnelle Qubit (interrupteur).

C'est comme faire ses bagages pour un voyage :

• Qubit : Vous apportez une valise remplie de chaussettes individuelles, une par une, et vous essayez de les faire tenir dans une boîte. Vous gaspillez de l'espace et du temps.
• Qudit : Vous apportez un seul paquet de chaussettes soigneusement pliées. Il tient parfaitement, occupe moins de place, et vous pouvez le saisir instantanément.

Les chercheurs suggèrent que pour les problèmes de planification réels comportant de nombreuses options, l'utilisation de ces cadrans quantiques « multi-valeurs » (qudits) constitue une voie pratique et efficace, permettant d'économiser à la fois du temps et de la puissance de calcul.

Résumé technique

Résumé Technique : Comparaison des Encodages Qubit et Qudit pour les Problèmes de Recharge de Véhicules Électriques et d'Affectation de Trajets

Énoncé du Problème
L'article aborde le problème d'optimisation sous contraintes de la gestion d'une flotte de véhicules électriques (VE). Cela implique deux processus décisionnels couplés : la planification de la recharge (bi-directionnelle ou uni-directionnelle) de $N_{EV}$ véhicules sur un horizon temporel discret $T$, et l'affectation de ces véhicules à $R$ demandes de trajets clients. L'objectif est de minimiser les coûts de recharge tout en satisfaisant des contraintes opérationnelles strictes, notamment les limites de l'état de charge (SOC) de la batterie, les chevauchements de trajets, les bornes de puissance du réseau, et l'exigence qu'un véhicule ne peut pas se recharger tout en effectuant un trajet.

Le défi central investigué est la manière dont le choix de l'encodage pour les variables d'affectation de trajets affecte les besoins en ressources et le comportement d'optimisation des Algorithmes Quantiques Variationnels (VQA), en particulier l'Algorithme Quantique d'Approximation d'Optimisation (QAOA). Les auteurs comparent deux représentations distinctes :

1. Encodage Binaire (Qubit) : Utilise une variable binaire ($r_{n,i} \in \{0,1\}$) pour chaque paire véhicule-trajet. Cela nécessite des contraintes explicites pour garantir que chaque trajet est desservi par au plus un véhicule et que les trajets chevauchants ne sont pas affectés au même véhicule.
2. Encodage Entier (Qudit) : Utilise une variable entière ($q_i \in \{0, \dots, N_{EV}\}$) par trajet, où la valeur spécifie directement le véhicule affecté (ou un état non desservi). Cet encodage satisfait intrinsèquement la contrainte « un véhicule par trajet », éliminant le besoin de contraintes binaires explicites sur l'affectation.

Méthodologie
Les auteurs formulent le problème en utilisant le QAOA. Les deux encodages utilisent des variables qudits pour les niveaux de puissance de recharge ($l_{n,t}$), mais diffèrent dans la base de calcul pour les affectations de trajets.

• Construction de l'Hamiltonien : Les fonctions de coût classiques et les contraintes sont promues en opérateurs diagonaux dans la base de calcul. Les contraintes (par exemple, limites SOC, pas de recharge pendant les trajets) sont appliquées via des termes de pénalité non linéaires ajoutés à l'hamiltonien de coût.
• Simulation : L'étude emploie des simulations exactes de vecteurs d'état pour évaluer les algorithmes. Pour imiter les limitations matérielles réalistes, les valeurs moyennes de la fonction de coût sont estimées en utilisant un nombre fini de tirs de mesure ($M=256$) plutôt qu'un calcul exact.
• Optimisation : Un optimiseur classique (méthode de Powell) minimise la fonction de coût en faisant varier les paramètres du QAOA ($\gamma, \beta$). L'étude exécute 10 instances aléatoires pour chaque classe de problème, avec 10 exécutions d'optimisation par instance, en utilisant un budget fixe de 200 itérations internes de l'optimiseur.
• Cas de Test : Deux classes de problèmes sont analysées :
  • Recharge bi-directionnelle : 3 VE, 2 pas de temps, 2 trajets, 3 niveaux de recharge ($d=3$).
  • Recharge uni-directionnelle : 2 VE, 3 pas de temps, trajets variables ($R=2,3,4$), 2 niveaux de recharge ($d=2$).

Contributions et Résultats Clés
L'article fournit une analyse comparative des deux encodages selon plusieurs métriques :

1. Réduction de l'Espace de Hilbert : L'encodage entier (qudit) réduit exponentiellement la dimension de l'espace de Hilbert par rapport à l'encodage binaire (qubit). Le ratio des configurations est donné par $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. Pour les instances testées, cela se traduit par une réduction de l'espace de recherche de dizaines de milliers à quelques milliers d'états.
2. Performance d'Optimisation :
   • Écart d'Énergie Moyen : L'encodage qudit atteint systématiquement un écart d'énergie moyen comparable ou légèrement supérieur à celui de l'encodage qubit.
   • Variance : Les résultats qudit présentent une variance significativement plus faible dans les écarts d'énergie à travers différentes exécutions.
   • Probabilité de Succès : La fraction d'exécutions trouvant l'optimum global et la fraction d'états réalisables échantillonnés sont généralement plus élevées ou plus stables pour l'encodage qudit.
3. Temps d'Exécution et Convergence :
   • Temps d'Exécution de Simulation : En raison de la plus petite dimension de l'espace de Hilbert, l'encodage qudit nécessite des temps d'exécution de simulation nettement plus courts (linéaires par rapport à la profondeur du circuit, mais avec un coefficient beaucoup plus faible).
   • Comportement de la Profondeur des Couches : À mesure que la profondeur du QAOA ($L$) augmente, la performance de l'encodage qubit se dégrade plus significativement que celle de l'encodage qudit. Les auteurs attribuent cela au nombre accru de paramètres variationnels rendant le paysage d'optimisation plus difficile à naviguer dans un budget d'itérations fixe. L'encodage qudit est plus robuste face à une terminaison prématurée de l'optimiseur classique.
4. Paysage de Coût : Les paysages de coût pour l'encodage qubit montrent une échelle d'énergie plus large et des fréquences d'oscillation plus élevées en raison de la plus grande fraction d'états non réalisables (qui encourt des coûts de pénalité élevés) par rapport à l'encodage qudit.

Signification et Revendications
L'article revendique que les encodages natifs aux qudits offrent une voie pratique pour résoudre des problèmes de planification entiers et multi-valeurs en optimisation quantique variationnelle. La signification principale réside dans la démonstration que la représentation directe de variables discrètes multi-valeurs via des qudits, plutôt que leur expansion en qubits binaires, produit :

• Des économies de ressources exponentielles dans la dimension de l'espace de Hilbert.
• Une réduction de la surcharge computationnelle dans les simulations classiques (servant de proxy pour la complexité représentationnelle).
• Une robustesse améliorée dans le processus d'optimisation, en particulier dans les régimes fortement contraints où les solutions réalisables sont rares.

Les auteurs notent que bien que l'étude utilise des simulations de vecteurs d'état, la représentation compacte suggère des avantages potentiels pour les implémentations matérielles en réduisant la surcharge de la gestion des contraintes et de la correspondance des variables logiques. Ils concluent que pour les problèmes de planification sous contraintes, l'encodage qudit est un choix supérieur qui maintient ou améliore la performance d'optimisation tout en réduisant drastiquement les besoins en ressources. L'article suggère modestement que des travaux futurs devraient tester ces tendances sur des instances plus grandes et sur du matériel quantique réel pour vérifier si les avantages persistent au-delà de la simulation.