Quantum advantage for the LOCAL model in distributed computing

DOI10.4230/LIPICS.STACS.2019.49MaRDI QIDQ5090500zbMATH OpenFDO

Authors François Le Gall, Harumichi Nishimura, Ansis Rosmanis

Publication date 18 July 2022

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

zbMATH Keywords

distributed computingLOCAL modelquantum computing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• What Can Be Observed Locally?
• Can quantum communication speed up distributed computation?
• Sublinear-time quantum computation of the diameter in CONGEST networks
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Quantum distributed complexity of set disjointness on a line

Cites work

• Can quantum communication speed up distributed computation?
• Distributed algorithms for network diameter and girth
• Distributed Computing: A Locality-Sensitive Approach
• Exact Quantum Algorithms for the Leader Election Problem
• Fast quantum byzantine agreement
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 2086394 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• Multiparty entanglement in graph states
• Networks cannot compute their diameter in sublinear time
• Optimal distributed all pairs shortest paths and applications
• Quantum advantage with shallow circuits
• Quantum communication and complexity.
• Quantum computation and quantum information. 10th anniversary edition
• Quantum search of spatial regions
• Sublinear-time quantum computation of the diameter in CONGEST networks
• What Can Be Observed Locally?

Cited in

(11)

• What Can Be Observed Locally?
• Average-case quantum advantage with shallow circuits
• scientific article; zbMATH DE number 7087308 (Why is no real title available?)
• Exact distributed quantum algorithm for generalized Simon's problem
• Contextuality and expressivity of non-locality
• Distributed generalized Deutsch-Jozsa algorithm
• 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)
• Shared randomness helps with local distributed problems

This page was built for publication: Quantum advantage for the LOCAL model in distributed computing

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