New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
22
Series
39th International Symposium on Distributed Computing (DISC 2025), pp. 1-22, Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 356
Abstract
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 distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm $\mathcal{A}$ that finds an $α$-approximation of some linear optimization problem $Π$ in $T$ communication rounds, we can construct a classical, deterministic LOCAL algorithm $\mathcal{A}'$ 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. Second, 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 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.Description
Keywords
Other note
Citation
Balliu, A, Coupette, C, Cruciani, A, d'Amore, F, Equi, M, Lievonen, H, Modanese, A, Olivetti, D & Suomela, J 2025, New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs. in 39th International Symposium on Distributed Computing (DISC 2025) . Leibniz International Proceedings in Informatics (LIPIcs), vol. 356, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-22, International Symposium on Distributed Computing, Berlin, Germany, 27/10/2025. https://doi.org/10.4230/LIPIcs.DISC.2025.11