Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees
Authors:
- 17 September 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 01, 1249-1259
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 $\overline{O}(n^{1/4})$ rounds of communication and $\tilde{O}(n^{9/4})$ 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 $\overline{O}$ notation, revealing that advances are needed to render both the quantum and classical algorithms practical.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Mind the : Asymptotically Better, but Still Impractical, Quantum Distributed AlgorithmsAlgorithms, 2023
- A Framework for Distributed Quantum Queries in the CONGEST Model2022
- A distributed algorithm for directed minimum-weight spanning treeDistributed Computing, 2021
- Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model2019
- Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks2018
- Algebraic methods in the congested cliqueDistributed Computing, 2016
- Optimal deterministic routing and sorting on the congested clique2013
- 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