Mind the : Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms
Open Access
- 11 July 2023
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 16 (7) , 332
Abstract
We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses rounds of communication and messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by notation, revealing that advances are needed to render both the quantum and classical algorithms practical.
Keywords
Funding Information
- NASA Ames Research Center (IAA 8839, Annex 130, NNA16BD14C)
- NASA SCaN program (IAA 8839, Annex 130, NNA16BD14C)
- DARPA (IAA 8839, Annex 130, NNA16BD14C)
- NASA Academic Mission Services (IAA 8839, Annex 130, NNA16BD14C)
This publication has 23 references indexed in Scilit:
- Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks2018
- Towards a Complexity Theory for the Congested Clique2018
- Algebraic methods in the congested cliqueDistributed Computing, 2016
- Can quantum communication speed up distributed computation?2014
- Optimal deterministic routing and sorting on the congested clique2013
- Quantum Random Access MemoryPhysical Review Letters, 2008
- All pairs lightest shortest paths1999
- Computing ears and branchings in parallel1985
- A fast algorithm for Steiner treesActa Informatica, 1981
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967