Quantum Distributed Complexity of Set Disjointness on a Line

Autor: Magniez, Frédéric, Nayak, Ashwin
Přispěvatelé: Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2022
Předmět:
FOS: Computer and information sciences
Theory of computation → Quantum communication complexity
MathematicsofComputing_GENERAL
FOS: Physical sciences
Computational Complexity (cs.CC)
Theoretical Computer Science
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
Theory of computation → Quantum query complexity
communication complexity
[INFO]Computer Science [cs]
Theory of computation → Distributed algorithms
Quantum distributed computing
ComputingMilieux_MISCELLANEOUS
Quantum Physics
Set Disjointness
TheoryofComputation_GENERAL
16. Peace & justice
Computer Science - Computational Complexity
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computer Science - Distributed
Parallel
and Cluster Computing
Computational Theory and Mathematics
Theory of computation → Quantum computation theory
ComputingMethodologies_DOCUMENTANDTEXTPROCESSING
query complexity
Distributed
Parallel
and Cluster Computing (cs.DC)
Quantum Physics (quant-ph)
Zdroj: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Jul 2020, Saarbrücken, Germany. pp.82:1--82:18, ⟨10.4230/LIPIcs.ICALP.2020.82⟩
ISSN: 1942-3462
1942-3454
DOI: 10.1145/3512751
Popis: Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with $d+1$ processors arranged on a path of length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path consists of O$( \log n)$ qubits for $n$-bit inputs. We prove an unconditional lower bound of $\widetilde{\Omega}\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$ rounds for Set Disjointness on a Line with $d + 1$ processors. The result gives us a new lower bound of $\widetilde{\Omega} \big( \sqrt[3]{n\delta^2}+\sqrt{n} \, \big)$ on the number of rounds required for computing the diameter $\delta$ of any $n$-node network with quantum messages of size O$(\log n)$ in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
Comment: 24 pages, 2 figures. In v3, background on Theorem 3.5 (from prior work) was included in an appendix. In v4, a detail in the statement of Theorem 3.5 has been corrected, and corresponding changes have been made in the rest of the paper. The results remain unchanged. In v5, extended main theorems to the entanglement-assisted setting, added explanations and clarifications, corrected typos
Databáze: OpenAIRE
Externí odkaz: