⚛️ quantum physics

Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

Cet article présente et examine les formulations QUDO, T-QUDO et HOBO pour l'optimisation combinatoire, en démontrant leurs codages explicites et leurs applications à des problèmes tels que le sac à dos et le voyageur de commerce, ainsi qu'à divers jeux de logique, afin de faciliter leur utilisation dans les algorithmes quantiques et inspirés du quantique.

Auteurs originaux : Alejandro Mata Ali

Publié 2026-05-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Alejandro Mata Ali

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de résoudre un puzzle massif et compliqué. Dans le monde de l'informatique, cela s'appelle l'optimisation combinatoire. C'est comme essayer de trouver la seule meilleure façon d'organiser un ensemble d'éléments pour obtenir le score le plus élevé, tout en respectant des règles strictes.

Pendant longtemps, on a appris aux ordinateurs à résoudre ces puzzles en utilisant un langage spécifique appelé QUBO (Optimisation Quadratique Non Contrainte Binaire). Considérez le QUBO comme un langage strict où chaque pièce du puzzle ne peut être que dans l'un des deux états suivants : ACTIVÉ ou DÉSACTIVÉ (comme un interrupteur lumineux). Bien que cela fonctionne pour de nombreuses choses, c'est souvent comme essayer de décrire une peinture complexe en utilisant uniquement des pixels en noir et blanc. Vous devez utiliser des milliers de petits interrupteurs pour représenter une seule couleur, ce qui rend le puzzle énorme et difficile à résoudre.

Cet article présente trois nouveaux langages plus flexibles qui permettent aux ordinateurs de s'exprimer avec des couleurs plus riches, facilitant ainsi la résolution de ces puzzles. L'auteur, Alejandro Mata Ali, explique le fonctionnement de ces nouveaux langages en utilisant des problèmes mathématiques célèbres et des jeux de logique.

Voici une analyse des trois nouveaux langages et des jeux utilisés pour les tester :

1. QUDO : Le « Cadran » au lieu de l'« Interrupteur »

Le Concept :
Dans l'ancien langage QUBO, les variables sont des interrupteurs binaires (0 ou 1). QUDO (Optimisation Quadratique Non Contrainte D-aire) transforme ces interrupteurs en cadran. Au lieu d'être simplement ACTIVÉ ou DÉSACTIVÉ, un cadran peut être réglé sur n'importe quel nombre de 0 jusqu'à une limite spécifique (comme un bouton de volume allant de 0 à 10).

L'Analogie :
Imaginez que vous faites vos valises.

Approche QUBO : Vous devez décider pour chaque chaussette, chemise et paire de chaussures individuellement si vous les mettez (1) ou non (0). Si vous voulez mettre 5 chemises, vous avez besoin de 5 interrupteurs séparés.
Approche QUDO : Vous avez un seul cadran pour les « Chemises ». Vous tournez simplement le cadran sur « 5 », et l'ordinateur sait que vous mettez cinq chemises.

Les Exemples de l'Article :

Le Problème du Sac à Dos : C'est le puzzle classique de « ce qui rentre dans le sac ». L'article montre que l'utilisation de cadrans QUDO est beaucoup plus efficace que l'utilisation de centaines d'interrupteurs binaires pour compter combien d'articles de chaque type vous prenez.
Hashiwokakero (Les Ponts) : Un puzzle où vous connectez des îles avec des ponts. Puisque vous pouvez construire 0, 1 ou 2 ponts entre les îles, un cadran (0, 1 ou 2) correspond parfaitement au problème, tandis que les interrupteurs binaires nécessiteraient des astuces supplémentaires pour compter jusqu'à 2.

2. T-QUDO : La Carte de « Relation Intelligente »

Le Concept :
Parfois, les règles d'un puzzle ne concernent pas seulement la valeur d'un cadran, mais la relation entre deux cadrans. T-QUDO (Tensor QUDO) est un langage qui comprend directement ces relations complexes.

L'Analogie :
Imaginez une fête où vous devez assigner des places aux invités.

QUDO : Vous pouvez dire à l'ordinateur : « L'invité A est heureux s'il s'assoit sur la Chaise 1. »
T-QUDO : Vous pouvez dire à l'ordinateur : « L'invité A est heureux s'il s'assoit sur la Chaise 1 ET que l'invité B s'assoit sur la Chaise 3. Mais si l'invité B s'assoit sur la Chaise 4, l'invité A se fâche. »
T-QUDO permet à l'ordinateur de comprendre ces associations spécifiques « si-alors » sans avoir besoin de les décomposer en étapes binaires minuscules et maladroites.

Les Exemples de l'Article :

Le Problème du Voyageur de Commerce : Un voyageur doit visiter chaque ville exactement une fois. T-QUDO facilite l'énoncé : « Si vous êtes dans la Ville A à l'étape 1, vous ne pouvez pas être dans la Ville A à l'étape 2. »
N-Reines : L'objectif est de placer des reines sur un échiquier de manière à ce qu'aucune n'en attaque une autre. T-QUDO gère très naturellement la règle « Si la Reine A est à la Ligne 1, Colonne 3, alors la Reine B ne peut pas être à la Ligne 2, Colonne 4 ».
Kakuro & Inshi no Heya : Ce sont des puzzles numériques (comme le Sudoku mais avec des sommes et des produits). T-QUDO permet à l'ordinateur de vérifier directement les sommes et les produits de groupes de nombres, plutôt que de les forcer dans des mathématiques binaires.

3. HOBO : Le « Câlin de Groupe »

Le Concept :
Parfois, une règle implique trois variables ou plus agissant simultanément. HOBO (Optimisation Binaire d'Ordre Supérieur) est un langage qui permet aux variables d'interagir en groupes, et non plus seulement par paires.

L'Analogie :
Imaginez un jeu de chaises musicales.

Binaire/Par Paires : Vous ne pouvez vérifier que si la Personne A est assise à côté de la Personne B.
HOBO : Vous pouvez vérifier si la Personne A, la Personne B et la Personne C sont toutes assises dans une formation triangulaire spécifique en même temps. Cela capture la « dynamique de groupe » en une seule fois.

L'Exemple de l'Article :

Solitaire à Clous : C'est le jeu où vous sautez par-dessus des clous pour les retirer. Un coup implique trois emplacements spécifiques : le clou de départ, le clou sauté et l'emplacement d'atterrissage. HOBO est parfait pour décrire cette interaction à trois voies en une seule étape, rendant la solution beaucoup plus claire.

Pourquoi est-ce important ?

L'article soutient que bien que ces nouveaux langages (QUDO, T-QUDO, HOBO) soient plus complexes à apprendre que l'ancien langage binaire, ils sont souvent beaucoup plus efficaces pour certains types de problèmes.

Moins de Désordre : Ils utilisent moins de variables (moins d'« interrupteurs » ou de « cadrans ») pour décrire le même problème.
Meilleur Matériel : L'article note que les futurs ordinateurs quantiques (qui utilisent des « qudits » au lieu de simples « qubits ») sont en cours de construction pour parler nativement ces langages. En formulant les problèmes de cette manière dès maintenant, nous nous préparons à ce futur matériel.
Le Compromis : Vous pouvez traduire ces nouveaux langages vers l'ancien langage binaire (QUBO), mais cela rend souvent le problème plus grand et plus désordonné. C'est comme traduire un poème de l'anglais vers une langue n'ayant que 26 lettres, puis essayer de le forcer à revenir en anglais : il perd son élégance.

Résumé

L'article est un guide pour les mathématiciens et les informaticiens. Il dit : « Arrêtez d'essayer de forcer chaque problème complexe dans une simple boîte ACTIVÉ/DÉSACTIVÉ. Parfois, vous avez besoin d'un cadran (QUDO), d'une carte de relations (T-QUDO) ou d'un câlin de groupe (HOBO) pour résoudre le puzzle efficacement. »

L'auteur le prouve en prenant des jeux de logique difficiles (comme Hashiwokakero, N-Reines et Solitaire à Clous) et en montrant comment ces nouvelles formulations les résolvent avec moins de ressources et des règles plus claires que les méthodes traditionnelles.

1. Énoncé du problème

Les problèmes d'optimisation combinatoire (par exemple, le sac à dos, le voyageur de commerce, les N-reines) sont souvent NP-difficiles et manquent de solutions classiques efficaces. Bien que la formulation Quadratic Unconstrained Binary Optimization (QUBO) soit la norme pour mapper ces problèmes vers du matériel quantique (spécifiquement via le Hamiltonien d'Ising et QAOA), elle présente des limites :

Inefficacité des variables : Les problèmes avec des états naturels multi-valeurs (par exemple, sélectionner $k$ éléments parmi $n$ ) nécessitent un codage binaire, ce qui augmente le nombre de variables et introduit des états invalides qui requièrent des termes de pénalité.
Limites des contraintes : Certaines contraintes logiques (par exemple, des implications de valeurs spécifiques ou la non-coïncidence de valeurs spécifiques) sont difficiles, voire impossibles, à implémenter efficacement dans le QUBO standard en raison de la nature binaire des variables ( $x_i^2 = x_i$ ).
Inadéquation matérielle : Les technologies quantiques émergentes, telles que les qudits (systèmes quantiques à $d$ niveaux), offrent un moyen naturel de représenter des variables non binaires mais nécessitent des formulations d'optimisation au-delà du QUBO.

Le papier répond au besoin de formulations plus générales qui exploitent les qudits et les interactions d'ordre supérieur pour réduire la surcharge des ressources et simplifier la mise en œuvre des contraintes.

2. Méthodologie

L'auteur introduit et analyse trois cadres d'optimisation généralisés, fournissant des formulations mathématiques explicites et démontrant leur application à des problèmes classiques et à des jeux combinatoires.

A. Quadratic Unconstrained D-ary Optimization (QUDO)

Définition : Une généralisation du QUBO où les variables $x_i$ sont des entiers non négatifs bornés ( $x_i \in \{0, 1, \dots, d_i-1\}$ ) plutôt que binaires.
Fonction de coût : $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$ .
Caractéristiques clés :
- Nécessite des qudits pour une implémentation directe.
- Autorise des termes linéaires (contrairement au QUBO pur où $x_i^2=x_i$ ).
- Limites : Certaines contraintes (par exemple, "si $x_i=a$ alors $x_j \neq b$ ") sont difficiles à implémenter car le signe des termes d'interaction dépend des valeurs spécifiques des variables non binaires.
- Implémentation : Peut être mappé vers QAOA en utilisant des portes de phase à qudit $P(\theta)$ et des portes de phase contrôlées.

B. Tensor Quadratic Unconstrained D-ary Optimization (T-QUDO)

Définition : Une généralisation catégorielle par paires du QUDO. Elle traite les variables comme des étiquettes catégorielles plutôt que comme des valeurs numériques.
Fonction de coût : $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$ .
Caractéristiques clés :
- Utilise un tenseur de coût $Q_{i,j, a, b}$ pour définir le coût de l'attribution de la valeur $a$ à la variable $i$ et de la valeur $b$ à la variable $j$ .
- Avantage : Surmonte les limites du QUDO en permettant une mise en œuvre aisée de contraintes logiques complexes (par exemple, implications de valeurs spécifiques, non-coïncidence de valeurs spécifiques) sans dépendre des propriétés arithmétiques.
- Codage : Peut être encodé dans un HOBO ou un QUBO (via un codage one-hot ou binaire), bien que cela puisse augmenter le nombre de variables.

C. Higher-Order Binary Optimization (HOBO)

Définition : Une formulation utilisant des fonctions pseudo-booléennes multilinéaires d'ordre $m$ (où $m > 2$ ).
Fonction de coût : $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$ , où $y_i \in \{0, 1\}$ .
Caractéristiques clés :
- Autorise des interactions entre plus de deux variables.
- Relation avec le T-QUDO : Les interactions du T-QUDO peuvent être encodées dans un HOBO en binarisant les étiquettes de qudits.
- Implémentation : Directement applicable aux dispositifs quantiques basés sur des qubits qui supportent des interactions d'ordre supérieur ou via des techniques de réduction.

3. Contributions clés et études de cas

Le papier valide ces formulations en les appliquant au problème du sac à dos, au problème du voyageur de commerce (TSP) et à cinq jeux combinatoires.

Problème	Formulation utilisée	Insight/Résultat clé
Sac à dos	QUDO	Démontre une réduction significative des ressources. Au lieu de variables binaires pour les comptes d'articles, un seul qudit par classe d'article représente directement le compte. Réduit le nombre de variables et de variables de rattrapage nécessaires par rapport au QUBO.
Hashiwokakero	QUDO	Modélise naturellement les connexions de ponts (0, 1 ou 2). Utilise des variables de flux auxiliaires (encodées comme des qudits) pour imposer la connectivité globale, prouvant que le QUDO peut gérer des contraintes topologiques complexes de manière exacte.
Voyageur de commerce (TSP)	T-QUDO	Utilise des variables $x_t$ représentant le nœud à l'instant $t$ . La contrainte "sans répétition" est naturellement gérée via un terme de pénalité par paires $\delta_{x_t, x_{t'}}$ , évitant le besoin de codages complexes par nombres premiers ou de matrices binaires massives.
N-Queens	T-QUDO	Réduit les variables de $N^2$ (grille binaire) à $N$ (indice de colonne par ligne). Le tenseur T-QUDO encode naturellement les contraintes de ligne, de colonne et de diagonale comme des entrées de tenseur spécifiques, simplifiant la structure de la fonction de coût.
Kakuro	T-QUDO	Combine le QUDO (pour les contraintes de somme) et le T-QUDO (pour les contraintes de non-répétition). La nature catégorielle du T-QUDO gère parfaitement la règle "nombre unique dans une ligne/colonne".
Inshi no Heya	T-QUDO	Gère les contraintes multiplicatives de région en convertissant les produits en sommes d'exposants premiers (fonctions unaires), ce qui s'intègre naturellement dans le cadre du T-QUDO.
Solitaire à clous	HOBO	Modélise le jeu comme une séquence d'états. La logique de mouvement (sauter par-dessus un clou) nécessite des interactions à 4 variables (source, milieu, destination, temps), ce qui s'exprime naturellement dans le HOBO sans avoir besoin de réduire à des termes quadratiques.

4. Résultats

Efficacité des ressources : Les formulations QUDO et T-QUDO nécessitent souvent moins de variables que leurs équivalents QUBO. Par exemple, N-Queens passe de $N^2$ variables binaires à $N$ qudits.
Flexibilité des contraintes : Le T-QUDO permet la mise en œuvre directe de contraintes logiques (implication, non-coïncidence) qui sont lourdes ou impossibles dans le QUDO/QUBO sans variables auxiliaires.
Faisabilité : Le papier fournit des fonctions de coût et des termes de pénalité explicites pour tous les exemples, démontrant que ces formulations sont mathématiquement solides et "exactes" (c'est-à-dire que les solutions valides ont un coût nul).
Implémentation quantique : L'auteur décrit comment implémenter ces fonctions de coût dans QAOA :
- QUDO : Utilise des portes de phase à qudit unique et des portes à deux qudits.
- T-QUDO : Utilise des portes de phase à focalisation contrôlée.
- HOBO : Utilise des portes de phase multi-contrôlées (ou des réductions basées sur des ancillas).

5. Importance

Pont entre théorie et matériel : Le papier sert de guide pratique pour l'utilisation du matériel quantique émergent basé sur les qudits, dépassant la limitation binaire de la recherche actuelle centrée sur les qubits.
Optimisation algorithmique : Il démontre que le choix de la formulation correcte (QUDO/T-QUDO/HOBO) basée sur la structure naturelle du problème peut réduire considérablement la complexité du paysage d'optimisation, améliorant potentiellement les performances d'algorithmes quantiques comme QAOA.
Cadre éducatif : En utilisant des jeux et des énigmes bien connus, le papier abaisse la barrière à l'entrée pour comprendre des formalismes d'optimisation complexes d'ordre supérieur et multi-valeurs.
Directions futures : Le travail suggère que les architectures de matériel quantique futures devraient prendre en charge nativement les interactions d'ordre supérieur et les qudits pour résoudre les problèmes combinatoires plus efficacement que ne le permettent les méthodes actuelles de réduction binaire.

En conclusion, le papier soutient que si le QUBO est un outil puissant, QUDO, T-QUDO et HOBO offrent une efficacité et une expressivité supérieures pour des classes spécifiques de problèmes combinatoires, en particulier ceux impliquant des variables multi-valeurs ou des contraintes logiques complexes, et sont directement implémentables sur les dispositifs quantiques de nouvelle génération.