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

all-pairs shortest pathscongest-clique modeldistributed algorithmsquantum algorithms

Mathematics Subject Classification ID

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

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

(12)

• Quantum algorithm for shortest path search in directed acyclic graph
• A dynamic programming approach for distributing quantum circuits by bipartite graphs
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• scientific article; zbMATH DE number 7496272 (Why is no real title available?)
• Quantum advantage for the LOCAL model in distributed computing
• Exact distributed quantum algorithm for generalized Simon's problem
• Quantum temporal logic and reachability problems of matrix semigroups
• On the power of quantum distributed proofs
• Even-cycle detection in the randomized and quantum CONGEST model
• Distributed quantum proofs for replicated data
• Distributed subgraph finding: progress and challenges (invited talk)
• Constant-round spanners and shortest paths in congested clique and MPC

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)