Quantum Network Algorithms

This project lays the foundations for large-scale networks of quantum computers and aims to identify the first distributed tasks with a practical quantum advantage. We take the first steps towards forming the basis of a quantum internet that can be used in practice not only for quantum key distribution but also more generally to solve various coordination and resource-allocation tasks between a large number of parties efficiently, on a global scale.

Recently, our project partners have made major breakthroughs in understanding which tasks in computer networks would benefit from quantum technologies and what the fundamental limits of quantum advantage in such settings are. We have designed distributed quantum algorithms that demonstrate quantum advantage, and we have also identified tasks where no quantum advantage is possible (in particular when we account for the number of communication rounds needed to solve these problems).

However, despite all the recent progress, the only known examples of distributed tasks that benefit from quantum communication (in terms of communication rounds) are completely impractical in two ways: they are artificial problems engineered to demonstrate quantum advantage, and they rely on quantum states that are hard to realize with near-term quantum network technology.

This project unites experts on distributed computing and quantum information theory to take major steps towards developing distributed quantum algorithms that are practically relevant: (i) they solve problems of real interest in network applications and (ii) they are feasible to implement on near-term quantum hardware. We focus on provable quantum advantage, i.e., on problems where we can prove that no classical system can match the performance of an optimal distributed quantum algorithm, even asymptotically.

We also aim to clarify why numerous practically relevant distributed problems do not seem to admit quantum advantage; we aim to identify fundamental obstacles to quantum advantage, with the ultimate goal of a complete characterization of the maximum extent of quantum advantage for broad, practically relevant problem families. We also seek to understand the capabilities and limitations of, e.g., communication networks consisting of local quantum subsystems. Key deliverables will include novel designs for distributed quantum algorithms, and mathematical and computational tools to automate their design and analysis.