4 papers
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Alkida Balliu, Corinna Coupette, Antonio Cruciani +6
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no d…
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know o…
Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +6
In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distribut…
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…