2026-07-22T13:28:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24828 2026-02-09T07:41:37Z ddc:004 open_access

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs Balliu, Alkida Coupette, Corinna Cruciani, Antonio d'Amore, Francesco Equi, Massimo Lievonen, Henrik Modanese, Augusto Olivetti, Dennis Suomela, Jukka linear programming distributed quantum advantage quantum-LOCAL model SLOCAL model online-LOCAL model non-signaling distributions locally checkable labeling problems dequantization 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: 1) We show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm 𝒜 that finds an α-approximation of some linear optimization problem Π in T communication rounds, we can construct a classical, deterministic LOCAL algorithm 𝒜' that finds an α-approximation of Π in T rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. 2) Using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alkida Balliu and Corinna Coupette and Antonio Cruciani and Francesco d'Amore and Massimo Equi and Henrik Lievonen and Augusto Modanese and Dennis Olivetti and Jukka Suomela 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.11 urn:nbn:de:0030-drops-248280 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode