Distributed Quantum Advantage for Local Problems

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10

We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…