Calcul quantique, résolution des équations de Pell

Encadrants : Fabrice Jaillet (LIRIS-ORIGAMI)
Collaboration : (Universidad de Concepción, Chili)
Détails : Le stage se déroulera au sein du laboratoire LIRIS (bâtiment Nautibus).
Domaine : ordinateur quantique, théorie des nombres.
Compétences requises : C++, éventuellement programmation quantique.

Sujet : En théorie des nombres, il n’y a pas que le théorème de Fermat ! Le problème de Büchi (Büchi's Problem, Wikipedia), aussi connu comme les n-ièmes différences des carrés, reste encore ouvert ! Les séries de Büchi sont des séquences d’entiers telles que la seconde différence de leurs carrés est constante et égale à 2.
Il existe une infinité de suites (non-triviales) de longueur 3 et 4. Celles de longueur 3 sont parfaitement connues. Celles de longueur 4 sont partiellement décrites, grâce notamment aux chercheurs de l’Universidad de Concepción, au Chili. Par contre, il n’existe pas de suite connue de longueur 5…


[Les solutions de l'équations de Pell-Fermat sont toutes sur une des hyperboles]

Une des pistes de recherche conduit à la résolution de l'équation diophantine de Pell-Fermat, x2 − Dy2 = K où D est un entier positif qui n'est pas un carré parfait, et K est un entier non nul. Les solutions cherchées sont telles que x et y soient entiers. Si l'on connait certaines paires (x,y) dites solutions fondamentales de Nagell, alors toutes les solutions se déduisent par une simple élévation à la puissance.

Mais la résolution de cette équation (par l'algorithme des fractions continues par exemple) peut vite devenir problématique, par exemple pour l'équation x2 − 2521y2 = -5040, qui admet 36 classes de solutions fondamentales, qui sont vitre grandes voire très grandes... comme :
(2312803, 46063), (1000000141075710310277093, 19916528332361059018247), (23783647135440471796694885628976327, 473687615194061319439971188129117) ou (19319936939039447868096874823213640181, 384786017141847472045802283284340041) !!

et dans le cadre de la recherche des suites de Büchi, on peut assez vite se trouver à manipuler des nombres encore plus grands, à plusieurs centaines de chiffres. L'utilisation d'un ordinateur quantique prend alors tout son sens !!


L’objectif du projet est donc :

  • Étude de l'équation de Pell-Fermat

  • Étude de l'algorithme quantique existant pour la résolution de l'équation fondamentale (K= ±1), problème décrit ici Quantum Algorithm Zoo (item 3) et PDF

  • Implémentation de l'algorithme sur Machine Quantique dans l'environnement qiskit.org.

  • Extension à la résolution de l'algorithme général quand K ≠ ±1.

  • Génération d'un très grand nombre de suites de Büchi de longueur 4, et test si l'une d'elle s'étend à 5 ??