Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms

Round 1

Reviewer 1 Report

In this manuscript, the authors propose an algorithm for producing an approximately optimal Steiner Tree, and another for producing an exact directed min. spanning tree. Even though no advantage can be enabled in the non-clique version, they show the speedup in the Congest-Clique model. They carefully present the points for further improvement to make the proposed algorithms more practical.

Although it is a relatively long article and looks difficult to digest at first glance, it goes so smoothly and is easy to understand. It is prepared so well in a systematic way. Moreover, the active links are very useful for navigating through the manuscript. I didn’t feel the necessity of illustrations, but it might be useful to add some considering a broad audience. Other than that, I  have no comments for further improvement. Despite short time to review it, I enjoyed reading it.

Author Response

"Although it is a relatively long article and looks difficult to digest at first glance, it goes so smoothly and is easy to understand. It is prepared so well in a systematic way. Moreover, the active links are very useful for navigating through the manuscript. I didn’t feel the necessity of illustrations, but it might be useful to add some considering a broad audience. Other than that, I have no comments for further improvement. Despite short time to review it, I enjoyed reading it. "

• We thank reviewer 1 for their time and the positive feedback on the manuscript. We will forego adding illustrations to not make the manuscript longer, since they are not deemed necessary by the reviewer, and make no changes in response to reviewer 1's comments.
  

Reviewer 2 Report

This manuscript presents two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation, achieving lower asymptotic round and message complexity compared to known classical algorithms in the CONGEST-CLIQUE model. The authors combine classical algorithmic frameworks with quantum subroutines to achieve these results, focusing on producing an approximately optimal Steiner Tree and an exact Directed Minimum Spanning Tree. They highlight the potential of quantum communication in the CONGEST-CLIQUE setting and discuss potential generalizations and open questions for further research. The authors also emphasize the need for practical improvements in terms of constants and logarithmic factors to make these algorithms more feasible. Overall, this work provides valuable insights into leveraging quantum communication in distributed computation and identifies areas for future exploration. Hence, I recommend it for publication in Algorithms.

Author Response

We thank reviewer 2 for their time and for the positive feedback. In light of the purely positive comments and lack of things to improve in the paper, we make no changes in response to reviewer 2's comments.