Quantum and Randomized Algorithms and Complexity

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.

Research activities
  Randomized algorithms
  Quantum computation
  Approximation algorithms
  Complexity
  Onilne algorithms

Participants