New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914120616378368 |
|---|---|
| author | Balliu, Alkida Coupette, Corinna Cruciani, Antonio d'Amore, Francesco Equi, Massimo Lievonen, Henrik Modanese, Augusto Olivetti, Dennis Suomela, Jukka |
| author_facet | Balliu, Alkida Coupette, Corinna Cruciani, Antonio d'Amore, Francesco Equi, Massimo Lievonen, Henrik Modanese, Augusto Olivetti, Dennis Suomela, Jukka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 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 Distributed, Parallel, and Cluster Computing Computational Complexity 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. |
| title | New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs |
| topic | Distributed, Parallel, and Cluster Computing Computational Complexity |
| url | https://arxiv.org/abs/2506.07574 |