11affiliationtext: Department of Applied Mathematics and Statistics, Johns
Hopkins University22affiliationtext: Research Institute of Advanced Computer
Science, USRA33affiliationtext: Quantum Artificial Intelligence Laboratory,
NASA Ames Research Center44affiliationtext: Davidson School of Chemical
Engineering, Purdue University

# Mind the $\tilde{\mathcal{O}}$: asymptotically better, but still
impractical, quantum distributed algorithms

Phillip A. Kerger  David E. Bernal Neira  Zoe Gonzalez Izquierdo  Eleanor G.
Rieffel

###### Abstract

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 $\mathcal{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{\mathcal{O}}(n^{1/4})$ rounds of communication and
$\tilde{\mathcal{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 a
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$.

Keywords— Quantum Computing, Distributed Computing, Steiner Tree, Directed
Minimum Spanning Tree

##  1 Introduction

The classical CONGEST-CLIQUE Model (cCCM henceforth) in distributed computing
has been carefully studied as a model central to the field, e.g., (?, ?, ?, ?,
?, ?, ?). In this model, processors in a network solve a problem whose input
is distributed across the nodes under significant communication limitations,
described in detail in §2. For example, a network of aircraft or spacecraft,
satellites, and control stations, all with large distances between them, may
have severely limited communication bandwidth to be modeled in such a way. The
quantum version of this model, in which quantum bits can be sent between
processors, the quantum CONGEST-CLIQUE Model (qCCM), as well as the quantum
CONGEST model, have been the subject of recent research (?, ?, ?, ?, ?) in an
effort to understand how quantum communication may help in these distributed
computing frameworks. For the quantum CONGEST Model, however, (?, ?) showed
that many problems cannot be solved more quickly than in the classical model.
These include shortest paths, minimum spanning trees, Steiner trees, min-cut,
and more; the computational advantages of quantum communication are thus
severely limited in the CONGEST setting, though a notable positive result is
sub-linear diameter computation in (?, ?). No comparable negative results
exist for the qCCM, and in fact, (?, ?) provides an asymptotic quantum speedup
for computing all-pairs shortest path (APSP henceforth) distances. Hence, it
is apparent that the negative results of (?, ?) cannot transfer over to the
qCCM, so investigating these problems in the qCCM presents an opportunity for
contribution to the understanding of how quantum communication may help in
these distributed computing frameworks. In this paper, we contribute to this
understanding by formulating algorithms in the qCCM for finding approximately
optimal Steiner trees and exact directed minimum spanning trees using
$\tilde{\mathcal{O}}(n^{1/4})$ rounds – asymptotically fewer rounds than any
known classical algorithms. This is done by augmenting the APSP algorithm of
(?, ?) with an efficient routing table scheme, which is necessary to make use
of the shortest paths information instead of only the APSP distances, and
using the resulting subroutine with existing classical algorithmic frameworks.
Beyond asymptotics, we also characterize the complexity of our algorithms as
well as those of (?, ?, ?, ?, ?) to include the logarithmic and constant
factors involved to estimate the scales at which they would be practical,
which was not included in the previous work. It should be noted that, like
APSP, these problems cannot see quantum speedups in the CONGEST (non-clique)
setting as shown in (?, ?). Our Steiner tree algorithm is approximate and
based on a classical polynomial-time centralized algorithm of (?, ?). Our
directed minimum spanning tree problem algorithm follows an approach similar
to (?, ?), which effectively has its centralized roots in (?, ?).

##  2 Background and Setting

This section provides the necessary background for our algorithms’ settings
and the problems they solve.

###  2.1 The CONGEST and CONGEST-CLIQUE Models of Distributed Computing

In the standard CONGEST model, we consider a graph of $n$ processor nodes
whose edges represent communication channels. Initially, each node knows only
its neighbors in the graph and associated edge weights. In rounds, each
processor node executes computation locally and then communicates with its
neighbors before executing further local computation. The congestion
limitation restricts this communication, with each node able to send only one
message of $\mathcal{O}(\log(n))$ classical bits in each round to its
neighbors, though the messages to each neighbor may differ. Since there are
$n$ nodes, assigning them ID labels $1,...,n$ means the binary encoding size
of a label is $\lceil\log(n)\rceil$ bits – i.e., each message in CONGEST of
$O(\log n)$ bits can contain roughly the amount of information to represent
one node ID. In the cCCM, we separate the communication graph from the problem
input graph by allowing all nodes to communicate with each other, though the
same $\mathcal{O}(\log(n))$ bits-per-message congestion limitation remains.
Hence, a processor node could send $n-1$ different messages to the other $n-1$
nodes in the graph, with a single node distributing up to
$\mathcal{O}(n\cdot\log(n))$ bits of information in a single round. Taking
advantage of this way of dispersing information to the network is paramount in
many efficient CONGEST-CLIQUE algorithms. The efficiency of algorithms in
these distributed models is commonly measured in terms of the round
complexity, the number of rounds of communication used in an algorithm to
solve the problem in question. A good overview of these distributed models can
be found in (?, ?).

###  2.2 Quantum Versions of CONGEST and CONGEST-CLIQUE

The quantum models we work in are obtained via the following modification:
Instead of restricting to messages of $\mathcal{O}(\log(n))$ classical bits,
we allow messages to consist of $\mathcal{O}(\log(n))$ quantum bits, qubits.
For background on qubits and the fundamentals of quantum computing, we refer
the reader to (?, ?). We formally define the qCCM, the setting for our
algorithms, as follows:

######  Definition 2.1 (Quantum CONGEST-CLIQUE).

The Quantum CONGEST-CLIQUE Model (qCCM) is a distributed computation model in
which an input graph $G=(V,E,W)$ is distributed over a network of $n$
processors, where each processor is represented by a node in $V$. Each node is
assigned a unique ID number in $[n]$. Time passes in rounds, each of which
consists of the following:

  1. 1.

Each node may execute unlimited local computation.

  2. 2.

Each node may send a message consisting of either a register of
$\mathcal{O}(\log n)$ qubits or a string of $\mathcal{O}(\log n)$ classical
bits to each other node in the network. Each of those messages may be
distinct.

  3. 3.

Each node receives and saves the messages the other nodes send it.

The input graph $G$ is distributed across the nodes as follows: Each node
knows its own ID number, the ID numbers of its neighbors in $G$, the number of
nodes $n$ in $G$, and the weights corresponding to the edges it is incident
upon. The output solution to a problem must be given by having each node $v\in
V$ return the restriction of the global output to
$\mathcal{N}_{G}(u):=\\{v:uv\in E\\}$, its neighborhood in $G$. No
entanglement is shared across nodes initially.

This is an analog of the cCCM, except that quantum bits may be sent in place
of classical bits. To clarify the output requirement, in the Steiner tree
problem, we require node $u$ to output the edges of the solution tree that are
incident upon $u$. Since many messages in our algorithms need not be sent as
qubits, we define the qCCM slightly unconventionally, allowing either quantum
or classical bits to be sent. We specify those that may be sent classically.
However, even without this modification, the quantum versions of CONGEST and
cCCM are at least as powerful as their classical counterparts. This is because
any $n$-bit classical message can be instead sent as an $n$-qubit message of
unentangled qubits; for a classical bit reading $0$ or $1$, we can send a
qubit in the state $\ket{0}$ or $\ket{1}$ respectively, and then take
measurements with respect to the $\\{\ket{0},\ket{1}\\}$ basis to read the
same message the classical bits would have communicated. Hence, one can also
freely make use of existing classical algorithms in the qCCM. Further, the
assumption that IDs are in $[n]$, with $n$ known, is not necessary but is
convenient; without this assumption, we could have all nodes broadcast their
IDs to the entire network and then assign a new label in $[n]$ to each node
according to an ordering of the original IDs, resulting in our assumed
situation.

######  Remark 2.2.

Definition 2.1 does not account for how the information needs to be stored. In
this paper, it suffices for all information regarding the input graph to be
stored classically as long as there is quantum access to that data. We provide
some details on this in §8.4 of the appendix.

######  Remark 2.3.

No entanglement being shared across nodes initially in definition 2.1 results
in quantum teleportation not being a trivial way to solve problems in the
qCCM.

######  Example 2.4.

To provide some intuition on how allowing communication through qubits in this
distributed setting can be helpful, we now describe and give an example of
distributed Grover search, first described in (?, ?). The high-level intuition
for why quantum computing gives an advantage for search is that quantum
operations use quantum interference effects to have canceling effects among
non-solutions. Grover search has a generalization called “amplitude
amplification” we will use; see (?, ?) for details on these algorithms. Now,
for a processor node $u$ in the network and a Boolean function
$g:X\rightarrow\\{0,1\\}$, suppose there exists a classical procedure
$\mathcal{C}$ in the cCCM that allows $u$ to compute $g(x)$, for any $x\in X$
in $r$ rounds. The quantum speedup will come from computing $\mathcal{C}$ in a
quantum superposition, which enables $g$ to be evaluated with inputs in
superposition so that amplitude amplification can be used for inputs to $g$.
Let $A_{i}:\\{x\in X:g(x)=i\\}$, for $i=0,1$, and suppose that
$0<|A_{1}|\leq|X|/2$. Then classically, node $u$ can find an $x\in A_{1}$ in
$\Theta(r|X|)$ rounds by checking each element of $X$. Using the quantum
distributed Grover search of (?, ?) enables $u$ to find such an $x$ with high
probability in only $\tilde{\mathcal{O}}(r\sqrt{|X|})$ rounds by evaluating
the result of computing $g$ on a superposition of inputs.

We illustrate this procedure in an example case where a node $u$ wants to
inquire whether one of its edges $uv$ is part of a triangle in $G$. We first
describe a classical procedure for this, followed by the corresponding
quantum-distributed search version. For $v\in\mathcal{N}_{G}(u)$, denote by
$\mathcal{I}_{v}:V\rightarrow\\{0,1\\}$ the indicator function of
$\mathcal{N}_{G}(v)$, and by $g_{uv}:\mathcal{N}_{G}(u)\rightarrow\\{0,1\\}$
its restriction to inputs in $\mathcal{N}_{G}(u)$. Classically, node $u$ can
evaluate $g_{uv}(w)$ in two rounds for any $w\in\mathcal{N}_{G}(u)$ by sending
the ID of $w$ (of length $\log n$) to $v$, and having $v$ send back the answer
$\mathcal{I}_{v}(w)$. Then $u$ can check $g_{uv}(w)$ for each
$w\in\mathcal{N}_{G}(u)$ one at a time to determine whether $uv$ is part of a
triangle in $G$ or not in $2\cdot|\mathcal{N}_{G}(u)|$ rounds.

For the distributed quantum implementation, $u$ can instead initialize a
register of $\log n$ qubits as
$|\psi\rangle_{0}:=\frac{1}{\sqrt{|\mathcal{N}_{G}(u)|}}\sum_{x\in\mathcal{N}_{G}(u)}|x\rangle$,
all the inputs for $g_{uv}$ in equal superposition. To do a Grover search, $u$
needs to be able to evaluate $g_{uv}$ with inputs $|\psi\rangle$ in
superposition. For the quantum implementation of $\mathcal{C}$, $u$ sends a
quantum register in state $|\psi\rangle|0\rangle$ to node $v$, and has node
$v$ evaluate a quantum implementation of $\mathcal{I}_{v}$, which we will
consider as a call to an oracle mapping $|x\rangle|0\rangle$ to
$|x\rangle|\mathcal{I}_{v}(x)\rangle$ for all $x\in V$. Node $v$ sends back
the resulting qubit register, and node $u$ has evaluated
$g_{uv}(|\psi\rangle)$ in 2 rounds. Now, since $u$ can evaluate $g_{uv}$ in
superposition, node $u$ may proceed using standard amplitude amplification,
using 2 rounds of communication for each evaluation of $g_{uv}$, so that $u$
can find an element $w\in\mathcal{N}_{G}(u)$ satisfying $g_{uv}(w)=1$ with
high probability in $\tilde{\mathcal{O}}(r\sqrt{|\mathcal{N}_{G}(u)|})$ rounds
if one exists. We note that in this example, $v$ cannot execute this procedure
by itself since it does not know $\mathcal{N}_{G}(u)$ (and sending this
information to $v$ would take $|\mathcal{N}_{G}(u)|$ rounds), though it is
able to evaluate $\mathcal{I}_{v}$ in superposition for any
$w\in\mathcal{N}_{G}(u)$. For any classical procedure $\mathcal{C}$ evaluating
a different function from this specific $g$ (that can be implemented
efficiently classically and, therefore, translated to an efficient quantum
implementation), the same idea results in the square-root advantage to find a
desired element such that $g$ evaluates to $1$.

###  2.3 Notation and Problem Definitions

For an integer-weighted graph $G=(V,E,W)$, we will denote $n:=|V|,m:=|E|,$ and
$W_{e}$ the weight of an edge $e\in E$ throughout the paper. Let
$\delta(v)\subset V$ be the set of edges incident on node $v$, and
$\mathcal{N}_{G}(u):=\\{v:uv\in E\\}$ the neighborhood of $u\in G$. Denote by
$d_{G}(u,v)$ the shortest-path distance in $G$ from $u$ to $v$. For a graph
$G=(V,E,W)$ two sets of nodes $U$ and $U^{\prime}$, let
$\mathcal{P}_{G}(U,U^{\prime}):=\\{uv\in E:u\in U,w\in U^{\prime}\\}$ be the
set of edges connecting $U$ to $U^{\prime}$. Let
$\mathcal{P}(U):=\mathcal{P}(U,U)$ as shorthand. All logarithms will be taken
with respect to base 2, unless otherwise stated.

######  Definition 2.5 (Steiner Tree Problem).

Given a weighted, undirected graph $G=(V,E,W)$, and a set of nodes
$\mathcal{Z}\subset V$, referred to as Steiner Terminals, output the minimum
weight tree in $G$ that contains $\mathcal{Z}$.

######  Definition 2.6 (Approximate Steiner Tree).

For a Steiner Tree Problem with terminals $\mathcal{Z}$ and solution
$\mathcal{S}_{OPT}$ with edge set $E_{\mathcal{S}_{OPT}}$, a tree $T$ in $G$
containing $\mathcal{Z}$ with edge set $E_{T}$ such that

$\sum_{uv\in E_{T}}W_{uv}\leq r\cdot\sum_{uv\in E_{\mathcal{S}_{OPT}}}W_{uv}$

is called an approximate Steiner Tree with approximation factor $r$.

######  Definition 2.7 (Directed Minimum Spanning Tree Problem (DMST)).

Given a directed, weighted graph $G=(V,E,W)$ and a root node $r\in V$, output
the minimum weight directed tree $T^{*}$ in $G$ such that there exists a
directed path in $T^{*}$ from $r$ to any other node of $G$. This is also known
as the minimum weight arborescence problem.

##  3 Contributions

We provide an algorithm for the qCCM that produces an approximate Steiner Tree
with high probability (w.h.p.) in $\tilde{\mathcal{O}}(n^{1/4})$ rounds and an
algorithm that produces an exact Directed Minimum Spanning Tree w.h.p. in
$\tilde{\mathcal{O}}(n^{1/4})$ rounds. To do this, we enhance the quantum APSP
algorithm of (?, ?) in an efficient way to compute not only APSP distances but
also the corresponding routing tables (described in §4) that our algorithms
rely on. Further, in addition to these $\tilde{\mathcal{O}}$ results, in
sections 4.7, 5.4, and 6.3, we characterize the constants and logarithmic
factors involved in our algorithms as well as related classical algorithms to
contribute to the community’s understanding of their implementability. This
reveals that the factors commonly obscured by $\tilde{\mathcal{O}}$ notation
in related literature, especially the logarithms, have a severe impact on
practicality.

We summarize the algorithmic results in the following two theorems:

######  Theorem 3.1.

There exists an algorithm in the Quantum CONGEST-CLIQUE model that, given an
integer-weighted input graph $G=(V,E,W)$, outputs a $2(1-1/l)$ approximate
Steiner Tree with probability of at least $1-\frac{1}{poly(n)}$, and uses
$\tilde{\mathcal{O}}(n^{1/4})$ rounds of computation, where $l$ denotes the
number of terminal leaf nodes in the optimal Steiner Tree.

######  Theorem 3.2.

There exists an algorithm in the Quantum CONGEST-CLIQUE model that, given a
directed and integer-weighted input graph $G=(V,E,W)$, produces an exact
Directed Minimum Spanning Tree with high probability, of at least
$1-\frac{1}{poly(n)}$, and uses $\tilde{\mathcal{O}}(n^{1/4})$ rounds of
computation.

##  4 APSP and Routing Tables

We first describe an algorithm for the APSP problem with routing tables in the
qCCM, for which we combine an algorithm of (?, ?) with a routing table
computation from (?, ?). For this, we reduce APSP with routing tables to
triangle finding via distance products as in (?, ?).

###  4.1 Distance Products and Routing Tables

######  Definition 4.1.

A routing table for a node $v$ is a function $R_{v}:V\to V$ mapping a vertex
$u$ to the first node visited in the shortest path going from $v$ to $u$ other
than $v$ itself.

######  Definition 4.2.

The distance product between two $n\crossproduct n$ matrices $A$ and $B$ is
defined as the $n\crossproduct n$ matrix $A\star B$ with entries:

$\displaystyle(A\star B)_{ij}=\min_{k}\\{A_{ik}+B_{kj}\\}.$ (4.1)

The distance product is also sometimes called the min-plus or tropical
product. For shortest paths, we will repeatedly square the graph adjacency
matrix with respect to the distance product. For an $n\crossproduct n$ matrix
$W$ and an integer $k$, let us denote $W^{k,\star}:=W\star(W\star(\dots(W\star
W))\dots)$ as the $k^{th}$ power of the distance product. For a graph
$G=(V,E,W)$ with weighted adjacency matrix $W$ (assigning $W_{uv}=\infty$ if
$uv\notin E$), $W^{k,\star}_{uv}$ is the length of the shortest path from $v$
to $u$ in $G$ using at most $k$ hops. Hence, for any $N\geq n$, $W^{N,\star}$
contains all the shortest path distances between nodes in $G$. As these
distance products obey standard exponent rules, we may take $N=2^{\lceil\log
n\rceil}$ to recursively compute the APSP distances via taking $\lceil\log
n\rceil$ distance product squares:

$\displaystyle W^{2,\star}=W\star
W,\phantom{x}W^{4,\star}=\left(W^{2,\star}\right)^{2,\star},\dots,\phantom{x}W^{2^{\lceil\log
n\rceil},\star}=\left(W^{2^{\lceil\log n\rceil-1},\star}\right)^{2,\star}.$
(4.2)

This procedure reduces computing APSP distances to computing $\lceil\log
n\rceil$ distance products. In the context of the CONGEST-CLIQUE model, each
node needs to learn the row of $W^{n}$ that represents it. As we also require
nodes to learn their routing tables, we provide a scheme in §4.3 that is well-
suited for our setting to extend (?, ?) to also compute routing tables.

###  4.2 Distance Products via Triangle Finding

Having established reductions to distance products, we turn to their efficient
computation. The main idea is that we can reduce distance products to a binary
search in which each step in the search finds negative triangles. This
procedure corresponds to (?, ?, Proposition 2), which we describe here,
restricting to finding the distance product square needed for Eq. (4.2).

A negative triangle in a weighted graph is a set of edges
$\Delta^{-}=(uv,vw,wu)\subset E^{3}$ such that $\sum_{e\in\Delta^{-}}W_{e}<0$.
Let us denote the set of all negative triangles in a graph $G$ as
$\Delta^{-}_{G}$. Specifically, we will be interested in each node $v$ being
able to output edges $vu\in\delta(v)$ such that $vu$ is involved in at least
one negative triangle in $G$. Let us call this problem 4.2, and define it
formally as:

FindEdges Input: An integer-weighted (directed or undirected) graph
$G=(V,E,W)$ distributed among the nodes, with each node $v$ knowing
$\mathcal{N}_{G}(v)$, as well as the weights $W_{vu}$ for each
$u\in\mathcal{N}_{G}(v)$. Output: For each node $v$, its output is all the
edges $vu\in E$ that are involved in at least one negative triangle in $G$.

######  Proposition 4.3.

If 4.2 on an $n$-node integer-weighted graph $G=(V,E,W)$ can be solved in
$T(n)$ rounds, then the distance product $A\star B$ of two $n\crossproduct n$
matrices $A$ and $B$ with entries in $[M]$ can be computed in
$T(3n)\cdot\lceil\log_{2}(2M)\rceil$ rounds.

###### Proof.

Let $A$ and $B$ be arbitrary $n\crossproduct n$ integer-valued matrices, and
$D$ be an $n\crossproduct n$ matrix initialized to $\textstyle\bf 0$. Let each
$u\in V$ simulate three copies of itself,$u_{1},u_{2},u_{3}$, writing
$V_{1},V_{2},V_{3}$ as the sets of copies of nodes in $V$. Consider the graph
$G^{\prime}=(V_{1}\cup V_{2}\cup V_{3},E^{\prime},W^{\prime})$, by letting
$u_{i}v_{j}\in E^{\prime}$ for $u_{i}\in V_{i},v_{j}\in V_{j},i\neq j$, taking
$W_{u_{1}v_{2}}^{\prime}=A_{uv}$ for $u_{1}\in V_{1},v_{2}\in V_{2}$,
$W_{u_{2}v_{3}}^{\prime}=B_{uv}$ for $u_{2}\in V_{2},v_{3}\in V_{3}$, and
$W_{u_{3}v_{1}}^{\prime}=D_{uv}$ for $u_{3}\in V_{3},v_{1}\in V_{1}$. An edge
$zv$ is part of a negative triangle in $G^{\prime}$ exactly whenever

$\min_{u\in V}\\{A_{vu}+B_{uz}\\}<-D_{zv}.$

Assuming we can compute 4.2 for a $k$-node graph in $T(n)$ rounds, with a non-
positive matrix $D=\mathbf{0}$ initialized we can apply simultaneous binary
searches on $D_{zv}$, with values between $\\{-2M,0\\}$, updating it for each
node $v$ after each run of 4.2 to find $\min_{u\in V}\\{A_{vu}+B_{uz}\\}$ for
every other node $z$ in
$T(3n)\cdot\lceil\log(\max_{v,z\in V}\\{\min_{u\in
V}\\{A_{vu}+B_{uz}\\}\\})\rceil$ rounds, since $G^{\prime}$ is a tripartite
graph with $3n$ nodes. ∎

######  Remark 4.4.

This procedure can be realized in a single $n$-node distributed graph by
letting each node represent the three copies of itself since $G^{\prime}$ is
tripartite. The $T(3n)$ stems from each processor node possibly needing to
send one message for each node it is simulating in each round of 4.2. If
bandwidth per message is large enough (3 times the bandwidth needed for
solving 4.2 in $T(n)$ rounds), then this can be done in $T(n)$ rounds.

So for this binary search, each node $v$ initializes and locally stores
$D_{vz}=0$ for each other $z\in V$, after which we solve 4.2 on $G^{\prime}$.
The node then updates each $D_{vz}$ according to whether or not the edge
copies of $vz$ were part of a negative triangle in $G^{\prime}$, after which
4.2 is computed with the updated values for $D$. This is repeated until all
the $\min_{u\in V}\\{A_{vu}+B_{uz}\\}$ have been determined.

###  4.3 Routing Tables via Efficient Computation of Witness Matrices

For the routing table entries, we also need each node $v$ to know the
intermediate node $u$ that is being used to attain $\min_{u\in
V}\\{W_{vu}+W_{uz}\\}$.

######  Definition 4.5.

For a distance product $A\star B$ of two $n\times n$ matrices $A,B$, a witness
matrix $C$ is an $n\times n$ matrix such that

$\displaystyle C_{ij}\in argmin_{k\in[n]}\\{A_{ik}+B_{kj}\\}$

Put simply, a witness matrix contains the intermediate entries used to attain
the values in the resulting distance product. We present here a simple way of
computing witness matrices along with the distance product by modifying the
matrix entries appropriately, first considered by (?, ?). The approach is
well-suited for our algorithm, as we only incur $\mathcal{O}(\log n)$
additional calls to 4.2 for a distance product computation with a witness
matrix.

For an $n\crossproduct n$ integer matrix $W$, obtain matrices $W^{\prime}$ and
$W^{\prime\prime}$ by taking $W^{\prime}_{ij}=nW_{ij}+j-1$ and
$W^{\prime\prime}_{ji}=nW_{ji}$. Set $K=W^{\prime}\star W^{\prime\prime}$.

######  Claim 1.

With $W,W^{\prime},W^{\prime\prime},$ and $K$ as defined immediately above,

  * (i)

$\left\lfloor{\dfrac{K}{n}}\right\rfloor=W^{2,\star}$

  * (ii)

$(K\mod n)+1$ is a witness matrix for $W^{2,\star}.$

The claim follows from routine calculations of the quantities involved and can
be found in the Appendix, §8.1.

Hence, we can obtain witness matrices by simply changing the entries of our
matrices by no more than a multiplicative factor of $n$ and an addition of
$n$. Since the complexity of our method depends on the magnitude of the
entries of $W$ logarithmically, we only need logarithmically many more calls
to 4.2 to obtain witness matrices along with the distance products, making
this simple method well-suited for our approach. More precisely, we can
compute $W^{2,\star}$ with a witness matrix using
$\left\lceil\log(2n\cdot\max_{i,j}\\{W^{2,\star}_{ij}<\infty\\})\right\rceil.$
calls to 4.2. We obtain the following corollary to proposition 4.3 to
characterize the exact number of rounds needed:

######  Corollary 4.6.

If 4.2 on an $n$-node integer-weighted graph $G=(V,E,W)$ can be solved in
$T(n)$ rounds, then the distance product square $W^{2,\star}$, along with a
witness matrix $H$, can be computed in
$T(3n)\cdot\lceil\log_{2}(n\cdot\max_{v,z\in V}\\{\min_{u\in
V}\\{W_{vu}+W_{uz}\\}\\}+n)\rceil$ rounds.

###### Proof.

This follows from claim 1 and proposition 4.3 upon observing that
$\max_{v,z\in V}\\{\min_{u\in
V}\\{W^{\prime}_{vu}+W^{\prime\prime}_{uz})\\}\\}\leq n\cdot\max_{v,z\in
V}\\{\min_{u\in V}\\{W_{vu}+W_{uz}\\}\\}+n$. ∎

Once we obtain witness matrices along with the distance product computations,
constructing the routing tables for each node along the way of computing APSP
is straightforward. In each squaring of $W$ in Eq. (4.2), each node updates
its routing table entries according to the corresponding witness matrix entry
observed. It is worth noting that these routing table entries need only be
stored and accessed classically so that we avoid using unnecessary quantum
data storage.

###  4.4 Triangle Finding

Given the results from sections 4.3 and 4.2, we have reduced finding both the
routing tables and distance product to having each edge learn the edges
involved in a negative triangle in the graph. This section will thus describe
the procedure to solve the 4.2 subroutine. We state here a central result from
(?, ?):

######  Proposition 4.7.

There exists an algorithm in the quantum CONGEST-CLIQUE model that solves the
4.2 subroutine in $\tilde{\mathcal{O}}(n^{1/4})$ rounds.

We will proceed to describe each step of the algorithm to describe the precise
round complexity beyond the $\tilde{O}(n^{1/4})$ to characterize the constants
involved in the interest of assessing the future implementability of our
algorithms.

As a preliminary, we give a message routing lemma of (?, ?) for the congested
clique, which will be used repeatedly:

######  Lemma 4.8.

Suppose each node in $G$ is the source and destination for at most $n$
messages of size $\mathcal{O}(\log n)$ and that the sources and destinations
of each message are known in advance to all nodes. Then all messages can be
routed to their destinations in $2$ rounds.

We introduce the subproblem FindEdgesWithPromise (4.4 henceforth). Let
$\Gamma(u,v)$ denote the number of nodes $w\in V$ such that $(u,v,w)$ forms a
negative triangle in $G$.  FEWP Input: An integer-weighted graph $G=(V,E,W)$
distributed among the nodes and a set $S\subset\mathcal{P}(V)$, with each node
$v$ knowing $\mathcal{N}_{G}(v)$ and $S$. Promise: For each $uv\in
S,\Gamma(u,v)\leq 90\log n.$ Output: For each node $v$, its output is the
edges $vu\in S$ that satisfy $\Gamma(u,v)>0$.

We give here a description of the procedure of (?, ?) to solve 4.2 given an
algorithm $\mathcal{A}$ to solve 4.4. Let $\varepsilon_{\mathcal{A}}$ be the
failure probability of the algorithm $\mathcal{A}$ for an instance of 4.4.
FindEdgesViaFEWP 1: $S:=\mathcal{P};M:=\emptyset;i:=0$. 2: WHILE $60\cdot
2^{i}\log n\leq n$: a): Each node samples each of its edges with probability
$\sqrt{\frac{60\cdot 2^{i}\log n}{n}}$, so that we obtain a distributed
subgraph $G^{\prime}$ of $G$ consisting of the sampled edges b): Run
$\mathcal{A}$ on $(G^{\prime},S)$. Denote the output by $S^{\prime}$. c):
$S\leftarrow S\setminus S^{\prime};M\leftarrow M\cup S;i\leftarrow i+1.$ 3:
Run $\mathcal{A}$ on $(G,S)$, and call $S^{\prime\prime}$ the output. 4:
Output $M\cup S$. From step 2: of this above algorithm, it is straightforward
to check that this requires a maximum of
$c_{n}:=\lceil\log\text{(}\frac{n}{60\log n}\text{)}\rceil+1$ calls to the
$\mathcal{A}$ subroutine to solve 4.4. Further, it succeeds with probability
at least $1-c_{n}/n^{3}-c_{n}/n^{2}8-(c_{n}+1)\varepsilon_{\mathcal{A}}$. We
refer the reader to (?, ?, §3) for the proof of correctness. We now turn
toward constructing an efficient algorithm for FEWP.

To solve this subroutine, we must first introduce an additional labeling
scheme over the nodes that will determine how the search for negative
triangles will be split up to avoid communication congestion in the network.
Assume for simplicity that $n^{1/4},\sqrt{n},n^{3/4}$ are integers. Let
$\mathcal{M}=[n^{1/4}]\times[n^{1/4}]\times[\sqrt{n}]$. Clearly,
$|\mathcal{M}|=n$, and $\mathcal{M}$ admits a total ordering
lexicographically. Since we assume each node $v_{i}\in V$ is labeled with
unique integer ID $i\in[n]$, $v_{i}$ can select the element in $\mathcal{M}$
that has place $i$ in the lexicographic ordering of $\mathcal{M}$ without
communication occurring. Hence, each node $v\in V$ is associated with a unique
triple $(i,j,k)\in\mathcal{M}$. We will refer to the unique node associated
with $(i,j,k)\in\mathcal{M}$ as node $v_{(i,j,k)}$.
The next ingredient is a partitioning scheme of the space of possible
triangles. Let $\mathcal{U}$ be a partition of $V$ into $n^{1/4}$ subsets
containing $n^{3/4}$ nodes each, by taking $U_{i}:=\\{v_{j}:j\in\\{(i-1)\cdot
n^{3/4},\dots,i\cdot n^{3/4}\\}\\}$ for $i=1,\dots,n^{1/4}$, and
$\mathcal{U}:=\\{U_{1},\dots,U_{n^{1_{4}}}\\}$. Apply the same idea to create
a partition $\mathcal{U}^{\prime}$ of $\sqrt{n}$ sets of size $\sqrt{n}$, by
taking
$U_{i}^{\prime}:=\\{v_{j}:j\in\\{(i-1)\cdot\sqrt{n},\dots,i\cdot\sqrt{n}\\}\\}$
for $i=1,\dots,\sqrt{n}$, and $\mathcal{U}:=\\{U_{1},\dots,U_{\sqrt{n}}\\}$.
Let $\mathbb{V}=\mathcal{U}\times\mathcal{U}\times\mathcal{U}^{\prime}$. Each
node $v_{(i,j,k)}$ can then locally determine its association with the element
$(U_{i},U_{j},U_{k}^{\prime})\in\mathbb{V}$ since $|\mathbb{V}|=n$. Further,
if we use one round to have all nodes broadcast their IDs to all other nodes,
each node $v_{(i,j,k)}$ can locally compute the $(U_{i},U_{j},U_{k}^{\prime})$
it is assigned to, so this assignment can be done in one round.

We present here the algorithm 4.4 used to solve the FEWP subroutine.
ComputePairs Input: An integer-weighted graph $G=(V,E,W)$ distributed among
the nodes, a partition of $V\times V\times V$ of
$(U_{i},U_{j},U^{\prime}_{k})$ associated with each node as above, and a set
$S\subset\mathcal{P}(V)$ such that for $uv\in S,\Gamma(u,v)\leq 90\log n.$
Output: For each node $v$, its output is the edges $vu\in S$ that satisfy
$\Gamma(u,v)>0$. 1: Every node $v_{(i,j,k)}$ receives the weights $W_{uv}$,
$W_{vw}$ for all $uv\in\mathcal{P}(U_{i},U_{j})$ and
$vw\in\mathcal{P}(U_{j},U_{k}^{\prime})$. 2: Every node $v_{(i,j,k)}$
constructs the set $\Lambda_{k}(U_{i},U_{j})\subset\mathcal{P}(U_{i},U_{j})$
by selecting every $uv\in\mathcal{P}(U_{i},U_{j})$ with probability
$10\cdot\frac{\log n}{\sqrt{n}}$. If $|\\{v\in
U_{1}:uv\in\Lambda_{k}(U_{i},U_{j})\\}|>100n^{1/4}\log n$ for some $u\in
U_{j}$, abort the algorithm and report failure. Otherwise, $v_{(i,j,k)}$ keeps
all pairs $uv\in\Lambda_{k}(U_{i},U_{j})\cap S$ and receives the weights
$W{uv}$ for all of those pairs. Denote those elements of
$\Lambda_{k}(U_{i},U_{j})\cap S$ as
$u_{1}^{k}v_{1}^{k},\dots,u_{m}^{k}v_{m}^{k}$. 3: Every node $v_{(i,j,k)}$
checks for each $l\in[m]$ whether there is some $U\in\mathcal{U}^{\prime}$
that contains a node $w$ such that $(u^{k}_{l},v^{k}_{l},w)$ forms a negative
triangle, and outputs all pairs $u^{k}_{l}v^{k}_{l}$ for which a negative
triangle was found.

With probability at least $1-2/n$, the algorithm 4.4 does not terminate at
step 2: and every pair $(u,v)\in S$ appears in at least one
$\Lambda_{k}(U_{i},U_{j})$. The details for this result can be found in (?, ?,
Lemma 2).

Step 1: requires $2n^{1/4}\lceil\frac{\log W}{\log n}\rceil$ rounds and can be
implemented fully classically without any qubit communication. Step 2:
requires at most $200\log n\lceil\frac{\log W}{\log n}\rceil$ rounds and can
also be implemented classically. Step 3: can be implemented in
$\tilde{\mathcal{O}}(n^{1/4})$ rounds quantumly taking advantage of
distributed Grover search but would take $\mathcal{O}(\sqrt{n})$ steps to
implement classically. The remainder of this section is devoted to
illustrating how this step can be done in $\tilde{\mathcal{O}}(n^{1/4})$
rounds.

Define the following quantity:

######  Definition 4.9.

For node $v_{(i,j,k)}$, let

$\Delta(i,j,k):=\\{(u,v)\in\mathcal{P}(U_{i},U_{j})\cap S:\exists w\in
U_{k}^{\prime}\textit{ with }(u,v,w)\textit{ forming a negative triangle in
}G\\}$

For simultaneous quantum searches, we divide the nodes into different classes
based on the number of negative triangles they are a part of with the
following routine:

IdentifyClass Input: An integer-weighted graph $G=(V,E,W)$ distributed among
the nodes, and a set $S\subset E$ as in 4.4. Output: For each node $v$, a
class $\alpha$ the node belongs to. 1: Every node $u_{(i,j,k)}\in V$ samples
each node in $\\{v\in V:(u_{(i,j,k)},v)\in S\\}$ with probability
$\frac{10\log n}{n}$, creating a set $\Lambda(u)$ of sampled vertices. If
$\max_{u}|\Lambda(u)|>20\log n$, abort the algorithm and report a failure.
Otherwise, have each node broadcast $\Lambda(u)$ to all other nodes, and take
$R:=\cup_{u\in V}\\{uv|v\in\Lambda(u)\\}$. 2: Each $v_{(i,j,k)}\in V$ computes
$d_{i,j,k}:=|\\{uv\in\mathcal{P}(i,j)\cap R:\phantom{x}\exists w\in
U^{\prime}_{k}$ such that $\\{u,v,w\\}$ forms a negative triangle in $G\\}|$,
then determines its class $\alpha$ to be
$min\\{c\in{\mathbb{N}}:d_{i,j,k}<10\cdot 2^{c}\log n\\}$.

This uses at most $20\log n$ rounds (each node sends at most that many IDs to
every other node) and can be implemented by having all exchanged messages
consist only of classical bits. Using Chernoff’s bound, one can show that the
procedure succeeds with probability of at least $1-1/n$ as seen in (?, ?,
Proposition 5).

Let us make the convenient assumption that $\alpha=0$ for all $v_{i,j,k}$,
which avoids some technicalities around congestion in the forthcoming triangle
search. Note that $\alpha\leq\frac{1}{2}\log n$, so we can run successive
searches for each $\alpha$ for nodes in with class $\alpha$ in the general
case. The general case is discussed in §8.2 of the appendix and can also be
found in (?, ?), but this case is sufficient to convey the central ideas.

We have all the necessary ingredients to describe the implementation of step
3: of the 4.4 procedure.  3.1: Each node executes the 4.4 procedure. 3.2: For
each $\alpha$, for every $l\in[m]$, every node $v_{(i,j,k)}$ in class $\alpha$
executes a quantum search to find whether there is a
$U_{k}^{\prime}\in\mathcal{U}^{\prime}$ with some $w\in U_{k}^{\prime}$
forming a negative triangle $(u^{k}_{l},v^{k}_{l},w)$ in $G$, and then reports
all the pairs $u^{k}_{l}v^{k}_{l}$ for which such a $U_{k}^{\prime}$ was
found.

This provides the basis of the triangle-searching strategy. To summarize the
intuition of the asymptotic speedup in this paper: Since the $U^{\prime}_{k}$
have size $\sqrt{n}$ (recall that $|\mathcal{U}^{\prime}|=\sqrt{n}$), if each
node using a quantum search can search through its assigned $U^{\prime}_{k}$
in $\tilde{\mathcal{O}}(n^{1/4})$ rounds, simultaneously, we will obtain our
desired complexity. We will complete this argument in §4.6 and first describe
the quantum searches used therein in the following subsection.

###  4.5 Distributed Quantum Searches

With this intuition in mind, we now state two useful theorems of (?, ?) for
the distributed quantum searches. Let $X$ denote a finite set throughout this
subsection.

######  Theorem 4.10.

Let $g:X\rightarrow\\{0,1\\}$, if a node $u$ can compute $g(x)$ in $r$ rounds
in the CONGEST-CLIQUE model for any $x\in X$, then there exists an algorithm
in the Quantum CONGEST-CLIQUE that has $u$ output some $x\in X$ with $g(x)=1$
with high probability using $\tilde{\mathcal{O}}(r\sqrt{|X|})$ rounds.

This basic theorem concerns only single searches, but we need a framework that
can perform multiple simultaneous searches. Let
$g_{1},\dots,g_{m}:X\rightarrow\\{0,1\\}$ and

$A_{i}^{0}:=\\{x\in X:g_{i}(x)=0\\},A_{i}^{1}:=\\{x\in X:g_{i}(x)=1\\},\forall
i\in[m].$

Assume there exists an $r$-round classical distributed algorithm $C_{m}$ that
allows a node $u$ upon an input $\chi=(x_{1},\dots,x_{m})\in X^{m}$ to
determine and output $(g_{1}(x_{1}),\dots,g_{m}(x_{m}))$. In our use of
distributed searches, $X$ will consist of nodes in the network, and searches
will need to communicate with those nodes for which the functions $g_{i}$ are
evaluated. To avoid congestion, we will have to consider those $\chi\in X^{m}$
that have many repeated entries carefully. We introduce some notation for this
first. Define the quantity

$\alpha(\chi):=\max_{I\subset[m]}|\\{\chi_{i}=\chi_{j}\quad\forall i,j\in
I\\}|,$

the maximum number of entries in $\chi$ that are all identical.

Next, given some $\beta\in{\mathbb{N}}$, assume that in place of $C_{m}$ we
now have a classical algorithm $\tilde{C}_{m,\beta}$ such that upon input
$\chi=(x_{1},\dots,x_{m})\in X^{m}$, a node $u$ outputs
$g_{1}(x_{1}),\dots,g_{m}(x_{m})$ if $\alpha(\chi)\leq\beta$ and an arbitrary
output otherwise. The following theorem summarizes that such a
$\tilde{C}_{m,\beta}$ with sufficiently large $\beta$ is enough to maintain a
quantum speedup as seen in the previous theorem:

######  Theorem 4.11.

For a set $X$ with $|X|<m/(36\log m)$, suppose there exists such an evaluation
algorithm $C_{m,\beta}$ for some $\beta>8m/|X|$ and that
$\alpha(\chi)\leq\beta$ for all $\chi\in A_{1}^{1}\times\cdot\cdot\cdot\times
A_{m}^{1}$. Then there is a $\tilde{\mathcal{O}}(r\sqrt{|X|})$-round quantum
algorithm that outputs an element of $A_{1}^{1}\times\cdot\cdot\cdot\times
A_{m}^{1}$ with probability at least $1-2/m^{2}$.

The proof can be found in (?, ?, Theorem 3).

###  4.6 Final Steps of the Triangle Finding

We continue here to complete the step 3.2: of the 4.4 procedure, armed with
Theorem 4.11. We need simultaneous searches to be executed by each node
$v_{(i,j,k)}$ to determine the triangles in $U_{i}\times U_{j}\times
U^{\prime}_{k}$. We provide a short lemma first that ensures the conditions
for the quantum searches:

######  Lemma 4.12.

The following statements hold with probability at least $1-2/n^{2}$:

  * (i):

$|\Delta(i,j,k)|\leq 2n$

  * (ii):

$|\Lambda_{k}(U_{i},U_{j})\cap\Delta(i,j,k)|\leq 100\cdot\sqrt{n}\log n$ for
$i,j\in[n^{1/4}]$.

The proofs of these statements are technical but straightforward, making use
of Chernoff’s bound and union bounds; hence we skip them here. To invoke
Theorem 4.11, we describe a classical procedure first, beginning with an
evaluation step, 4.6 implementable in $\tilde{\mathcal{O}}(1)$ rounds.

EvaluationA
Input: Every node $v_{(i,j,k)}$ receives $m$ elements
$(u^{i,j,k}_{1},\dots,u^{i,j,k}_{m})$ of $\mathcal{U}^{\prime}$
Promise: For every node $v_{i,j,k}$ and every
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf
w$}}}\in\mathcal{U}^{\prime},|L_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}}^{i,j,k}|\leq 800\sqrt{n}\log
n$.
Output: Each node outputs a list of exactly those $u^{i,j,k}_{l}$ such that
there is a negative triangle in $U_{i}\times U_{j}\times u^{i,j,k}_{l}$. 1.
Every node $v_{(i,j,k)}$, for each $r\in\sqrt{n}$ routes the list
$L_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}}^{i,j,t}$ to node
$v_{(i,j,t)}$. 2. Every node $v_{(i,j,k)}$, for each $vu$ it received in step
1., sends the truth value of the inequality $\displaystyle\min_{w\in
U^{\prime}_{k}}\\{W_{uw}+W_{wv}\\}\leq W_{vu}$ (4.3) to the node that sent
$vu$.

Each node is the source and destination of up to $800n\log n$ messages in step
1, meaning that this step can be implemented in $1600\log n$ rounds. The same
goes for step 2, noting that the number of messages is the same, but they need
only be single-bit messages (the truth values of the inequalities). Hence, the
evaluations for Theorem 4.11 can be implemented in $3200\log n$ rounds. Now,
applying the theorem with $X=\mathcal{U}^{\prime},\beta=800\sqrt{n}\log n$,
noting that then the assumptions of the theorem hold with probability at least
$1-2/n^{2}$ due to Lemma 4.12, implies that step 3.2: is implementable in
$\tilde{\mathcal{O}}(n^{1/4})$ rounds, with a success probability of at least
$1-2/m^{2}$.

For the general case in which we do not assume $\alpha=0$ for all $i,j,k$ in
4.4, covered in the appendix, one needs to modify the 4.6 procedure in order
to implement load balancing and information duplication to avoid congestion in
the simultaneous searches. These details can be found in the appendix, where a
new labeling scheme and different evaluation procedure 8.2, are described for
this, or in (?, ?).

###  4.7 Complexity

As noted previously and in (?, ?), this APSP scheme uses
$\tilde{\mathcal{O}}(n^{1/4})$ rounds. Let us characterize the constants and
logarithmic factors involved to assess this algorithm’s practical utility.
Suppose that in each round, $2\cdot\log n$ qubits can be sent in each message
(so that we can send two IDs or one edge with each message), where $n$ is the
number of nodes. For simplicity, let’s assume that for the edge weights $W\ll
n$ and drop $W$.

  1. 1.

APSP with routing tables needs $\log(n)$ distance products with witness
matrices.

  2. 2.

Computing the $i^{th}$ distance product square for Eq. (4.2) with a witness
matrix needs up to $\log(2^{i})=i$ calls to 4.2, since the entries of the
matrix being squared may double each iteration. Then APSP and distance
products together make $\sum_{i=1}^{\lceil\log
n\rceil}i=\frac{\lceil\log(n)\rceil(\lceil\log(n)\rceil+1)}{2}$ calls to 4.2.

  3. 3.

Solving 4.2 needs $\log(\frac{n}{60\log n})$ calls to 4.4, using 4.4.

  4. 4.

Step 1: of 4.4 needs up to $2\cdot n^{1/4}$ rounds and step 2: takes up to
$200\log n$ rounds.

  5. 5.

Step 1: of 4.4 needs up to $20\log n$ rounds.

  6. 6.

In step 2: of 4.4, the $c_{uvw}$ are up to $\frac{1}{2}\log n$ large, and
hence $\alpha$ may range up to $\frac{1}{2}\log n$.

  7. 7.

Step 0. of the 8.2 procedure needs $n^{1/4}$ rounds. Steps 1. and 2. of the
8.2 (or 4.6, in the $\alpha=0$ case) procedure use a total of $3200\log n$
rounds.

  8. 8.

8.2 (or 4.6) procedure is called up to $\log(n)n^{1/4}$ times for each value
of $\alpha$ in step 3.2: of 4.4.

Without any improvements, we get the following complexity, using $3n$ in place
of $n$ for the terms of steps 3-8 due to corollary 4.6:

$\displaystyle\frac{\lceil\log(n)\rceil(\lceil\log(n)\rceil+1)}{2}\log(\frac{3n}{60\log
3n})\Big{(}2(3n)^{1/4}+220\log 3n+2(3n)^{1/4}+$ $\displaystyle\frac{1}{2}\log
3n\cdot\log 3n\cdot(3n)^{1/4}3200(\log 3n)\Big{)},$ (4.4)

which we will call $f(n)$, so that $f(n)=\mathcal{O}(n^{1/4}\log^{6}(n))$,
with the largest term being about $800\log^{6}(n)n^{1/4}$, and we have dropped
$W$ to just consider the case $W\ll n$. We can solve the problem trivially in
the (quantum or classical) CONGEST-CLIQUE within $n\log(W)$ rounds by having
each node broadcast its neighbors and the weight on the edge. Let us again
drop $W$ for the case $W\ll n$ so that in order for the quantum algorithm to
give a real speedup, we will need

$f(n)<n,$

which requires $n>10^{18}$ (even with the simpler under-approximation
$800\log^{6}(n)n^{1/4}$ in place of $f$). Hence, even with some potential
improvements, the algorithm is impractical for a large regime of values of $n$
even when compared to the trivial CONGEST-CLIQUE $n$-round strategy.
For the algorithm of (?, ?) computing only APSP distances, the first term in
4.4 becomes simply $\lceil\log n\rceil$, so that when computing only APSP
distances the advantage over the trivial strategy begins at roughly $n\approx
10^{16}$.

######  Remark 4.13.

In light of logarithmic factors commonly being obscured by
$\tilde{\mathcal{O}}$ notation, we point out that even an improved algorithm
needing only $\log^{4}(n)n^{1/4}$ would not be practical unless $n>10^{7}$,
for the same reasons. Recall that $n$ is the number of processors in the
distributed network – tens of millions would be needed to make this algorithm
worth implementing instead of the trivial strategy. Practitioners should mind
the $\tilde{\mathcal{O}}$ if applications are of interest, since even
relatively few logarithmic factors can severely limit practicality of
algorithms, and researchers should be encouraged to fully write out the exact
complexities of their algorithms for the same reason.

####  4.7.1 Memory Requirements

Although in definition 2.1 we make no assumption on the memory capacities of
each node, the trivial $n$-round strategy uses at least
$2\log(n)|E|^{2}\cdot\log(W)$ memory at the leader node that solves the
problem. For the APSP problem in question, using the Floyd-Warshall algorithm
results in memory requirements of $2n^{2}\log(n)\cdot\log(nW)$ at the leader
node. Hence, we may ask whether the quantum APSP algorithm leads to lower
memory requirements. The memory requirement is largely characterized by up to
$720n^{7/4}\log(n)\log(nW)$ needed in step 0. of the 8.2 procedure, which can
be found in the appendix. This results in a memory advantage for quantum APSP
over the trivial strategy beginning in the regime of $n>1.6\cdot 10^{10}$.

####  4.7.2 Complexity of the Classical Analogue

For completeness, we provide here a characterization of the complexity of a
closely related classical algorithm for APSP with routing tables in the
CONGEST-CLIQUE as proposed in (?, ?) that has complexity
$\tilde{\mathcal{O}}(n^{1/3})$. In their framework, the approach to finding
witness matrices requires $\mathcal{O}(\log(n)^{3})$ calls to the distance
product (?, ?, §3.4), and similarly to our approach $\log(n)$ distance
products are required. Their classical algorithm computes distance products in
$\mathcal{O}(n^{1/3})$ rounds, or under $2\log n$ message bandwidth in up to

$\displaystyle 20n^{1/3}\log(n)^{4}=:g(n)$ (4.5)

rounds, the details of which can be found in the appendix, §8.2.1. Then
$g(n)>n$ up until about $n\approx 2.6\cdot 10^{11}$. As with the quantum APSP,
though this algorithm gives the best known asymptotic complexity of
$\tilde{\mathcal{O}}(n^{1/3})$ in the classical CONGEST-CLIQUE, it also fails
to give any real improvement over the trivial strategy across a very large
regime of values of $n$. Consequently, algorithms making use of this APSP
algorithm, such as (?, ?) or (?, ?), suffer from the same problem of
impracticality. However, the algorithm only requires within
$4n^{4/3}\log(n)\log(nW)+n\log(n)\log(nW)$ memory per node, which is less than
required for the trivial strategy even for $n\geq 4$.

##  5 Approximately Optimal Steiner Tree Algorithm

###  5.1 Algorithm Overview

We present a high-level overview of the proposed algorithm to produce
approximately optimal Steiner Trees, divided into four steps.

Step 1 - APSP and Routing Tables:

Solve the APSP problem as in (?, ?) and add an efficient routing table scheme
via triangle finding in $\tilde{\mathcal{O}}(n^{1/4})$ rounds, with success
probability $(1-1/poly(n))$ (this step determines the algorithm’s overall
success probability).

Step 2 - Shortest-path Forest:

Construct a shortest-path forest (SPF), where each tree consists of exactly
one source terminal and the shortest paths to the vertices whose closest
terminal is that source terminal. This step can be completed in one round and
$n$ messages, per (?, ?, §3.1). The messages can be in classical bits.

Step 3 - Weight Modifications:

Modify the edge weights depending on whether they belong to a tree (set to 0),
connect nodes in the same tree (set to $\infty$), or connect nodes from
different trees (set to the shortest path distance between root terminals of
the trees that use the edge). This uses one round and $n$ messages.

Step 4 - Minimum Spanning Tree:

Construct a minimum spanning tree (MST) on the modified graph in
$\mathcal{O}(1)$ rounds as in (?, ?), and prune leaves of the MST that do not
connect terminal nodes since these are not needed for the Steiner Tree.

The correctness of the algorithm follows from the correctness of each step
together with the analysis of the classical results of (?, ?), which uses the
same algorithmic steps of constructing a shortest path forest and building it
into an approximately optimal Steiner Tree.

###  5.2 Shortest Path Forest

After the APSP distances and routing tables have been found, we construct a
Shortest Path Forest (SPF) based on the terminals of the Steiner Tree.

######  Definition 5.1.

(Shortest Path Forest): For a weighted, undirected graph $G=(V,E,W)$ together
with a given set of terminal nodes $Z=\\{z_{1},\dots,z_{k}\\}$, a subgraph
$F=(V,E_{F},W)$ of $G$ is called a shortest path forest if it consists of
$|Z|$ disjoint trees $T_{z}=(V_{z},E_{z},W)$ satisfying

  * i)

$z_{i}\in T_{z_{j}}$ if and only if $i=j$, for $i,j\in[k]$.

  * ii)

For each $v\in Z_{i},d_{G}(v,z_{i})=\min_{z\in Z}d_{G}(v,z)$, and a shortest
path connecting $v$ to $z_{i}$ in $G$ is contained in $T_{z_{i}}$

  * iii)

The $V_{z_{i}}$ form a partition of $V$, and $E_{z_{1}}\cup E_{z_{2}}\dots\cup
E_{z_{k}}=E_{F}\subset E$

In other words, an SPF is a forest obtained by gathering, for each node, a
shortest path in $G$ connecting it to the closest Steiner terminal node.

For a node $v$ in a tree, we will let $par(v)$ denote the parent node of $v$
in that tree, $s(v)$ the Steiner Terminal in the tree that $v$ will be in, and
$ID(v)\in[n]$ the ID of node $v\in V$. Let
$\mathcal{Q}(v):=\\{z:d_{G}(v,z)=\min_{z\in Z}d_{G}(v,z)\\}$ be the set of
Steiner Terminals closest to node $v$. We make use of the following procedure
for the SPF:  DistributedSPF Input: For each node $v\in G$, APSP distances and
the corresponding routing table $R_{v}$. Output: An SPF distributed among the
nodes. 1: Each node $v$ sets $s(v):=\text{argmin}_{z\in\mathcal{Q}(v)}ID(z)$
using the APSP information. 2: Each node $v$ sets $par(v):=R_{v}(s(v))$,
$R_{v}$ being the routing table of $v$, and sends a message to $par(v)$ to
indicate this choice. If $v$ receives such a message from another node $u$, it
registers $u$ as its child in the SPF. Step 1: in 5.2 requires no
communication since each node already knows the shortest path distances to all
other nodes, including the Steiner Terminals, meaning it can be executed
locally. Each node $v$ choosing $par(v)$ in step 2: can also be done locally
using routing table information, and thus step 2: requires $1$ round of
communication of $n-|Z|$ classical messages, since all non-Steiner nodes send
one message.

######  Claim 2.

After executing the 5.2 procedure, the trees
$T_{z_{k}}=(V_{z_{k}},E_{z_{k}},W)$ with $V_{z_{k}}:=\\{v\in V:s(v)=z_{k}\\}$
and $E_{z_{k}}:=\\{v,par(v)\\}:v\in V_{z_{k}}\\}$ form an SPF.

###### Proof.

i) holds since each Steiner Terminal is closest to itself. iii) is immediate.
To see that ii) holds, note that for $v\in V_{z_{k}}$, $par(v)\in V_{z_{k}}$
and $\\{v,par(v)\\}\in E_{z_{k}}$ as well. Then $par(par(\dots
par(v)\dots))=z_{k}$ and the entire path to $z_{k}$ lies in $T_{z_{k}}$. ∎

Hence, after this procedure, we have a distributed SPF across our graph, where
each node knows its label, parent, and children of the tree it is in.

###  5.3 Weight Modified MST and Pruning

Finally, we introduce a modification of the edge weights before constructing
an MST on that new graph that will be pruned into an approximate Steiner Tree.
These remaining steps stem from a centralized algorithm first proposed by (?,
?) whose steps can be implemented efficiently in the distributed setting, as
in (?, ?). We first modify the edge weights as follows:

Partition the edges $E$ into three sets – tree edges $E_{F}$ as in 5.1 that
are part of the edge set of the SPF, intra-tree edges $E_{IT}$ that are
incident on two nodes in the same tree $T_{i}$ of the SPF, and inter-tree
edges $E_{XT}$ that are incident on two nodes in different trees of the SPF.
Having each node know which of these its edges belong to can be done in one
round by having each node send its neighbors the ID of the terminal it chose
as the root of the tree in the SPF that is a part of. Then the edge weights
are modified as follows, denoting the modified weights as $W^{\prime}$:

  * (i):

For $e=(u,v)\in E_{T},W^{\prime}(u,v):=0$

  * (ii):

For $e=(u,v)\in E_{IT},W^{\prime}(u,v):=\infty$

  * (iii):

For $e=(u,v)\in E_{XT},W^{\prime}(u,v):=d(u,Z_{u})+W(u,v)+d(v,Z_{v})$,

noting that $d_{G}(u,s(u))$ is the shortest-path distance in $G$ from $u$ to
its closest Steiner Terminal.

Next, we find a minimum spanning tree on the graph
$G^{\prime}=(V,E,W^{\prime})$, for which we may implement the classical
$\mathcal{O}(1)$ round algorithm proposed by (?, ?). On a high level, this
constant-round complexity is achieved by sparsification techniques, reducing
MST instances to sparse ones, and then solving those efficiently. We skip the
details here and refer the interested reader to (?, ?). After this step, each
node knows which of its edges are part of this weight-modified MST, as well as
the parent-child relationships in the tree for those edges.

Finally, we prune this MST by removing non-terminal leaf nodes and the
corresponding edges. This is done by each node $v$ sending the ID of its
parent in the MST to every other node in the graph. As a result, each node can
locally compute the entire MST and then decide whether or not it connects two
Steiner Terminals. If it does, it decides it is part of the Steiner Tree;
otherwise, it broadcasts that it is to be pruned. Each node that has not been
pruned then registers the edges connecting it to non-pruned neighbors as part
of the Steiner Tree. This pruning step takes $2$ rounds and up to $n^{2}+n$
classical messages.

###  5.4 Overall Complexity and Correctness

In algorithm 5.1, after step Step 1 - APSP and Routing Tables:, steps Step 2 -
Shortest-path Forest:, and Step 3 - Weight Modifications: can each be done
within $2$ rounds. Walking through (?, ?) reveals that the MST for step Step 4
- Minimum Spanning Tree: can be found in $54$ rounds, with an additional $2$
rounds sufficing for the pruning. Hence, the overall complexity remains
dominated by Eq. (4.4). Hence, the round complexity is
$\tilde{\mathcal{O}}(n^{1/4})$, which is faster than any known classical
CONGEST-CLIQUE algorithm to produce an approximate Steiner tree of the same
approximation ratio. However, as a consequence of the full complexity obtained
in §4.7, the regime of $n$ in which this algorithm beats the trivial strategy
of sending all information to a single node is also $n>10^{18}$. For the same
reason, the classical algorithm provided in (?, ?) making use of the APSP
subroutine from (?, ?) discussed in §4.7.2 has its complexity mostly
characterized by Eq. (4.5), so that the regime in which it provides an
advantage over the trivial strategy lies in $n>10^{11}$. Our algorithm’s
correctness follows from the correctness of each step together with the
correctness of the algorithm by (?, ?) that implements these steps in a
classical, centralized manner.

##  6 Directed Minimum Spanning Tree Algorithm

This section will be concerned with establishing Theorem 3.2 for the Directed
Minimum Spanning Tree (DMST) problem, in definition 2.7. Like (?, ?), we
follow the algorithmic ideas first proposed by (?, ?), implementing them in
the quantum CONGEST-CLIQUE. Specifically, we will use $\log n$ calls to the
APSP and routing tables scheme described in §4, so that in our case, we
retrieve complexity $\tilde{\mathcal{O}}(n^{1/4})$ and success probability
$(1-\frac{1}{poly(n)})^{\log n}=1-\frac{1}{poly(n)}$.

Before describing the algorithm, we need to establish some preliminaries and
terminology for the procedures executed during the algorithm, especially the
ideas of shrinking vertices into super-vertices and tracking a set $H$ of
specific edges as first described in (?, ?). We use the following language to
discuss super-vertices and related objects.

######  Definition 6.1.

A super-vertex set $\mathbb{V}^{*}:=\\{V^{*}_{1},\dots,V^{*}_{t}\\}$ for a
graph $G=(V,E,W)$ is a partition of $V$, and each $V^{*}_{i}$ is called a
super-vertex. We will call a super-vertex simple if $V^{*}$ is a singleton.
The corresponding minor $G^{*}:=(\mathbb{V}^{*},E^{*},W^{*})$ is the graph
obtained by creating edges $(V^{*}_{i},V^{*}_{j})$ with weight
$W^{*}(V^{*}_{i},V^{*}_{j}):=\min\\{W(v_{i},v_{j}):v_{i}\in V^{*}_{i},v_{j}\in
V^{*}_{j}\\}$.

Notably, we continue to follow the convention of an edge of weight $\infty$
being equivalent to not having an edge. We will refer to creating a super-
vertex $V^{*}$ as contracting the vertices in $V^{*}$ into a super-vertex.

###  6.1 Edmonds’ Centralized DMST Algorithm

We provide a brief overview of the algorithm proposed in (?, ?), which
presents the core ideas of the super-vertex-based approach. The following
algorithm produces a DMST for $G$:  Edmonds DMST Algorithm Input: An integer-
weighted digraph and a root node $r$. Output: A DMST for $G$ rooted at $r$. 1.
Initialize a subgraph $H$ with the same vertex set as G by subtracting for
each node the minimum incoming edge weight from all its incoming edges, and
selecting exactly one incoming zero-weight edge for each non-root node of $G$.
Set $G_{0}=G,H_{0}=H,t=0$. 2. WHILE $H_{t}$ is not a tree: (a) For each cycle
of $H$, contract the nodes on that cycle into a super-vertex. Consider all
non-contracted nodes as simple super-vertices, and obtain a new graph
$G_{t+1}$ as the resulting minor. (b) If there is a non-root node of $G_{t+1}$
with no incoming edges, report a failure. Otherwise, obtain a subgraph
$H_{t+1}$ by, for each non-root node of $G_{t+1}$, subtracting the minimum
incoming edge weight from all its incoming edges, and selecting exactly one
incoming zero-weight edge for each non-root, updating $t\leftarrow t+1$. 3.
Let $B_{t}=H_{t}$. FOR $k\in(t,t-1,\dots,1)$: (a) Obtain $B_{k-1}^{\prime}$ by
expanding the non-simple super-vertices of $B_{k}$ and selecting all but one
of the edges for each of the previously contracted cycles of $H_{k}$ to add to
$B_{k-1}$. 4. Return $B_{0}$. Note that the edge weight modifications modify
the weight of all directed spanning trees equally, so optimality is
unaffected. In step 2., if $H_{t}$ is a tree, it is an optimal DMST for the
current graph $G_{t}$. Otherwise, it contains at least one directed cycle, so
that indeed step 2. is valid. Hence, at the beginning of step 3., $B_{t}$ is a
DMST for $G_{t}$. Then the first iteration produces $B_{t-1}$ a DMST for
$G_{t-1}$ since only edges of zero weight were added, and $B_{t-1}$ will have
no cycles. The same holds for $B_{t-2},B_{t-3},\dots,B_{0}$, for which $B_{0}$
corresponds to the DMST for the original graph $G$. If the algorithm reports a
failure at some point, no spanning tree rooted at $r$ exists for the graph,
since a failure is reported only when there is an isolated non-root connected
component in $G_{t+1}$.

Note that in iteration $t$ of step 2., $H$ has one cycle for each of its
connected components that does not contain the root node. Hence, the drawback
of this algorithm is that we may apply up to $\mathcal{O}(n)$ steps of
shrinking cycles. This shortcoming is remedied by a more efficient method of
selecting how to shrink nodes into super-vertices in (?, ?), such that only
$\log n$ shrinking cycle steps take place.

###  6.2 Lovasz’ Shrinking Iterations

We devote this subsection to discuss the shrinking step of (?, ?) that will be
repeated $\log n$ times in place of step 2. of Edmonds’ algorithm to obtain
Lovasz’ DMST algorithm.

Lovasz’ Shrinking Iteration LSI
Input: A directed, weighted graph $G=(V,E,W)$ and a root node $r\in V$.
Output: Either a new graph $G^{*}$, or a success flag and a DMST $H$ of $G$.
1. If there is a non-root node of $G$ with no incoming edges, report a
failure. Otherwise, for each non-root node of $G$, subtract the minimum
incoming edge weight from all its incoming edges. Select exactly one incoming
zero-weight edge for each non-root node to create a subgraph $H$ of $G$ with
those edges. 2 Find all cycles of $H$, and denote them $H_{1},\dots,H_{C}.$ If
$H$ has no cycles, abort the iteration and return (SUCCESS, H). For
$j=1,\dots,C$, find the set $V_{j}$ of nodes that dipaths in $H$ from $H_{j}$
can reach. 3. Compute the All-Pairs-Shortest-Path distances in $G$. 4. For
each node $v\in V$, denote $d_{j}(v):=\min\\{d(v,u):u\in H_{j}\\}$. For each
$j=1,\dots,C$, set $\beta_{j}:=\min\\{d_{j}(v):v\in
V(G)\setminus\mathbb{V}_{j}\\}$ and $U_{j}:=\\{u\in
V_{j}:d_{j}(u)\leq\beta_{j}\\}$. 5. Create a minor $G^{*}$ by contracting each
$U_{j}$ into a super-vertex $U_{j}^{*}$, considering all other vertices of $G$
as simple super-vertices $V^{*}_{1},\dots,V^{*}_{k}$. For each vertex $N^{*}$
of $G^{*}$, let the edge weights in $G^{*}$ be: $\displaystyle
W^{*}_{N^{*}U^{*}_{j}}$ $\displaystyle=\min\\{W_{vu}:v\in N^{*},u\in
U^{*}_{j}\\}-\beta_{j}+\min\\{d_{j}(u):u\in U^{*}_{j}\\}$
$\displaystyle\text{for all }j=1,\dots,C,\text{ and}$ $\displaystyle
W^{*}_{N^{*}V^{*}}$ $\displaystyle=\min\\{W_{vV^{*}}:v\in N^{*}\\}$
$\displaystyle\text{for all the simple super-vertices }V^{*}\text{ of }G^{*}.$
6. Return $G^{*}$.

To summarize these iterations: The minimum-weight incoming edge of each node
is selected. That weight is subtracted from the weights of every incoming edge
to that node, and one of those edges with new weight 0 is selected for each
node to create a subgraph $H$. If $H$ is a tree, we are done. Otherwise, we
find all cycles of the resulting directed subgraph, then compute APSP and
determine the $V_{j},U_{j},$ and $\beta_{j}$, which we use to define a new
graph with some nodes of the original $G$ contracted into super-vertices.

The main result for the DMST problem in (?, ?) is that replacing (a) and (b)
of step 2. in the 6.1, taking the new $H$ obtained at each iteration to be
$H_{t+1}$ and the $G^{*}$ to be $G_{t+1}$, leads to no more than $\lceil\log
n\rceil$ such shrinking iterations needed before a success is reported.

####  6.2.1 Quantum Distributed Implementation

Our goal is to implement the Lovasz iterations in the quantum distributed
setting in $\tilde{\mathcal{O}}(n^{1/4})$ rounds by making use of quantum APSP
of §4. In the distributed setting, processor nodes cannot directly be shrunk
into super-vertices. As in (?, ?), we reconcile this issue by representing the
super-vertex contractions within the nodes through soft contractions.

First, note that a convenient way to track what nodes we want to consider
merging into a super-vertex is to keep a mapping $sID:V\rightarrow S$, where
$S$ is a set of super-vertex IDs, which we can just take to be the IDs of the
original nodes. We will refer to a pair of $(G,sID)$ as an annotated graph. An
annotated graph naturally corresponds to some _minor_ of $G$, namely, the
minor obtained by contracting all vertices sharing a super-vertex ID into a
super-vertex.

######  Definition 6.2 (Soft Contractions).

For an annotated graph $(G,sID)$, a set of active edges $H$, and active
component $H_{i}$ with corresponding weight modifiers $\beta_{i}$, and a
subset $A\subset S$ of super-vertices, the soft contraction of $H_{i}$ in G is
the annotated graph $(G^{H_{i}},sID^{\prime})$ obtained by taking
$G^{H_{i}}=(V,E,W^{\prime})$ with

  * •

$W^{\prime}_{uv}=0$ if $sID(u)=sID(v)$

  * •

$W^{\prime}_{uv}=W_{uv}+dist_{G(A)}(v,C(H_{i}))-\beta_{i}$ if $u\in V\setminus
A$ and $v\in A$

  * •

$W^{\prime}_{uv}=W_{uv}$ otherwise

and updating the mapping $sID$ to $sID^{\prime}$ defined by
$sID^{\prime}(v)=sID(v),\forall v\notin A$,
$sID^{\prime}(v)=\min\\{sID(u):u\in A\\}$.

####  6.2.2 Quantum Distributed Lovasz’ Iteration

We provide here a quantum distributed implementation of Lovasz’ iteration that
we will form the core of our DMST algorithm.  Quantum Distributed Lovasz’
Iteration QDLSI
Input: A directed, weighted, graph $G=(V,E,W)$ with annotations $sID$ and a
subgraph $H$.
Output: A new graph $G^{*}$ with annotations $sID^{\prime}$, or a success flag
and a DMST $H$ of $G$. 1: Have all nodes learn all edges of $H$, as well as
the current super-vertices. 2: For each connected component $H_{i}\subset H$,
denote by $C(H_{i})$ the cycle of $H_{i}$. Let $c(H_{i})$ be the node with
maximal ID in $C(H_{i})$, which each node can locally compute. 3: Run the
quantum algorithm for APSP and routing tables described in §4 on this graph,
or report a failure if it fails. 4: For each $i$, determine an edge
$v_{i}u_{i}$, $v_{i}\notin H_{i},u_{i}\in H_{i}$ minimizing
$\beta_{i}:=W_{v_{i}u_{i}}+d_{G}(u_{i},c(H_{i}))$, and broadcast both to all
nodes in $H_{i}$. 5: Each node $v_{i}$ in each $H_{i}$ applies the following
updates $locally$: – Soft-contract $H_{i}$ at level $\beta_{i}$ to soft-
contract all super-vertices with distance $\beta_{i}$ to $C(H_{i})$ into one
super-vertex, with each contracted node updating its super-vertex ID to
$c(H_{i})$ – add edge $v_{i}u_{i}$ to $H$, effectively merging $H_{i}$ with
another active component of $H$

We can follow exactly the steps of Lovasz’s DMST algorithm, distributedly by
replacing steps 2:-5: of the 6.2 with this quantum-distributed version. The
following ensues:

######  Lemma 6.3.

If none of the APSP and routing table subroutines fail, within $\lceil\log
n\rceil$ iterations of the 6.2.2, $H$ is a single connected component.

######  Lemma 6.4.

With probability $(1-\frac{1}{poly(n)})^{\log n}$, all the APSP and routing
table subroutines in step 3: succeed.

Lemmas 6.3 and 6.4 then together imply Theorem 3.2. Within $\lceil\log
n\rceil$ iterations, only one active component remains: the root component.
This active component can then be expanded to a full DMST on $G$ within
$\lceil\log n\rceil$ rounds, as detailed in (?, ?, §7) or the 8.3 procedure in
§8.3 of the appendix. All messages in the algorithm other than those for
computing the APSP in 6.2.2 may be classical. We provide here the full
algorithm for completeness:  Quantum DMST Algorithm Input: An integer-weighted
digraph and a root node $r$. Output: A DMST for $G$ rooted at $r$. 1.
Initialize a subgraph $H$ with the same vertex set as G by subtracting for
each node the minimum incoming edge weight from all its incoming edges, and
selecting exactly one incoming zero-weight edge for each non-root node of $G$.
Set $t=0,H_{0}=H$, and $G_{0}=G$ with annotations $sID_{0}$ to be the identity
mapping. 2. WHILE: $H_{t}$ is not a single component (a) Run 6.2.2 with inputs
$H_{t}$, $(G_{t},sID_{t})$ to obtain $H_{t+1}$, $(G_{t+1},sID{t+1})$ as
outputs. Increment $t\leftarrow t+1$. 3. Let $T_{t}:=H_{t}$. For
$k=t,\dots,1$: For each super-vertex of the $k^{th}$ iteration of 6.2.2
applied, simultaneously run the 8.3 procedure with input tree $T_{k}$ to
obtain $T_{k-1}$. 4. Return $T_{0}$ as the distributed minimum spanning tree.

###  6.3 Complexity

In the 6.2.2, all steps other than the APSP step 3: of the quantum Lovasz
iteration can be implemented within $2$ rounds. In particular, to have all
nodes know some tree on G for which each node knows its parent, every node can
simply broadcast its parent edge and weight. Since this iteration is used up
to $\lceil\log(n)\rceil$ times and expanding the DMST at the end of the
algorithm also takes logarithmically many rounds, we obtain a complexity
dominated by the APSP computation of $\tilde{\mathcal{O}}(n^{1/4})$, a better
asymptotic rate than any known classical CONGEST-CLIQUE algorithm. However,
beyond the $\tilde{\mathcal{O}}$, the complexity is largely characterized by
$\log(n)\cdot f(n)$, with $f(n)$ as in Eq. (4.4). In order to have
$\log(n)f(n)<n$ to improve upon the trivial strategy of having a single node
solve the problem, we then need $n>10^{21}$. Using the classical APSP from (?,
?) in place of the quantum APSP of §4 as done in (?, ?) to attain the
$\tilde{\mathcal{O}}(n^{1/3})$ complexity in the cCCM, one would need
$\log(n)\cdot g(n)<n$ to beat the trivial strategy, with $g$ as in Eq. (4.5),
or more than $n>10^{14}$.

##  7 Discussion and Future Work

We have provided algorithms in the Quantum CONGEST-CLIQUE model for computing
approximately optimal Steiner Trees and exact Directed Minimum Spanning trees
that use asymptotically fewer rounds than their classical known counterparts.
As Steiner Tree and Minimum Spanning Trees cannot benefit from quantum
communication in the CONGEST (non-clique) model, the algorithms reveal how
quantum communication can be exploited thanks to the CONGEST-CLIQUE setting. A
few open questions remain as well. In particular, there exist many
generalizations of the Steiner Tree problem, so these may be a natural
starting point to attempt to generalize the results. A helpful overview of
Steiner-type problems can be found in (?, ?). Regarding the DMST, it may be
difficult to generalize a similar approach to closely related problems. Since
the standard MST can be solved in a (relatively small) constant number of
rounds in the classical CONGEST-CLIQUE, no significant quantum speedup is
possible. Other interesting MST-type problems are the bounded-degree and
minimum-degree spanning tree problems. However, even the bounded-degree
decision problem on an unweighted graph, “does $G$ have a spanning tree of
degree at most $k$?” is NP-complete, unlike the DMST, so we suspect that other
techniques would need to be employed. (?, ?) provides a classical distributed
approximation algorithm for the problem. Additionally, we have traced many
constants and $\log$ factors throughout our description of the above
algorithms, which, as shown, would need to be significantly improved for these
and related algorithms to be practical. Hence, a natural avenue for future
work is to work towards such practical improvements. Beyond the scope of the
particular algorithms involved, we hope to help the community recognize the
severity with which the practicality of algorithms is affected by logarithmic
factors that may be obscured by $\tilde{\mathcal{O}}$ notation, and thus
encourage fellow researchers to present the full complexity of their
algorithms beyond asymptotics. Particularly in a model like CONGEST-CLIQUE,
where problems can always be solved trivially in $n$ rounds, these logarithmic
factors should clearly not be taken lightly. Further, a question of potential
practical interest would be to ask the following: What algorithms solving the
discussed problems are the most efficient with respect to rounds needed in the
CONGEST-CLIQUE in the regimes of $n$ in which the discussed algorithms are
impractical?

## Acknowledgements

We are grateful for support from the NASA Ames Research Center, from the NASA
SCaN program, and from DARPA under IAA 8839, Annex 130. PK and DB acknowledge
support from the NASA Academic Mission Services (contract NNA16BD14C). The
authors thank Ojas Parekh for helpful input and discussions regarding the
arborescence problem, Shon Grabbe for ongoing useful discussions, and Filip
Maciejewskifor for helpful feedback on the work.

## References

  * Booth, O'Gorman, Marshall, Hadfield, RieffelBooth et al. Booth, K. E. C., O'Gorman, B., Marshall, J., Hadfield, S., Rieffel, E.  (2021, sep).  Quantum-accelerated constraint programming.  _Quantum_ , _5_ , 550.  Retrieved from https://arxiv.org/abs/2103.04502 doi: doi:10.22331/q-2021-09-28-550
  * Censor-Hillel, Fischer, Le Gall, Leitersdorf, OshmanCensor-Hillel et al. Censor-Hillel, K., Fischer, O., Le Gall, F., Leitersdorf, D., Oshman, R.  (2022).  _Quantum Distributed Algorithms for Detection of Cliques._ arXiv.  Retrieved from https://arxiv.org/abs/2201.03000 doi: doi:10.48550/ARXIV.2201.03000
  * Censor-Hillel et al.Censor-Hillel et al. Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A., Suomela, J.  (2016, mar).  Algebraic methods in the congested clique.  _Distributed Computing_ , _32_(6), 461–478.  doi: doi:10.1007/s00446-016-0270-2
  * Dinitz, Halldorsson, Izumi, NewportDinitz et al. Dinitz, M., Halldorsson, M. M., Izumi, T., Newport, C.  (2019).  Distributed Minimum Degree Spanning Trees.  In _Proceedings of the 2019 acm symposium on podc_ (p. 511–520).  New York, NY, USA: ACM.  doi: doi:10.1145/3293611.3331604
  * Dolev, Lenzen, PeledDolev et al. Dolev, D., Lenzen, C., Peled, S.  (2012).  ”Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting - (Extended Abstract).  _ArXiv_ , _abs/1201.6652_.
  * Edmonds et al.Edmonds et al. Edmonds, J., et al. (1967).  Optimum branchings.  _Journal of Research of the national Bureau of Standards B_ , _71_(4), 233–240.
  * Elkin, Klauck, Nanongkai, PanduranganElkin et al. Elkin, M., Klauck, H., Nanongkai, D., Pandurangan, G.  (2012).  _Can Quantum Communication Speed Up Distributed Computation?_ arXiv.  Retrieved from https://arxiv.org/abs/1207.5211 doi: doi:10.48550/ARXIV.1207.5211
  * Fischer OshmanFischer Oshman Fischer, O., Oshman, R.  (2021).  A distributed algorithm for directed minimum-weight spanning tree.  _Distributed Computing_ , 1–31.
  * GhaffariGhaffari Ghaffari, M.  (2020).  _Distributed Graph Algorithms (Lecture Notes)._ Retrieved from https://disco.ethz.ch/courses/podc/lecturenotes/LOCAL.pdf
  * Giovannetti, Lloyd, MacconeGiovannetti et al. Giovannetti, V., Lloyd, S., Maccone, L.  (2008, apr).  Quantum random access memory.  _Physical Review Letters_ , _100_(16).  Retrieved from https://doi.org/10.1103%2Fphysrevlett.100.160501 doi: doi:10.1103/physrevlett.100.160501
  * Hauptmann KarpinskiHauptmann Karpinski Hauptmann, M., Karpinski, M.  (2015).  _A Compendium on Steiner Tree Problems._ Retrieved from http://theory.cs.uni-bonn.de/info5/steinerkompendium
  * Izumi GallIzumi Gall Izumi, T., Gall, F. L.  (2019, jul).  Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.  In _Proceedings of the 2019 ACM symposium on podc._ ACM.  Retrieved from https://arxiv.org/abs/1906.02456 doi: doi:10.1145/3293611.3331628
  * Izumi, Le Gall, MagniezIzumi et al. Izumi, T., Le Gall, F., Magniez, F.  (2020).  _Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model._ Schloss Dagstuhl - Leibniz-Zentrum für Informatik.  Retrieved from https://drops.dagstuhl.de/opus/volltexte/2020/11884/ doi: doi:10.4230/LIPICS.STACS.2020.23
  * Korhonen SuomelaKorhonen Suomela Korhonen, J. H., Suomela, J.  (2017).  _Towards a complexity theory for the congested clique._ arXiv.  Retrieved from https://arxiv.org/abs/1705.03284 doi: doi:10.48550/ARXIV.1705.03284
  * Kou, Markowsky, BermanKou et al. Kou, L. T., Markowsky, G., Berman, L.  (1981).  A fast algorithm for Steiner trees.  _Acta Informatica_ , _15_ , 141–145.  Retrieved from http://aturing.umcs.maine.edu/~markov/SteinerTrees.pdf
  * Le Gall MagniezLe Gall Magniez Le Gall, F., Magniez, F.  (2018, jul).  Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.  In _Proceedings of the 2018 ACM symposium on podc._ ACM.  Retrieved from https://arxiv.org/pdf/1804.02917.pdf doi: doi:10.1145/3212734.3212744
  * LenzenLenzen Lenzen, C.  (2012).  _Optimal Deterministic Routing and Sorting on the Congested Clique._ arXiv.  doi: doi:10.48550/ARXIV.1207.1852
  * LovaszLovasz Lovasz, L.  (1985).  Computing ears and branchings in parallel.  In _26th annual symposium on foundations of computer science (sfcs 1985)_ (pp. 464–467).  doi: doi:10.1109/SFCS.1985.16
  * NowickiNowicki Nowicki, K.  (2019).  _A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique._ arXiv.  doi: doi:10.48550/ARXIV.1912.04239
  * Rieffel PolakRieffel Polak Rieffel, E., Polak, W.  (2011).  _Quantum Computing: A Gentle Introduction_ (1st ed.).  The MIT Press.
  * Saikia KarmakarSaikia Karmakar Saikia, P., Karmakar, S.  (2019).  _Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE._ arXiv.  Retrieved from https://arxiv.org/abs/1907.12011 doi: doi:10.48550/ARXIV.1907.12011
  * van Apeldoorn de Vosvan Apeldoorn de Vos van Apeldoorn, J., de Vos, T.  (2022).  _A Framework for Distributed Quantum Queries in the CONGEST Model._ arXiv.  Retrieved from https://arxiv.org/abs/2202.10969 doi: doi:10.48550/ARXIV.2202.10969
  * ZwickZwick Zwick, U.  (2000).  _All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication._ arXiv.  doi: doi:10.48550/ARXIV.CS/0008011

##  8 Appendix

###  8.1 Proof of claim 1

For an $n\crossproduct n$ integer matrix $W$, obtain matrices $W^{\prime}$ and
$W^{\prime\prime}$ by taking $W^{\prime}_{ij}=nW_{ij}+j-1$ and
$W^{\prime\prime}_{ji}=nW_{ji}$. Set $D=W^{\prime}\star W^{\prime\prime}$. We
aim to show that $\left\lfloor{\dfrac{D}{n}}\right\rfloor=W^{2,\star}$ and
$(D\mod n)+1$ is a witness matrix for $W^{2,\star}.$

###### Proof.

  *   * (i)

We have

$\displaystyle\left\lfloor{\dfrac{D}{n}}\right\rfloor_{ij}$
$\displaystyle=\left\lfloor\min_{k\in[n]}\left\\{nW_{ik}+k-1+nW_{kj}\right\\}/n\right\rfloor=\left\lfloor\min_{k\in[n]}\left\\{W_{ik}+W_{kj}+\frac{k-1}{n}\right\\}\right\rfloor$
$\displaystyle=W^{2}_{ij}+\left\lfloor\min_{k\in[n]}\left\\{\frac{k-1}{n}:W_{ik}+W_{kj}=W^{2}_{ij}\right\\}\right\rfloor=W^{2}_{ij}.$

  * (ii)

Next,

$\displaystyle
D_{ij}=nW^{2}_{ij}+\left\lfloor\min_{k\in[n]}\left\\{k-1:W_{ik}+W_{kj}=W^{2}_{ij}\right\\}\right\rfloor$

gives us

$(D\mod
n)+1=\left\lfloor\min_{k\in[n]}\left\\{k-1:W_{ik}+W_{kj}=W^{2}_{ij}\right\\}\right\rfloor+1=\min_{k\in[n]}\left\\{k:W_{ik}+W_{kj}=W^{2}_{ij}\right\\},$

which proves the claim.

∎

###  8.2 The $\alpha$ ¿ 0 case

The strategy will be to assign each $v_{(i,j,k)}\in\mathbb{V}$ into classes in
accordance with approximately how many negative triangles are in $U_{i}\times
U_{j}\times U^{\prime}_{k}$ before starting the search.

To assign each node to a class, we use the routine 4.4 of (?, ?), also
described in the main text.

The main body of this paper discussed the special case assuming $\alpha=0$.
Hence we now consider the $\alpha>0$ case.

For each $\alpha\in\mathbb{N}$, let us denote $c_{i,j,k}$ the smallest
nonnegative integer satisfying $d_{i,j,k}<10\cdot 2^{c}\log n$, and

$\displaystyle V_{\alpha}$ $\displaystyle:=\\{v_{(i,j,k)}:c_{i,j,k}=\alpha\\}$
(8.1) $\displaystyle V_{\alpha}[i,j]$
$\displaystyle:=\\{U_{k}^{\prime}\in\mathcal{U}^{\prime}:v_{(i,j,k)}\in
V_{\alpha}\\}$ (8.2)

for any $i,j\in[n^{1/4}]$. Notably, $\mathcal{P}(i,j)$ contains at most
$\sqrt{n}$ edges, so that $d_{i,j,k}\leq\sqrt{n}$ as well. Hence,
$c=\frac{1}{2}\log n$ provides an upper bound for the minimum in step 2:. The
important immediate consequence is that we only need to consider $V_{\alpha}$
up to at most $\alpha=\frac{1}{2}\log n$.

######  Lemma 8.1.

The 4.4 algorithm and the resulting $V_{\alpha}$ satisfy the following
statements with probability at least $1-2/n$:

  * (i):

The algorithm does not abort

  * (ii):

$|\Delta(i,j,k)|\leq 2n$

  * (iii):

For $\alpha>0$, $v_{(i,j,k)}\in V_{\alpha}$, we have
$2^{\alpha-3}n\leq|\Delta(i,j,k)|\leq 2^{\alpha+1}n$.

  * (iv):

$|\Lambda_{x}(i,j)\cap\Delta(i,j,k)|\leq 100\cdot 2^{\alpha}\sqrt{n}\log n$
for $i,j\in[n^{1/4}]$ and $\alpha\in{\mathbb{N}}$.

This provides an adapted version of lemma 4.12 for the $\alpha>0$ case.

The following lemma provides a tool that will allow for ”duplication” of
information to avoid message congestion in the network in the 8.2 procedure.

######  Lemma 8.2.

For all $\alpha\geq 0$ and $i,j\in[n^{1/4}]$,

$\displaystyle|V_{\alpha}[i,j]|\leq\dfrac{720\sqrt{n}\log n}{2^{\alpha}}$
(8.3)

###### Proof.

The $\alpha=0$ case is immediate since $|\mathcal{U}^{\prime}|=\sqrt{n}$, so
consider $\alpha\geq 1$. The “promise” in the FEWP subroutine we are in
guarantees that for all $(u,v)\in S,\Gamma(u,v)\leq 90\log n$, so that for any
$i,j\in[n^{1/4}]$, each edge in $\mathcal{P}(U_{i},U_{j})\cap S$ has at most
$90\log n$ other nodes forming a negative triangle with it, leading to the
inequality

$\sum_{k:v_{(i,j,k)}\in V_{\alpha}}|\Delta(i,j,k)|\leq 90n^{3/2}\log n.$

Using $|\Delta(i,j,k)|\geq 2^{\alpha-3}n$ from part (i): of lemma 8.1, the
conclusion follows. ∎

We now describe the implementation of step 3: of the 4.4 procedure for the
$\alpha>0$ case.  3.1: Each node executes the 4.4 procedure. 3.2: For each
$\alpha$:
For every $l\in[m]$, every node $v_{(i,j,k)}$ executes a quantum search to
find whether there is a $U_{k}^{\prime}\in V_{\alpha}[U_{i},U_{j}]$ with some
$w\in U_{k}^{\prime}$ forming a negative triangle $(u^{k}_{l},v^{k}_{l},w)$ in
$G$, and then reports all the pairs $u^{k}_{l}v^{k}_{l}$ for which such a
$U_{k}^{\prime}$ was found.

The $\alpha=0$ case was described in the main text. We proceed to describe the
classical procedure for invoking theorem 4.11 to obtain the speedup for the
general $\alpha$ case, as in (?, ?, §5.3.2). Some technical precautions must
be taken to avoid congestion of messages between nodes. This crucially relies
on information duplication to effectively increase bandwidth between nodes.
Lemma 8.2 provides a strong bound for the size of each $V_{\alpha}$. For this
duplication of the information stored by the relevant nodes, a new labeling
scheme is convenient. Suppose for simplicity that
$C_{\alpha}:=2^{\alpha}/(720\log n)$ is an integer, and assign each node a
label $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},\mathbf{v},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y)\in
V_{\alpha}\times[C_{\alpha}]$, which is possible due to the bound of lemma
8.2. The following 8.2 implementable in $\mathcal{O}(\log n)$ rounds (using a
slightly sharper complexity analysis than (?, ?)) can then be used for
invoking theorem 4.11:

EvaluationB
Input: A list $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf
w$}}}_{1}^{k},\dots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}_{m}^{k})$ of elements of
$V_{\alpha}[{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf u$}}},\mathbf{v}]$ assigned to each
node $k=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf u$}}},\mathbf{v},x)$.
Promise: $|L^{k}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}|\leq 800\cdot
2^{\alpha}\sqrt{n}\log n$ for each node $k$ and all $|w\in
V_{\alpha}[{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf u$}}},\mathbf{v}]$.
Output: Every node $k=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf u$}}},\mathbf{v},x)$ outputs for
each $\ell\in[m]$ whether some
$w\in{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}_{l}$ forms a negative
triangle $\\{u^{k}_{\ell},v_{\ell}^{k},w\\}$. 0. Every node
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},\mathbf{v},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}})\in V_{\alpha}$ broadcasts
the edge information loaded in step 1: of 4.4 to
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},\mathbf{v},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y)$ for each
$y\in[C_{\alpha}]$. 1. Every node
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf u$}}},\mathbf{v},x)$ splits each
$L_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}$ into smaller sublists
$L_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf
w$}}},1}^{k},\dots,L^{k}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},C_{\alpha}}$ for each
$\textstyle\bf w$, with each sublist containing up to
$\lceil|L_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}|/C_{\alpha}\rceil=\lceil
800\cdot 720\sqrt{n}\log^{2}n\rceil$ elements,and sends each
$L_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y}^{k}$ to node
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},\mathbf{v},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y)$ along with the relevant
edge weights. 2. Every $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},\mathbf{v},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y)$ node returns the truth
value $\min_{w\in{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}}\\{W_{uw}+W_{wv}\\}\leq
W_{vu}$ to node $k$ for each $uv\in
L_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}},y}^{k}$ received in step 1..

For each value of $\alpha$, we separately solve step 3.2: of the 4.4
procedure. Since lemma 8.2 tells us that there are $C_{\alpha}$ times more
nodes not in $V_{\alpha}$ than there are in $V_{\alpha}$, every node in
$V_{\alpha}$ can use $C_{\alpha}$ of those nodes not in $V_{\alpha}$ to relay
messages and effectively increase its message bandwidth, which is exactly what
8.2 takes advantage of. Steps 1. and 2. of the procedure take up to
$2\cdot\lceil|L_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}|\rceil/n\leq
1600\cdot\log n$ rounds, since lists of size
$\lceil|L_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}|/C_{\alpha}\rceil$ are
sent to $C_{\alpha}$ nodes, and the bound on $\alpha$ gives
$\lceil|L_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
w$}}{\mbox{\boldmath$\textstyle\bf w$}}{\mbox{\boldmath$\scriptstyle\bf
w$}}{\mbox{\boldmath$\scriptscriptstyle\bf w$}}}^{k}|\rceil\leq 800n\log(n)$.

####  8.2.1 Complexity of the Classical Analogue

This subsection of the appendix serves to provide some supplemental
information to §4.7.2 discussing the complexity of an algorithm for APSP with
routing tables in the CONGEST-CLIQUE as proposed in (?, ?) that has complexity
$\tilde{\mathcal{O}}(n^{1/3})$. Note that (?, ?, corollary 6) applied to APSP
distance computations only, whereas the routing table computations are
discussed in (?, ?, §3.4). As shown there, $\mathcal{O}(\log^{3})$ distance
products (without witnesses) are needed to compute one distance product with a
witness matrix. More precisely:

  1. 1.

Obtaining a witness matrix when witnesses are unique requires $\log(n)$
distance products.

  2. 2.

The procedure for finding witnesses in the general case calls the procedure to
find witnesses in the unique witness case $\mathcal{O}(\log^{2}n)$ times, or
$2\cdot\log^{2}n$ times if $c=2$ is deemed as sufficient for the success
probability.

  3. 3.

$\log n$ such distance products with witnesses are needed for the APSP
algorithm with routing tables.

Then $2\log^{4}n$ distance products are computed in total for one distance
product with witnesses. The distance product via the semi-ring matrix
multiplication algorithm of (?, ?, §2.1) uses $10n^{1/3}$ rounds ($4n^{1/3}$
for its steps 1 and 2, and $2n^{1/3}$ for step 3) using lemma 4.8, and hence
one obtains the full round complexity of

$\displaystyle 10n^{1/3}\cdot 2\log(n)^{4}=g(n).$ (8.4)

###  8.3 Expanding the DMST in the Distributed Setting

We handle the expansion of the DMST in the same way as in (?, ?, §7),
borrowing much of their discussion for our description here. However, as we
have computed APSP distances along the way in place of SSSP, ‘unpacking’ the
DMST becomes a bit simpler in our case.
Consider a component $H_{i}$ in one of the iterations of 6.2.2, with input
graph for the iteration being $G_{i}$. For each contraction in 6.2.2, we
determined edges $v_{i}u_{i}$, $v_{i}\notin H_{i},u_{i}\in H_{i}$ minimizing
$\beta_{i}:=W_{v_{i}u_{i}}+d_{G}(u_{i},c(H_{i}))$ to contract nodes. Recall
that what happens in the iteration is that the cycle $c(H_{i})$ and all nodes
that have distance $\beta_{i}$ to $c(H_{i})$ are contracted into one super-
vertex. Denote that super-vertex by $V_{H_{i},\beta_{i}}^{*}$. Let $G_{i+1}$
denote the graph obtained after this contraction. Then our goal, given a DMST
$T_{i+1}$ for $G_{i+1}$, is to recover $G_{i}$ along with a DMST $T_{i}$ for
$G_{i}$. We make use of the following 8.3 operation of (?, ?, §7):

Unpacking Input: A digraph $G_{i+1}$ with a DMST $T_{i+1}$ with root $r$, a
set of edges $H_{i}$ as in 6.2.2, a node $V^{*}_{H_{i},\beta_{i}}$ of
$G_{I+1}$ marked as a super-vertex, a set $c(H_{i})$ of the nodes contracted
into it, and $G_{i}$ the graph before contracting $c(H_{i})$. Output: A DMST
$T_{i}$ for $G_{i}$ rooted at $r$. 1: For any $v_{1},v_{2}\notin
V_{H_{i},\beta_{i}}^{*}$, let edge $v_{1}v_{2}\in T_{i}$ iff $v_{1}v_{2}\in
T_{i+1}$. 2: For $uV_{H_{i},\beta_{i}}^{*}\in T_{i+1}$, which exists since
$T_{i+1}$ is a DMST for $G_{i+1}$, denote the edge
$uv^{*}:=argmin_{uv:v\in V_{H_{i},\beta_{i}}^{*},u:\exists uv\in
G_{i+1}}W_{vu}+d_{G}(u,c(H_{i}))$. Add $uv^{*}$ and the shortest path $\zeta$
connecting $v^{*}$ to $c(H_{i})$ to $T_{i}$. 3: For any edge
$V_{H_{i},\beta_{i}}^{*}u\in T_{i+1}$ outgoing from the contracted super-
vertex, add the edge
$argmin_{vu:v\in V_{H_{i},\beta_{i}}^{*}}W_{vu}^{G_{i}}$ to $T_{i}$. 4: Add
all edges $H_{i}\setminus\delta^{in}(\zeta)$ to $T_{i}$, where
$\delta^{in}(\zeta)$ denotes all edges incoming on $\zeta$.

At the end of this procedure, $T_{i}$ is a DMST for $G_{i}$ (?, ?, lemma 8).
We now describe how it can be implemented distributedly, needing only
classical messages and information. For every contracted super-vertex, the
following steps can be implemented at the same time, as will become clear in
how the steps are executed for the nodes of each contracted super-vertex. Let
us focus on unpacking one super-vertex $V_{H_{i},\beta_{i}}^{*}$. Each node
knows its neighbors in $G_{i}$, and every node’s super-vertex ID in $G_{i}$
and $G_{i+1}$, since each node stores this information before the initial
contraction to $G_{i+1}$ in 6.2.2 happens. Hence, step 1: can be done locally
at each node without any communication. Step 2: can be done by first having
each node $v\in V_{H_{i},\beta_{i}}^{*}$ send $\beta(u,v)$ to the other nodes
in $V_{H_{i},\beta_{i}}^{*}$, in one round, and then having each node of
$V_{H_{i},\beta_{i}}^{*}$ send to $v^{*}$ the routing table entry
corresponding to its shortest path to $c(H_{i})$ in $G_{i}$, also in one round
(the nodes have already computed this information in 6.2.2. Then $v^{*}$
notifies the nodes that are part of $\zeta$, which can then add the
appropriate edge to $T_{i}$, needing yet another round, so that step 2: can be
done in three rounds of classical communication only. Step 3: is handled
similarly. For the outgoing edge, each node in $V_{H_{i},\beta_{i}}^{*}$ sends
$W_{vu}^{G_{i}}$ to the other nodes in $V_{H_{i},\beta_{i}}^{*}$ so that the
appropriate edge to add to $T_{i}$ can be determined (in case of a tie, the
node with smaller ID can be the one to add the edge), so this can be done in
one round. For step 4:, every node in $\zeta$ notifies its neighbors that it
is in $\zeta$, after which every node can determine which edges to add to
$T_{i}$. For the unpacking of $V_{H_{i},\beta_{i}}^{*}$, the information and
communication for implementing its unpacking is contained in the nodes of
$V_{H_{i},\beta_{i}}^{*}$, so we can indeed unpack all vertices synchronously
to obtain $G_{i}$ even when multiple super-vertices were contracted to get
$G_{i+1}$. Hence, one layer of unpacking using this procedure can be
implemented in $5$ rounds (making use of the APSP and routing table
information computed earlier before the contractions in 6.2.2). Since there
are at most $\lceil\log n\rceil$ contraction steps, the unpacking procedure
can be implemented in $5\cdot\lceil\log n\rceil$ rounds.

###  8.4 Information access

In remark 2.2, we mention that it suffices for all information regarding the
input graph to be stored classically, with quantum access to it. Here, we
expand on what we mean by that and refer the interested reader to (?, ?) for
further details.

While our algorithms use quantum subroutines, the problem instances and their
solutions are encoded as classical information. The required quantum access
refers to the ability to access the classical data so that computation in
superposition of this data is possible. For instance, in the standard (non-
distributed) Grover search algorithm, with a problem instance described by a
function $g:X\rightarrow{0,1}$, we need the ability to apply the unitary
$U_{w}|x\rangle=(-1)^{g(x)}|x\rangle$ to an $N$-qubit superposition state
$|s\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$. This unitary is also
referred to as the “oracle”, and a call to it as a “query”. If we wish to use
the distributed Grover search in example 2.4, in which the node $u$ leading
the search tries to determine whether each edge $uv$ incident on it is part of
a triangle in graph $G$, the unitary that node $v$ must be able to evaluate is
the indicator function of its neighborhood, and $u$ must be able to apply the
Grover diffusion unitary restricted to its neighborhood. Then after
initializing the $N$-qubit equal superposition, nodes $u$ and $v$ can send a
register of qubits back and forth between each other, with $v$ evaluating the
unitary corresponding to the indicator of its neighborhood and $u$ applying
the Grover diffusion operator restricted to its neighborhood.The same ideas
transfer over to a distributed quantum implementation of the 4.6 (or 8.2)
procedure. There, instead of evaluating unitaries corresponding to indicators,
in step 2., each node $v_{(i,j,k)}$ evaluates the unitary corresponding to the
truth values of inequality 4.3 for the evaluation steps. That information is
then returned to the node that sent it, which can then apply the appropriate
Grover diffusion operator.

In general, quantum random access memory (QRAM) is the data structure that
allows queries to the oracle. We can use circuit QRAM in our protocols or
could make use of special-purpose hardware QRAM if it were to be realized.
This choice does not affect the number of rounds of communication but would
affect the efficiency of computation at each node. A main component of the
distributed algorithms discussed in this work is quantum query access for each
node to its list of edges and their weights in some graph $G$. This
information is stored in memory, and the QRAM implementing the query to
retrieve it can be called in time $\mathcal{O}(\log n)$, resulting in a
limited overhead for our algorithms. This retrieval of information takes place
locally at each node; hence, this overhead does not add to the round
complexity of our algorithms in the CONGEST-CLIQUE setting. We refer to (?, ?)
for more details on QRAM.