Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 6 min ago
PreprintarXiv licencearXiv

Quantum Advantage for Distributed Symmetry Breaking

  • Maxime Flin
  • Longcheng Li
  • Jukka Suomela
Open at sourcePDFDOICite

Abstract

We present a distributed quantum algorithm that $3$-colors cycles in O(1) rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity O(log* n) in the classical LOCAL model can be solved in O(1) rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.

Related

  1. Structural Conditions for Distributed Quantum Advantage
    Sabina Drăgoi, María Gragera Garcés, Lirandë Pira
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Taking Advantage of Noise in Distributed Random Quantum Circuits
    J. Montes, F. Borondo, Gabriel G. Carlo
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Spontaneous particle-hole symmetry breaking in a disordered two-site quantum breakdown model
    Kinya Guan
    arXivPreprintarXiv licenceFull textStatistical & nonlinear physicsarXiv
  4. Emergent Quantum Synchronization Without Symmetry Breaking
    Juan David Álvarez-Cuartas, Joakim Bergli, John H. Reina
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Quantum manifestations of converse symmetry breaking
    Daniel P. Buser, Biswabibek Bandyopadhyay, Adilson E. Motter
    arXivPreprintarXiv licenceFull textCondensed matterQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{flin2026quantum,
  title = {{Quantum Advantage for Distributed Symmetry Breaking}},
  author = {Maxime Flin and Longcheng Li and Jukka Suomela},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26788},
  eprint = {2609.26788},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26788},
}
RIS
TY  - UNPB
TI  - Quantum Advantage for Distributed Symmetry Breaking
AU  - Maxime Flin
AU  - Longcheng Li
AU  - Jukka Suomela
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26788
UR  - https://arxiv.org/abs/2609.26788
AB  - We present a distributed quantum algorithm that $3$-colors cycles in O(1) rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity O(log^* n) in the classical LOCAL model can be solved in O(1) rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.
ER  -