DISC 2025 · 39th International Symposium on Distributed Computing, Berlin, Germany, October 2025 · doi:10.4230/LIPIcs.DISC.2025.11
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.

Dariusz R. Kowalski (Ed.): 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:22, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025
ISBN 978-3-95977-402-4