Paper Info
Title
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.
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(log n) bits per round (here n denotes the number of nodes of the network), it is known that exact computation of the diameter requires Ω(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(log n) quantum bits per round. Our main result is a O(√D )-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 Ω(√ ) on the round complexity of any quantum algorithm computing the diameter, and furthermore show a tight lower bound Ω(√D ) for any distributed quantum algorithm in which each node can use only poly(log n) quantum bits of memory.
Year
DOI
Venue
2018
10.1145/3212734.3212744
PODC '18: ACM Symposium on Principles of Distributed Computing Egham United Kingdom July, 2018
Keywords
DocType
Volume
distributed algorithms, quantum computation, CONGEST model, graph algorithms
Conference
abs/1804.02917
ISBN
Citations 
PageRank 
978-1-4503-5795-1
0
0.34
References 
Authors
13
2
Name
Order
Citations
PageRank
François Le Gall140026.27
Frédéric Magniez257044.33