Sublinear-time quantum computation of the diameter in CONGEST networks

DOI10.1145/3212734.3212744MaRDI QIDQ5197698zbMATH OpenOpenAlexWikidataFDO

Authors François Le Gall, Frédéric Magniez

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.02917

zbMATH Keywords

Congest modeldistributed algorithmsgraph algorithmsquantum computation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Quantum algorithms and complexity in the theory of computing (68Q12) Distributed algorithms (68W15)

Abstract: The computation of the diameter is one of the most central problems in distributed computation. In the standard CONGEST model, in which two adjacent nodes can exchange $O(logn)$ bits per round (here $n$ denotes the number of nodes of the network), it is known that exact computation of the diameter requires $ildeOmega(n)$ rounds, even in networks with constant diameter. In this paper we investigate quantum distributed algorithms for this problem in the quantum CONGEST model, where two adjacent nodes can exchange $O(logn)$ quantum bits per round. Our main result is a $ildeO(sqrtnD)$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model. We also show an unconditional lower bound $ildeOmega(sqrtn)$ on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound $ildeOmega(sqrtnD)$ for any distributed quantum algorithm in which each node can use only $extrmpoly(logn)$ quantum bits of memory.

Recommendations

• Quantum distributed complexity of set disjointness on a line
• Networks cannot compute their diameter in sublinear time
• Distributed algorithms for network diameter and girth
• Can quantum communication speed up distributed computation?
• A note on hardness of diameter approximation

Cited in

(11)

• Quantum advantage for the LOCAL model in distributed computing
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Quantum distributed complexity of set disjointness on a line
• Exact distributed quantum algorithm for generalized Simon's problem
• Quantum temporal logic and reachability problems of matrix semigroups
• Quantum distributed complexity of set disjointness on a line
• Distributed generalized Deutsch-Jozsa algorithm
• On the power of quantum distributed proofs
• Even-cycle detection in the randomized and quantum CONGEST model
• Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
• Distributed quantum proofs for replicated data

This page was built for publication: Sublinear-time quantum computation of the diameter in CONGEST networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197698)