analiza aiqbench
This research establishes a fundamental lower bound for one-way, one-round quantum LOCAL algorithms, proving they cannot solve the 4-coloring problem for directed cycles even with unlimited local computation. The study bridges distributed quantum computing and noncommutative extremal combinatorics by leveraging a novel stability theorem for matrix-space decompositions. It represents a significant theoretical advance in understanding the structural limits of high-probability quantum distributed protocols beyond standard non-signaling models.
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
arXiv:2609.09091v1 Announce Type: new Abstract: We show that one-way one-round quantum LOCAL algorithms cannot $4$-color directed cycles with high probability, even with unbounded local computation and quantum message length. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.
Abstract:We show that one-way one-round quantum LOCAL algorithms cannot $4$-color directed cycles with high probability, even with unbounded local computation and quantum message length. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.
Quantum Physics (quant-ph); Distributed, Parallel, and Cluster Computing (cs.DC)
arXiv:2609.09091 [quant-ph]
(or arXiv:2609.09091v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.09091 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 194 cuvinte