Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model

DOI10.1145/3293611.3331628OpenAlexW2962811409WikidataQ130868652 ScholiaQ130868652MaRDI QIDQ5145184FDOQ5145184

Authors: Taisuke Izumi, François Le Gall 

Publication date: 20 January 2021

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

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

Recommendations

• Sublinear-time quantum computation of the diameter in CONGEST networks
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Can quantum communication speed up distributed computation?
• Exponentially Faster Shortest Paths in the Congested Clique
• Fast Approximate Shortest Paths in the Congested Clique

zbMATH Keywords

distributed algorithmsquantum algorithmsall-pairs shortest pathscongest-clique model

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (6)

• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• A dynamic programming approach for distributing quantum circuits by bipartite graphs
• Quantum temporal logic and reachability problems of matrix semigroups
• Title not available (Why is that?)
• Exact distributed quantum algorithm for generalized Simon's problem
• Quantum algorithm for shortest path search in directed acyclic graph

This page was built for publication: Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model

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