CAPP - Quantum and Classical Computation

Quantum and Classical Computation

CAPP (Calculi, Algorithms, Programs and Proofs) is a team of the LIG (Laboratoire d’Informatique de Grenoble) devoted to theoretical computer science. Our research topics belong to the domains of automated reasoning, quantum computing, and the theoretical foundations of programming languages.

Job Opportunities

Formalization of Transactions in Concentrated Liquidity Market Makers (postdoctoral fellowship)

Presentation

The CAPP team carries out research in theoretical computer science, especially in the fields of rewriting, logic, automated reasoning, and quantum computing. We devise formalisms, algorithms, and tools for the specification, design, analysis, and certification of complex computing systems.

Motivations

Computing devices are becoming increasingly numerous, heterogeneous, and complex, with most human activities now relying on them. In this context, errors or malfunctions can lead to dramatic consequences, ranging from significant financial losses to human casualties, or more subtle issues such as incorrect or inappropriate decisions. It is therefore crucial to simplify and rigorize the development of these systems and to ensure their correct behavior. Additionally, equipping computing devices with reasoning capabilities allows them to extract explicit knowledge from their environment, provide convincing justifications for their decisions, interact with other agents, and more. The CAPP team develops theoretical tools and results to tackle these challenges.

Research Program

We design high-level languages to describe computations, tailored to various application domains and grounded in solid theoretical foundations, such as rewriting, logic, or category theory. We analyze the properties of these models for information processing, define logics to specify and verify computation properties, and study their expressivity and computability. We also develop automated reasoning procedures, implement them as research prototypes, and apply them to solve real-world problems. Here, reasoning encompasses a broad scope: not only proving valid properties but also extracting knowledge through tasks like data analysis, synthesizing explanations, filling in missing information, and transforming proofs.

Part of the team is dedicated to quantum computing, a pivotal challenge at the intersection of computer science and physics. Quantum computing leverages phenomena such as superposition and entanglement to perform computations (e.g., a quantum bit can exist in a superposition of 0 and 1 with certain probabilities). These phenomena enable algorithms that surpass the speed of classical counterparts, offering transformative potential for computational efficiency.

Topics

Quantum Computing
- Error correction for quantum information
- Quantum control of quantum circuits
- Erasure of quantum information
- Incompatibility of quantum measurements
- Quantum entropies
Automated Reasoning
- Separation logic
- Inductive reasoning
- Superposition calculus
- Formalization of financial mathematics
Rule-based Programming
- High-level frameworks for graph transformation
- Parallel graph rewriting
- Verification of graph transformations

Grants

ANR project BlockFi: Blockchain et Finance Décentralisée (PI: E. Gobet, local coordinator: M. Echenim, 24-29).
PEPR ANR project – EPiQ (22-27): Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l’informatique quantique (local coordinator: M. Echenim).
IRGA project – POQIT (23-24) – Non-commutative polynomial optimization methods for quantum information theory (PI: A. Bluhm).
ANR project VerifGraph (22-26): Verifiable Graph Queries and Transformations, R. Echahed, with Leonid Libkin (head) and Angela Bonifati.
ANR project NARCO (22-26): Non-Aggregative Resource COmpositions (PI: N.Peltier, partners: LIG, LMF, LORIA, Verimag).
LIG project “Emergence”. Graph Rewriting for Quantum Computing (2020-2021, N. Peltier).
LIG project “Emergence” Réécriture Parallèle (2019-2020, T. Boy de la Tour)
LIG project “Emergence” Abductive Reasoning and Separation Logic (2018-2019, heads: M. Echenim and N. Peltier)
ANR project ASAP (PI: A. Leistch and N. Peltier)
ANR project CLIMT (PI: R. Echahed).

Publications

You can obtain all publications of the CAPP team on HAL

Major Events

February 25. I. Šupić (CR CNRS) joined CAPP.
September 24. Start of the BlockFi ANR project.
November 22. A. Bluhm (CR CNRS) joined CAPP.
January 22. Kesitys is now part of Kaiko.
January 22. Start of the NARCO project (ANR).
January 22. Start of the EPiQ project (ANR, Etude de la pile quantique: Algorithmes, modèles de calcul et simulation pour l’informatique quantique).
October 21. Start of the VeriGraph project (ANR).
December 2020. Alastair A. Abbott (CR Inria) is hosted by the CAPP team.
IJCAR 2020: International Joint Conference of Automated Reasoning (co-PC-chair: N. Peltier)
Start of the “LIG TIC Talks” (organized by F. Prost)
July 2019. 10th International Workshop on Graph Computation Models. (co-chaired by R. Echahed, with D. Plump)
February 2019: N. Peltier replaced R. Echahed as the head of the CAPP team.
End 2018: creation of the Kesitys start-up, co-founded by M. Echenim (CAPP), Emmanuel Gobet and Anne-Claire Jeancolas.

Members

Scientific Leader

Nicolas Peltier (CNRS Researcher, HdR)
Office: 481, Phone: 04 57 42 14 90
Email: nicolas.peltier@imag.fr

Permanent Members

Andreas Bluhm (CNRS Researcher)
Office: 486, Email: Andreas.Bluhm@univ-grenoble-alpes.fr
Thierry Boy de la Tour (CNRS Researcher)
Office: 482, Phone: 04 57 42 14 62
Email: thierry.boy-de-la-tour@imag.fr
Mnacho Echenim (Professor GINP)
Office: 486, Phone: 04 57 42 14 91
Email: mnacho.echenim@imag.fr
Rachid Echahed (CNRS Researcher, HdR)
Office: 480, Phone: 04 57 42 15 40
Email: rachid.echahed@imag.fr
Mehdi Mhalla (CNRS Researcher, HdR)
Office: 484, Phone: 04 57 42 15 30
Email: mehdi.mhalla@imag.fr
François Puitg (associate lecturer UGA)
Office: 483, Phone: 04 57 42 15 46
Email: francois.puitg@imag.fr
Ivan Šupić (CNRS Researcher)
Office: 480, Phone: 04 57 42 15 40
Email: ivan.supic@univ-grenoble-alpes.fr

PhD Students

Tomas Barros Carneiro
Simon Hofer
Raphael Le Bihan

Former Members

Paul-Elliot Anglès d’Auriac
Julien Du Crest
Richard East
Ashutosh Goswami
Pierre Pocreau
Frédéric Prost (MdC INSA Lyon)
Qi Qiu
Yanis Sellami (CEA)
Sophie Tourret (INRIA Researcher, Nancy)
Julian Wechs

Venue

Address:

CAPP – Laboratoire LIG

Bâtiment IMAG – 150 place du Torrent

Domaine universitaire de Saint Martin d’Hères

38400 Saint Martin d’Hères

FRANCE

Scientific Head: Nicolas Peltier

Tél. : (+33) 4 57 42 15 40

Venue:

Our building is located at the center of the campus (domaine universitaire) close to the tramway station “Gabriel Fauré” on line B. Tramways reach the campus from Grenoble railway station (or bus station) in approx. 15 mn. The tramway station “Gares” is shared between lines A and B, so make sure to take a tramway with a green sign reading: “B – Gières Plaine des sports”. Tickets are sold by machines at every station, and should be validated before the trip.

Links

The QInfo INRIA project-team

Some international journals in our field of research

Some international conferences

Some relevant Wikipedia articles