PhD Position F/M Resource-Aware Quantum Lambda Calculi with Coherent Control

Contexte et atouts du poste The PhD is funded by funded by PEPR EPiQ will be carried out at Inria Nancy Grand-Est within the Inria mocqua project team. Mission confiée Quantum programming languages with quantum control allow the execution flow of programs to depend onquantum data, enabling superpositions of computational paths, as exemplified by the Quantum Switch [1].While this paradigm provides a natural and expressive way to model quantum computation, it raisesfundamental challenges regarding physical implementability and computational complexity. In particular,programs with quantum control must respect both the laws of quantum mechanics and strict resourcebounds in order to admit efficient physical realizations. Recent work [2, 3] has shown that type systems inspired by linear logic and realizability techniques can beused to ensure key physical properties of quantum programs, such as unitarity and feasibility. However, theinteraction between quantum control, higher-order features, and resource guarantees remains only partiallyunderstood. In particular, there is currently no fully satisfactory typed framework that simultaneouslysupports quantum control, higher-order quantum lambda calculi, and precise certifications of time and spacecomplexity. The goal of this PhD is to develop a typed quantum programming language with quantum control in whichresource consumption is certified by construction. The approach will rely on light linear logic and realizabilitytechniques to control duplication and iteration, ensuring that programs normalize within prescribedcomplexity bounds while remaining physically meaningful. A central objective is to design a type system that characterizes quantum complexity classes such as BQP andFBQP in a sound and complete way. This includes establishing a correspondence between typable programsand families of quantum circuits with polynomial-time (and potentially polynomial-space) bounds, therebyproviding an implicit-complexity-style characterization of quantum complexity classes in a higher-ordersetting. Principales activités More specifically, the PhD will address the following research directions: the design of a typed quantum lambda calculus with quantum control, combining linear and lightlinear logic modalities with realizability-based semantics, in order to certify polynomial-timenormalization of quantum programs; the development of sound and complete characterizations of quantum complexity classes such asBQP and FBQP via typing disciplines, extending existing first-order or classically controlled results tohigher-order and quantum controlled languages; the identification of a well-behaved fragment of the language in which programs can be compiledinto quantum circuits (or alternative low-level models) of polynomial size, preserving both semanticsand complexity guarantees; the extension of the analysis to space complexity, with the aim of controlling and certifying thenumber of qubits used during program execution. The obtained results will be published in main conferences and main journals of the domain. Compétences Technical skills and level required : Good level in quantum computing Good level in functional programming Knowledge on type systems Knowledge in complexity theory Languages : english (mandatory) + french Avantages Subsidized meals Partial reimbursement of public transport costs Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.) Possibility of teleworking (after 6 months of employment) and flexible organization of working hours Professional equipment available (videoconferencing, loan of computer equipment, etc.) Social, cultural and sports events and activities Access to vocational training Social security coverage Rémunération 2300€ gross/month References [1] O. Oreshkov, F. Costa and Č. Brukner, “Quantum correlations with no causal order,” Nature Communications, no. 1092, 2012.[2] A. Díaz-Caro, M. Guillermo, A. Miquel and B. Valiron, \"Realizability in the Unitary Sphere,\" in 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019.[3] E. Hainry, R. Péchoux and M. Silva, \"Branch Sequentialization in Quantum Polytime,\" in 10th International Conference on Formal Structures for Computation and Deduction (FSCD), 2025. #J-18808-Ljbffr