[PhD position] Computational complexity of reversible computations and applications to quantum programming

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

Inria team : mocqua

Reversible computations have a growing number of challenging application domains such as coding and decoding, testing and verification, database recovery, reversible programming languages or process algebra. Studies on reversible sytems have been successfully applied for modeling biochemical systems [1] and have gained renewed interest due to the reversibility of quantum circuits [2] without measurement. The computability aspects of reversible computations have been deeply studied [3] and the main properties needed for a programming language to be reversible have been delineated [4] leading to the development of reversible programming languages, such as Janus [5]. While a particular attention has been paid to study the semantics properties of such reversible languages [6,7], their complexity-related properties have not been investigated.

This PhD project aims at studying the complexity properties of reversible computations. To that purpose, a particular attention will be paid
to the following tasks:

  1. Design a framework allowing the time complexity analysis of reversible programs.
  2. Characterize and study reversible fragments of standard complexity classes.
  3. Extend the analysis to space complexity and subpolynomial and circuit-based complexity classes.

To achieve these tasks, the use of the main techniques developped in the field of Implicit Computational Complexity [8] will be investigated. These techniques allow for automatic certification of program worst case runtime complexity on several programming paradigms. As applications, we intend to apply the obtained framework to study the complexity of reversible polynomial time programs over the reals [9] and to study the complexity (both in terms of number of gates and using the standard quantum complexity classes [10]) of quantum circuits and quantum programs, such as QPL [11].


The PhD student will be supervised by Romain Péchoux, PhD, HDR, and  by Emmanuel Hainry, PhD in the Inria mocqua, a leading team on implicit computational complexity, computational models and quantum programming. The supervision will be performed by the two supervisors through weekly meetings.


[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