Distributed Quantum Algorithms

Quantum advantages designate situations where processing qubits of information solves a task significantly more efficiently than processing classical bits of information in some basic abstract scenario. Our understanding of quantum advantages for distributed computing is limited. In particular, it is not well understood whether quantum information can deal with issues inherent to networks such as latency due to the finite speed of information, by allowing for distributed algorithms using fewer communication steps than classical distributed algorithms. With coauthors, Marc O. Renou obtained the first natural quantum advantage for a local task quite recently [arXiv:2411.03240 [cs.DC]]. On the contrary, it also has been demonstrated that the methods to find limits on quantum capabilities at such distributed algorithms fail to understand these limits fully [arXiv:2403.01903 [cs.DC]]. The project aims to develop novel methods to understand the limits of quantum capabilities at distributed algorithms by adapting the quantum Inflation-NPA technique, introduced by Elie Wolfe [J. Causal Inference 7(2), 2019], to the context of distributed algorithms.

Faculty Supervisor:

Elie Wolfe

Student:

Partner:

INRIA - Saclay

Discipline:

Physics

Sector:

Quantum Science; Information and Communications Technology

University:

University of Waterloo

Program: