[Offre de thèse] Analyse de la complexité des calculs réversibles et applications à l’informatique quantique

Encadrement : Romain Péchoux (romain.pechoux@loria.fr) et Emmanuel Hainry (emmanuel.hainry@loria.fr)

Équipe : mocqua

Financement : concours pour un contrat doctoral

L’étude des modèles de calcul réversibles possède un nombre important de domaine d’application tels que le codage/décodage, les tests de programme et, plus généralement, la vérification, la récupération de base de données, les langages de programmation réversibles ou les algèbres de processus.
Ces études ont été appliquées avec succès à la modélisation de systèmes biochimiques [1] et ont connu un récent regain d’intérêt lié aux propriétés de réversibilité des circuits quantiques sans mesure [2]. Les aspects calculatoires des calculs réversibles ont été étudiés en détail [3] et les principales propriétés nécessaires pour élaborer un langage de programmation réversible sont désormais connues [4]. Ces résultats ont permis le développement de langages réversibles tels que Janus [5]. Alors que des résultats probants ont été obtenus sur les propriétés sémantiques de tels langages réversibles [6,7], leurs propriétés de complexité n’ont pas encore été étudiées en détail.
L’obtention de tels résultats de complexité permet d’envisager des applications à l’informatique quantique dont les circuits sans mesure sont des modèles réversibles.

Dans le cadre de ce doctorat, nous proposons d’étudier les propriété de complexité des langages et modèles de calcul réversibles. Dans ce but, nous attacherons une attention particulière aux tâches suivantes :

  1. Développer des formalismes permettant d’analyser la complexité en temps d’un langage de programmation réversible.
  2. Caractériser et étudier les fragments réversibles des classes de complexité standard.
  3. Etendre cette analyse à la complexité en espace et aux classes de complexité sur les circuits.

Afin d’accomplir ces tâches, nous essaierons d’appliquer les principales techniques développées par la communauté de la complexité implicite [8]. Ces techniques permettent d’analyser automatiquement la complexité, dans le pire cas, de programmes pour différents paradigmes de programmation (fonctionnel, objet, impératif, …). Applications : nous espérons pouvoir appliquer les formalismes obtenus à l’analyse de la complexité de programmes réversibles s’exécutant en temps polynomial sur les réels [9]. Nous espérons aussi pouvoir /étudier la complexité, tant en terme de nombre de portes qu’en terme de classes de complexité quantiques standard [10] sur les circuits quantiques et sur les programmes quantiques, tels que QPL [11].

Encadrement

Le doctorant sera encadré par Romain Péchoux, PhD, HDR, et par Emmanuel Hainry, PhD au sein de l’équipe Inria mocqua, qui possède une forte expertise en complexité implicite, sur les modèles de calcul et sur l’informatique quantique.

References

[1] G. Berry, G. Boudol. The chemical abstract machine. Theoretical computer science, 96:1, Elsevier, 1992.
[2] T. Toffoli: Reversible computing. ICALP 1980.
[3] H. Axelsen, R. Glück. What do reversible programs compute?. FoSSaCS 2011.
[4] T. Yokoyama, H. Axelsen, R. Glück. Principles of a reversible programming language. CF 2008.
[5] T. Yokoyama. Reversible computation and reversible programming languages. Electronic Notes in Theoretical Computer Science,
253:6, Elsevier, 2010.
[6] A. B. Matos, L. Paolini, L. Roversi. On the Expressivity of Total Reversible Programming Languages. RC 2020.
[7] A. B. Matos, L. Paolini, L. Roversi. The fixed point problem of a simple reversible language. Theoretical Computer Science, 813, 2020.
[8] R. Péchoux. Implicit Computational Complexity: Past and Future. Habilitation thesis. Université de Lorraine. 2020.
[9] E. Hainry, D. Mazza, R. Péchoux. Polynomial time over the reals with parsimony. FLOPS 2020.
[10] E. Bernstein, U. Vazirani. Quantum complexity theory. Journal on computing, 26:5, SIAM, 1997.
[11] P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14:4, 2004.

Logo d'Inria