Abstract

In this project we study the fundamental limits of computation in large computer networks. While the limits of classical distributed systems are getting better and better understood, not much is known about the limits systems that make use of quantum computation and quantum communication. Understanding the laws that govern both classical and quantum distributed systems is the main goal of this project.

All kinds of present and future distributed systems, regardless of whether they are based on classical or quantum physics, are fundamentally limited by physical causality: no matter what the system does, it cannot allow communication faster than the speed of light. However, currently the causal limits of distributed computation are still poorly understood.

Causality-based lower-bound results would be very widely applicable: they hold in numerous models of distributed graph algorithms, including CONGEST, LOCAL, quantum-CONGEST, and quantum-LOCAL, even if the algorithm has access to shared randomness and shared quantum state. However, not many such results are known, and there has been little progress in the recent years in understanding the causal limits, in spite of the big leaps related to the classical limits.

In this project we seek to understand the causal limits of distributed computation. We identify problems in which causality-based arguments can be used to rule out any distributed quantum advantage, and we develop mathematical techniques for proving such results. We also seek to identify problems in which classical algorithms cannot reach the limits of causality—these are problems in which there is potential for exploiting quantum computation and quantum communication to outperform what can be achieved with classical distributed algorithms.

Funding

This project is funded by the Research Council of Finland, Grant 359104.