Quantum Advantage for Distributed Symmetry BreakingResearch Paper
In distributed computing, symmetry breaking asks the nodes of a network, all running the same program, to produce locally different outputs; the basic example is a proper colouring of a cycle. In the classical LOCAL model, 3-colouring an -cycle requires communication rounds, with or without randomness (Linial 1992). Whether quantum…