  The CONGEST and CONGEST-CLIQUE models have been carefully studied to
represent situations where the communication bandwidth between processors in a
network is severely limited. Messages of only $O(log(n))$ bits of information
each may be sent between processors in each round. The quantum versions of
these models allow the processors instead to communicate and compute with
quantum bits under the same bandwidth limitations. This leads to the following
natural research question: What problems can be solved more efficiently in
these quantum models than in the classical ones? Building on existing work, we
contribute to this question in two ways. Firstly, 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
$\tilde{O}(n^{1/4})$ rounds of communication and $\tilde{O}(n^{9/4})$ messages,
where $n$ is the number of nodes in the network. The algorithms thus achieve 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. An
existing framework for using distributed version of Grover's search algorithm
to accelerate triangle finding lies at the core of the asymptotic speedup.
Secondly, we carefully characterize the constants and logarithmic factors
involved in our algorithms as well as related algorithms, otherwise commonly
obscured by $\tilde{O}$ notation. The analysis shows that some improvements are
needed to render both our and existing related quantum and classical algorithms
practical, as their asymptotic speedups only help for very large values of $n$.
