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

DOI10.1145/3293611.3331628MaRDI QIDQ5145184zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

distributed algorithmsquantum algorithmsall-pairs shortest pathscongest-clique model

Mathematics Subject Classification ID

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

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

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
• scientific article; zbMATH DE number 7496272 (Why is no real title available?)
• 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)