Algorithmique et Complexité Quantique et Probabiliste

Our project consists in joining the strengths of experts in both randomized and quantum computation. Our global objective is to make progress on both quantum and probabilistic computation, and also, by joining forces, to ensure that the flow of techniques goes in both directions, from randomized computation to quantum and back.
In the randomized model our emphasis is on sublinear algorithms for large data sets, in particular property testing, approximate verification, and online algorithms. In quantum computation, we will continue to work on algorithms for the hidden subgroup problem, vector lattice problems, among others. At the intersection of quantum and randomized computation, our goal is to study random and quantum walks, communication complexity, and lower bound methods for circuit and formula size complexity.

Activités de recherche
  Algorithmes probabilistes
  Calcul quantique
  Algorithmes approchés
  Complexité
  Algorithmes en ligne

Membres LRI