With intermediate-size quantum computers currently being built, the development of new quantum algorithms has never been more relevant. The aim of this project is to push forward the frontier of quantum algorithms and quantum algorithmic techniques for solving key problems in optimization and sampling. To this end, we will combine and build on recent but mostly disjoint progress in quantum algorithms in discrete and continuous settings. Examples are the recent quantum algorithms by the scientific coordinator for graph problems such as sparsification and Laplacian solving, and an independent line of works on quantum algorithms for convex optimization techniques such as gradient descent and semi-definite programming. The project takes inspiration from the modern paradigm in optimization and high-dimensional sampling that critically combines techniques from both discrete and continuous settings. Indeed, the current best algorithms for problems such as linear programming and sampling from polytopes combine sparsification techniques with random walk algorithms and interior point methods from convex optimization. Building on these new insights, the QUOPS project is bound to obtain a better understanding of quantum speedups for these problems. Concrete objectives are quantum algorithms that speed up canonical optimization tasks such as maximum flow and lp-regression, and key tasks in statistics and machine learning such as logconcave sampling and polytope sampling. By building on the consortium expertise both in quantum algorithms and in modern optimization, we will be able to bridge the current gap between quantum algorithms and modern paradigms in classical computing.

The variety of challenges laid down by software-driven systems (in particular cyber-physical systems) call all the time for new techniques for assessing their performance, safety and security. Beyond the Boolean question whether a given system satisfies these properties, one would rather ask how much it does so. Thus, researchers have introduced different quantitative properties: probability of violating the specification, value of simulation games, quantitative semantics of specification logics, robustness measures, entropy as information measure or entropy rate of the set of bad behaviors. For computing their values, usual model-checking approaches were augmented with various quantitative technicalities: linear programming, game-theoretic approaches, differential and integral equations etc. This diversity causes several issues, making quantitative verification extremely challenging. We can state the difficulty for choosing the most relevant technique among already existing ones (because of non consistent presentation styles and choices of terminology) and the tediousness of developing appropriate variants for each criterion which we want to evaluate. We believe that, because common patterns are used in many cases, for quantitative verification of timed, hybrid, and/or stochastic systems, the above issues can be strongly mitigated by developing unified frameworks. For instance, we noticed similar are the work-flows for handling probability distributions in Markov Chains, language volumes in timed automata (TA) and probability distributions of runs in stochastic timed automata. First, state space, transitions and behaviors are endowed with a measure, then a measure transforming transfer operator is defined, and finally several properties of the model can be determined as spectral properties of the operator (stationary distributions, volume growth rate/entropy, ... ). In the above example, the common pattern is clear. We believe that by allowing some variations, many more instances could be unified. The notion of transfer operator (and associated measure) is central in the methods we want to promote (its spectrum yields many pieces of information about algorithms based on iterations of the operator: convergence, speed of convergence, fixed point, ... ). As such, it is the topic of our first work package. Questions of the form ``How many behaviors are there?'' or ``How much does it cost?'' can easily be formalized in terms of iterations of an operator. Unfortunately, answering the question may have a high algorithmic complexity or the question may be undecidable. For this reason, the second work package focuses on abstraction and approximation techniques for efficiently answering such questions. A prototype tool will be provided and tested on a case study (robust control of cyber-physical systems). Other questions (robustness questions) have the form ``How far from reaching a bad state are the behaviors of the system?'' or ``How far can we perturb a model or its execution while still avoiding bad states?''. Such statements depend on the notion of distance, of which several versions can be considered, with different properties. Comparative study of distances, their links with the operator method and their application to robustness problems is the topic our third work package. Last, when the complexity of the model is too high or when there is no complete model of the system to begin with (black box) (often true for cyber-physical systems), validation requires the use of simulation technique, for which different sampling methods exist. In the last work package, we consider exhaustive sampling up to distance $\varepsilon$ (linked with study of distances) and uniform random sampling (linked to study on measures and operators). These techniques will also be implemented in a tool and tested on CPS case studies from the ARCH Workshop (contributed by industrial actors).

The topic of this project is the design of efficient approximation algorithms for NP-hard combinatorial optimization problems. Such problems abound in all fields of science and engineering - in fact the vast majority of interesting problems are NP-hard and therefore do not admit fast (polynomial-time), exact algorithms. However, these problems still need to be solved! This has motivated the study of algorithms which are allowed to return sub-optimal solutions (approximation algorithms), or algorithms which use more than polynomial time (exponential-time and parameterized algorithms). The two approaches are among the most well-studied topics in theoretical computer science. Both have produced many notable successes, but they have now reached their limits. In particular, thanks to advances in fine-grained complexity theory and hardness of approximation, we know that large classes of problems are hard to approximate in polynomial time and hard to solve exactly with sub-exponential or parameterized algorithms (under standard assumptions). The SEXAPPEAL project aims to overcome these barriers by adopting a unified approach for the design of algorithms for NP-hard problems. Its scientific hypothesis is that for many important optimization problems finding an almost-optimal solution requires dramatically less time than exact optimization. This hypothesis is strongly supported by preliminary results produced by our team. This early work indicates that, by combining techniques from polynomial-time approximation with exact exponential-time and parameterized algorithms, we can guarantee a solution quality unachievable in polynomial time, often coming extremely close to optimal, while investing time significantly smaller than that needed to solve a problem exactly. Our project proposes to compose in new and innovative ways the techniques which have so far been studied disjointly in the context of exponential-time and FPT algorithms, and of polynomial-time approximation. The study of such algorithms has recently attracted interest, but is still in a nascent stage. We propose a methodology that will allow us to make rapid progress, while minimizing risk, by aligning our research across three Tasks: 1. Exponential/Parameterized Approximation Algorithms for Network Optimization Problems. 2. Generic Approximation Techniques in Super-Polynomial Time. 3. Lower Bounds and Hardness of Approximation. Task 1 will focus on the design of novel algorithms for optimization problems with applications in transportation, communication, and social networks, with the goal of out-performing the best exact algorithms in terms of running time and the best approximation algorithms in terms of solution quality. This Task is an out-growth of current work and offers the potential for rapid progress. It also includes a significant emphasis on software implementations, which will allow our work to compete with state-of-the-art solutions for various optimization problems. Task 2 will focus on the distillation of the algorithmic techniques discovered in Task 1, the development of new techniques, and their precise formalization into general meta-theorems. Finally, Task 3 aims to complete the picture by providing lower bound results on approximation in the context of super-polynomial time algorithms. The project is structured in a way that minimizes risk but maximizes gain, as work is set to begin on a Task that builds upon recent advances (Task 1), and culminate into the more ambitious Tasks (2, 3) that aim to produce a complete unified theory for dealing with NP-hardness. The state-of-the art is ripe for this work and our project can be seen as the natural continuation of a line of research in which the members of our team have played central roles in recent years. Furthermore, our team includes researchers with significant expertise in all relevant fields, and is led by a PI with a well-recognized research record fitting ideally the project topic.

Despite the practical interests of reusable frameworks for implementing specific distributed services, many of these frameworks still lack solid theoretical bases, and only provide partial solutions for a narrow range of services. We argue that this is mainly due to the lack of a generic framework that is able to unify the large body of fundamental knowledge on distributed computation that has been acquired over the last 40 years. The DESCARTES project aims at bridging this gap, by developing a systematic model of distributed computation that organizes the functionalities of a distributed computing system into reusable modular constructs assembled via well-defined mechanisms that maintain sound theoretical guarantees on the resulting system. DESCARTES arises from the strong belief that distributed computing is now mature enough to resolve the tension between the social needs for distributed computing systems, and the lack of a fundamentally sound and systematic way to realize these systems.

Quantum information aims at a revolution in information technologies, in the form of a large-scale network of classical and quantum devices able to communicate and process massive amounts of data efficiently and securely. Our goal is a comprehensive analysis of the potential of quantum computing in this context. The objectives of our project are to provide quantum applications for machine learning, design quantum algorithms for models with restricted access to data, design software suites for programming such applications, use our high-performance computing platforms to simulate the behaviour on real data sets, and optimize the resources of such algorithms. Our ambition is to push quantum information protocols closer to commercialization and create a new platform for potential disruptive technologies through the synergy of quantum mechanics and information sciences.