FR3166458A1 - Dispositif et procédé de traitement pour la résolution de systèmes linéaires - Google Patents

Abstract

Dispositif et procédé de traitement pour la résolution de systèmes linéaires Procédé de traitement dans un ordinateur (1) comprenant un dispositif électronique de traitement (2) et un module d’optimisation (3) Ising ou QUBO selon lequel pour résoudre un système linéaire initial Ax + B=0, x = [xj] j = 0 à N-1, A =[aij] i,j = 0 à N-1 et B =[bj] j = 0 à N-1 , comprenant : transposition du système linéaire comprenant, dans chaque ligne i, le remplacement de , et par leur représentation binaire de résolution r, donnant ainsi, pour chaque ligne i du système linéaire initial, r équations chacune correspondant à un poids de bit respectif de 0 à r-1,  pour chaque ligne i, des variables binaires additionnelles étant en outre ajoutées pour prendre en compte les retenues binaires issues des opérations réalisées dans les équations aux différents poids de bits et le report desdites retenues aux poids de bit supérieurs ; détermination d’une représentation de type QUBO ou Hamiltonien d’Ising du système linéaire transposé et résolution par calcul d’optimisation du module d’optimisation (3)  Figure pour l’abrégé : Fig. 1

Description

Dispositif et procédé de traitement pour la résolution de systèmes linéaires

L’invention se situe dans le domaine de la résolution de systèmes linéaires, notamment en utilisant un ordinateur quantique.

Les ordinateurs quantiques fonctionnent avec des bits quantiques, ou qubits, qui, contrairement aux bits informatiques classiques ayant une valeur de soit 0 soit 1, peuvent être une superposition des états 0 et 1. Cette caractéristique signifie que les ordinateurs quantiques pourraient être beaucoup plus rapides que les ordinateurs classiques pour de nombreuses tâches et pourraient également être utilisés pour résoudre certains problèmes qu’un ordinateur classique ne peut pas résoudre. Les qubits peuvent être fabriqués à partir de différentes plateformes ou briques de base matérielles, telles que les qubits supraconducteurs, les particules élémentaires ou les ions piégés. D’autres méthodes en devenir sont les processeurs quantiques photoniques qui utilisent la lumière. Des modules de traitement électroniques comprenant des blocs optiques tels que lasers, lentilles, miroirs contrôlent les qbits.

La nature imparfaite du matériel actuel donne lieu à des erreurs quantiques qui peuvent empêcher d’arriver au résultat final du calcul. La cause principale de ces erreurs est la décohérence des qubits, qui détruit le caractère quantique des qubits et les ramène à l’état de bits classiques. La décohérence est provoquée par l’interaction des qubits avec leur environnement.

Des techniques de correction d’erreurs quantiques (QEC) consistant à utiliser un grand nombre de qubits pour créer un « qubit logique » beaucoup moins sujet aux erreurs, peuvent être utilisées dans le but de se rapprocher du fonctionnement de typeFTQC(« Fault Tolerant Quantum Computer »), i.e. d’une « informatique quantique tolérante aux pannes ».

Par ailleurs, la résolution de systèmes linéaires est d’intérêt majeur, tant sur le plan scientifique qu’industriel et sociétal : elle intervient dans de multiples domaines, allant de divers aspects de la simulation numérique, comme la physique des plasma, l’électromagnétisme, la mécanique des fluide, et s’étend naturellement à des aspects d’analyse des scénarios de catastrophe naturelle (météorologique, sismique, tsunami, …) mais aussi des scénarios de prévision climatiques, de planétologie, d’astrophysique, de physique des particules, etc.

Dans ce domaine particulier, un article marquant, « Aram W. and Hassidim, Avinatan and Lloyd, Seth, Quantum Algorithm for Linear Systems of Equations, 2009 » correspond à la publication de l’algorithme dit « HHL » d’après les initiales des trois auteurs, qui démontre l’existence d’un possible avantage exponentiel de ce type de calculs sur un ordinateur quantique. Cet avantage est conditionné par plusieurs particularités du système d’équations linéaires et de l’utilisation de la solution :

- la matrice du système doit être creuse,

- le résultat vectoriel doit être impérativement exploité sous la forme d’un produit scalaire (il n’est pas possible d’obtenir le vecteur solution explicitement sans abandonner tout espoir d’avantage exponentiel).

Malgré ces limitations, l’algorithme HHL est l’un des algorithmes les plus attendus pour l’utilisation des machines quantiques. Cependant, cet algorithme suppose l’utilisation d’un ordinateur quantique parfait, dit FTQC. Or il n’existe pas, à l’heure actuelle, d’ordinateurs FTQC. Les calculateurs quantiques actuels et ceux disponibles dans les prochaines années ont des caractéristiques de bruit relativement élevées (>10^-4) et le nombre de qubits physiques (les unités de stockage et d’utilisation de l’information quantique) reste relativement limités, entre quelques dizaines et quelques centaines. Dans ce cadre, les algorithmes susceptibles de fournir une accélération exponentielle tels que HHL se révèlent infaisables même à des échelles modestes.

Il existe d’autres types de calculateurs quantiques, les calculateurs dits calculateurs quantiques analogiques, qui ne possèdent probablement pas les caractéristiques pour fournir une accélération exponentielle sauf sur des simulations physiques potentiellement (problèmes dits « many-body ») mais qui peuvent offrir une possibilité d’amélioration polynomiale des algorithmes et/ou une possibilité d’avoir des consommations énergétiques réduites par rapport aux ordinateurs « classiques » : cf. les calculateurs quantiques de D-Wave® qui se basent sur une technologie de qubits supraconducteurs, et ceux de Pasqal® qui manipulent des atomes neutres dans des matrices optiques.

Il existe des ordinateurs quantiques adaptés pour effectuer une procédure de type recuit quantique (aussi appelé recuit adiabatique) sur une base hamiltonienne de type Ising bidimensionnelle. Ce type d’approche du calcul quantique est particulièrement bien adapté aux calculs d’optimisation, car on démontre facilement qu’ils sont formellement équivalents à des solveurs spécialisés pour les problèmes d’optimisation non contraints en variables binaires souvent désignés par leur acronyme anglo-saxon QUBO (« Quadratic Unconstrained Binary Optimization »). Dans le cadre général, les problèmes QUBO sont NP-complets mais l’allocation d’un problème NP-complet d’échelle non-triviale (au moins plusieurs centaines de variables) sur ces ordinateurs n’est lui-même pas forcément un problème simple. De plus, il n’existe pas de résultats concernant un quelconque avantage calculatoire de cette technique de calcul par rapport à un ordinateur classique.

Ci-dessous est rappelé brièvement rapidement le principe de fonctionnement d’un ordinateur quantique utilisant un calcul adiabatique sur une base d’hamiltonien d’Ising bidimensionnel.

Ordinateur quantique utilisant un calcul adiabatique sur une base d’hamiltonien d’Ising bidimensionnel.

Le recuit quantique, “quantum annealing” en anglais, est une technologie particulière d’ordinateur quantique avec des niveaux de performance intermédiaires entre ceux des supercalculateurs traditionnels et ceux des ordinateurs quantiques universels. Le principe général de l’ordinateur adiabatique/à recuit quantique consiste à établir des liaisons entre qubits avec des poids, puis à faire trouver un point d’équilibre au système en modifiant ces poids pour identifier un minimum énergétique de l’ensemble, qui correspond à la solution recherchée du problème. Le processus est dit adiabatique car il n’y a pas de transfert énergétique entre le chipset de l’ordinateur et son environnement : on reste sur le même niveau d’énergie pendant tout le processus de recuit adiabatique et donc les états excités sont supprimés de façon exponentielle (conditions du-dit « théorème adiabatique » de la mécanique quantique).

Le principe de base de l’ordinateur quantique adiabatique consiste à préparer un “hamiltonien”, i.e. un système quantique avec plusieurs qubits interconnectés. Cet hamiltonien est initialisé dans un état qui est solution d’un problème facile à résoudre. L’ordinateur va alors faire évoluer cet hamiltonien de façon adiabatique vers le hamiltonien du problème posé en respectant des contraintes préalables et correspondant à un minimum énergétique et ainsi donner une solution au problème difficile que l’on cherche à résoudre.

Le principe du calcul quantique adiabatique est le suivant : il est déterminé d'abord un hamiltonien complexe dont l'état fondamental décrit une solution du problème étudié (le hamiltonier final est dérivé de la fonction coût dont on cherche la solution de plus basse énergie et qui correspondra à l’état fondamental (de plus basse énergie) de ce hamiltonien). On prépare ensuite un système possédant un hamiltonien plus simple, que l'on initialise dans son état fondamental. On fait alors évoluer adiabatiquement cet hamiltonien vers le hamiltonien complexe qu'on a déterminé ; d'après le théorème adiabatique, le système reste dans l'état fondamental, et son état final décrit une solution du problème envisagé.

Considérons un hamiltonien initialet un hamiltonien finalcorrespondants aux formes suivantes :
(Equation 1)

où :
-
sont les opérateurs de Pauli habituels agissant sur les spins, i.e. les matrices complexes de dimensions 2*2 qui représentent le spin des particules suivantes :

- les
sont des champs magnétiques de biais et
- la matrice
est une matrice de couplage inter-spins.

Il est défini un paramètre de temps, appelé temps de recuit quantique (« annealing time ») et deux fonctions monotonesetrespectivement décroissante et croissante, à support surtelles queetde sorte que le système quantique interne du calculateur quantique soit soumis au hamiltonien dépendant du temps suivant durant le temps de recuit :

(Equation 2)

Si les spins du calculateur quantique sont préparés dans l’état fondamental du hamiltonienet si le temps de recuit quantiqueest suffisamment long, alors le système de calcul quantique sera au tempsdans l’état fondamental du hamiltonien(théorème adiabatique de la mécanique quantique).

L’état fondamental du hamiltonienpermet de déduire trivialement la solution (ou une solution) de coût minimum du problème de type QUBO (Quadratic Unconstrained Binary Optimization) directement déduit de ce hamiltonien.

Un problème classique d’optimisation appelé QUBO est, dans le cas général, NP-difficile. Il se caractérise par une fonction de coût :

(Equation 3)

oùest une matrice généralement écrite sous forme triangulaire supérieure, mais qui peut être n’importe quelle matrice à coefficients réelset oùest un vecteur binaire de dimension n,.

Or, le problème QUBO est équivalent par changement de variables simple au problème quantique très étudié des hamiltoniens d’Ising. Dans ce dernier cas, au lieu d’étudier des variables binaires (0 ou 1), on étudie des orientation de spin (valeurvalant +1 ou -1 sur un axe sélectionné qui est souvent - par convention - l’axe , vertical).

Avec la substitution de variables suivante :avec, le Hamiltonien s’écrit :

avec

Comme indiqué précédemment, les ordinateurs quantiques analogiques à base de hamiltonien d’Ising sont bien indiqués pour les simulations physiques de verre de spin et des problèmes d’optimisation grâce à l’équivalence Ising-QUBO. Pour résoudre des systèmes d’équations linéaires, la représentation initiale du problème linéaire doit être transformée en un problème quadratique. On cherche en outre à s’assurer de la meilleure capacité de résolution possible du hamiltonien résultant de cette transformation.

En partant du système d’équation linéaire exprimé sous forme vectorielle à l’aide d’une matrice de coefficients constantsde l’ensemble des matrices carrées de dimension N x N à coefficients (a_i,ji= 0 à N-1 et j = 0 à N-1) dans et d’un vecteur, (vecteur de composante b_i, i = 0 à N-1) on cherche à résoudre l’équation suivante :

(Equation 6)

où Α, Βsont connus etest la solution qui est recherchée (vecteur de composantes x_i, i = 0 à N-1).

Pour permettre la résolution de l’équation, il s’agit de le transposer dans une formulation hamiltonienne qui respecte les principes suivants :

- le minimum de l’énergie pour le hamiltonien d’Ising choisi doit correspondre à la solution l’équation n°6,

- le gap spectral du hamiltonien défini devrait être le plus grand possible afin d’augmenter les probabilités de résolution par le calcul quantique adiabatique (en vertu du théorème adiabatique),

- l’échelle de valeur des couplages relatifdéfini ci-dessous est le plus faible possible afin d’éviter les problèmes de résolution intrinsèque et de bruit intrinsèque du calculateur quantique, avec :

(Equation 7)

Pour limiter les problèmes de résolution et de bruit intrinsèques, l’idéal est d’avoiret avec les technologies actuelles il est recommandé de rester dans tous les cas avec.

L’article Kyungtaek Jun, « QUBO formulations for a system of linear equations, 2024 ») étudie le problème de résoudre l’équation n°6 par la méthode des moindres carrés, sur une machine D-Wave Advantage et illustre l’état de l’art du domaine.

Il y est utilisé une représentation binaire de chaque élément du vecteur solution. Et une résolution en virgule fixe ou (de façon équivalente) en représentation entière dans laquelle un facteur commun est introduit et sous-entendu dans la suite du document (i.e. tous les coefficients ont été implicitement multipliés parpour retomber sur une équation en nombres entiers).

Pour la représentation binaire, il est nécessaire selon la méthode décrite dans cet article de choisir une résolutionet chaque élémentdu vecteur solutionde l’équation peut s’écrire :

(Equation 8)

où chaque , j = 0 à r, est une variable binaire. Chaque, i = 0 à N-1, est donc un nombre entier compris entreet: de ce fait est la résolution intrinsèque en nombre entier de la méthode de résolution.

La méthode des moindres carrées considérée dans l’article susmentionné consiste à construire une fonction de coût d’un problème QUBO dont le minimum correspond à la solution du système d’équation que l’on recherche. Pour chaque ligne de l’équation n°6, on a :

La i^èmeligne ( i = 0 à N-1) de l’équation 6 s’écrit ainsi : 0, ou encore ainsi :

(Equation 9)

La fonction coût partielle étant classiquement définie par , il est donc défini ici une fonction de coût partielle telle que :

(Equation 10)

Il s’avère que(c’est un carré) et qu’une condition suffisante, pour que cette fonction de coût partielle soit nulle, est quesoit solution de l’équation n°6. On peut définir une fonction coût globale :

(Equation 11)

qui est positive ou nulle ; donc la condition pour qu’elle s’annule est quesoit solution de l’équation n°6. Si l’équation n’a pas de solution entière, alors il n’y a pas de solution à 0 de la fonction de coûtmais le minimum de la configuration en variables binaires correspond bien au vecteur en valeurs entières le plus proche de la solution exacte en valeurs réelles.

Il est théoriquement possible de dépasser la résolution intrinsèqueen utilisant une interpolation quadratique de la valeur à 0 entre les résultats de plus bas coûts révélés par la recherche du minimum. En pratique, cela sera potentiellement limité par le bruit du système de résolution QUBO ou Ising.

À noter qu’en formulation QUBO, le coût minimum ne sera pas 0, mais une constante correspondant à la somme des carrés des, du fait de la formulation matricielle qui implique que le coût en formulation QUBO soit de 0 pour un vecteur nul.

On constate, à partir de la fonction de coût définie en équations n°10 et n°11, un problème d’explosion exponentielle en résolution des coefficients de la matrice QUBO : le coefficient (C_r) multipliant le terme endans cette formule va conduire va croître ainsi :

(Equation 12)

Le fait que l’on soit en représentation QUBO ou Ising change peu le fait que comme la mise en œuvre des coefficients de la matrice d’Ising ou QUBO ne peut pas avoir une précision infinie, et que les technologies actuelles limitent même autour de, la capacité d’une machine sera limitée à(en pratique, c’est encore moins, à cause des bruits intrinsèques de qubits et des bruits d’interactions entre qubits (crosstalks).

Pour obtenir une précision correcte de 32 bits par exemple, il faudrait pour cela avoir une qualité de résolution sur les coefficients qui soit meilleure quece qui est complètement irréaliste : il est donc nécessaire de trouver des solutions qui se comportent au pire linéairement avec l’augmentation de la résolutionet de la dimensionde l’équation que l’on cherche à résoudre.

A cet effet, suivant un premier aspect, la présente invention décrit un procédé de traitement dans un ordinateur comprenant un dispositif électronique de traitement et un module d’optimisation adapté pour effectuer des calculs d’optimisation d’un type déterminé parmi Ising et QUBO et tout type réductible à une optimisation Ising ou QUBO, selon lequel ledit procédé comprend les étapes suivantes mises en œuvre par le dispositif électronique de traitement suite à la réception, par le dispositif électronique de traitement, d’une commande de résolution d’un système linéaire initial Ax + B=0, où x est le vecteur solution à déterminer x = [x_j]_{j = 0 à N-1}, A =[a_ij]_{i,j = 0 à N-1}et B =[b_j]_{j = 0 à N-1}avec en ligne i du système linéaire initial, i =0 à N-1, l’équation : :

a/ transposition du système linéaire comprenant, dans chaque ligne i, le remplacement de chaque variable par une représentation binaire de basée sur r variables binaires x_jk, j = 0 à N-1 et k = 0 à r-1, où r indique la résolution de la représentation binaire ;

b/ détermination d’une représentation dans un format prédéfini de type QUBO ou de type Hamiltonien d’Ising du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jk, ladite représentation étant fonction d’au moins les coefficients dudit système linéaire transposé ;

c/ fourniture de ladite représentation déterminée du système linéaire au module d’optimisation,

d/ le procédé comprend en outre une détermination, en fonction de ladite représentation fournie, des valeurs des variables binaires x_jkvérifiant ledit système transposé par calcul d’optimisation dudit type déterminé mis en œuvre par ledit module d’optimisation

ledit procédé étant caractérisé en ce que :

à l’étape a :

- la transposition comprend en outre le remplacement de et de par leur représentation binaire basée sur, respectivement, et , k= 0 à r-1, donnant ainsi, pour chaque ligne i du système linéaire initial, r équations chacune correspondant à un poids de bit respectif de 0 à r-1, le système linéaire transposé comprenant ainsi N*r équations et

- pour chaque ligne i, des variables binaires additionnelles sont en outre ajoutées pour prendre en compte les retenues binaires issues des opérations réalisées dans les équations aux différents poids de bits et le report desdites retenues aux poids de bit supérieurs ;

à l’étape b : il est déterminé une représentation dans le format prédéfini du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jket les variables binaires additionnelles, ladite représentation étant déterminée en fonction d’au moins les coefficients dudit système linéaire transposé ;

à l’étape d, ledit calcul d’optimisation détermine en outre des valeurs des variables binaires additionnelles vérifiant ledit système transposé.

La présente invention offre donc une solution de résolution de systèmes linéaires particulièrement avantageuse en termes de complexité pour déterminer la solution du système.

Dans des modes de réalisation, un tel procédé comprendra en outre l’une au moins des caractéristiques suivantes :

- ledit module d’optimisation comprend un calculateur quantique analogique adiabatique à recuit quantique,

et à l’étape d, ladite détermination est effectuée par calcul quantique analogique adiabatique à recuit quantique mis en œuvre par ledit calculateur quantique analogique adiabatique à recuit quantique ;

- à l’étape a, pour chaque ligne i : les r lignes associées à la ligne i sont traitées successivement par poids de bits croissant, en reportant les retenues issues des poids de bits inférieurs et en introduisant à chacune des r lignes les au plusretenues nécessaires pour garantir l’égalité à 0 de la ligne i ;

- à l’étape a, pour chaque ligne i, il est appliqué une méthode de sommation en arbre binaire selon laquelle il est en outre considéré les sommes partielles deux à deux des termes successifs à sommer dans la ligne, puis de façon itérative, à un niveau donné de l’arbre, il est considéré les sommes partielles deux à deux des sommes partielles du précédent niveau ; et

dans l’étape b, les variables binaires additionnelles comprennent en outre les représentations binaires des sommes partielles des différents niveaux de l’arbre ;

- à l’étape b, le gap spectral de ladite représentation est augmenté tout en maintenant la table de vérité.

Suivant un autre aspect, l’invention décrit un ordinateur comprenant un dispositif électronique de traitement et un module d’optimisation adapté pour effectuer des calculs d’optimisation d’un type déterminé parmi Ising et QUBO et tout type réductible à une optimisation Ising ou QUBO, dans lequel ledit dispositif électronique de traitement est adapté pour recevoir une commande de résolution d’un système linéaire initial Ax + B=0, où x est le vecteur solution à déterminer x = [x_j]_{j = 0 à N-1}, A =[a_ij]_{i,j = 0 à N-1}et B =[b_j]_{j = 0 à N-}avec en ligne i du système linéaire initial, i =0 à N-1, l’équation : , ledit dispositif étant en outre adapté pour effectuer les traitements suivants :

a/ transposition du système linéaire comprenant, dans chaque ligne i, le remplacement de chaque variable par une représentation binaire de basée sur r variables binaires x_jk, j = 0 à N-1 et k = 0 à r-1, où r indique la résolution de la représentation binaire ;

b/ détermination d’une représentation dans un format prédéfini de type QUBO ou de type Hamiltonien d’Ising du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jk, ladite représentation étant fonction d’au moins les coefficients dudit système linéaire transposé ;

c/ fourniture de ladite représentation déterminée du système linéaire au module d’optimisation,

ledit module d’optimisation étant adapté pour déterminer, en fonction de ladite représentation fournie, des valeurs des variables binaires x_jkvérifiant ledit système transposé par calcul d’optimisation dudit type déterminé mis en œuvre par

ledit ordinateur étant caractérisé en ce que :

à l’étape a :

- la transposition comprend en outre le remplacement de et de par leur représentation binaire basée sur, respectivement, et , , k = 0 à r-1, donnant ainsi, pour chaque ligne i du système linéaire initial, r équations chacune correspondant à un poids de bit respectif de 0 à r-1, le système linéaire transposé comprenant ainsi Nxr équations et

- pour chaque ligne i, des variables binaires additionnelles sont en outre ajoutées pour prendre en compte les retenues binaires issues des opérations réalisées dans les équations aux différents poids de bits et le report desdites retenues aux poids de bit supérieurs ;

à l’étape b : il est déterminé une représentation dans le format prédéfini du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jket les variables binaires additionnelles, ladite représentation étant déterminée en fonction d’au moins les coefficients dudit système linéaire transposé ;

à l’étape d, ledit calcul d’optimisation détermine en outre des valeurs des variables binaires additionnelles vérifiant ledit système transposé.

Dans des modes de réalisation, un tel dispositif comprendra en outre l’une au moins des caractéristiques suivantes :

- ledit module d’optimisation comprend un calculateur quantique analogique adiabatique à recuit quantique,

et à l’étape d, ladite détermination est effectuée par calcul quantique analogique adiabatique à recuit quantique mis en œuvre par ledit calculateur quantique analogique adiabatique à recuit quantique ;

- à l’étape a, pour chaque ligne i : les r lignes associées à la ligne i sont traitées successivement par poids de bits croissant, en reportant les retenues issues des poids de bits inférieurs et en introduisant à chacune des r lignes les au plusretenues nécessaires pour garantir l’égalité à 0 de la ligne i ;

- à l’étape a, pour chaque ligne i, il est appliqué une méthode de sommation en arbre binaire selon laquelle il est en outre considéré les sommes partielles deux à deux des termes successifs à sommer dans la ligne, puis de façon itérative, à un niveau donné de l’arbre, il est considéré les sommes partielles deux à deux des sommes partielles du précédent niveau ; et

dans l’étape b, les variables binaires additionnelles comprennent en outre les représentations binaires des sommes partielles des différents niveaux de l’arbre.

Suivant un autre aspect, l’invention décrit un produit programme d’ordinateur destiné à être stocké dans la mémoire d’un dispositif électronique de traitement et comprenant en outre un microcalculateur, ledit programme d’ordinateur comprenant des instructions qui, lorsqu’elles sont exécutées sur le microcalculateur, mettent en œuvre les étapes incombant au dispositif de traitement d’un procédé suivant le premier aspect de l’invention.

L’invention décrit également un support d’enregistrement lisible par ordinateur stockant un tel programme d’ordinateur. De tels supports d'enregistrement peuvent comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une clé USB ou un disque dur. De tels supports d'enregistrement peuvent être des supports transmissibles tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens, de sorte que le programme d’ordinateur qu’il contient est exécutable à distance. Les programmes selon l'invention peuvent être en particulier téléchargés sur un réseau par exemple le réseau Internet. De tels supports d'enregistrement peuvent comprendre un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé de contrôle d’affichage précité.

L’invention sera mieux comprise et d’autres caractéristiques, détails et avantages apparaîtront mieux à la lecture de la description qui suit, donnée à titre non limitatif, et grâce aux figures annexées, données à titre d’exemple.

FIG. 1LaFIG. 1est une illustration d’un ordinateur comprenant un dispositif électronique de traitement et un module d’optimisation dans un mode de réalisation de l’invention ;

FIG. 2LaFIG. 2décrit les étapes d’un procédé de traitement dans un mode de réalisation de l’invention ;

FIG. 3LaFIG. 3illustre la prise en compte de retenues binaires dans un exemple de mode de réalisation de l’invention dite de simple sommation par ligne de bits ;

FIG. 4LaFIG. 4illustre la prise en compte de retenues binaires dans le mode de réalisation de l’invention de laFIG. 3;

FIG. 5LaFIG. 5illustre l’utilisation d’un registre et d’une sélection par multiplexage dans un mode de réalisation de l’invention ;

FIG. 6LaFIG. 6illustre l’usage des additionneurs en contrainte QUBO dans un mode de réalisation de l’invention avec arbre binaire de sommation 2 à 2.

Des références identiques peuvent être utilisées dans des figures différentes lorsqu’elles désignent des éléments identiques ou comparables.

LaFIG. 1illustre un dispositif électronique de traitement 1 comprenant un bloc électronique de traitement 2 et un module d’optimisation 3 dans un mode de réalisation de l’invention.

Dans le mode de réalisation considéré, le bloc électronique de traitement 2 comprend une unité matérielle de type FPGA ou ASIC, ou encore une mémoire comprenant des instructions logicielles et un processeur « classique » adapté pour exécuter ces instructions logicielles (on entend ici par technologie classique un processeur non quantique).

Dans un mode de réalisation, le module d’optimisation 3 comprend un accélérateur quantique, adapté pour recevoir en entrée les représentations sous forme Ising ou QUBO de systèmes linéaires à résoudre et pour déterminer les solutions de tels systèmes par exemple par mise en œuvre d’une procédure de type recuit quantique adiabatique sur une base d’Hamiltonien d’Ising bidimensionnel, par exemple D-Wave® ou Pasqal®.

Dans un mode de réalisation, le module d’optimisation 3 comprend, à la place d’un accélérateur quantique, un QPU (Quantum Processing Unit). Cette invention peut également être mise en œuvre avec un accélérateur de calcul QUBO ou Ising (ou plus globalement adapté pour déterminer un extremum : par exemple : dans le cas QUBO, un minimum de la fonction coût et dans le cas Ising, un minimum de l’énergie du Hamiltonien) simplement analogique, au lieu d’un calculateur quantique.

LaFIG. 2indique les étapes d’un procédé de traitement 100 mis en œuvre selon l’invention. Le dispositif de traitement 1 est adapté pour mettre en œuvre ce procédé dans un mode de réalisation de l’invention.

Dans une étape 101, la matriceΑet le vecteurΒtels que précédemment introduits définissant le système linéaire à résoudre tel qu’indiqué à l’équation 6 sont fournis en entrée du bloc de traitement 2, qui détermine leur représentation binaire respective en virgule fixe :

; et

Ici, les nombres seront codés en binaire selon la méthode dite du complément à deux (ainsi sur 4 bits, on aura 1000b pour -8, 1111b pour -1 et 0111b pour 7). Par convention et de façon usuelle en calcul quantique, les nombres en binaire sont ici notés en « petit-boutiste » (« little endian binary »), i.e. avec les bits de plus faible poids à gauche. Une autre convention peut toutefois être choisie pour la mise en œuvre de l’invention.

Dans une étape 102, en considérant en outre la représentation binaire retenue (du complément à deux) de la composante scalaire x_j, soit :

le système linéaire de l’équation 6 est transposé par le bloc de traitement 2 en utilisant ces représentations binaires de x_j, a_ijet b_i.

Le système linaire à résoudre est ainsi transposé en utilisant d’une part par ces coefficients binaires et d’autre part ces variables binaires dont la valeur est à déterminer et en outre en introduisant des variables supplémentaires correspondant aux retenues binaires, ce qui permet d’éviter l’explosion exponentielle des coefficients rencontrée en utilisant la méthode précédemment évoquée des moindres carrés standard.

Des matrices sont définies correspondant aux produitsissus de l’équation n°6 avec l’utilisation en notation binaire des constantes a_ij, b_jet des valeurs scalaires x_javec j compris entre 0 et N-1, oùest le nombre d’équations du système.

En effet, le produits’exprime comme un ensemble de produits simples, décalages et additions ce qui permet d’obtenir une matrice binaire correspondant au produitsous la forme d’un produit matrice vecteur: ainsi (on se limite ici à une résolution r ; on peut toutefois vouloir une résolution (cachée) de 2r mais si cette solution est possible, il est avantageux de la remplacer par une normalisation des lignes à i fixé : cela limitera drastiquement les cas spurieux) :

(Equation 13)

Comme on peut le voir illustré enFIG. 5, chacun des coefficients de A_ijest simple à obtenir de la représentation binaire de en utilisant un registre et une sélection par multiplexage : le bit de sortie (« out ») correspond au bit du registre a_ik(RGSTR) sélectionné par la somme l+c (l et c étant les indices de, respectivement, ligne et colonne de la matrice de multiplication A_ikque l’on cherche).

Selon l’invention, dans l’équation 9 (une équation 9 pour chaque i = 0 à N-1), chaque terme a_ijx_i‘ du polynôme est alors remplacé par la représentation de A_ijx_jde l’équation 13 sans prendre en compte les facteurs multiplicatifsde cette équation 9 du fait de la représentation binaire ici utilisée, et b_iest lui aussi remplacé par ses composantes binaires β_ik, k=0 à r-1 ce qui donne pour chaque i, r lignes correspondantes d’équations, chacune de ces r lignes d’équation correspondant à un poids de bits respectif k, de k = 0 (poids de bit le plus faible) à r-1 (poids de bit le plus fort). Et ligne de poids de bit par ligne de poids de bits, en commençant par k = 0, des variables binaires additionnelles sont en outre ajoutées pour prendre en compte les retenues binaires issues des sommes réalisées dans la ligne d’équation correspondant au poids de bits courant ; ces retenues sont en outre reportées aux poids de bit supérieurs et les retenues issues des poids de bit inférieurs sont reportées à la ligne de poids courante. La prise en compte de ces variables correspondant aux retenues permet d’assurer l’égalité stricte à zéro de la somme courante (et pas l’égalité à 0moduloles puissances de 2).

Deux méthodes différentes (nommées ci-après respectivement méthode I, méthode II) par exemple mises en œuvre dans l’étape 102 pour prendre en compte ce principe de prise en compte des retenues, pour les additions bit à bit, après transposition du système sont détaillées ci-dessous (d’autres méthodes peuvent être utilisées) : la première (méthode I) effectuant toute les additions en une fois, en ajoutant l’ensemble des retenues nécessaires pour cette addition et le report correct des retenues aux ordres suivants en poids des bits ; la seconde (méthode II) effectue l’addition en arbre binaire avec sortie systématique d’une retenue et d’un bit de débordement («overflow »), et l’entrée facultative d’une retenue.

Méthode I (simple sommation): elle est plus simple et permet de minimiser le nombre de variables auxiliaires (= retenues) puisqu’elles sont introduites seulement en fonction de la nécessité. Elle a pour inconvénient de générer potentiellement des coefficients un peu plus élevés, et de ne pas détecter de façon simple les potentiels débordements (overflow) de la capacité de codage des nombres entiers. Il sera toutefois facile de mettre en œuvre par le bloc de traitement 2 une mitigation/rectification de ce type de configuration.

Avec une représentation binaire complète de l’équation, on peut maintenant chercher à la résoudre ligne de bit par ligne de bit, i.e. pour chaque i fixé, i = 0 à N-1, en considérant les r équations binaires, l’une après l’autre, i.e. avec chaque k fixé (k dans l’intervalle 0, r-1) depuis l’équation correspondant au poids de bit k = 0 jusqu’à celle correspondant au poids de bits r-1).

Par exemple, la première ligne de bits donnera l’équation suivante :

(Equation 14)

On notera que dans un mode de réalisation, pour aller plus loin dans la prise en compte des retenues, les indices peuvent aller jusqu’à 2r.

Pour obtenir une égalité au lieu d’un modulo, le bloc de traitement 2 introduit un ensemble de retenues de sommations binaire qui sont en outre reportées à la ligne suivante (correspondant au poids de bit supérieur). Comme il y a au maximumtermes binaires par ligne, il est ajouté de façon intrinsèque au plusretenues pour la ligne (ici la relationdésigne la partie entière la plus petite, c’est à dire la plus proche de 0 pour les valeurs positives). En général le nombre réel de retenues est inférieur, car le maximum de retenues ne peut être obtenu que pour des valeurs uniformes de -1 pour les éléments de la matrice . De plus pour les lignes suivantes (i.e. correspondant au poids de rang supérieur) il y a moins de coefficientsissus du produitcomme on peut le voir sur l’équation 13.

Pour la première ligne (i.e. pour i = 0), l’équation 14 devient, avec prise en compte des retenues:

(Equation 15)

où est le nombre de retenues ( ) et les variables binaires sont les retenues en notation binaires. Il faut reporter à chaque étape les retenues à la ligne de résolution aux lignes suivantes de résolution, donc on ajoute la variable c₀₀₁à la ligne de résolution suivant au rang, la variable c₀₀₂au ranget ainsi de suite. La prise en compte de ces nouvelles variables à chaque ligne peut ajouter de nouvelles retenues par cascade, mais l’évolution du nombre de retenues est logarithmique en fonction du nombre de variables et de retenues à un rang de résolution donné, la progression en nombre de variable est donc bornée et rapidement contenue.

Avec la prise en compte des retenues, l’égalité à 0 peut être retrouvée, tant que la résolution est suffisante pour coder l’ensemble des nombres nécessaires (y compris les valeurs de sommes intermédiaires) (à partir de ces équations intégrant les retenues, le bloc 2 pourra ensuite définir une fonction de coût QUBO et/ou son équivalent Ising).

Les principes de base s’énoncent de la façon suivante :
- les lignes de base (i.e sans retenue) sont écrites avec les variables binaires avec les constantes binaires
et
;
- les retenues de base (les retenues dites «de base » sont les retenues issues de l’équation courante considérée sans la prise en compte des retenues au rang (poids) inférieurs) sont ajoutées en fonction du nombre de termes binaires de l’étape précédente (i.e. dans la ligne de base mentionnée au § précédent) et du nombre de retenue reportées, en provenance des lignes de poids de bit inférieur,
;

- les retenues sont reportées aux lignes suivantes ;

- si (il est connu que) toutes les valeurs sont positives, alors dans la dernière ligne (celle de poids de bit le plus fort), seulement les retenues nécessaires pour assurer la nullité de la ligne de poids fort (qui est également le bit de signe) sont reportées (si ce n’est pas le cas, il faut reporter jusqu’à la ligne suivant le bit de poids le plus fort pour assurer la nullité du report de retenue) ;

- sinon, on peut se limiter à cette méthode en effectuant un post-traitement pour faire revenir les résultats à 0 pour la somme si celle-ci est un multiple de 2^N(en effectuant des additions modulo 2N sur le vecteur résultat « spurieux ») soit en ajoutant des contraintes sur les retenues pour que le débordement du bit de signe donne également 0. Le principe est le même que pour les autres lignes de bits mais il n’y a pas de variables en entrée, juste les retenues et les retenues engendrées pour assurer le 0 ;
- de façon alternative, les résultats spurieux peuvent être supprimés en prenant en compte les inconnues
qui n’apparaissent pas dans la fonction coût (colonnes à zéros, ce qui est facile à vérifier) et soit a posteriori déterminer leur valeurs (comme il n’y en a généralement pas beaucoup, ce n’est pas forcement un problème, cf supra), soit ajouter des lignes de prise en compte des retenues, mais tronquées à r bits. Au plus il y aura 2r lignes, et donc autant de lignes de retenues à ajouter. Il n’est pas difficile de limiter le nombre de lignes à prendre en compte pour s’assurer que toutes les variables binaires sont bien prise en compte dans les équations binaires. Ce que l’on peut perdre en ajoutant davantage de variables de retenues est la diminution de la probabilités de découverte d’une solution optimale à la fonction de coût.

Méthode II (méthode en arbre binaire de sommation 2 à 2): la méthode en arbre binaire consiste à effectuer les sommes 2 à 2 d’éléments de chaque ligne. Elle nécessite plus de ressources et plus de variables auxiliaires puisque ces dernières comportent les sommes intermédiaires (les bits résultats de sommation 2 à 2) en plus des retenues potentielles (les retenues sont au maximum 1 par bit de la somme partielle). Mais cela peut parfois être compensé par le fait que les coefficients sont globalement toujours les mêmes et compris entre -2 et 1. La sommation pourra se faire en arbre binaire inversée, ce qui permet de limiter le nombre de niveaux de sommation proportionnellement au logarithmique base 2 du nombre de termes d’une ligne.
Le principe de multiplication par les constantes
est le même que pour la méthode I précédente, par contre la sommation de bits se fait par paire avec report de retenues, et en arbre binaire de largeur
et de profondeur
similairement à ce qui peut être réalisé dans un multiplieur câblé. Le but ici est de créer des intermédiaires de calcul en additions 2 à 2 : ainsi les 2 premiers termes de la première ligne de l’équation (i.e. i = 0 parmi les i = 1 à N) sont sommés par le bloc de traitement 2 : (après leur transposition en produit binaire conformément à l’équation 13) et sur la même ligne les deux suivants, , etc. jusqu’aux deux derniers (voir plus loin un exemple décrit en référence à laFIG. 7).

La traduction en mini fonction de coût sera effectuée en passant les termes de l’autre côté de l’équation, et en élevant au carré pour chaque équation. Comme dans la méthode I, le bloc de traitement 2 introduit (après transposition en produit binaire conformément à l’équation 13, des termes de chaque somme deux à deux), pour chaque niveau de poids, les retenues qui sont reportées au niveau de bits suivant en poids. La procédure est poursuivie avec les sommes partielles en les combinant deux à deux : , de la même façon , jusqu’à . La première ligne de sommation a(arrondi à l’entier supérieur terme, au second niveau) termes ; au second niveau, il n’y en a plus que, et ainsi enlignes, la somme totale est déterminée.

Cela nécessite l’ensemble des variables supplémentaires , , … avec r bits de résolution chacune, plus les variables de retenues que l’on doit introduire de la même façon que la méthode I pour résoudre le problème, les équations du problème considérées étant alors le résultat final de la somme complète de la ligne, avec toutes les variables et toutes les sommes intermédiaires, chacune de ces sommes étant en outre transposées en écriture binaire puis les retenues binaires étant prises en compte comme précédemment. Il y a toutefois moins de retenues par fonction de coût partielle du fait qu’il y a moins de termes.

Dans une étape 103, le bloc de traitement 2 détermine une représentation du système linaire transposé obtenu à l’étape 102 comportant ces coefficients binaires et ces variables binaires dont la valeur est à déterminer dans un format prédéterminé. Dans le cas considéré, le bloc de traitement 2 est adapté pour générer un Hamiltonien d’Ising partiel et/ou la matrice QUBO partielle pour chaque équation binaire obtenue à l’étape 102 (r équations pour chaque i , i = 0 à N-1), puis pour générer un Hamiltonien global ou matrice QUBO globale en fonction des Hamiltonien d’Ising partiels ou des matrices QUBO partielles.

Le coût de référence considéré (-R₀) est déterminé en même temps que la matrice QUBO et/ou ou que le Hamiltonien d’Ising. Comme il est connu, la fonction coût en QUBO est la somme des carrés de chaque ligne du système transposé (devant être égale à 0). Le Hamiltonien d’Ising se déduit en utilisant la formule 5.

Comme la vérification de la solution (étape 106) est plus simple à réaliser en forme QUBO, le bloc de traitement 2 génère par exemple la matrice QUBO en même temps que l’hamiltonien d’Ising.

Dans une étape 104, optionnelle, le bloc de traitement 2 effectue une optimisation (ici du Hamiltonien d’Ising) pour augmenter le gap spectral.

En effet, le gap spectral est une quantité importante dans le cadre de la résolution par un accélérateur quantique basé sur le recuit quantique et le théorème adiabatique de la mécanique quantique, du problème d’Ising tel que généré à l’étape 103 : typiquement, le temps de recuit quantique sur un annealer quantique doit être bien supérieur à un temps inversement proportionnel au gap spectral (voire à une puissance du gap spectral).

De ce fait, plus le gap spectral augmente, plus la probabilité de résolution du problème par une machine basée sur le recuit quantique augmente, et ceci de façon très significative. Il est donc utile dans le cas présent que le gap spectral relatif soit le plus élevé possible. On notera qu’il en est de même dans un mode de réalisation utilisant un algorithme qui imite le processus adiabatique, comme par exemple QAOA ou Quantum Approximate Optimization Algorithm qui est utilisable sur une machine quantique à porte.

La solution proposée ainsi que son implémentation par fonction câblée et micro-programmée diffère d’un calcul booléen classique puisqu’elle fournit les coefficients d’un problème de satisfaisabilité booléenne exprimés sous forme QUBO ou Ising dont la solution (ou au moins une solution, les autres étant aisément réductibles à la solution cherchée) correspond à la solution du système d’équations linéaires.

Une autre différence avec la méthode des moindres carrés est que le bloc de traitement 2 ne va pas chercher à déterminer les coefficients qui correspondent forcément au résultat de l’application de cette méthode, mais utilise des combinaisons de coefficients qui sont susceptibles d’apporter une plus grande probabilité de réussite pour résoudre le système d’équations (augmentation du gap spectral sur le hamiltonien cible dans le cadre des modèles d’Ising, donc augmente les chances d’avoir aussi un gap spectral minimal plus élevé dans une évolution adiabatique du hamiltonien, ce qui par le théorème adiabatique permet de valider les conditions du théorème de la mécanique quantique).

L’obtention de la matrice QUBO ou de celle d’Ising est de l’ordre de complexitépour une matrice dense (moins pour une matrice creuse) et de ce fait, si le processus d’attribution des coefficients au système quantique de résolution du problème d’Ising est intégré, et que la probabilité de résolution du problème par le calculateur quantique est important, alors, cela fournit un avantage polynomial aux systèmes quantiques de calculs à hamiltonien d’Ising pour les calculs d’algèbre linéaire — la meilleure complexité connue pour la résolution classique d’un système d’équations linéaires étant. À noter que cela reste vrai pour la résolution de systèmes creux d’équations linéaires.

A titre d’illustration, dans le cas de 3 variables binaires (ou de façon équivalente trois variables de spin), le bloc de traitement 2 calcule la matrice QUBO partielle (ou de façon équivalente, la matrice de couplage d’Ising partielle et le vecteur de biais partiel) de la façon suivante:

- avant correction de gap spectral avec respectivement bits de poids faible d’une inconnue x, d’une inconnue y et première retenue de l’addition, dans le cas où : .

- la matrice QUBO associée, est donc égale à :

mais elle correspond à un gap QUBO relatif de seulement 0.11 (le gap spectral considéré étant la différence d’énergie minimale entre le niveau d’énergie fondamental et le premier niveau « excité » du hamiltonien), tandis qu’avec le choix de la matrice améliorée suivante, à la place :

(Equation 16)

le bloc de traitement 2 aboutit à la même table de vérité (comprenant le classement –ordonné- en énergie ou en coût des configurations de spin ou binaires) pour la fonction de coût partielle, mais avec un gap spectral relatif de -0,42.

Une telle optimisation partielle est effectuée par le bloc de traitement 2 pour différentes configurations (i.e. selon le nombre de bits à prendre en compte ; par exemple, la matrice est la configuration sur 2 bits, plus une constante à 1 ; pour chaque configuration possible, il faut une matrice différente que l’on peut précalculer) de façon à accroitre significativement le gap spectral relatif de chaque QUBO (de façon équivalente, de chaque Ising partiel). Une façon de faire est de disposer d’une banque de QUBO ou Ising partiels selon le nombre de variables en entrée et le nombre de retenues, et selon les valeurs de la constante (β_k). A noter, qu’il peut être utile d’utiliser des qubits (auxiliaires) supplémentaires pour augmenter ce gap pour certaines configurations (par exemple lorsque la constante β_k=0).

En notation Ising, la matrice , s’écrit :

(Equation 17)

En Ising le gap spectral relatif est de 0,21 (minimum à -6,75 niveau suivant à -2,75 pour un maximum à 12,25) et 0,11 pour le gap relatif de la matrice originale (minimum à -2,5 gap à -1,5 et maximum à 6,5). Par un doublement du gap spectral de façon systématique, on peut espérer avoir un ordre de grandeur supplémentaire sur les probabilités de réussite.

La façon de choisir les matrices de substitution peut dépendre de la plateforme. Il n’est pas forcément utile de faire une liste de telles matrices, car on peut utiliser des solveurs hors ligne pour chercher des hamiltoniens partiels qui permettent d’avoir le gap spectral relatif le plus grand.

Suite à l’étape 103 (si pas d’étape 104) ou sinon suite à l’étape 104, dans une étape 105, l’accélérateur quantique 3 est adapté pour, en fonction de ces données reçues en entrée au format prédéterminé définissant le système linéaire à résoudre, (soit directement, soit à travers un système de mapping (embedding) automatique comme il est connu), mettre en œuvre une procédure d’optimisation pour déterminer les valeurs des variables binaires qui sont solutions du système linéaire, la procédure d’optimisation étant dans l’exemple considéré un recuit adiabatique (de façon plus générale, suivant les méthodes et technologies utilisées pour la mise en œuvre de l’invention, il est recherché dans cette étape un extremum (généralement un minimum) : par exemple, de la fonction coût dans le cas QUBO, de l’énergie du hamiltonien pour le cas Ising …).

Dans une étape 106, le cas échéant, au moins une solution déterminée est fournie par l’accélérateur quantique 3 au bloc de traitement 2.

Dans le cas où aucune solution n’a pu être déterminée par l’accélérateur quantique 3, il fournit dans un mode de réalisation quelques « solutions » de plus bas coût découvertes et le bloc de traitement recherche alors une solution par interpolation de ces solutions. Une possibilité pour cela est de prendre au moins 3 (potentiellement plus si les coûts sont proches afin d’assurer un peu plus de précision) solutions de plus bas coût trouvées par l’accélérateur quantique 3, puis de calculer un gradient local de la fonction de coût. La solution approximée devrait se situer au croisement des 2 tangentes construites sur le gradient. Cela n’est valide que dans l’hypothèse où la fonction coût est localement convexe et qu’on est effectivement proche de la solution. Cela peut partiellement être vérifié par le cas de 3 tangentes de références : si les 3 combinaisons de 2 tangentes arrivent peu ou prou sur la même valeur de vecteur, la solution obtenue est associée à un bon niveau de confiance.

Si les deux tangentes sont sur un même plan ou approximativement sur un même plan, il peut être plus avantageux que le bloc de traitement 2 effectue une extrapolation sur le passage à 0 de la dérivée (ou une extrapolation quadratique ce qui revient au même).

Le bloc de traitement 2 dans un mode de réalisation teste en outre la validité de cette solution en calculant les coûts QUBO des valeurs des variables binaires de la solution. Et dans le cas où le coût de référence considéré (-R₀déterminé en même temps que la matrice QUBO à l’étape 103) est atteint ou dans le cas où une interpolation tangentielle satisfaisante est obtenue, la validité des solutions est alors confirmée, en bénéficiant d’un avantage polynomial (donc d’une baisse de complexité : diminution du temps de traitement et de l’énergie nécessaire à la réalisation du calcul) par rapport aux algorithmes classiques de résolution de systèmes linéaires.

Dans le cas contraire, la recherche est close par un constat d’échec.

L’invention propose ainsi notamment un solveur de problèmes d’algèbre linéaire pour ordinateur quantique sur base de modèle d’Ising 2D.

Dans un mode de réalisation, il est en outre effectué dernier pré-traitement de la matrice A par le bloc 2 avant la résolution du système afin de réduire drastiquement les problèmes potentiels de résultats spurieux et la nécessité de prendre en compte davantage de retenues : si une ligne de la matrice A est divisible par 2, il faut diviser cette ligne par 2 (ce qui implique de diviser la valeur b_i par deux également). On doit refaire cette opération tant qu'il existe une ligne divisible par 2. La perte en résolution sur le vecteur B fait partie des limites de résolution en virgule fixe de toute façon. On peut garder la fonction coût avec la matrice A originale si on veut faire l'interpolation vers une solution fractionnaire pour le vecteur X.

Dans le cas d’utilisation de la méthode I :il est détaillé l’obtention des matrices QUBO partielles et des sommations de la fonction coût

Une fois les r x N lignes en égalité binaire complétées avec les retenues à l’issue de l’étape 102, l’obtention des valeurs partielles de la matrice QUBO se fait par détermination des coefficients (unitaires ou multiplicateurs des variables) obtenus en élevant la ligne (de la matrice représentative du système considéré comportant les coefficients des α_ijket des c_ijket β_kj) au carré comme il est connu (comme il s’agit de coefficients puissances exactes de 2, le calcul des coefficients n’a pas besoin d’un multiplieur complet, mais simplement de registres à décalage et de logique simple pour la prise en compte du signe).

Le principe mis en œuvre par le bloc de traitement 2 se décompose de la façon suivante :

- pour chaque coefficientval1non nul de chaque ligneide cette matrice représentative du système considéré :

- pour chaque coefficientval2dans la colonnej:

ajouter la valeurval1×val2à la matrice QUBO en (i,j)si i≥j et (j,i)sinon (cela permet d’économiser sur la mémoire nécessaire, même si ce n’est pas obligatoire) ;

mettre à jour la matriceJen ajoutantval1×val2/4en (i,j) ou (j,i) avec les même conditions que pour la matrice QUBO mais seulement sii≠j;

mettre à jour le vecteurhavec la valeurval1×val2/4en positionietj(une seule fois sii=j)

mettre à jour la diagonale de Q (mode QUBO, i.e. ajouter à la diagonale) et/ou le vecteur h (notation Ising), avec le double de la constante (on est en binaire donc le double de la constante beta_ik est soit 0 soit 2 (ou la conversion en Ising)
- mettre à jour la valeur du résultat optimal
en y ajoutant la valeur2×val1(la valeur de
est initialisée à 0 au début du processus).

À l’issue de ce processus, il est obtenu la matrice QUBO et sa valeur optimale pour la sélection de la solution dans les échantillons issus du processus de calcul Ising ou QUBO, et un hamiltonien d’Ising sous la forme de sa matriceJet de son vecteur de biaish.

Néanmoins, pour un hamiltonien d’Ising optimisé par rapport à son gap spectral, il faudra utiliser pour chaque ligne une autre méthode en utilisant un hamiltonien dont le gap spectral sera pré-optimisé.

Dans un mode de réalisation, la solution cherchée est une probabilité suffisamment importante d’être découverte par le processeur de recuit (ou le processeur quantique) pour qu’en une ou deux dizaines d’échantillons, il y ait une probabilité très grande d’avoir au moins une solution.

Pour illustrer encore la mise en œuvre de la solution selon l’invention et en reprenant les notations introduites précédemment, considérons maintenant le système linéaire initial suivant (correspondant à AX + B), avec N = 2, a₀₀= 1, a₀₁= 1, a₁₀= -1, a₁₁= 1, b₀= 1, b₁= 3 :

(Equation 18)

En considérant que r = 3 (résolution de 3 bits), au cours de l’étape 101, pour chaque ligne de ce système initial, une équation binaire est obtenue pour chaque bit de résolution, avant de prendre en compte les retenues, comme représenté à laFIG. 3, J_kreprésentant les entiers qui seront dérivés ensuite en retenues binaires pour l’équation binaire relative au poids de bit k, issue de la transposition de la première ligne du système linéaire ci-dessus, avec k = 0 à r-1(=2) et J’_kreprésentant les entiers qui seront dérivés ensuite en retenues binaires pour l’équation binaire relative au poids de bit k, issue de la transposition de la deuxième ligne du système linéaire ci-dessus. Les deux lignes de l’équation 18 deviennent 2x3 lignes en notation binaire ; les constantes ‘1’ et ‘3’ ont été converties en trois constantes ‘1’ ; la multiplication par ‘-1’ (i.e. ‘111’ en notation binaire en complément à 2) est visible de par la forme triangulaire de la sous-matrice.

La figure 4 illustre l’étape 102 de prise en compte des retenues binaires selon la méthode I (c_let c’_l, l=0 à 2) pour assurer l’égalité à 0 de chaque ligne. Les retenues sont reportées dans les lignes relatives au poids de bit supérieur. La première ligne comporte deux variables binaires et une constante, donc retenue est suffisante pour satisfaire l’égalité à 0. Pour la dernière ligne, il y a quatre variables binaires et une retenue reportée de la ligne précédente ; par conséquent, 2 retenues sont nécessaires pour satisfaire l’égalité.

Dans l’étape 103, il est construit la matrice QUBO correspondant à ces 2 x 3 (= N x r) équations traduisant le système linéaire initial à chaque poids de bits avec variables binaires additionnelles correspondant aux retenues et il est déterminé la fonction coût associée.

Pour l’équation x₀₁+ x₁₁+ c₀-2c₁= 0, où x₀₁+ x₁₁sont les variables (1 bit chacune) à déterminer et c₀(retenue reçue en entrée, venant d’un poids de bit inférieur), c₁(retenue fournie en sortie, pour un poids de bit supérieur) sont les variables additionnelles de type retenue, la fonction coût correspond au polynôme de degré 2, (x₀₁+ x₁₁+ c₀-2c₁)², et on détermine Q_P, la matrice partielle QUBO correspondant à cette équation :

(x₀₁+ x₁₁+ c₀-2c₁)²= 0

La matrice complète est composée de ces matrices partielles successivement déterminées.

Exemple en cas d’utilisation de la méthode II :

On considère un cas où l’étape 102 met en œuvre la méthode II (méthode en sommation en arbre binaire de sommation 2 à 2), en utilisant comme blocs de base des additionneurs du type additionneur à deux nombres A_set B_sen codant chaque bloc de base en contraintes QUBO et en propageant au niveau suivant de sommation dans l’arbre les variables issues de l’addition. LaFIG. 6illustre un tel mode de réalisation : Ss est le résultat de la somme partielle des deux éléments binaires A_set B_sici avec s = 0 à 3 (les R_entréerespectivement R_entréesont : retenue en entrée respectivement retenue en sortie et « overflow ») . respectivement. On rappelle que l’overflow est une situation que l’on détecte dans la ligne de poids le plus fort en cas de sommation 2 nombres en binaire : le poids le plus fort ne doit pas donner de retenue si les bits de signe sont à 0 et au contraire donner une retenue si les bits de signe sont à 1. L’overflow ou« l'indicateur de débordement est généralement généré par un OU exclusif de la retenue interne à l’intérieur et à l’extérieur du bit de signe. Dans la mesure où le bit de signe est le même que le bit de poids fort d'un nombre considéré comme non signé, l'indicateur de débordement est "vide de sens" et normalement ignoré lors de l'addition ou de la soustraction de nombres non signés. Chacun des quatre additionneurs considérés ici est un additionneur basique 4 bits (on considère ici le cas d’une résolution de 4 bits). Il s’agit d’additionneur complet (additionneur 2 bits avec report de retenue entrante et sortante, en anglais « full adder »). Il ne s’agit pas ici d’un additionneur logique mais d’un additionneur en contraintes QUBO : i.e. tel que son coût minimum est vérifié si et seulement si la configuration des bits est conforme à la table de vérité d’un additionneur binaire.

Pour chaque étape d’addition, une fonction coût QUBO partielle est calculée:(il s’agit ici de la sommation bit à bit de A_set B_s. Les retenues et le résultat de somme intermédiaire sont des valeurs binaires que l’on reporte bit à bit du bit de poids faible (sans retenue entrante) au bit de poids fort (aussi appelé bit de signe)).

En effectuant les additions 2 éléments par 2 éléments pour une ligne donnée, on aboutit àsorties d’additions pour ce premier niveau de sommation partielle (arrondi à l’entier supérieur). En répétant la manœuvre pour les entiers, S₁, etc la sommation complète (composée de sommations de 2 éléments à chaque fois) de la première ligne de l’équation, est ainsi finalement obtenue avec 1 fonction coût partielle par éléments de sommation, et autant de variables intermédiaires.

La figure 7 illustre les opérations de sommes partielles illustrées en considérant à titre d’exemple l’équation :. Il y aura donc 3 résultats intermédiaires surrbits et les retenues qui vont avec, le tout intégré dans une somme de fonction coût QUBO partielle.

Dans le mode de réalisation considéré, N est un entier quelconque supérieur ou égal à 2 ; dans un mode de réalisation, la résolution r est un nombre entier quelconque supérieur ou égal à 2, respectivement à 3, respectivement à 4.

Claims (10)

1. Procédé de traitement dans un ordinateur (1) comprenant un dispositif électronique de traitement (2) et un module d’optimisation (3) adapté pour effectuer des calculs d’optimisation d’un type déterminé parmi Ising et QUBO et tout type réductible à une optimisation Ising ou QUBO, selon lequel ledit procédé comprend les étapes suivantes mises en œuvre par le dispositif électronique de traitement (2) suite à la réception, par le dispositif électronique de traitement, d’une commande de résolution d’un système linéaire initial Ax + B=0,
   où x est le vecteur solution à déterminer x = [x_j]_{j = 0 à N-1}, A =[a_ij]_{i,j = 0 à N-1}et B =[b_j]_{j = 0 à N-1}
   avec en ligne i du système linéaire initial, i =0 à N-1, l’équation : :
   a/ transposition du système linéaire comprenant, dans chaque ligne i, le remplacement de chaque variable par une représentation binaire de basée sur r variables binaires x_jk, j = 0 à N-1 et k = 0 à r-1, où r indique la résolution de la représentation binaire ;
   b/ détermination d’une représentation dans un format prédéfini de type QUBO ou de type Hamiltonien d’Ising du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jk, ladite représentation étant fonction d’au moins les coefficients dudit système linéaire transposé ;
   c/ fourniture de ladite représentation déterminée du système linéaire au module d’optimisation,
   d/ le procédé comprend en outre une détermination, en fonction de ladite représentation fournie, des valeurs des variables binaires x_jkvérifiant ledit système transposé par calcul d’optimisation dudit type déterminé mis en œuvre par ledit module d’optimisation (3)
   ledit procédé étant caractérisé en ce que :
   à l’étape a :
   - la transposition comprend en outre le remplacement de et de par leur représentation binaire basée sur, respectivement, et , k = 0 à r-1, donnant ainsi, pour chaque ligne i du système linéaire initial, r équations chacune correspondant à un poids de bit respectif de 0 à r-1, le système linéaire transposé comprenant ainsi Nxr équations et
   - pour chaque ligne i, des variables binaires additionnelles sont en outre ajoutées pour prendre en compte les retenues binaires issues des opérations réalisées dans les équations aux différents poids de bits et le report desdites retenues aux poids de bit supérieurs ;
   à l’étape b : il est déterminé une représentation dans le format prédéfini du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jket les variables binaires additionnelles, ladite représentation étant déterminée en fonction d’au moins les coefficients dudit système linéaire transposé ;
   à l’étape d, ledit calcul d’optimisation détermine en outre des valeurs des variables binaires additionnelles vérifiant ledit système transposé.
2. Procédé de traitement selon la revendication 1, selon lequel ledit module d’optimisation (3) comprend un calculateur quantique analogique adiabatique à recuit quantique,
   et à l’étape d, ladite détermination est effectuée par calcul quantique analogique adiabatique à recuit quantique mis en œuvre par ledit calculateur quantique analogique adiabatique à recuit quantique.
3. Procédé de traitement selon la revendication 1 ou 2, selon lequel à l’étape a, pour chaque ligne i : les r lignes associées à la ligne i sont traitées successivement par poids de bits croissant, en reportant les retenues issues des poids de bits inférieurs et en introduisant à chacune des r lignes les au plusretenues nécessaires pour garantir l’égalité à 0 de la ligne i.
4. Procédé de traitement selon la revendication 1 ou 2, selon lequel à l’étape a, pour chaque ligne i, il est appliqué une méthode de sommation en arbre binaire selon laquelle il est en outre considéré les sommes partielles deux à deux des termes successifs à sommer dans la ligne, puis de façon itérative, à un niveau donné de l’arbre, il est considéré les sommes partielles deux à deux des sommes partielles du précédent niveau ; et
   dans l’étape b, les variables binaires additionnelles comprennent en outre les représentations binaires des sommes partielles des différents niveaux de l’arbre.
5. Procédé de traitement dans un ordinateur (1) selon l’une quelconque des revendications précédentes, selon lequel, à l’étape b, le gap spectral de ladite représentation est augmenté tout en maintenant la table de vérité.
6. Programme d’ordinateur, destiné à être stocké dans la mémoire d’un dispositif électronique de traitement (2) et comprenant en outre un microcalculateur, ledit programme d’ordinateur comprenant des instructions qui, lorsqu’elles sont exécutées sur le microcalculateur, mettent en œuvre les étapes incombant au dispositif de traitement d’un procédé selon l’une des revendications précédentes.
7. Ordinateur (1) comprenant un dispositif électronique de traitement (2) et un module d’optimisation (3) adapté pour effectuer des calculs d’optimisation d’un type déterminé parmi Ising et QUBO et tout type réductible à une optimisation Ising ou QUBO, dans lequel ledit dispositif électronique de traitement est adapté pour recevoir une commande de résolution d’un système linéaire initial Ax + B=0, où x est le vecteur solution à déterminer x = [x_j]_{j = 0 à N-1}, A =[a_ij]_{i,j = 0 à N-1}et B =[b_j]_{j = 0 à N-}avec en ligne i du système linéaire initial, i =0 à N-1, l’équation : , ledit dispositif (2) étant en outre adapté pour effectuer les traitements suivants :
   a/ transposition du système linéaire comprenant, dans chaque ligne i, le remplacement de chaque variable par une représentation binaire de basée sur r variables binaires x_jk, j = 0 à N-1 et k = 0 à r-1, où r indique la résolution de la représentation binaire ;
   b/ détermination d’une représentation dans un format prédéfini de type QUBO ou de type Hamiltonien d’Ising du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jk, ladite représentation étant fonction d’au moins les coefficients dudit système linéaire transposé ;
   c/ fourniture de ladite représentation déterminée du système linéaire au module d’optimisation,
   ledit module d’optimisation (3) étant adapté pour déterminer, en fonction de ladite représentation fournie, des valeurs des variables binaires x_jkvérifiant ledit système transposé par calcul d’optimisation dudit type déterminé mis en œuvre par
   ledit ordinateur (1) étant caractérisé en ce que :
   à l’étape a :
   - la transposition comprend en outre le remplacement de et de par leur représentation binaire basée sur, respectivement, et , k = 0 à r-1, donnant ainsi, pour chaque ligne i du système linéaire initial, r équations chacune correspondant à un poids de bit respectif de 0 à r-1, le système linéaire transposé comprenant ainsi Nxr équations et
   - pour chaque ligne i, des variables binaires additionnelles sont en outre ajoutées pour prendre en compte les retenues binaires issues des opérations réalisées dans les équations aux différents poids de bits et le report desdites retenues aux poids de bit supérieurs ;
   à l’étape b : il est déterminé une représentation dans le format prédéfini du système linéaire ainsi transposé avec pour variables à déterminer au moins lesdites variables binaires x_jket les variables binaires additionnelles, ladite représentation étant déterminée en fonction d’au moins les coefficients dudit système linéaire transposé ;
   à l’étape d, ledit calcul d’optimisation détermine en outre des valeurs des variables binaires additionnelles vérifiant ledit système transposé.
8. Ordinateur (1) selon la revendication 7, dans lequel ledit module d’optimisation (3) comprend un calculateur quantique analogique adiabatique à recuit quantique,
   et à l’étape d, ladite détermination est effectuée par calcul quantique analogique adiabatique à recuit quantique mis en œuvre par ledit calculateur quantique analogique adiabatique à recuit quantique.
9. Ordinateur (1) selon la revendication 7 ou 8, dans lequel à l’étape a, pour chaque ligne i : les r lignes associées à la ligne i sont traitées successivement par poids de bits croissant, en reportant les retenues issues des poids de bits inférieurs et en introduisant à chacune des r lignes les au plusretenues nécessaires pour garantir l’égalité à 0 de la ligne i.
10. Ordinateur (1) selon la revendication 7 ou 8, dans lequel à l’étape a, pour chaque ligne i, il est appliqué une méthode de sommation en arbre binaire selon laquelle il est en outre considéré les sommes partielles deux à deux des termes successifs à sommer dans la ligne, puis de façon itérative, à un niveau donné de l’arbre, il est considéré les sommes partielles deux à deux des sommes partielles du précédent niveau ; et
    dans l’étape b, les variables binaires additionnelles comprennent en outre les représentations binaires des sommes partielles des différents niveaux de l’arbre.