RESEARCH CENTRE

Inria Centre
at Université de Lorraine

IN PARTNERSHIP WITH:

Université de Lorraine, CNRS

2023
ACTIVITY REPORT

Project-Team

MOCQUA

Designing the Future of Computational
Models

IN COLLABORATION WITH: Laboratoire lorrain de recherche en
informatique et ses applications (LORIA)

DOMAIN

Algorithmics, Programming, Software and
Architecture

THEME

Proofs and Verification

Contents

Project-Team MOCQUA

1 Team members, visitors, external collaborators

2 Overall objectives

3 Research program

3.1 Quantum computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Higher-order computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Infinite precision - Dynamical Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Application domains

4.1 Quantum computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Higher-order computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Simulation of dynamical systems by cellular automata . . . . . . . . . . . . . . . . . . . . . .

5 Social and environmental responsibility

6 Highlights of the year

7 New software, platforms, open data

7.1 New software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 FiatLux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2

3

4
4
4
4

5
5
5
6

6

6

7
7
7

8 New results

7
7
8.1 Quantum computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
8.1.1 Quantum programming languages
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8.1.2 Quantum Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.3 Quantum error correcting codes and fault-tolerance . . . . . . . . . . . . . . . . . . .
9
8.1.4 Graph states and Measurement-based quantum computing . . . . . . . . . . . . . . 10
8.2 Computability over topological spaces and polynomial time characterisation . . . . . . . . 10
8.2.1 Producing a point in a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.2.2 Algorithmic properties of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.2.3 Noninterference policies for polynomial time . . . . . . . . . . . . . . . . . . . . . . . 11
8.3 Dynamical systems and combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.3.1 Probabilistic cellular automata for problem solving . . . . . . . . . . . . . . . . . . . . 11
8.3.2 Enumerative or bijective combinatorics
. . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.3.3 Probabilistic or geometric combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . . . . . . 13
8.3.4 Analysis of graphs in the field of economics

9 Bilateral contracts and grants with industry

13
9.1 Bilateral contracts with industry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

10 Partnerships and cooperations

10.2 International research visitors

13
10.1 International initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10.1.1 Inria associate team not involved in an IIL or an international program . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.2.1 Visits of international scientists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.2.2 Visits to international teams
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.3.1 Horizon Europe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.3.2 H2020 projects
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.3.3 Other european programs/initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.4 National initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.4.1 ANR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

10.3 European initiatives

10.4.2 Other initiatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

11 Dissemination

18
11.1 Promoting scientific activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.1.1 Scientific events: organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.2 Journal
11.1.3 Invited talks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.4 Leadership within the scientific community . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1.5 Scientific expertise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.1.6 Research administration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.2 Teaching - Supervision - Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.2.1 Supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.2.2 Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.3 Popularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.3.1 Interventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

12 Scientific production

23
12.1 Major publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12.2 Publications of the year
12.3 Other . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
12.4 Cited publications

Project MOCQUA

1

Project-Team MOCQUA

Creation of the Project-Team: 2020 March 01

Keywords

Computer sciences and digital sciences

A2.3.2. – Cyber-physical systems

A2.4.1. – Analysis

A6.5. – Mathematical modeling for physical sciences

A7.1.4. – Quantum algorithms

A7.2. – Logic in Computer Science

A7.3. – Calculability and computability

A8.1. – Discrete mathematics, combinatorics

A8.3. – Geometry, Topology

A8.6. – Information theory

Other research topics and application domains

B9.5.1. – Computer science

B9.5.2. – Mathematics

B9.5.3. – Physics

2

Inria Annual Report 2023

1 Team members, visitors, external collaborators

Research Scientists

• Simon Perdrix [Team leader, INRIA, Senior Researcher, HDR]

• Mathilde Bouvel [CNRS, Researcher]

• Nazim Fates [INRIA, Researcher, HDR]

• Isabelle Gnaedig-Antoine [INRIA, Researcher]

• Mathieu Hoyrup [INRIA, Researcher, HDR]

• Christophe Vuillot [INRIA, Researcher]

Faculty Members

• Guilhem Gamard [UL, Associate Professor]

• Emmanuel Hainry [UL, Associate Professor]

• Emmanuel Jeandel [UL, Professor, HDR]

• Julien Provillard [UL, Associate Professor]

• Romain Péchoux [UL, Associate Professor, HDR]

PhD Students

• Djamel Amir [LORIA, ATER, from Oct 2023]

• Djamel Amir [UL, until Sep 2023]

• Agustin Borgna [LORIA, until Jan 2023]

• Nathan Claudet [INRIA]

• Alexandre Clement [INRIA, until Apr 2023]

• Kinnari Dave [INRIA]

• Noé Delorme [INRIA, from Jul 2023]

• Alexandre Guernut [INRIA]

• Joannes Guichon [INRIA]

• Mario Machado Da Silva [UL]

• Pierre-Adrien Tahay [UL, ATER, from Sep 2023]

• Benjamin Testart [UL]

• Vivien Vandaele [CNRS]

Technical Staff

• Cole Comfort [CNRS, Engineer, from Oct 2023]

Project MOCQUA

3

Interns and Apprentices

• Kathleen Barsse [UL, Intern, from Mar 2023 until Aug 2023]

• Noé Delorme [CNRS, Intern, until Jun 2023]

• Rachel Dufau-Sansot [UL, Intern, until Jul 2023]

• Kévin Engrand [UL, Intern, from Mar 2023 until Aug 2023]

• Tom Favereau [UL, Intern, from Oct 2023]

• Nathan Faynot [UL, Intern, from Apr 2023 until Jun 2023]

• Théo Joffroy [UL, Intern, from Apr 2023 until Jun 2023]

• Martin Novello [UL, Intern, from Mar 2023 until Sep 2023]

Administrative Assistants

• Juline Brevillet [UL, from Apr 2023]

• Sophie Drouot [INRIA]

• Sylvie Hilbert [CNRS]

• Josiane Reffort [CNRS, until Sep 2023]

Visiting Scientists

• Nikolas Breuckmann [University of Bristol, until Jan 2023]

• Alejandro Diaz-Caro [Universidad Nacional de Quilmes and ICC (CONICET / Universidad de

Buenos Aires), from Nov 2023]

External Collaborator

• Luc Sanselme [Ministère Education]

2 Overall objectives

The goal of the Mocqua team is to tackle challenges coming from the emergence of new or future
computational models. The landscape of computational models has indeed changed drastically in the
last few years: the complexity of digital systems is continually growing, which leads to the introduction
of new paradigms, while new problems arise due to this larger scale (tolerance to faulty behaviors,
asynchronicity) and constraints of the present world (energy limitations). In parallel, new models based
on physical considerations have appeared. There is thus a real need to accompany these changes, and we
intend to investigate these new models and try to solve their intrinsic problems by computational and
algorithmic methods.

While the bit remains undeniably the building block of computer architecture and software, it is
fundamental for the development of new paradigms to investigate computations and programs working
with inputs that cannot be reduced to finite strings of 0’s and 1’s. Our team focuses on a few instances
of this phenomenon: programs working with qubits (quantum computing), programs working with
functions as inputs (higher-order computation) and programs working in infinite precision (real numbers,
infinite sequences, streams, coinductive data, ...).

In the Mocqua team, we address problems that can lie at the interface with physics, biology, or
mathematics. We employ tools and methods originating from computer science, that we sometimes
enrich through these interdisciplinary interactions.

4

Inria Annual Report 2023

Mocqua is structured around three models: Quantum Computing, Higher-Order Computing and
Computing with infinite precision. The last term is arguably quite large in scope and will mostly stand
here for dynamical systems. While quantum computing and higher-order computing are decidedly
different, it turns out that similar techniques can be used to answer their specific problems.

These three models are discussed more precisely in the following section.

3 Research program

3.1 Quantum computing

The field of quantum computing is currently experiencing a rapid growth, at the same time on the
experimental physics and hardware side as well as the theoretical side, involving physics, mathematics
and computer science. At the creation of Mocqua in 2018, only a handful of very primitive programmable
quantum computer prototypes existed in the world. Whereas today, many academic and industrial
groups try to build and operate them. These prototypes are still only very small scale and very noisy
without any systematic error correction applied. Most of them differ fundamentally on the hardware
substrate, and it is quite hard to predict which solution will take the lead when scaling up.

The landscape of quantum programming languages is also constantly evolving. Comparably to
compiler design, the foundation of quantum software therefore relies on an intermediate representation
that is suitable for manipulation, easy to produce from software, and easily encodable into hardware.
The languages of choice for this are the historical and ubiquitous quantum circuit model, and the more
recent, flexible and powerful ZX-calculus.

Regardless of the models that will take the lead, the hurdles into scaling up quantum computers from
a few noisy qubits to many almost noiseless qubits remain similar. Understanding how to use near- and
mid-term devices; how to implement quantum error correction and fault-tolerant operations; how to
compile for and program large-scale quantum computers all stand at the heart of the challenge.

3.2 Higher-order computing

While programs often operate on natural numbers or finite structures such as graphs or finite strings, they
can also take functions as input. In that case, the program is said to perform higher-order computations,
or to compute a higher-order functional. Functional programming or object-oriented programming are
important paradigms allowing higher-order computations.

While computability and complexity theories are well developed for first-order programs, difficulties
arise when dealing with higher-order programs. There are many non-equivalent ways of presenting
inputs to such programs: an input function can be presented as a black box, encoded in an infinite
binary sequence, or sometimes by a finite description. Comparing those representations, both from
complexity and computability perspectives, is an important problem. A particularly useful application of
higher-order computations is to compute with infinite objects that can be represented by functions or
symbolic sequences. The theory is well understood in many cases (to be precise, when these objects live
in a topological space with a countable basis), but is not well understood in other interesting cases. For
instance, when the inputs are second-order functionals (of type (N → N) → (N → N)), these results do not
apply and many problems are still open.

3.3 Infinite precision - Dynamical Systems.

The most natural example of a computation with infinite precision is the evolution of a dynamical system.
The underlying space might be Rn in the case of the simulation of physical systems, or the Cantor space
{0, 1}

in the case of discrete dynamical systems.

Z

From the point of view of computation, the main point of interest is the link between the long-term
behavior of a system and its initial configuration. There are two questions here: (a) predict the behavior,
(b) design dynamical systems with some prescribed behavior. We mainly examine the first one through
the angle of reachability and more generally control theory for hybrid systems.

The model of cellular automata is of particular interest. This computational model is relevant for sim-
ulating complex global phenomena which emerge from local interactions between simple components.

Project MOCQUA

5

It is widely used in various natural sciences (physics, biology, etc.) and in computer science, as it is an
appropriate model to reason about errors that occur in systems with a great number of components.

The simulation of a physical dynamical system on a computer is made difficult by various aspects.
First, the parameters of the dynamical systems are seldom exactly known. Secondly, the simulation is
usually not exact: real numbers are usually represented by floating-point numbers, and simulations of
cellular automata only simulate the behavior of finite or periodic configurations.

4 Application domains

4.1 Quantum computing

Quantum computing is currently the most promising technology to extend Moore’s law, whose end is
expected to be reached soon with engraving technologies struggling to reduce transistor size. Thanks to
promising algorithmic and complexity theoretic results on its computational power, quantum computing
will represent a decisive competitive advantage for those who will control it.

Quantum computing is also a major security issue, since it allows us to break today’s asymmetric
cryptography. Hence, mastering quantum computing is also of the highest importance for national
security concerns. Small-scale quantum computers already exist and recent scientific and technical
advances suggest that the construction of the first practical quantum computers will be possible in the
coming years.

As a result, the major US players in the IT industry have embarked on a dramatic race, mobilizing huge
resources: IBM, Microsoft, Google and Intel have each invested huge sums of money, and are devoting
significant budgets to attract and hire the best scientists on the planet. Some states have launched ambi-
tious national programs, including United Kingdom, Netherlands, Canada, China, Australia, Singapore,
and very recently the European Union, with the 10-year FET Flagship program in Quantum Engineering.
The French government also recently announced its Plan Quantique – a 1.8 billion euros initiative to
develop quantum technologies.

An important pillar of the Plan Quantique concerns the development of Large Scale Quantum com-

puters. This will come with progress all across the quantum stack.

The Mocqua team contributes to the computer science approach to quantum computing, with
expertise ranging all across the quantum stack from quantum software to fault tolerance and quantum
error correction. We aim at a better understanding of the power and limitations of the quantum computer,
and therefore of its impact on society. We also contribute to ease the development of the quantum
computer by filling gaps across the quantum stack from programming languages to compilation and
intermediate representations for faul-tolerant implementations on hardware.

4.2 Higher-order computing

The idea of considering functions as first-class citizens and allowing programs to take functions as inputs
has emerged since the very beginning of theoretical computer science through Church’s λ-calculus and is
nowadays at the core of functional programming, a paradigm that is used in modern software and by
digital companies (Google, Facebook, . . . ). In the meantime higher-order computing has been explored
in many ways in the fields of logic and semantics of programming languages.

One of the central problems is to design programming languages that capture most of, if not all,
the possible ways of computing with functions as inputs. There is no Church thesis in higher-order
computing and many ways of taking a function as input can be considered: allowing parallel or only
sequential computations, querying the input as a black-box or via an interactive dialog, and so on.

The Kleene-Kreisel computable functionals are arguably the broadest class of higher-order continuous
functionals that could be computed by a machine. However their complexity is such that no current
programming language can capture all of them. Better understanding this class of functions is therefore
fundamental in order to identify the features that a programming language should implement to make
the full power of higher-order computation expressible in such a language.

Higher-order computing provides a model for computations involving real numbers and other math-
ematical objects that cannot be finitely represented. Indeed, such infinite objects can be encoded as

6

Inria Annual Report 2023

functions or streams of bits, which can then be given as inputs to a higher-order program. This method
raises many questions, such as the impact of the encoding on the solvability and complexity of problems,
and its relationship with the mathematical structures underlying the spaces of objects, such as a topology
or a partial order.

4.3 Simulation of dynamical systems by cellular automata

We aim at developing various tools to simulate and analyse the dynamics of spatially-extended discrete
dynamical systems such as cellular automata. The emphasis of our approach is on the evaluation of the
robustness of the models under study, that is, their capacity to resist various perturbations.

In the framework of pure computational questions, various examples of such systems have already
been proposed for solving complex problems with a simple bio-inspired approach (e.g. the decentralized
gathering problem [50]). We are now working on their transposition to various real-world situations. For
example when one needs to understand the behaviour of large-scale networks of connected components
such as wireless sensor networks. In this direction of research, a first work has been presented on how to
achieve a decentralized diagnosis of networks made of simple interacting components and the results
are rather encouraging [52]. Nevertheless, there are various points that remain to be studied in order to
complete this model for its integration in a real network.

We have also tackled the evaluation of the robustness of a swarming model proposed by A. Deutsch to
mimic the self-organization process observed in various natural systems (birds, fishes, bacteria, etc.) [4].
We now wish to develop our simulation tools to apply them to various biological phenomena where many
agents are involved.

We are also currently extending the range of applications of these techniques to the field of economy.
We have started a collaboration with Massimo Amato, a professor in economy at the Bocconi University
in Milan. Our aim is to propose a decentralized view of a business-to-business market and totally
decentralized, agent-oriented models of such markets. Various banks and large businesses have already
expressed their interest in such modeling approaches.

5 Social and environmental responsibility

The main footprint of the research activities of the team is due the attendance of scientific events. We
give preference to participation by videoconference or to travel by train for events in Europe.

Given our topics of research, their environmental impact is modest. However, we have cooperated in
the recent past with EDF though a CIFRE PhD on quantum algorithms for optimisation problems with
applications in fleet electric vehicle charging.

6 Highlights of the year

• One of the major questions in quantum computing is to demonstrate in practice the advantage of
the quantum computer compared to classical ones. For instance some sampling problems have
been shown to be hard for classical computers while easy for quantum computers. The main
difficulty in implementing such sampling problems is that the quantum advantage can be washed-
up by noise in the device. We showed how to implement a minimal amount of error correction to
be able to demonstrate a robust and scalable advantage [26], and our publication was accepted for
a plenary talk at the QIP2024 conference, the main conference in the field.

• The Quantum circuit model is ubiquitous in quantum computing. We have introduced the first
complete equational theory for quantum circuits, a problem which was open for more than 30 years.
This result opens new avenues for quantum circuit transformations including circuit optimisation
and hardware constraint satisfaction. The paper was accepted at LICS’23 [18], and also presented
at TQC’23 [25].

• We have introduced a new noninterference policy to capture the class of functions computable
in polynomial time on an object-oriented programming language. This policy makes a clear

Project MOCQUA

7

separation between the standard noninterference techniques for the control flow and the layering
properties required to ensure that each "security" level preserves polynomial time soundness, and
is thus very powerful as for the class of programs it can capture. This result was presented at POPL
2023 [22].

7 New software, platforms, open data

7.1 New software

7.1.1 FiatLux

Keywords: Cellular automaton, Multi-agent, Distributed systems, Numerical simulations

Scientific Description: FiatLux is a discrete dynamical systems simulator that allows the user to ex-
periment with various models and to perturb them. It includes 1D and 2D cellular automata,
moving agents, interacting particle systems, etc. Its main feature is to allow users to change the
type of updating, for example from a deterministic parallel updating to an asynchronous random
updating. FiatLux has a Graphical User Interface and can also be launched in a batch mode for the
experiments that require statistics.

Functional Description: FiatLux is a cellular automata simulator in Java specially designed for the study
of the robustness of the models. Its main distinctive features are to allow users to perturb the
updating of the system (synchrony rate) and the topology of the grid.

URL: https://project.inria.fr/fiatlux/

Contact: Nazim Fates

Participant: Nazim Fates

Partners: ENS Lyon, Université de Lorraine

8 New results

8.1 Quantum computing

Participants: Mathilde Bouvel, Nathan Claudet, Alexandre Clément, Kinnari Dave,
Noé Delorme, Alexandre Guernut, Emmanuel Hainry, Emmanuel Jean-
del, Romain Péchoux, Simon Perdrix, Mário Silva, Vivien Vandaele,
Christophe Vuillot.

Quantum software is crucial in the development of the quantum computer. In the Mocqua team,
we contribute to the development of the quantum stack with several complementary results, from high
level programming languages, to models of quantum computation, through quantum circuits and error
correcting codes.

8.1.1 Quantum programming languages

Quantum programming languages are essential for developing new algorithms and actually using the
quantum computer. We have two contributions described in this section, based on the introduction
of two languages: Qimaera dedicated to some particular classes of quantum algorithms, including
variational quantum algorithms, a particular promising family of quantum algorithms for short terms
applications; The second contribution is the FOQ language which, in the implicit complexity framework,
captures quantum polynomial time, so roughly speaking a FOQ program is guaranteed by construction
to run in polynomial time on a quantum computer.

8

Inria Annual Report 2023

Variational quantum programming in Idris. Variational Quantum Algorithms [58, 55, 49] are hybrid
classical-quantum algorithms where classical and quantum computation work in tandem to solve compu-
tational problems. These algorithms create interesting challenges for the design of suitable programming
languages, because they have to be able to accommodate both classical and quantum programming
primitives simultaneously.

As part of this research project, we develop a set of libraries for the Idris 2 programming language
that enable the programmer to implement (variational) quantum algorithms where the full power of the
elegant Idris language works in synchrony with quantum programming primitives that we introduce. The
two key ingredients of Idris that make this possible are (1) dependent types which allow us to implement
unitary (i.e. reversible and controllable) quantum operations; and (2) linearity which allows us to enforce
fine-grained control over the execution of quantum operations that ensures compliance with the laws
of quantum mechanics. We demonstrate that our libraries, named Qimaera, are suitable for variational
quantum programming by providing implementations of the two most prominent variational quantum
algorithms – QAOA [49] and VQE [58]. To the best of our knowledge, this is the first implementation of
these algorithms that has been achieved in a type-safe framework.

The results of this work were presented in 2023 in the conference ESOP [19]. The software is open-
source, available under the MIT license here. These results were obtained during the (bachelor) internship
of Liliane-Joy Dandy in our team and she was awarded the "Research Internship Prize" at École Poly-
technique for her work.

Characterization of quantum polynomial time. In [23], we introduce a First-Order Quantum program-
ming language, hence named FOQ, whose terminating programs are reversible. We restrict FOQ to a strict
and tractable subset – called PFOQ for polynomial FOQ – of terminating programs with bounded width,
that provides a first programming language-based characterization of the quantum complexity class
FBQP. FBQP is the functional extension of the class BQP known as Bounded-error Quantum Polynomial
time, the class of decision problems that can be solved by a polynomial time quantum Turing machine
with probability greater than 2/3. We finally present a tractable semantics-preserving algorithm compiling
a PFOQ program to a quantum circuit of size polynomial in the number of input qubits.

8.1.2 Quantum Circuits

The quantum circuit model is the most standard model of quantum computing. Quantum circuits are
ubiquitous in quantum computing, serving as both a low-level language and, surprisingly, a higher-level
language used to describe certain quantum algorithms. We have introduced the first complete equational
theory for quantum circuits, for reasoning on quantum circuits; we have also introduced new techniques
for quantum circuit optimisation.

Completeness for Quantum Circuits. With the current advances in quantum technologies and quantum
software, it is essential to develop formalisms for transforming and reasoning about quantum circuits.
This is crucial for optimizing their size or depth, adapting code to architectural constraints, making it
fault-tolerant, or verifying the equivalence of two circuits.

To achieve these goals, quantum circuits can be equipped with equational theories that enable the
transformation of circuits using rules that are preferably simple and intuitive. These rules allow the
replacement of a circuit fragment with an equivalent circuit. An equational theory is considered complete
when, for any pair of circuits representing the same quantum evolution, there is a way to transform one
into the other using only the rules of the equational theory.

We have introduced the first complete equational theory for quantum circuits [18], a problem which
was open for more than 30 years. Indeed the only fragments equipped with a complete equational
theory before, were non-universal and efficiently classically simulatable [59, 43, 44, 53]. This result has
been presented at LICS’23. We have obtained the completeness for quantum circuits through a non-
trivial completion procedure based on the LOv-calculus [47] for which we have introduced a complete
equational theory recently. This result has been obtained in collaboration with the Quacs Inria team in
Saclay and the start-up Quandela.

This year, we have also simplified and generalised this equational theory to quantum circuits involving
ancillary qubits and quantum measurements [17]. This result will be presented at CSL’24. Finally, we have
recently a minimal equational theory for vanilla quantum circuits (i.e. the standard model of quantum
circuits without ancillary qubits) that we have proved to be minimal, i.e. each rule is necessary for the

Project MOCQUA

9

completeness [36]. One of the main and original contributions of this paper is demonstrating that the use
of a rule acting on an unbounded number of qubits is necessary for completeness.

Hadamard count minimization in Clifford+T circuits. We have introduced an algorithm which essen-
tially optimally minimizes the number of Hadamard in a Clifford+T circuit. When compiling quantum
circuit with the gate set Clifford+T, one usually tries to minimize the number of T gates. This is because
T gates are usually more costly to implement fault-tolerantly. This minimization problem when there
are no Hadamard gates in the circuit is well understood. To handle the general case one can optimize
around Hadamard gates or use some gadgetisation techniques. In both cases minimizing the number of
Hadamard gate in the circuit beforehand can also help reducing the number of T gates overall.

This work has been done in collaboration with Simon Martiel (Atos), and has been accepted in
the ACM journal Transactions on Quantum Computing [40] and has been presented at the prestigious
conference TQC’23 [24].

8.1.3 Quantum error correcting codes and fault-tolerance

Quantum error correcting codes are crucial in the quest of a fault-tolerant large-scale quantum computer.
We have contributed to the development of surface codes, we have also introduced a new family of
quantum codes, the quantum rotor codes, finally and may be more surprisingly, we have shown that
minimalist error correcting codes can be used in near-term experiments for demonstrating a separation
between classical and quantum computers.

Fault-tolerant Clifford gates on toric codes. Quantum error correcting codes with good encoding rates
promise to reduce the cost of fault-tolerant quantum computation by reducing the number of physical
qubits needed for a target level of protection and number of logical qubits needed. The savings come at
the price of more complex procedures for the implementation of gates on logical qubits within the code.
One technique for homological codes from 2D manifold is to apply a Dehn twist to a handle of the surface
which implements a CNOT gate between the logical qubits of the handle. Alexandre Guernut for his PhD
studied the generalization of Dehn-twists to other 2D codes, namely color codes. We discovered that in
practice for small system size the color code Dehn twists were spreading too much the noise. Therefore
we switched gears by unfolding the color code to two copies of the toric code and set out to design and
evaluate the performance of a generating set of the Clifford group on toric codes that would have a
constant-depth implementation. The numerical results are now promising and a paper is in preparation.

Quantum rotor codes. The work [41] is a collaboration in progress with Barbara Terhal (Delft University)
and Allessandro Ciani (Forschungszentrum Jülich). Quantum systems in real laboratories do not always
consist in a set of qubits but often systems with a richer structure for their Hilbert space. For instance they
are often infinite dimensional, as are quantum oscillators or quantum rotors. Exploiting the structure
and knowledge of the full physical system when designing quantum error correcting codes is a promising
way of reducing the overhead of error correction. Quantum error correction with quantum oscillators has
been well studied either for encoding qubits within quantum oscillators (the field of bosonic codes) or
encoding oscillators in several oscillators for which several no-gos have been proven. Quantum rotors
can be thought as intermediate systems between qubits (finite) and quantum oscillators (infinite and
continuous). We are studying quantum error correcting codes for quantum rotors both encoding finite
or infinite logical information. The codes we defined encoding finite systems have some similarity with
so-called protected superconducting qubits such as the 0-π qubit. Moreover our construction generalizes
to more protected qubits potentially realizable in superconducting circuits. This was submitted and
accepted for publication in Communication in Mathematical Physics.

Robust Sparse IQP Sampling in Constant depth. In collaboration with the Inria teams Quantic and
Cosmiq we studied the problem of making the sparse instantaneous quantum polynomial-time (IQP)
sampling problem robust to noise and constant depth, therefore making it more accessible to near-term
experiments [26]. Sparse IQP sampling problems are problems that are demonstrably hard to sample
from with a classical computer but straightforward for a quantum computer and hence candidates for
demonstration of quantum advantage. The problem is that convincing advantage needs to be able to
scale up the quantum circuit which cannot be done in the presence of noise. This work shows how to use
the minimal amount of quantum error correction necessary to be able to scale while correcting errors.
This work has been accepted for a plenary talk at the QIP2024 conference.

10

Inria Annual Report 2023

8.1.4 Graph states and Measurement-based quantum computing

There are various models of quantum computation. Whereas unitary evolutions are at the heart of the
standard model of quantum computing, measurement-based quantum computing (MBQC) is an altern-
ative model introduced more than 20 years ago, which consists in performing quantum measurements
over a large entangled initial resource called a graph state. We have contributed to the development
of MBQC and also to a recent graph-state-based protocol called k-parability which is a primitive for
distributed quantum computing.

Measurement-based quantum computing on qudit-graph states. In measurement-based quantum
computing (MBQC), computation is carried out by a sequence of measurements and corrections on an
entangled state. Flow, and related concepts that we have contributed to develop in the past decades
[56, 57], are powerful techniques for characterising the dependence of the corrections on previous
measurement outcomes. We have introduced flow-based methods for MBQC with qudit graph states
when the local dimension of the entangled state is an odd prime. Our main results are a proof that such
flow is a necessary and sufficient condition for a strong form of determinism. This work has been done
in collaboration with Aleks Kissinger (Oxford), Damian Markham (LIP6), Clément Meignant (LIP6) and
Robert Booth who did a joint PhD in the Mocqua team and LIP6 and who is now postdoc in Edinburgh.
This paper has been publish in Journal of Physics A: Mathematical and Theoretical [13].

Small pairable states. A k-pairable n-qubit state is a resource state that allows Local Operations and
Classical Communication (LOCC) protocols to generate pairs of maximally entangled 2-qubit states
among any k-disjoint pairs of the n qubits. The best known resource states, introduced by Bravyi et al.
[45], had a number of qubits growing exponentially with the parameter k. We have shown the existence
of ‘small’ pairable quantum states with a number n of qubits polynomial in k. We have also established
bounds on the pairability, relating this quantity to other graph parameters, in particular the local minimal
degree. We have also extended the notion of pairability to vertex minor universality, a natural graph
property. This work has been done in collaboration with Mehdi Mhalla (LIG, Grenoble) [35]. We are
currently working in collaboration with Stéphan Thomassé (LIP, ENS Lyon), Valentin Savin and Maxime
Cautrès (CEA Grenoble) on the extensions of these results.

8.2 Computability over topological spaces and polynomial time characterisation

Participants: Djamel Eddine Amir, Isabelle Gnaedig, Emmanuel Hainry, Math-

ieu Hoyrup, Romain Péchoux.

Our main results on Axis 2 are on the computability over topological spaces, as well as a character-
isation of polynomial time in object-oriented programming languages. Notice that the results on the
characterisation of quantum polynomial time, presented in the previous section are at the intersection of
axis 1 and 2, and could have been presented in this section.

8.2.1 Producing a point in a set

We have studied the solvability of the following problem: given a set in a fixed space, produce a point in
that set. This problem was studied in [46] for various spaces. It was proved that for a restricted class of
spaces, this problem is solvable precisely when the space is in some sense complete. We have shown that
this characterization fails for general spaces but holds under a natural modification of the problem, by
allowing more sets as inputs. The results are published in [15].

8.2.2 Algorithmic properties of sets

We investigated the relationship between the computability of sets and their topological properties. More
precisely, we are studying which sets have “computable type”, which is the property that any algorithm
that semidecides the set can be converted into an algorithm that fully decides the set. We have shown
that this property is equivalent to the fact that the set satisfies an invariant of low complexity, and such
that no proper subset satisfies this invariant. For instance, the circle is minimal satisfying the invariant

Project MOCQUA

11

“having a hole”. This result unifies many previous results, implies new results and opens up a new research
direction: finding invariants of low complexity. The result is published in [11].

In the study of computable type, one also wants to show that a set does not have computable
type, by producing a copy of the set which is semicomputable but not computable. This task can be
difficult, especially if the set is not expliticly given but is defined in an implicit way. We have obtained
a very general result which characterizes when two notions of computability are not equivalent, using
topological arguments. This gives a much simpler way of separating two computability notions, reducing
it to a comparison between two topologies. The result is published in [10].

To a topological space is associated the problem of producing a presentation of this space. We have
investigated the possible degrees of difficulty of this problem. This study requires the understanding of
the algorithmic complexity of detecting various topological invariants, notably the ones coming from
homology and which count the holes in the space. The results are published in [16].

8.2.3 Noninterference policies for polynomial time

In [22], we introduce a new noninterference policy to capture the class of functions computable in
polynomial time on an object-oriented programming language. This policy makes a clear separation
between the standard noninterference techniques for the control flow and the layering properties required
to ensure that each "security" level preserves polynomial time soundness, and is thus very powerful as for
the class of programs it can capture. This new characterization is a proper extension of existing tractable
characterizations of polynomial time based on safe recursion. Despite the fact that this noninterference
policy is Π0
1-complete, we show that it can be instantiated to some decidable and conservative instance
using shape analysis techniques.

8.3 Dynamical systems and combinatorics

Participants: Mathilde Bouvel, Nazim Fatès, Guilhem Gamard, Joannès Guichon,
Emmanuel Jeandel, Julien Provillard, Benjamin Testart.

Regarding Axis 3 of the team, we have contributions on probabilistic cellular automata, on probabil-
istic and enumerative combinatorics, and also in analysis of graphs in the field of economics. The latter
have been developed in the context of the exploratory research action Murene.

8.3.1 Probabilistic cellular automata for problem solving

The decentralised diagnosis problem consists in the detection of a certain amount of defects in a distrib-
uted network. We continued our work with Régine Marchand (IECL, Université de Lorraine) and Irène
Marcovici (now at Université de Rouen) [20]. We tackled this problem in the context of two-dimensional
cellular automata with three states: given a threshold of defects to detect, we want the alert state to
coexist with the neutral state when this density is above the threshold, we want the alert state to invade
the whole grid. We presented two probabilistic rules to solve this problem. The first one is isotropic
and is studied with numerical simulations. The second one is defined on Toom’s neighbourhood and is
examined with an analytical point of view. These solutions constitute a first step towards a broader study
of the decentralised diagnosis problem on more general networks.

8.3.2 Enumerative or bijective combinatorics

Baxter Tree-like tableaux. The article [12] is the result of a collaboration of M. Bouvel started at LaBRI
in 2012 (when she was there), with J.-C. Aval, A. Boussicault, O. Guibert and M. Silimbani. It has been
completed and submitted in 2021, but has then been largely revised and published in 2023.

Tree-like tableaux are objects in bijection with alternative or permutation tableaux, which are classical
objects in combinatorics. Our work defines and studies a new subclass of tree-like tableaux enumerated
by the famous Baxter numbers. We exhibit simple bijective links between these objects and three other

12

Inria Annual Report 2023

combinatorial classes: (packed or mosaic) floorplans, twisted Baxter permutations and triples of non-
intersecting lattice paths. From several (and unrelated) works, these last objects are already known to be
enumerated by Baxter numbers, and our main contribution is to provide a unifying approach to bijections
between Baxter objects, where Baxter tree-like tableaux play the key role.

Enumeration of pattern-avoiding inversion sequences. The results presented here have been obtained
by Benjamin Testart during the first year of his PhD thesis. They are concerned with inversion sequences,
which are integer sequences (σ1, . . . , σn) such that 0 ≤ σi < i for all 1 ≤ i ≤ n. The study of pattern-
avoiding inversion sequences began in two independent articles [54, 48], which solved the enumeration
of inversion sequences avoiding a single pattern for every pattern of length 3 except the patterns 010 and
100. The case 100 was recently solved by Mansour and Yildirim.

In his 2022 preprint, Benjamin solves the final case by making use of a decomposition of inversion
sequences avoiding the pattern 010 according to original parameters. The method is then expanded to
solve the enumeration of inversion sequences avoiding several pairs of patterns containing 010, most of
the time solving also the enumeration of some family of constrained words as an auxiliary problem.

In a paper that is currently being written, Benjamin in addition managed to obtain all missing
enumerations for inversion sequences avoiding a pair of patterns of size 3 (17 such families in total). To
achieve this, Benjamin has used in a clever way the (established) method of generating trees in a few
cases, and has otherwise used several decompositions of inversion sequences that he introduced. This
work will be submitted soon to a good journal in combinatorics.

8.3.3 Probabilistic or geometric combinatorics

Convergence law for 231-avoiding permutations. In earlier work with Michael Albert (University of
Otago) and Valentin Féray (IECL, Université de Lorraine), we compared the expressibility of two logics
on permutations, called TOOB (theory of one bijection, seeing permutations as a bijection) and TOTO
(theory of two orders, seeing permutations as a pair of total orders). In the paper [9] (recently accepted for
publication in DMTCS, in the special issue following the conference Permutation Patterns 2023), we focus
on TOTO, and study a different problem. Namely, we investigate the existence of 0/1 or convergence
laws when the domain is restricted to families of permutations avoiding patterns, similarly to a classical
approach in the study of graphs.

Specifically, we prove that the class of 231-avoiding permutations satisfies a convergence law (but
not a 0/1 law). In other words, for any first-order sentence ψ in the language TOTO of two total orders,
the probability pn(ψ) that a uniform random 231-avoiding permutation of size n satisfies ψ admits a
limit as n is large. Moreover, we establish two further results about the behaviour and value of pn(ψ): (i)
it is either bounded away from 0, or decays exponentially fast; (ii) the set of possible limits is dense in
[0, 1]. Our tools come mainly from analytic combinatorics and singularity analysis. We hint at possible
generalisations to other families of pattern-avoiding permutaitons.

Scaling limits of families of intersection graphs. This is the latest result of a collaboration of M. Bouvel
with Frédérique Bassino (LIPN, Université Paris Nord), Valentin Féray (IECL, Université de Lorraine),
Lucas Gerin (CMAP, École Polytechnique) and Adeline Pierrot (LISN, Université Paris-Sud) which started
over ten years ago. The purpose of this collaboration is to establish limit shape results for combinatorial
structures (like permutations or graphs) constrained by the avoidance of substructures, often using
methods from analytic combinatorics (which is original in the landscape of the research on this topic).
In an almost finished paper, we obtain the scaling limits of random graphs drawn uniformly in three
families of intersection graphs: permutation graphs, circle graphs, and unit interval graphs. The two first
families typically generate dense graphs (with a quadratic number of edges), and in these cases we prove
almost sure convergence to an explicit deterministic graphon. Uniform unit interval graphs are nondense
and we prove convergence in the sense of Gromov–Prokhorov after normalization of the distances.

Decomposition of order types, with applications to counting problems. This topic, at the interface
of combinatorics and discrete geometry, has emerged as the result of a collaboration between several
teams in Nancy, and involves M. Bouvel, V. Feray (IECL, Université de Lorraine), X. Goaoc (Gamble) and
F. Koechlin (post-doc with X. Goaoc until September 2023). In this undergoing work, we introduce and
study an original notion of decomposition of planar point sets (or rather of their chirotopes, also called
order types) as trees decorated by smaller chirotopes. This decomposition is based on the concept of

Project MOCQUA

13

mutually avoiding sets, and adapts in some sense the modular decomposition of graphs (or its cousin the
substitution decomposition of permutations) in the world of chirotopes. We prove that the associated
tree always exists and is unique up to some appropriate constraints. We also show how to compute the
number of triangulations of a chirotope efficiently, starting from its tree and the (weighted) numbers of
triangulations of its parts.

8.3.4 Analysis of graphs in the field of economics

In collaboration with Massimo Amato and Lucio Gobbi (Bocconi University and University of Trento), we
developed some economic and operational foundations of a new method of financing companies’ finan-
cial obligations [51]. In this new banking business model, a network funder sets an optimal combination
of netting and financing. Given a network of companies and their respective invoices, and under the
condition of a full settlement of the invoices, we applied a multilateral netting algorithm to the network,
conceived as an oriented multi-graph. Our problem, which is NP-complete, was to find a set of invoices
which maximises the amount of debt reduced given a quantity of loanable funds.

To consolidate our approach of the problem, we analysed the data of a large economic network from
an Italian invoice operator on a one-year span [21]. We compared different methods to detect structures
or communities that could be helpful for debt netting algorithms. Indeed, the structure of such networks
is not currently well known. We gave hints on how to sort and identify the type of business-to-business
invoice graphs, in particular, how to identify relevant communities in such networks.

9 Bilateral contracts and grants with industry

9.1 Bilateral contracts with industry

Participants:

Emmanuel Jeandel, Simon Perdrix, Christophe Vuillot.

The team is currently supervising one CIFRE PhD in collaboration with industry partners (Atos/Eviden)
which started in 2021. Vivien Vandaele is working on “Optimisation du calcul quantique tolérant aux
fautes par le ZX-Calculus” under the supervision of Simon Perdrix and Christophe Vuillot from the team,
and initially Simon Martiel, formerly from ATOS now moved to IBM replaced by Cyril Allouche from
ATOS.

10 Partnerships and cooperations

Participants: Nazim Fatès, Guilhem Gamard, Joannès Guichon, Emmanuel Hainry,
Mathieu Hoyrup, Emmanuel Jeandel, Romain Péchoux, Simon Perdrix,
Christophe Vuillot.

10.1 International initiatives

10.1.1 Inria associate team not involved in an IIL or an international program

TC(PRO)3

Title: Termination and Complexity Properties of Probabilistic Programs

Duration: 2020 onwards

Coordinator: Romain Péchoux

Local Members: Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux and Simon Perdrix.

14

Inria Annual Report 2023

Partners: Inria Nancy Grand Est, University of Innsbruck, Inria Université Côte d’Azur

Summary: Probabilistic languages consist in higher-order functional, imperative languages, and reduc-
tion systems with sampling and conditioning primitive instructions. The associate team TC(Pro)3
has the aim to contribute to the field by developing methods for reasoning on quantitative proper-
ties of probabilistic programs and models. Extensions of these methods on quantum programs will
be studied.

QASAR

Title: Quantum Architectures, Small And Reliable

Duration: 2022 onwards

Local Coordinator: Christophe Vuillot

Local Members: Emmanuel Jeandel and Christophe Vuillot.

Partners: Inria Centre at Université de Lorraine, University College London London, University of Bristol

Summary: The objective for the associate team is to establish strong foundations for fault-tolerant
quantum computation in realistic and practical settings. For this, a systematic understanding of
the fault-tolerant computation capabilities of small quantum codes is required. This includes small
block codes using qubits as well as small codes leveraging hardware control for error correction
like bosonic codes. These kind of small setups are the most mature today.

MURENE

Title: MURENE exploratory research action: mutual debt reduction in B2B payment networks

Duration: 2023-2026

Local Coordinator: Nazim Fatès

Local Members: Joannès Guichon and Sylvain Contassot-Vivier (Loria).

Partners: Massimo Amato, Bocconi University, Milan, Italy ; Lucio Gobbi, University of Trento, Italy.

Summary: The reduction of mutual debts between companies is a major economic stake, especially
when the lack of liquidities can trigger cascading failures. We aim at reducing the global debt in
business-to-business networks of payments. We model the problem with multigraphs and our goal
is to cancel part of the debts contained in this graph, for instance when they form cycles or strongly
interrelated sets. We analyse real-world graphs and propose various netting techniques to reduce
the inter-debts of strongly interrelated economic actors [51, 21].

10.2 International research visitors

10.2.1 Visits of international scientists

• Martin Avanzini (Focus team, Inria Sophia) visited Emmanuel Hainry, Romain Péchoux, and Simon

Perdrix in November 2023 (1 week, funded by the Inria associate team TC(Pro)3).

• Alejandro Diaz-Caro (CONICET Buenos Aires) visited Emmanuel Hainry, Romain Péchoux, and
Simon Perdrix in November 2023 (1 month, funded by the Inria Chercheur Invité programme).

• Rebecca Smith (SUNY Brookport) visited Mathilde Bouvel for a week in March 2023.

• Nikolas Breuckmann (University of Bristol) and Oscar Higgot (University College London) visited

Christophe Vuillot in January 2023 (1 week funded by the Inria associate team QASAR).

Project MOCQUA

15

10.2.2 Visits to international teams

Research stays abroad

• Christophe Vuillot visited Nikolas Breuckmann in Bristol in April 2023 (1 week funded by the Inria

associate team QASAR).

10.3 European initiatives

10.3.1 Horizon Europe

NEASQC (Horizon Europe)

Title: NExt ApplicationS of Quantum Computing

Coordinator Eviden (formerly Atos)

Local Coordinator: Emmanuel Jeandel

Local members: Emmanuel Jeandel, Simon Perdrix and Romain Péchoux

Partner Institution(s): Atos-Bull, Université de Lorraine, AstraZeneca, Cesga, EDF, HQS, HSBC, ICHEC,

Tilde, Total, University of Leiden, Universidade da Coruna

Duration: 01/09/2020-31/08/2024

Summary: The project brings together academic experts and industrial end-users to investigate and
develop a new breed of Quantum-enabled applications that can take advantage of NISQ (Noise
Intermediate-Scale Quantum) systems in the near future. NEASQC is use-case driven. Along with
EDF we are investigating smart energy management in this context.

Total Amount: 4 671 332,50 euros

10.3.2 H2020 projects

HPCQS

Title: High Performance Computer and Quantum Simulator hybrid

Duration: From December 1, 2021 to November 30, 2025

Coordinator: Kristel Michielsen (Aachen University)

Local Coordinator: Simon Perdrix

Local members: Emmanuel Jeandel, Romain Péchoux, Simon Perdrix, and Christophe Vuillot

Partners: Inria, GENCI, NUI GALWAY, FZJ, ParityQC, FHG, CEA, Eurice, CNR, Bull, Flysight SRL, Partec,

UIBK, Cineca, CNRS, CentraleSupélec, BSC CNS, Sorbonne Université

Summary: The aim of HPCQS is to prepare European research, industry and society for the use and
federal operation of quantum computers and simulators. HPCQS is developing the programming
platform for the quantum simulator, which is based on the European Atos Quantum Learning
Machine (QLM), and the deep, low-latency integration into modular HPC systems based on ParTec’s
European modular supercomputing concept.

Total Amount: 12 million euros

16

Inria Annual Report 2023

10.3.3 Other european programs/initiatives

CID (Marie Skłodowska-Curie Action RISE)

Title: Computing with Infinite Data (CID)

Duration: 1 April 2017 - 31 March 2023

Coordinator : Dieter Spreen (University of Siegen)

Local Coordinator : Mathieu Hoyrup

Partners Universities of Trier, Muenchen, Swansea, Birmingham, Ljubljana, Maastricht, Stockholm,
Padova, Algarve, Aston, Dortmund, South Africa, Andres Bello (Chile), Canterbury, Cincinatti, Nan-
yang; Inria, Korean Advanced Institute of Science and Technology, National University Corporation
Japan Advanced Institute of Science and Technology, Intitution of the Russian Academy of Sciences
A.P. Ershov Institute of Informatics Systems Siberian Branch of RAS

Summary: The joint research in this programme studies important aspects - both theoretical as well as
applied - of computing with infinite objects. A central aim is laying the grounds for the generation
of efficient and verified software in engineering applications.

Amount: 958 500 euros

10.4 National initiatives

10.4.1 ANR

ANR PRCE SoftQPro (ANR-17-CE25-0009)

Title: Solutions logicielles pour l’optimisation des programmes et ressources quantiques

Coordinator: Simon Perdrix

Local members: Emmanuel Jeandel, Emmanuel Hainry, Romain Péchoux, and Simon Perdrix.

Partner Institution(s): LORIA, Atos-Bull LRI, CEA-Saclay

Duration: Dec. 2017 - Jun. 2023

Summary: We aim at easing the crucial back and forth interactions between the theoretical approach
to quantum computing and the technological efforts made to implement the quantum computer.
Our software-based quantum program and resource optimization (SoftQPRO) project consists
in developing high level techniques based on static analysis, certification, transformations of
quantum graphical languages, and optimization techniques to obtain a compilation suite for
quantum programming languages.

Total Amount: 550 keuros

10.4.2 Other initiatives

PEPR EPIQ - Plan Quantique

Title: EPIQ: Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l’informatique

quantique

Coordinator: Simon Perdrix

Local Members : Simon Perdrix, Guilhem Gamard, Emmanuel Hainry, Emmanuel Jeandel, Romain

Péchoux, Christophe Vuillot.

Project MOCQUA

17

Partner Institution(s): Inria, Université Grenoble Alpes, CNRS Paris Villejuif, Sorbonne Université, CEA
Grenoble, Institut National Polytechnique Grenoble, Université d’Aix-Marseille, Université de
Bordeaux, Comue Université Bourgogne Franche Comté, Université de Bretagne Sud, Université de
Lyon I, Université de Lorraine, CentraleSupelec, Université Paris-Saclay, Ecole Nationale des Ponts
et Chaussées, Université Paris Cité

Duration: Jan. 2022 - Dec 2027

Summary: Based on the outstanding French position, our project aims at developing algorithmic tech-
niques for both noisy quantum machines (NISQ) and fault-tolerant ones so as to facilate their
practical implementation. To this end, a first Work Package (WP) is dedicated to algorithmic
techniques, a second one focuses on computational models and languages so as to facilitate the
programming of quantum machines and to optimize the code execution steps. Lastly, the third WP
aims at developing the simulation techniques of quantum computers.

Total Amount: 13,5 million euros

PEPR NISQ2LSQ - Plan Quantique

Title: NISQ2LSQ

Coordinator: Anthony Leverrier (Cosmiq, Inria Paris)

Local Coordinator: Christophe Vuillot

Local Members: Nazim Fates, Emmanuel Jeandel, Simon Perdrix, Christophe Vuillot

Partner Institution(s): Inria, CNRS, CEA, Université Grenoble Alpes, ENS Lyon, Sorbonne Université,
Université Paris-Saclay, Université Paris Cité, Université de Bordeaux, CEA-LETI, Université d’Aix-
Marseille, Université de Rouen, Université de Limoges, Alice&Bob (Startup), Quandela (Startup)

Duration: Jan. 2022 - Dec 2027

Summary: This project aims at accelerating the R&D efforts in the theory and conception of hardware-
efficient fault-tolerant quantum codes. As far as codes are concerned, the project will focus on
two of the most promising solutions, namely bosonic codes and Low-Density Parity-Check (LDPC)
codes. On the hardware side, the targetted platforms are superconducting qubits and photonic
ones.

Total Amount: 10 million euros

HQI - Plan Quantique

Title: HQI

Coordinator: Jacques-Charles Lafoucrière (CEA)

Local Coordinator: Simon Perdrix

Local Members: Simon Perdrix, Romain Péchoux, Christophe Vuillot

Partner Institution(s): CEA, Inria, CNRS, Centre de Physique Théorique, Sorbonne Université, Uni-
versité Grenoble Alpes, Université Paris-Saclay, Université de Bordeaux, École Normale Supérieure,
École Normale Supérieure de Lyon, École nationale supérieure de techniques avancées, Atos-Bull
SAS (Eviden (formerly Atos)), Grand equipement national de calcul intensif, Quandela SAS, Qubit
Phamarceuticals, VeriQloud, WeLinQ.

Duration: Apr. 2022 - Apr. 2027

18

Inria Annual Report 2023

Summary: Following the announcement made in January 2021 of the National Quantum Strategy by
the President of the French Republic, the SGPI entrusted the CEA, GENCI and Inria with the
responsibility of setting up a national hybrid HPC quantum-computing platform named HQI.
The project to set up this platform consists of purchases of quantum computers, research and
development entrusted to industrialists and academics as well as support for communities using
the platform.

Total Amount: 36 million euros

11 Dissemination

Participants: Mathilde Bouvel, Nazim Fatès, Guilhem Gamard, Isabelle Gnaedig,
Emmanuel Hainry, Mathieu Hoyrup, Emmanuel Jeandel, Ro-
main Péchoux, Simon Perdrix, Julien Provillard, Christophe Vuillot.

11.1 Promoting scientific activities

11.1.1 Scientific events: organisation

Member of the organizing committees

• Simon Perdrix was one of the co-organisers of The 20th International Conference on Quantum

Physics and Logic (QPL 2023) in Paris, July 2023.

• Christophe Vuillot organized a Workshop on Quantum LDPC Codes in March 2023, in Pont-à-

Mousson, as part of the PEPR NISQ2LSQ.

Chair of conference program committees

• Mathilde Bouvel served as chair of the program committee of the conference Permutation Patterns

2023.

Member of the conference program committees

• Mathilde Bouvel and Emmanuel Jeandel are members of the program committee of STACS 2023,

respectively in Track A and B (see webpage).

• Nazim Fatès was a member of the PC of the workshop AUTOMATA’23.

• Emmanuel Jeandel and Simon Perdrix are members of the program committee of QPL’23(see

webpage)

• Romain Péchoux was member of the PC of the post-review program commitee of IFL 2022.

Reviewer

• Emmanuel Hainry reviewed articles for FoSSaCS 2024, ISMVL 2023, MFCS 2023, and POPL 2024.

• Mathieu Hoyrup reviewed articles for FCT 2023, STACS 2023.

• Romain Péchoux reviewed articles for FSCD 2023, IFL 2022, MFCS 2023, STACS 2023, WOLLIC 2023.

• Christophe Vuillot reviewed articles for TQC 2023, QPL 2023.

Project MOCQUA

19

11.1.2 Journal

Member of the editorial boards

• Mathilde Bouvel: Executive editor of the European Journal of Combinatorics, and Member of the
editorial board of the journal Annals of combinatorics. She also guest-edited a special volume of
DMTCS following the conference Permutation Patterns 2019.

• Nazim Fatès: Member of the editorial board of the Journal of cellular automata.

• Emmanuel Jeandel: Member of the editorial board of the journal RAIRO-ITA.

• Simon Perdrix: Member of the editorial board of the journal Logical Methods in Computer Science

(LMCS).

Reviewer - reviewing activities

• Mathilde Bouvel has been a reviewer for one article in the journal Advances in Applied Mathematics

and one article in the journal Discrete Mathematics.

• Nazim Fatès was a reviewer for Natural Computing and the Journal of cellular automata.

• Emmanuel Hainry has been a reviewer for one article in the journal Mathematical Structures in

Computer Science

• Mathieu Hoyrup has been a reviewer for Computability, Journal of the ACM, Mathematical Com-

munications, Mathematical Structures in Computer Science, Theory of Computing Systems.

• Romain Péchoux has been a reviewer for two articles in the journal of Mathematical Structures in

Computer Science and one article in Information and Computation.

11.1.3 Invited talks

• Nazim Fatès has given an invited talk at the workshop « Automates cellulaires, systèmes de partic-
ules, et auto-organisation », Rouen, November 15, 2023 ; he was invited to give a talk at the « Journée
représentations du langage », Fédération Charles-Hermite, November 21, 2023, Nancy.

• Mathieu Hoyrup has been invited to give a talk at the workshop Recursion Theory and its Applica-

tions at the Institute for Advanced Study in Mathematics, Hangzhou.

• Romain Péchoux has given an invited talk at the SCOT seminar (online), 13th of January 2023, and

a talk at the Complexity Days, GDR IM, 13rd of December 2023, Paris.

• Christophe Vuillot has given an invited talk at the CEA Leti Innovation Days, 28th of June 2023,

Grenoble.

11.1.4 Leadership within the scientific community

• Mathilde Bouvel is a member of the steering committee of the conference series Permutation

Patterns.

• Nazim Fatès is the chair of the IFIP working group 1.5 on Cellular Automata and Discrete Complex

Systems.

• Christophe Vuillot is organizing the QASAR seminar, a regular online international seminar on
quantum error correction, started in June 2023, once every two weeks, 29 connections on average.

20

Inria Annual Report 2023

11.1.5 Scientific expertise

• Mathilde Bouvel has been an external evaluator on an research project submitted to the ANR

(generic call AAPG).

• Nazim Fatès evaluated a research project submitted to the National Science Center (Narodowe

Centrum Nauki) in Poland.

• Mathieu Hoyrup has been evaluator on a Fondecyt research project.

• Romain Péchoux was expert and rapporteur for the MSCA HORIZON call.

11.1.6 Research administration

• Christophe Vuillot is a member of the scientific board of the GdR TeQ.

• Simon Perdrix is co-responsible, with Renaud Vilmart, of the groupe de travail Informatique

Quantique at GdR IM.

11.2 Teaching - Supervision - Juries

• Licence

– Guilhem Gamard:

* Systems programming, 42h, L2 and L3 Informatique
* Databases, 42h, L2 and L3 Informatique
* Networking, 21h, L3 Informatique

– Isabelle Gnaedig:

* To the limits of the computable, 6 hours, Opening course-conference of the collegium

“Lorraine INP”, Université de Lorraine, Nancy, France.

– Emmanuel Hainry:

* Algorithmics, 71h, L1, IUT Nancy Brabois.
* Dynamic Web, 31h, L1, IUT Nancy Brabois.
* Developing Full Stack Applications, 38h, L1, IUT Nancy Brabois.
* Automating Operating Systems, 72h, L2, IUT Nancy Brabois.
* Complexity, 21h, L2, IUT Nancy Brabois.
* Full Stack Project, 8h, L2, IUT Nancy Brabois.

– Emmanuel Jeandel:

* Algorithmics and Programming 1, 60h, L1 Maths-Info
* Networking, 60h, L2 and L3 Informatique.
* Functional Programming, 14h, L3 Informatique.
* System Administration, 24h, Licence Pro Infographie Paysagère.

– Romain Péchoux:

* Propositional logic, L1 MIASHS, 35 HETD.
* Computer architecture, L2 MIASHS, 68 HETD
* Algorithmic complexity, L3 MIASHS, 52 HETD

– Julien Provillard

* Object-oriented programming, L3 Informatique, 44h

• Master

– Nazim Fatès:

* Systèmes distribués adapatifs, Master 2 AVR, université de Lorraine, 12 hours

Project MOCQUA

21

* Introduction à l’intelligence artificielle, IAE Nancy School of Management, Marketing et

Gestion Commerciale, université de Lorraine, 3h

* Introduction à l’intelligence artificielle, Seminar to the students of Engineering School

(cours d’ouverture), Telecom Nancy, université de Lorraine, 3h

– Guilhem Gamard:

* Networking, 58h, M1 Informatique

– Isabelle Gnaedig:

* Rule-based Programming, 28 hours, M2, Telecom-Nancy, Université de Lorraine, Nancy,

France.

– Emmanuel Jeandel:

* Algorithmics and Complexity, 30h, M1 Informatique
* Networking, 24h, M1 Informatique

– Romain Pechoux:

* OO design and UML, M1 MIASHS, 54 HETD

– Simon Perdrix:

* Informatique Quantique, 15h, M2 Telecom Paris Tech
* Informatique Quantique, 12h, M1 Informatique

– Julien Provillard

* Design patterns, 40h, M1 Informatique
* Analysis and software design, 23h, M1 Informatique

– Christophe Vuillot:

* Informatique Quantique, 12h, M1 Informatique

11.2.1 Supervision

• PhD: Djamel Eddine Amir, “Computability of subsets of topological spaces”, Start: October 2020,

Advisors: Emmanuel Jeandel and Mathieu Hoyrup. Djamel Defended in October 2023.

• PhD: Alexandre Clément, “Graphical Languages for Quantum Control”, Start: September 2019,

Advisors: Emmanuel Jeandel and Simon Perdrix. Alexandre defended in May 2023.

• PhD: Agustin Borgna “Vers une formalisation d’une chaîne de compilation pour un ordinateur
quantique”, Start: October 2019, Advisors: Simon Perdrix and Benoit Valiron (LMF). Agustin defen-
ded in January 2023.

• PhD in progress: Nathan Claudet, “Structures fondamentales et applications des états graphes et

du calcul par mesures”, Start: October 2022, Advisors: Simon Perdrix and Mathilde Bouvel.

• PhD in progress, Kinnari Vijay Dave, “Quantum programming with (co)inductive types”, Start:

December 2022, Advistors: Romain Péchoux and Vladimir Zamdzhiev.

• PhD in progress: Noé Delorme, “Wielding Quantum Circuits”, Start: July 2023, Advisors: Simon

Perdrix.

• PhD in progress: Alexandre Guernut, “Efficient Fault-Tolerant Quantum Computation with Quantum

LDPC Codes”, Start: October 2021, Advisors: Emmanuel Jeandel and Christophe Vuillot.

• PhD in progress: Joannès Guichon, “B2B exchange networks and liquidity-saving mechanism by
mutualisation of debt”, Start: October 2022, Advisors: Nazim Fatès and Sylvain Contassot-Vivier.

• PhD in progress: Mario Machado Da Silva, “Computational complexity of reversible computations
and applications to quantum programming”, Start: October 2021, Advisors: Emmanuel Hainry and
Romain Péchoux.

22

Inria Annual Report 2023

• PhD in progress: Benjamin Testart, “Énumération et formes limites des tables d’inversions évitant

des motifs”, Start: October 2022, Advisors: Mathilde Bouvel and Emmanuel Jeandel.

• PhD in progress: Vivien Vandaele, “Optimisation du calcul quantique tolérant aux fautes par le ZX-
Calculus”, Start: September 2021, Advisors: Simon Perdrix and Christophe Vuillot, joint supervision
with Simon Martiel at ATOS (CIFRE).

11.2.2 Juries

• Mathilde Bouvel participated in the PhD defense of Daniel Tamayo Jimenez (Université Paris-

Saclay).

• Nazim Fatès reviewed the PhD manuscript of Witold Bołt (Polish Academy of Science, Warsaw,

Poland).

• Emmanuel Jeandel participated in the PhD defense of David Desobry (Université de Lorraine) and

the HDR defenses of Mathieu Hoyrup and Nazim Fatès (Université de Lorraine).

• Emmanuel Jeandel reviewed the PhD manuscript of Kostia Chardonnet (Université Paris-Saclay)

• Emmanuel Jeandel reviewed the HDR manuscript of Damien Regnault (Université d’Evry)

• Simon Perdrix was external examinator for the PhD defense of Matthew Wilson (University of

Oxford).

• Simon Perdrix participated in the PhD defense of Marc Bataille (Université de Rouen).

• Simon Perdrix was the president of the jury of Quentin Yang (Université de Lorraine).

11.3 Popularization

11.3.1 Interventions

• Nazim Fatès: talk destined to the classes of the Collège Jean-Lurçat, Frouard, on the work of Alan

TURING, May 31, 2023. An article in L’est republicain covered this event.

• Nazim Fatès: talk to a wide audience in Marsal, a village near Nancy: «Intelligence artificielle, qu’en

dirait Socrate ?». An article appeared in Le républicain lorrain to present this meeting.

• Nazim Fatès: talk to a wide audience in Strasbourg, «Intelligence artificielle : qu’y a-t-il de l’autre
côté du miroir ?», jointly with Amélie Cordier (independent), organised by the association Le Jardin
des sciences, October 5, 2023.

• Nazim Fatès: talk to high-school and undergraduate students, as well as to large-audience public
(approx. 300 persons in total), in Espace Sadoul, Saint-Dié-des-Vosges, for « La fête de la science »,
jointly with Marie Baron (Université de Lorraine), October 10, 2023.

• Nazim Fatès: Radio interview with Bénédicte Bossard, RCF Strasbourg, Le Grand Entretien, «In-
telligence artificielle : puiser dans les sciences humaines face au débat », November 6, 2023 (read
podcast). This interview followed the meeting in Strasbourg.

• Mathieu Hoyrup gave an introductory talk to MP2I students from Lycée Henri Poincaré on the topic

of game theory.

Project MOCQUA

23

12 Scientific production

12.1 Major publications

[1] D. E. Amir and M. Hoyrup. ‘Computability of finite simplicial complexes’. In: ICALP. Paris, France,

July 2022. URL: https://inria.hal.science/hal-03564904.

[2] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun and A. Pierrot. ‘Scaling limits of permutation
classes with a finite specification: a dichotomy’. In: Advances in Mathematics 405 (27th Aug. 2022),
p. 108513. DOI: 10.1016/j.aim.2022.108513. URL: https://hal.science/hal-02412965.

[3] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix and B. Valiron. ‘A Complete Equational Theory for
Quantum Circuits’. In: 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).
2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Boston, United
States: IEEE, July 2023, pp. 1–13. DOI: 10.1109/LICS56636.2023.10175801. URL: https://hal
.science/hal-03926757.

[4] N. Fatès, V. Chevrier and O. Bouré. ‘Is there a trade-off between simplicity and robustness? Illustra-
tion on a lattice-gas model of swarming’. In: Probabilistic Cellular Automata. Ed. by P.-Y. Louis and
F. R. Nardi. Emergence, Complexity and Computation. Springer, 2018. DOI: 10.1007/978-3-319-
65558-1_16. URL: https://hal.inria.fr/hal-01230145.

[5] E. Hainry, B. M. Kapron, J.-Y. Marion and R. Péchoux. ‘Complete and tractable machine-independent
characterizations of second-order polytime’. In: FoSSaCS 2022 - 25th International Conference on
Foundations of Software Science and Computation Structures. Vol. 13242. Lecture Notes in Com-
puter Science. Munich, Germany: Springer International Publishing, 29th Mar. 2022, pp. 368–388.
DOI: 10.1007/978-3-030-99253-8_19. URL: https://inria.hal.science/hal-03722245.

[6] E. Hainry and R. Péchoux. ‘A General Noninterference Policy for Polynomial Time’. In: POPL 23.
Vol. 7. Boston, United States, 9th Jan. 2023, pp. 806–832. DOI: 10.1145/3571221. URL: https://i
nria.hal.science/hal-04190355.

[7] E. Jeandel and M. Rao. ‘An aperiodic set of 11 Wang tiles’. In: Advances in Combinatorics (6th Jan.

2021). DOI: 10.19086/aic.18614. URL: https://inria.hal.science/hal-01166053.

[8] C. Vuillot and N. P. Breuckmann. ‘Quantum Pin Codes’. In: IEEE Transactions on Information Theory
(26th Apr. 2022). DOI: 10.1109/TIT.2022.3170846. URL: https://hal.science/hal-023514
17.

12.2 Publications of the year

International journals

[9] M. Albert, M. Bouvel, V. Féray and M. Noy. ‘Convergence law for 231-avoiding permutations’. In:
Discrete Mathematics and Theoretical Computer Science. Permutation Patterns 2023 (2024). URL:
https://hal.science/hal-03908625.

[10] D. E. Amir and M. Hoyrup. ‘Comparing computability in two topologies’. In: The Journal of Symbolic
Logic (2023), pp. 1–19. DOI: 10.1017/jsl.2023.17. URL: https://inria.hal.science/hal-0
3702999.

[11] D. E. Amir and M. Hoyrup. ‘Strong computable type’. In: Computability 12.3 (20th Sept. 2023),

pp. 227–269. DOI: 10.3233/COM-220430. URL: https://inria.hal.science/hal-03806572.

[12]

J.-C. Aval, A. Boussicault, M. Bouvel, O. Guibert and M. Silimbani. ‘Baxter Tree-like Tableaux’. In: The
Australasian Journal of Combinatorics 86.1 (2023), pp. 24–75. DOI: 10.48550/arXiv.2108.06212.
URL: https://hal.science/hal-03385234.

[13] R. I. Booth, A. Kissinger, D. Markham, C. Meignant and S. Perdrix. ‘Outcome determinism in
measurement-based quantum computation with qudits’. In: Journal of Physics A: Mathematical
and Theoretical 56.11 (24th Feb. 2023), p. 115303. DOI: 10.1088/1751-8121/acbace. URL: https:
//hal.science/hal-03358122.

24

Inria Annual Report 2023

[14] R. I. Booth and D. Markham. ‘Flow conditions for continuous variable measurement-based quantum
computing’. In: Quantum 7 (19th Oct. 2023), p. 1146. DOI: 10.22331/q-2023-10-19-1146. URL:
https://hal.science/hal-03217062.

[15] M. Hoyrup. ‘Notes on overt choice’. In: Computability (14th Apr. 2023), pp. 1–19. DOI: 10.3233

/COM-230458. URL: https://inria.hal.science/hal-04164138.

[16] M. Hoyrup, T. Kihara and V. Selivanov. ‘Degree Spectra of Homeomorphism Types of Compact
Polish Spaces’. In: The Journal of Symbolic Logic (2023), pp. 1–32. DOI: 10.1017/jsl.2023.93.
URL: https://inria.hal.science/hal-02555111.

International peer-reviewed conferences

[17] A. Clément, N. Delorme, S. Perdrix and R. Vilmart. ‘Quantum Circuit Completeness: Extensions
and Simplifications’. In: International Conference on Computer Science Logic CSL 2024. Naples,
Italy, Feb. 2024. URL: https://hal.science/hal-04016498.

[18] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix and B. Valiron. ‘A Complete Equational Theory for
Quantum Circuits’. In: 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).
2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Boston, United
States: IEEE, July 2023, pp. 1–13. DOI: 10.1109/LICS56636.2023.10175801. URL: https://hal
.science/hal-03926757.

[19] L.-J. Dandy, E. Jeandel and V. Zamdzhiev. ‘Type-safe Quantum Programming in Idris’. In: Lecture
Notes in Computer Science. ESOP 2023 - European Symposium on Programming. Vol. LNCS-13990.
Programming Languages and Systems. Paris, France: Springer, 17th Apr. 2023, pp. 507–534. DOI:
10.1007/978-3-031-30044-8_19. URL: https://inria.hal.science/hal-03519238.

[20] N. Fatès, R. Marchand and I. Marcovici. ‘A decentralised diagnosis method with probabilistic
cellular automata’. In: LNCS. Cellular Automata and Discrete Complex Systems. AUTOMATA 2023.
Vol. 14152. Trieste (Italy), France: Springer, 24th Aug. 2023. DOI: 10.1007/978-3-031-42250-8_5.
URL: https://inria.hal.science/hal-04094230.

[21]

J. Guichon, N. A. Fatès, S. Contassot-Vivier and M. Amato. ‘Properties of B2B invoice graphs
and detection of structures’. In: Complex Networks 2023. Menton, France, 28th Nov. 2023. URL:
https://inria.hal.science/hal-04230839.

[22] E. Hainry and R. Péchoux. ‘A General Noninterference Policy for Polynomial Time’. In: POPL 23.
Vol. 7. Boston, United States, 9th Jan. 2023, pp. 806–832. DOI: 10.1145/3571221. URL: https://i
nria.hal.science/hal-04190355.

[23] E. Hainry, R. Péchoux and M. Silva. ‘A programming language characterizing quantum polynomial
time’. In: Foundations of Software Science and Computation Structures - 26th International Con-
ference, FoSSaCS 2023, Held as Part of the European Joint Conferences on Theory and Practice of
Software, ETAPS 2023, Paris, France, April 22-27, 2023, Proceedings. Paris, France, 22nd Apr. 2023.
DOI: 10.1007/978-3-031-30829-1\_8. URL: https://inria.hal.science/hal-04190385.

[24] V. Vandaele, S. Martiel, S. Perdrix and C. Vuillot. ‘Optimal Hadamard gate count for Clifford+T
synthesis of Pauli rotations sequences’. In: TQC 2023: 18th Theory of Quantum Computation,
Communication and Cryptography. Aveiro, Portugal, July 2023. URL: https://hal.science/hal
-04318278.

Conferences without proceedings

[25] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix and B. Valiron. ‘A Complete Equational Theory
for Quantum Circuits’. In: Theory of Quantum Computation, Communication and Cryptography
(TQC 2023). Aveiro, Portugal, July 2023. URL: https://hal.science/hal-04318291.

[26] L. Paletta, A. Leverrier, A. Sarlette, M. Mirrahimi and C. Vuillot. ‘Robust sparse IQP sampling in
constant depth’. In: QIP2024. Taipei, Taiwan, 20th July 2023. URL: https://inria.hal.science
/hal-04312163.

Project MOCQUA

25

Doctoral dissertations and habilitation theses

[27] D. E. Amir. ‘Computability of Topological Spaces’. Université de Lorraine, 6th Oct. 2023. URL:

https://theses.hal.science/tel-04324721.

[28] A. Borgna. ‘Towards a formal compilation stack-frame in quantum computing’. Université de

Lorraine, 13th Jan. 2023. URL: https://hal.univ-lorraine.fr/tel-04102354.

[29] A. Clément. ‘Graphical Languages for Quantum Control and Linear Optics’. Université de Lorraine,

16th May 2023. URL: https://theses.hal.science/tel-04213655.

[30] N. A. Fatès. ‘Robustesse des systèmes complexes : étude du rôle de l’aléa dans la dynamique des
automates cellulaires’. Université de Lorraine, 24th May 2023. URL: https://inria.hal.scienc
e/tel-04165486.

[31] M. Hoyrup. ‘Topological Aspects of Representations in Computable Analysis’. Université de Lor-

raine, 9th Jan. 2023. URL: https://inria.hal.science/tel-03932408.

Reports & preprints

[32] D. E. Amir and M. Hoyrup. Descriptive complexity of topological invariants. 29th Sept. 2023. URL:

https://inria.hal.science/hal-04222391.

[33] D. E. Amir and M. Hoyrup. The surjection property and computable type. 26th June 2023. URL:

https://inria.hal.science/hal-04140772.

[34] M. Avanzini, G. Moser, R. Péchoux and S. Perdrix. On the Hardness of Analyzing Quantum Programs

Quantitatively. 20th Dec. 2023. URL: https://inria.hal.science/hal-04349874.

[35] N. Claudet, M. Mhalla and S. Perdrix. Small k-pairable states. 4th Dec. 2023. URL: https://hal.sc

ience/hal-04320674.

[36] A. Clément, N. Delorme and S. Perdrix. Minimal Equational Theories for Quantum Circuits. 13th Nov.

2023. URL: https://hal.science/hal-04399210.

[37] A. Díaz-Caro, E. Hainry, R. Péchoux and M. Silva. A feasible and unitary programming language
with quantum control. 15th Nov. 2023. URL: https://inria.hal.science/hal-04266203.

[38] G. Gamard, P. Guillon, K. Perrot and G. Theyssier. Hardness of monadic second-order formulae over

succinct graphs. 8th Feb. 2023. URL: https://hal.science/hal-03978957.

[39] M. Malenfer, M. Sarrey, J. Clerté, M. Hery, M. Bieri, B. Braunschweig, R. Chatellier, N. Fatès, S.
Halluin, F. de Jouvenel, V. Mandinaud, J. Munoz, A. Olympio, T. Silvestre and J.-F. Soupizet. Artificial
intelligence in the service of health and safety at work: Perspectives and challenges from now to 2035
- A prospective study. 23rd Nov. 2023. DOI: 10.32388/NRENI6. URL: https://inria.hal.scienc
e/hal-04302464.

[40] V. Vandaele, S. Martiel, S. Perdrix and C. Vuillot. Optimal Hadamard gate count for Clifford+T
synthesis of Pauli rotations sequences. 14th Feb. 2023. URL: https://hal.science/hal-0399115
4.

[41] C. Vuillot, A. Ciani and B. M. Terhal. Homological Quantum Rotor Codes: Logical Qubits from

Torsion. 23rd Mar. 2023. URL: https://inria.hal.science/hal-04057182.

12.3 Other

Scientific popularization

[42] N. Fatès. ‘Que faire de l’expression intelligence artificielle ?’ In: Alliage : Culture - Science - Technique

(2023). URL: https://inria.hal.science/hal-04282291.

12.4 Cited publications

[43] X. Bian and P. Selinger. ‘Generators and Relations for 2-Qubit Clifford+T Operators’. In: Proceedings
of QPL’22, Electronic Proceedings in Theoretical Computer Science 394 (Nov. 2023), pp. 13–28. DOI:
10.4204/eptcs.394.2. URL: http://dx.doi.org/10.4204/EPTCS.394.2.

26

Inria Annual Report 2023

[44] X. Bian and P. Selinger. ‘Generators and Relations for 3-Qubit Clifford+CS Operators’. In: Proceedings
QPL’23, Electronic Proceedings in Theoretical Computer Science 384 (Aug. 2023), pp. 114–126. DOI:
10.4204/eptcs.384.7. URL: http://dx.doi.org/10.4204/EPTCS.384.7.

[45]

S. Bravyi, Y. Sharma, M. Szegedy and R. De Wolf. ‘Generating k EPR-pairs from an n-party resource
state’. In: QIP2023, arXiv:2211.06497 (2022).

[46] M. de Brecht, A. Pauly and M. Schröder. ‘Overt choice’. In: Comput. 9.3-4 (2020), pp. 169–191. DOI:

10.3233/COM-190253. URL: https://doi.org/10.3233/COM-190253.

[47] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix and B. Valiron. ‘LO_v-Calculus: A Graphical Lan-
guage for Linear Optical Quantum Circuits’. In: MFCS 2022 - 47th International Symposium on
Mathematical Foundations of Computer Science. Vol. 241. https://arxiv.org/abs/2204.11787.
Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Aug. 2022, 35:1–35:16. DOI:
10.4230/LIPIcs.MFCS.2022.35. URL: https://hal.science/hal-03926660.

[48]

S. Corteel, M. A. Martinez, C. D. Savage and M. Weselcouch. ‘Patterns in Inversion Sequences I’. In:
Discrete Mathematics and Theoretical Computer Science 18.2 (2016).

[49] E. Farhi, J. Goldstone and S. Gutmann. A Quantum Approximate Optimization Algorithm. 2014.

arXiv: 1411.4028 [quant-ph].

[50] N. Fatès. ‘Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis
scheme - Social amoebae as a source of inspiration’. In: Swarm Intelligence 4.2 (2010), pp. 91–
115. URL: http://dx.doi.org/10.1007/s11721-010-0038-4.

[51] N. A. Fatès, M. Amato and L. Gobbi. ‘The economics and algorithmics of an integral settlement
procedure on B2B network’. preprint available on SSRN. Dec. 2021. URL: https://hal.inria.fr
/hal-03475245.

[52] N. Gauville. ‘Système robuste de diagnostic décentralisé à l’aide d’automates cellulaires simples’.
MA thesis. Université de Lorraine (Nancy), Sept. 2018. URL: https://hal.inria.fr/hal-01894
581.

[53]

J. Makary, N. J. Ross and P. Selinger. ‘Generators and Relations for Real Stabilizer Operators’. In:
Proceedings of the 18th International Conference on Quantum Physics and Logic, QPL 2021 (Gdansk,
Poland, and online, 7th–11th June 2021). Ed. by C. Heunen and M. Backens. Vol. 343. EPTCS. 2021,
pp. 14–36. DOI: 10.4204/EPTCS.343.2.

[54] T. Mansour and M. Shattuck. ‘Pattern avoidance in inversion sequences’. In: Pure Mathematics and

Applications 25.2 (2015), pp. 157–176.

[55]

J. R. McClean, J. Romero, R. Babbush and A. Aspuru-Guzik. ‘The theory of variational hybrid
quantum-classical algorithms’. In: New Journal of Physics 18.2 (2016), p. 023023.

[56] M. Mhalla, S. Perdrix and L. Sanselme. ‘Characterising Determinism in MBQCs involving Pauli
Measurements’. https://arxiv.org/abs/2207.09368 - working paper or preprint. 2022. DOI:
10.48550/arXiv.2207.09368. URL: https://hal.science/hal-04320656.

[57]

S. Perdrix and L. Sanselme. ‘Determinism and Computational Power of Real Measurement-based
Quantum Computation’. In: FCT’17- 21st International Symposium on Fundamentals of Compu-
tation Theory. Bordeaux, France, Sept. 2017. DOI: 10.1007/978- 3- 662- 55751- 8\_31. URL:
https://hal.science/hal-01377339.

[58] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik and J. L.
O’brien. ‘A variational eigenvalue solver on a photonic quantum processor’. In: Nature communic-
ations 5.1 (2014), pp. 1–7.

[59] P. Selinger. ‘Generators and relations for n-qubit Clifford operators’. In: Logical Methods in Com-
puter Science Volume 11, Issue 2 (June 2015). DOI: 10.2168/LMCS-11(2:10)2015. URL: http://l
mcs.episciences.org/1570.
<scratchpad>
- Main topic: Inria Centre at Université de Lorraine's Project MOCQUA
- Key points:
  - The MOCQUA team focuses on computational models, including quantum computing, higher-order computing, and infinite precision.
  - The team's research program covers three main models: Quantum Computing, Higher-Order Computing, and Computing with Infinite Precision.
  - The team has made significant contributions to the development of quantum software, including the introduction of a complete equational theory for quantum circuits.
  - The team has also worked on probabilistic cellular automata, graph states, and measurement-based quantum computing.
  - The team has collaborated with various international partners, including universities, research institutions, and industry partners.
- Structure: The document is divided into several sections, including an activity report, a research program, and a list of publications.
- Potential artifacts to ignore: The document contains unnecessary web-related elements, such as links, HTML tags, and images.
</scratchpad>

<final_summary>
The MOCQUA team at Inria Centre at Université de Lorraine is a research group focused on computational models, including quantum computing, higher-order computing, and infinite precision. The team's research program covers three main models: Quantum Computing, Higher-Order Computing, and Computing with Infinite Precision. The team has made significant contributions to the development of quantum software, including the introduction of a complete equational theory for quantum circuits. The team has also worked on probabilistic cellular automata, graph states, and measurement-based quantum computing, and has collaborated with various international partners. The team's research has been published in several international journals and conferences, and has been recognized through various awards and grants.</final_summary>
The MOCQUA team at Inria Centre at Université de Lorraine is a research group focused on computational models, including quantum computing, higher-order computing, and infinite precision. The team's research program covers three main models: Quantum Computing, Higher-Order Computing, and Computing with Infinite Precision. The team has made significant contributions to the development of quantum software, including the introduction of a complete equational theory for quantum circuits. The team has also worked on probabilistic cellular automata, graph states, and measurement-based quantum computing, and has collaborated with various international partners. The team's research has been published in several international journals and conferences, and has been recognized through various awards and grants.