Quantum Advantage for the LOCAL Model in Distributed Computing

Abstract

There are two central models considered in (fault-free synchronous) distributed computing: the CONGEST model, in which communication channels have limited bandwidth, and the LOCAL model, in which communication channels have unlimited bandwidth. Very recently, Le Gall and Magniez (PODC 2018) showed the superiority of quantum distributed computing over classical distributed computing in the CONGEST model. In this work we show the superiority of quantum distributed computing in the LOCAL model: we exhibit a computational task that can be solved in a constant number of rounds in the quantum setting but requires $\Omega (n)$ rounds in the classical setting, where $n$ denotes the size of the network.

14 pages

References in corpus (8)

• Multi-party entanglement in graph states
• Quantum Computational Supremacy
• Quantum advantage with shallow circuits
• Quantum vs. Classical Communication and Computation
• Improved Quantum Communication Complexity Bounds for Disjointness and Equality
• Can quantum mechanics help distributed computing?
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• A Time Hierarchy Theorem for the LOCAL Model

Cited by in corpus (4)

• Quantum repeaters: From quantum networks to the quantum internet
• On Distributed Listing of Cliques
• On the Power of Quantum Distributed Proofs
• Contextuality and Expressivity of Non-locality