DISC 2025 · 39th International Symposium on Distributed Computing, Berlin, Germany, October 2025
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:
Our results extend from quantum-LOCAL also to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.