Keywords
Computer Science and Digital Science
- A2.1.1. Semantics of programming languages
- A2.2.1. Static analysis
- A2.4. Formal method for verification, reliability, certification
- A2.4.1. Analysis
- A6.5. Mathematical modeling for physical sciences
- A7.2.3. Interactive Theorem Proving
- A8. Mathematics of computing
- A8.6. Information theory
Other Research Topics and Application Domains
- B5.11. Quantum systems
1 Team members, visitors, external collaborators
Research Scientists
- Pablo Arnault [INRIA, Researcher]
- Marc De Visme [INRIA, Researcher]
- Renaud Vilmart [INRIA, ISFP]
- Vladimir Zamdzhiev [INRIA, ISFP]
Faculty Members
- Pablo Arrighi [Team leader, UNIV PARIS SACLAY, Professor, HDR]
- Luidnel Maignan [Université Paris-Est Créteil, INRIA Delegation]
- Benoît Valiron [CENTRALE]
Post-Doctoral Fellows
- Titouan Carette [UNIV PARIS SACLAY, until Jul 2022]
- Augustin Vanrietvelde [INRIA, from Nov 2022]
PhD Students
- Agustín Borgna [Loria, Université de Lorraine]
- Kostia Chardonnet [UNIV PARIS SACLAY]
- Marin Costes [ENS PARIS-SACLAY, from Oct 2022]
- Kinnari Dave [Université de Lorraine, from Nov 2022]
- Amélia Durbec [Aix-Marseille Université]
- Nathanaël Eon [Aix-Marseille Université, until Nov 2022]
- Nicolas Heurtel [UNIV PARIS SACLAY & QUANDELA, CIFRE, from Jun 2022]
- Dongho Lee [CENTRALE, until Jul 2022]
- Louis Lemonnier [ENS PARIS-SACLAY]
- Jérome Ricciardi [CEA, from Mar 2022]
Interns and Apprentices
- Colin Blake [UNIV PARIS SACLAY, Intern, from May 2022 until Jun 2022]
- Carlo Elia Doncecchi [UNIV PARIS SACLAY, Intern, from May 2022 until May 2022]
- Thibault Fredon [ENS PARIS-SACLAY, Intern, from Feb 2022 until Jul 2022]
- Carole Happe [UNIV PARIS SACLAY, Intern, from May 2022 until Jul 2022]
- Emile Larroque [ENS PARIS-SACLAY, Intern, from Mar 2022 until Jul 2022]
- Hugo Massonnat [École Polytechnique, Intern, from Mar 2022 until Jul 2022]
- Octave Mestoudjian [Université Sorbonne Paris Nord, from Jun 2022 until Jul 2022]
- Ramdane Mouloua [UNIV PARIS SACLAY, Intern, from Apr 2022 until Jul 2022]
- Ugo Nzongani [UNIV PARIS SACLAY, Intern, from May 2022 until Jun 2022]
- Alice Petiot [UNIV PARIS SACLAY, Intern, from May 2022 until Jul 2022]
- Joshua Talidec [Lycée Chevreul, Intern, from Apr 2022 until Apr 2022]
Administrative Assistant
- Natalia Alves [INRIA]
2 Overall objectives
Quantum information processing is one of the rising forces of the information era. Encoding information within quantum systems and manipulating them promises to lead to great advantages, with three main application domains: quantum cryptography, quantum simulation, and quantum algorithmics. To understand its strengths and limits, we take a transversal stance and seek to capture which resources are granted to us by nature, at the fundamental level, for the sake of computing (e.g. quantum and spatial parallelism). We do so by abstracting away physics’ ability to compute, into formal models of quantum computation (e.g. quantum automata and graph rewriting models). We then verbalize its main structures as quantum programming languages (e.g. quantum lambda-calculus, process algebra). Actually, the process goes both ways, when developments in quantum programming languages lead to the discovery of new structures which may or may not be compilable into formal models of quantum computation, raising the sometimes fascinating question of the physicality of these resources.
3 Research program
3.1 Quantum simulation
One usually distinguishes three main fields of applications of Quantum Computing: quantum cryptography (short-term), quantum simulation (mid-term), quantum algorithmic (long-term). Quantum simulation then divides into two subfields: continuous-time quantum simulation, which is very physicky and consists of ad hoc emulation of one Hamiltonian by another, and discrete-time quantum simulation, which is much closer to quantum algorithmic: this is where we stand. In particular, we focus on the provision of a quantum-circuit description of the dynamics of fundamental particles. In particular, as we design these quantum simulation schemes, our focus is on retaining the symmetries of the simulated model. This is both a matter of efficiency and correctness. For instance, our discretizations have a maximum speed of propagation of the information, which coincides with the speed of light in the simulated system, as a first step towards retaining Lorentz symmetry. Similarly, our discretizations exhibit the gauge symmetries that motivate the different fundamental particles. The long term goal of this program is to provide a satisfactory quantum-circuit descriptions of the whole standard model of particle physics.
3.2 Semantics
In the research program on Semantics, the QuaCS team is working on developing mathematical methods and tools that formulate the precise meaning and behavior of (quantum) systems, processes, type systems and programming languages, other formal languages and computational models. This includes, but is not limited, to the following:
- Operational semantics: a mathematically precise description of the dynamics of quantum programs and other computational models (e.g., the small-step semantics of quantum lambda calculi, token-machine semantics of quantum diagrammatic calculi).
- Mathematical and denotational semantics: a mathematical interpretation of a quantum programming language, process theory, diagrammatic calculus, etc., which is always expected to be sound and often expected to be adequate or complete.
This line of research is focused on identifying fundamental connections between the static specification (e.g. syntax) of quantum languages, their dynamic behavior (e.g. operational semantics) and their mathematical interpretation (e.g. denotational semantics) with the intention of developing each of these components further.
3.3 Graphical languages and optimization for quantum computation
The QuaCS team is involved in the development and study of graphical calculi such as quanctum circuits, ZX-, ZW-, ZH-calculi, but also languages for linear optics, such as the LOv-calculus. These languages are supposed to represent particular features of quantum computing, and hence are designed with a particular semantics in mind. A question of interest in the field is that of completeness with respect to that semantics : the ability to graphically turn any two equivalent diagrams into one another, making it possible to entirely reason within the language. The team is interested in the structure quantum operators have, that can be exhibited by the graphical approach, and depending on the model of computation at hand. It then becomes possible to study the links between the graphical languages, and hence, between the different models of computation. Recently, some focus has been put in the use of graphical languages for the study of indefinite causal orders, a extension to the usual quantum computation model, where not only data is quantum, but also the control flow of the program, which is allowed by the theory but still not well understood.
4 Application domains
4.1 Quantum simulation
Feynman’s invention of Quantum Computing really came out of a frustration: that of seeing classical computers take such a long time to simulate quantum systems. His intuition was that «quantum computers» would do a better job at simulating quantum systems. There is not the slightest doubt indeed that quantum simulation will have major outcomes for society. Thinking about it, most of the objects that surround us (cars, computers, furniture…) are designed on computers, thanks to the fact that we can prototype and simulate them on classical computers. That is, up to a certain scale. Below that we are left in the dark as quantum effects come into play, yielding an exponential blow up of the cost or simulation. For now. But, the day we will have good quantum computers and good quantum simulation algorithms to run upon them, we will be able to simulate these particles, atoms, molecules and the way they interact. Consequently we will be able to design specific-purpose molecules, materials, nanotechnologies, with applications in chemistry, biochemistry, electronics, mechanics. At QuaCS we focus on the bottom layer: the quantum-simulation algorithms for fundamental particles. After all, to be able to efficiently simulate fundamental interactions is to be able to simulate virtually everything, from first principles. An added bonus of this strand of research is that usually when we express some physics as a quantum algorithm, it becomes way simpler, more explanatory.
4.2 Semantics
This line of research can reveal interesting connections between mathematical structures, computational models, type systems and other formal languages. Ideally, one endpoint of such a connection can be used to influence the design and development of the other endpoint, because these connections can allow us to improve our understanding of the different aspects of the (quantum) systems and computational models under consideration.
For instance, monads in category theory were the inspiration for introducing monads in programming languages. Another example includes categorical quantum mechanics which lead to the development of the ZX-calculus along with other useful tools, such as PyZX/QuiZX, which may be used for optimisation of quantum circuits and classical simulation of quantum processes.
4.3 Graphical languages and optimization for quantum computation
One of the main features of graphical languages is that they can be made abstract enough to remove unnecessary clutter and ease reasoning on quantum operators. This has several consequences : They are rather intuitive to work with, while at the same time being completely formal They can provide an intermediate representation of quantum programs, with enough abstraction to reason about and modify the program during compilation. The most illustrative example of such modification is circuit optimisation, where the goal is to reduce the number of "expensive" quantum gates in the circuit, which can be achieved by turning the circuit into a ZX-diagram, then using its equational theory to perform the reduction. Together with the simplification heuristic, it is possible to exploit this "uncluttering" effect to perform more efficient classical simulation of quantum programs. It can be exploited to perform automated verification of quantum programs.
5 New results
5.1 Quantum simulation
Participants: Pablo Arnault, Pablo Arrighi.
5.1.1 A relativistic discrete spacetime formulation of 3+1 QED
We achieved the first quantum cellular automaton model for real-life interacting particles, namely electrons and photons, a.k.a 3+1 quantum electrodynamics. We motivated our construction by proposing a discrete version of a fundamental symmetry of Physics, namely gauge symmetry, which turns out to be reminiscent of fault-tolerance in Computer Science. This opens the way for natively discrete formulations of quantum field theories, otherwise renowned for their ill-definedness. (Preprint 14)
5.1.2 A single-particle framework for unitary lattice gauge theory in discrete time
We provided a discrete-spacetime action functional for 1+1 quantum electrodynamics, based on a discrete-time quantum walk. Let us explain the relevance of such a result. Remember that there are two mathematical frameworks for constructing a given theory made of quantum fields (matter fields and interaction fields): the path-integral manner, or the operator approach. The previous result follows the operator approach. An advantage of the path-integral approach in continuum spacetime is that it makes certain symmetries more manifest, especially the Lorentz symmetry, which cannot be manifest in the operator approach. We expect our result will bring these benefits to the discrete. (1)
5.2 Classical Simulation
Participants: Renaud Vilmart.
We exploit the ZX-calculus and its simplification heuristic, together with new decompositions of pieces of diagrams into simpler ones to perform classical simulation of quantum programs. On the circuits that were benchmarked, this approach is a significant improvement upon the competition, allowing to simulate within minutes on a consumer laptop circuits of a size that would require a supercalculator to simulate naively. (8)
5.3 Graphical Languages
Participants: Kostia Chardonnet, Marc De Visme, Benoît Valiron, Renaud Vilmart.
We designed a graphical language, called "Many-World-calculus" (MWC) that accommodates for both a tensor product and a coproduct in a natural way, where other graphical languages either have only one of the two products, or have to use three-dimensional diagrams with unintuitive ways to compose them. While the tensor product is the usual way to pair quantum systems together, the coproduct allows the representation of "branching", hence quantum control flow. The MWC is given a denotational semantics, allowing us to understand the diagrams as the operator they perform, and is given an equational theory, which we show to be complete with respect to that semantics (i.e. all diagrams that represent the same operator can be turned into one another using the rules of the equational theory). (Preprint: 12)5.4 Completeness for Quantum Circuits and the LOv calculus
Participants: Benoît Valiron, Nicolas Heurtel.
We introduced a new language called the LOv-calculus which is used for reasoning about linear optical quantum circuits. The language is graphical in nature, and has a specific set of rules to follow. We show that the language is sound and complete, meaning that two LOv-circuits that represent the same quantum process can be transformed into each other with the rules of the LOv-calculus. We also recover several known canonical forms of circuits from the literature. As a follow-up, we derive the first complete equational theory for quantum circuits, the standard language for quantum computation. (6, 13)5.5 Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions
Participants: Titouan Carette.
We designed a universal and complete graphical language for the stabilizer fragments for qudits when d is prime. (Published in MFCS2022)
5.6 Fact-nets: towards a mathematical framework for relational quantum mechanics
Participants: Titouan Carette.
They are different interpretation of quantum mechanics, most of them come with their own mathematical formalism. This was not the case of relational quantum mechanics that was usually only formulated is an additional interpretational layer on top of the usual mathematical framework of quantuml mechanics. In this paper, we propose a refoundation of quantum mechanics whose premises are relational from the start. (Published in Foundations of Physics)
5.7 Semantics
Participants: Titouan Carette, Louis Lemonnier, Vladimir Zamdzhiev.
5.7.1 Central Submonads
Monads in category theory are algebraic structures that can be used to model computational effects in programming languages. We show how the notion of “centre", and more generally “centrality", may be formulated for strong monads acting on symmetric monoidal categories. We identify three equivalent conditions which characterise the existence of the centre of a strong monad and we show that every strong monad on many well-known naturally occurring categories does admit a centre, thereby showing that this new notion is ubiquitous. More generally, we study central submonads, which are necessarily commutative, just like the centre of a strong monad. We provide a computational interpretation for our ideas by formulating equational theories of lambda calculi equipped with central submonads, we describe categorical models for these theories and we prove soundness, completeness and internal language results for our categorical semantics. (Preprint: 10)
5.7.2 Others
Vladimir Zamdzhiev has other semantics results published in 2022 (e.g. publications in LICS and POPL), but they are not reported here, because these results were obtained while he was a member of the MOCQUA team.
6 Bilateral contracts and grants with industry
Quandela
Participants: Benoît Valiron, Pablo Arrighi, Nicolas Heurtel.
In the context of a PhD funded by CIFRE, QuaCS and Quandela are building a collaboration on the study of quantum linear optics. The approach is both theoretical –with the development of a formal language for reasoning on optical circuits, and practical, targeted towards simulation.
7 Partnerships and cooperations
7.1 International initiatives
QISS
Participants: Pablo Arnault, Pablo Arrighi, Marc de Visme, Benoit Valiron, Renaud Vilmart, Vladimir Zamdzhiev.
-
Title:
Quantum Information Structure of Spacetime
-
Partner Institution(s):
- Center for the Space, Time and the Quantum, France
- Institute for Quantum Optics and Quantum Information, Vienna, Austria
- Rotman Institute for Philosophy, Western University, Canada
- Center for Theoretical Physics, Aix-Marseille University, France
- Quantum Group and Clarendon Laboratory, University of Oxford, United-Kingdom
- Perimeter Institute, Canada
- University of Paris-Saclay, Quantum Computation Structures group, France
- Quantum Information and Computation Initiative, HKU, United-Kingdom
- Okinawa Institute of Science and Technology, Japan
- University of California Santa Barbara, Physics dpt, United States of America
- Center for Quantum Information and Communication, Brussels, Belgium
- Quantum Information Laboratory, Rome La Sapienza University, Italy
- Penn State University, Institute for Gravitation and the Cosmos, United States of America
- Center for Mathematical Sciences, UNAM, Namibia
- Bard College, New York, United States of America
-
Additionnal info/keywords:
QISS is an interdisciplinary initiative in Quantum Information and Quantum Gravity, bringing together theorists, experimentalists and philosophers. Our research program aims to unravel the Quantum Information Structure of Spacetime. The consortium is supported by the John Templeton foundation and from numerous smaller grants obtained by individual participating research groups. The overarching theme investigated is the conceptual role of Information in gravitational physics. This calls for a rethinking of Space, Time and Quantum foundations.
7.2 National initiatives
EPiQ (PEPR Quantique)
Participants: Pablo Arnault, Pablo Arrighi, Marc de Visme, Benoit Valiron, Renaud Vilmart, Vladimir Zamdzhiev.
-
Title:
Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l’informatique quantique
-
Partner Institution(s):
- INRIA, France
- CNRS, France
- CEA, France
-
Additionnal info/keywords:
Despite its relatively small size, the French quantum computing research community has always been at the forefront of international research. It thus provides the foundations for an ambitious strategy aiming at: (1) Understanding the advantages and limits of quantum computing via both quantum complexity research and the discovery and enhancement of algorithms (2) Defining the framework for quantum computation using high-level languages, comparison of computational models as well as using their relations for program optimization (3) Develop simulation tools to anticipate the performances of algorithms on noisy quantum machines. Algorithmic aspects are key in the field of quantum computing which witnesses a tremendous intensification of research efforts worldwide. Indeed, in addition to determining the design and the construction of hardware quantum processors, algorithms also constitute the interface through which users will solve their practical use cases leading to potential economic gain. Based on the outstanding French position, our project aims at developing algorithmic techniques 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.
8 Dissemination
8.1 Promoting scientific activities
8.1.1 Scientific events: selection
Member of the conference program committees
- Benoit Valiron for AFADL 2022
- Benoit Valiron for PPDP 2022
- Benoit Valiron and Vladimir Zamdzhiev for QPL 2022
- Benoit Valiron and Vladimir Zamdzhiev for WADT 2022
- Benoit Valiron and Vladimir Zamdzhiev for PlanQC 2022
- Vladimir Zamdzhiev for ACT 2022
- Pablo Arrighi for MCU 2022
Reviewer
- Renaud Vilmart for QPL 2022
- Renaud Vilmart FoSSaCS 2023
8.1.2 Journal
Reviewer - reviewing activities
- Pablo Arrighi for Nature Communcation
- Vladimir Zamdzhiev for Quantum
8.1.3 Invited talks
- Pablo Arrighi, on Quantum cellular automata for quantum simulation, for ACRI 2022, Geneva, Switzerland, September 2022.
- Pablo Arrighi, on A quantum information perspective on the problem of quantum gravity, for QISS 2022, London Ontario, Canada, June 2022.
- Renaud Vilmart, on How to Verify Quantum Processes for Movep 2022, Aalborg, Denmark, June 2022
8.1.4 Leadership within the scientific community
The internationl consortium on Quantum Information Structure of Spacetime (2020–2023, 2023–2026, qiss.fr) is made of the top researchers, worldwide, on the question of the interaction between quantum information and quantum gravity. The grant is managed by the board of this center (center for space, time and the quantum), of which Pablo Arrighi is a member.
8.1.5 Scientific expertise
- Pablo Arrighi, “Shepherd” for the creation of the EPC Inria team Quriosity
- Pablo Arrighi, RIPEC C3 expert for three applicants
8.1.6 Research administration
- Pablo Arrighi is an elected council member (2021–) of the Univ Paris-Saclay's Graduate School of Computer Science. The Graduate School structures Computer Science at the scale of Univ. Paris-Saclay.
- Pablo Arrighi and Benoit Valiron are executive committee member (2020–) of the Quantum center of Saclay. The center coordinates the French strategy for quantum technologies at the scale of Univ. Paris-Saclay and Institut Polytechnique de Paris.
8.2 Teaching - Supervision - Juries
Participants: Benoit Valiron.
- Introduction Course to Algorithmic and Quantum Programming, M2 QDCS, ENS ArteQ, 3A CentraleSupélec.
- 192 hours of Teaching in the Computer Science curiculum of CentraleSupélec.
Participants: Pablo Arrighi.
Courses/Master level- 2020– Found. of quantum information 30 students/y. (M1, UPSaclay)
- 2020– Elements of CS for quantum technologies. 30 students/y. (M1.5, ENS PSaclay) with Marc de Visme
- 2020– Introduction to research 10 students/y. (M1, ENS PSaclay),
- 2020– Func. programming (M1, Polytech PSaclay)
Courses/Undergraduate level
- 2020– Advanced functional prog., 100 students/y. (L3, UPSaclay)
Participants: Renaud Vilmart.
- Advanced quantum computation and error correction. 20 students (M2, QDCS, UPSaclay)
- Projet informatique. 50 students (L2, LDD2 Info-Maths, UPSaclay)
Participants: Vladimir Zamdzhiev.
- Introduction to Research, 9 students (M1, ENS PSaclay)
8.2.1 Supervision
- Benoit Valiron co-supervised 6 PhD students in 2022: Agustín Borgna, Kostia Chardonnet, Nicolas Heurtel, Dongho Lee, Louis Lemonier, and Jérome Ricciardi
- Pablo Arrighi co-supervised 6 PhD students in 2022: Kostia Chardonnet, Marin Costes, Amélia Durbec, Nathanaël Eon, Nicolas Heurtel, and Louis Lemonier.
- Vladimir Zamdzhiev co-supervised 2 PhD students in 2022: Kinnari Dave and Louis Lemonier.
8.2.2 Juries
Discounting own students, Pablo Arrighi was PhD jury member for
- Matteo Luigi (U. of Pavia), written report and jury member
- Nicola Pinzani (Oxford U.), written report and jury member
- Hippolyte Dourdent (Institut Néel, Grenoble), written report and jury member
- Alexandre Fernandez (UPEC), president of the jury
- Kevissen Selapillay (AMU), jury member
Pablo Arnault was PhD jury member for Nathanaël Eon (Aix-Marseille U.)
8.3 Popularization
8.3.1 Internal or external Inria responsibilities
- Pablo Arrighi is Co-head of M1 and M2 QDCS, 30 students/y. (UPSaclay)
- Pablo Arrighi is Head of M1 MPRI, 15 students/y. (UPSaclay)
8.3.2 Articles and contents
- Participation of Pablo Arrighi in the Podcast RDV Tech 493 – Spécial : L’informatique quantique , December 2022
- Participation of the whole team to the Inria's "Exposition Photo" by Frédéric Stucin
- Inria interview of Benoit Valiron and Pablo Arrighi, published on the Inria website
- Inria "portrait métier" of Renaud Vilmart, published on the Inria website
- Inria interview of Benoit Valiron and Shane (from Quandela), published on the Inria website
8.3.3 Interventions
- Pablo Arrighi, round-table discussion on “Ordinateur quantique: avancées majeures et perspectives”, Convention annuelle 2022 - Pôle de compétitivité SYSTEMATIC Paris-Region.
- Pablo Arrighi, Vers l’informatique quantique, Larger audience talk at “La Commanderie”, Saint-Quentin-en-Yvelines, October 2022
9 Scientific production
9.1 Publications of the year
International journals
International peer-reviewed conferences
Reports & preprints