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

Abstract

We present two algorithms in the quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability: one for producing an approximately optimal Steiner tree, and one for producing an exact directed minimum spanning tree, each of which uses $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds of communication and $\tilde{\mathcal{O}}\left(n^{9/4}\right)$ messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by $\tilde{\mathcal{O}}$ notation, revealing that advances are needed to render both the quantum and classical algorithms practical.

1. Introduction

The classical CONGEST-CLIQUE model (henceforth referred to as cCCM) in distributed computing has been carefully studied as a model central to the field, e.g., [1,2,3,4,5,6]. 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 Section 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 subjects of recent research [7,8,9,10] in an effort to understand how quantum communication may help in these distributed computing frameworks. For the quantum CONGEST model, however, ref. [10] 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 [11]. No comparable negative results exist for the qCCM, and in fact, ref. [7] provides an asymptotic quantum speedup for computing all-pairs shortest path (APSP, henceforth) distances. Hence, it is apparent that the negative results of [10] cannot transfer over to the qCCM, so investigating these problems in the qCCM presents an opportunity for contributing 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 exacting directed minimum spanning trees using $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds—asymptotically fewer rounds than any known classical algorithms. This is done by augmenting the APSP algorithm of [7] with an efficient routing table scheme, which is necessary to make use of the shortest path 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 [2,3,7,12] 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, similar to APSP, these problems cannot see quantum speedups in the CONGEST (non-clique) setting, as shown in [10]. Our Steiner tree algorithm is approximate and based on a classical polynomial-time centralized algorithm of [13]. Our directed minimum spanning tree problem algorithm follows an approach similar to [3], which effectively has its centralized roots in [14].

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\left)\right)$ classical bits in each round to its neighbors, though the messages to each neighbor may differ. In the cCCM, we separate the communication graph from the problem’s input graph by allowing all nodes to communicate with each other, though the same $\mathcal{O}(log(n\left)\right)$ 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·log(n\left)\right)$ 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, or 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 [15].

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\left)\right)$ classical bits, we allow messages to consist of $\mathcal{O}(log(n\left)\right)$ quantum bits, i.e., qubits. For background on qubits and the fundamentals of quantum computing, we refer the reader to [16]. We formally define the qCCM, the setting for our algorithms, as follows:

Definition 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 $\left[n\right]$. Time passes in rounds, each of which consists of the following:

• Each node may execute unlimited local computation.
• Each node may send a message consisting of either a register of $\mathcal{O}(logn)$ qubits or a string of $\mathcal{O}(logn)$ classical bits to every other node in the network. Each of those messages may be distinct.
• 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\left(u\right):=\{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 $|0\rangle$ or $|1\rangle$, respectively, and then take measurements with respect to the $\{|0\rangle ,|1\rangle \}$ 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 $\left[n\right]$, 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 $\left[n\right]$ to each node according to an ordering of the original IDs, resulting in our assumed situation.

Remark 1.

Definition 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 Appendix A.4.

Remark 2.

No initial entanglement being shared across nodes, as outlined in Definition 1, results in quantum teleportation not being a straightforward method to solve problems in the qCCM.

Example 1.

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 the distributed Grover search, first described in [11]. The high-level intuition for why quantum computing provides an advantage for search is that quantum operations use quantum interference effects to have canceling effects among non-solutions. Grover search has a generalization referred to as “amplitude amplification” that we will use; see [16] for details on these algorithms. Now, for a processor node u in the network and a Boolean function $g:X\to \{0,1\}$, suppose that there exists a classical procedure $\mathcal{C}$ in the cCCM that allows u to compute $g\left(x\right)$, 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\left(x\right)=i\}$, for $i=0,1$, and suppose that $0<|A_1|\le |X|/2$. Classically, node u can then find an $x\in A_1$ in $\mathsf{\Theta }(r|X|)$ rounds by checking each element of X. Using the quantum distributed Grover search of [11] enables u to find such an x with high probability in only $\tilde{\mathcal{O}}\left(r\sqrt{|X|}\right)$ rounds by evaluating the result of computing g on a superposition of inputs.

We illustrate this procedure in an example case where 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\left(u\right)$, we denote by ${\mathcal{I}}_v:V\to \{0,1\}$ the indicator function of ${\mathcal{N}}_G\left(v\right)$, and by $g_{uv}:{\mathcal{N}}_G\left(u\right)\to \{0,1\}$ its restriction to inputs in ${\mathcal{N}}_G\left(u\right)$. Classically, node u can evaluate $g_{uv}\left(w\right)$ in two rounds for any $w\in {\mathcal{N}}_G\left(u\right)$ by sending the ID of w (of length $logn$) to v, and having v send back the answer ${\mathcal{I}}_v\left(w\right)$. u can then check $g_{uv}\left(w\right)$ for each $w\in {\mathcal{N}}_G\left(u\right)$ one at a time to determine whether $uv$ is part of a triangle in G or not in $2·|{\mathcal{N}}_G\left(u\right)|$ rounds.

For the distributed quantum implementation, u can instead initialize a register of $logn$ qubits as ${|\psi \rangle }_0:=\frac{1}{\sqrt{|{\mathcal{N}}_G\left(u\right)|}}{\sum }_{x\in {\mathcal{N}}_G\left(u\right)}|x\rangle$, all the inputs for $g_{uv}$ in equal superposition. To conduct 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\left(x\right)\rangle$ for all $x\in V$. Node v sends back the resulting qubit register, and node u evaluates $g_{uv}(|\psi \rangle )$ in two rounds. Now, since u can evaluate $g_{uv}$ in superposition, node u may proceed using standard amplitude amplification, using two rounds of communication for each evaluation of $g_{uv}$, so that u can find an element $w\in {\mathcal{N}}_G\left(u\right)$ satisfying $g_{uv}\left(w\right)=1$ with high probability in $\tilde{\mathcal{O}}\left(r\sqrt{|{\mathcal{N}}_G\left(u\right)|}\right)$ 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\left(u\right)$ (and sending this information to v would take $|{\mathcal{N}}_G\left(u\right)|$ rounds), though it is able to evaluate ${\mathcal{I}}_v$ in superposition for any $w\in {\mathcal{N}}_G\left(u\right)$. For any classical procedure $\mathcal{C}$ evaluating a different function from this specific g (which can be efficiently implemented 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 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 \left(v\right)\subset V$ be the set of edges incident on node v, and ${\mathcal{N}}_G\left(u\right):=\{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)$, given 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}\left(U\right):=\mathcal{P}(U,U)$ as shorthand. All logarithms will be taken with respect to base 2, unless otherwise stated.

Definition 2.

(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 3.

(Approximate Steiner tree) For a Steiner tree problem with terminals $\mathcal{Z}$ and a 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}\le r·\sum _{uv\in E_{{\mathcal{S}}_{OPT}}}{W}_{uv}$$

is called an approximate Steiner tree with approximation factor r.

Definition 4.

(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 spanning tree for G rooted at r. 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}}\left(n^{1/4}\right)$ rounds and an algorithm that produces an exact directed minimum spanning tree w.h.p. in $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds. To do this, we enhance the quantum APSP algorithm of [7] in an efficient way to compute APSP distances as well as the corresponding routing tables (described in Section 4) that our algorithms rely on. Furthermore, in addition to these $\tilde{\mathcal{O}}$ results, in Section 4.7, Section 5.4, and Section 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 the $\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 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 a probability of at least $1-\frac{1}{poly\left(n\right)}$, and uses $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds of computation, where l denotes the number of terminal leaf nodes in the optimal Steiner tree.

Theorem 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\left(n\right)}$, and uses $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ 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 [7] with a routing table computation from [17]. For this, we reduce APSP with routing tables to triangle finding by utilizing distance products, as demonstrated in [12].

4.1. Distance Products and Routing Tables

Definition 5.

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 from v to u, other than v itself.

Definition 6.

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

$$\begin{array}{c}\hfill {(A★B)}_{ij}=\underset{k}{min}\{A_{ik}+B_{kj}\}.\end{array}$$

(1)

The distance product is also sometimes referred to as the min-plus or tropical product. For shortest paths, we will repeatedly square the graph adjacency matrix with respect to the distance product. For a $n\times n$ matrix W and an integer k, let us denote $W^{k,★}:=W★(W★(\dots (W★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_{uv}^{k,★}$ is the length of the shortest path from v to u in G using at most k hops. Hence, for any $N\ge n$, $W^{N,★}$ contains all the shortest-path distances between nodes in G. As these distance products obey standard exponent rules, we may take $N=2^{\lceil logn\rceil }$ to recursively compute the APSP distances by taking $\lceil logn\rceil$ distance product squares:

$$\begin{array}{c}\hfill W^{2,★}=W★W,\phantom{x}{W}^{4,★}={\left(W^{2,★}\right)}^{2,★},\dots ,\phantom{x}{W}^{2^{\lceil logn\rceil },★}={\left(W^{2^{\lceil logn\rceil -1},★}\right)}^{2,★}.\end{array}$$

(2)

This procedure reduces computing APSP distances to computing $\lceil logn\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 Section 4.3 that is well-suited for our setting to extend [7] 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 ([18] Proposition 2), which we describe here, restricting to finding the distance product square needed for Equation (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 \left(v\right)$, such that $vu$ is involved in at least one negative triangle in G. Let us call this problem FindEdges, and define it formally as follows:

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\left(v\right)$, as well as the weights $W_{vu}$ for each $u\in {\mathcal{N}}_G\left(v\right)$.
• 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 1.

If FindEdges on an n-node integer-weighted graph $G=(V,E,W)$ can be solved in $T\left(n\right)$ rounds, then the distance product $A★B$ of two $n\times n$ matrices A and B with entries in $\left[M\right]$ can be computed in $T\left(3n\right)·\lceil {log}_2\left(2M\right)\rceil$ rounds.

Proof. 

Let A and B be arbitrary $n\times n$ integer-valued matrices, and D be an $n\times n$ matrix initialized to $\mathbf{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\ne 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

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

Assuming we can compute FindEdges for a k-node graph in $T\left(n\right)$ 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 FindEdges to find ${min}_{u\in V}\{A_{vu}+B_{uz}\}$ for every other node z in $T\left(3n\right)·\lceil log\left({max}_{v,z\in V}\left\{{min}_{u\in V}\{A_{vu}+B_{uv}\}\right\}\right)\rceil$ rounds, since $G^{\prime }$ is a tripartite graph with $3n$ nodes. □

Remark 3.

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\left(3n\right)$ stems from each processor node possibly needing to send one message for each node it is simulating in each round of FindEdges. If the bandwidth per message is large enough (i.e., three times the bandwidth needed for solving FindEdges in $T\left(n\right)$ rounds), then this can be conducted in $T\left(n\right)$ rounds.

Thus, for this binary search, each node v initializes and locally stores $D_{vz}=0$ for each other $z\in V$; subsequently, we solve FindEdges 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, FindEdges is computed with the updated values for D. This is repeated until all the ${min}_{u\in V}\{A_{vu}+B_{uz}\}$ are 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 7.

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

$$\begin{array}{c}\hfill C_{ij}\in argmi{n}_{k\in \left[n\right]}\{A_{ik}+B_{kj}\}\end{array}$$

To put it 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 [17]. The approach is well-suited for our algorithm, as we only incur $\mathcal{O}(logn)$ additional calls to FindEdges for a distance product computation with a witness matrix.

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

Claim 1.

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

(i)

$\lfloor {\displaystyle \frac{K}{n}}\rfloor =W^{2,★}$

(ii)

$(Kmodn)+1$ is a witness matrix for $W^{2,★}.$

The claim follows from routine calculations of the quantities involved and can be found in Appendix A.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 logarithmically depends on the magnitude of the entries of W, we only logarithmically need many more calls to FindEdges 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$ with a witness matrix using $\lceil log(2n·{max}_{i,j}\{W_{ij}^2<\infty \})\rceil .$ calls to FindEdges. We obtain the following corollary to Proposition 1 to characterize the exact number of rounds needed:

Corollary 1.

If FindEdges on an n-node integer-weighted graph $G=(V,E,W)$ can be solved in $T\left(n\right)$ rounds, then the distance product square $W^{2,★}$, along with a witness matrix H, can be computed in $T\left(3n\right)·\lceil {log}_2(n·{max}_{v,z\in G}\left\{{min}_{u\in V}\{W_{vu}+W_{uv}\}\right\}+n)\rceil$ rounds.

Proof. 

This follows from Claim 1 and Proposition 1 upon observing that

${max}_{v\in V}\left\{{min}_{u\in V}\{W_{vu}^{\prime }+W_{uv}^{\prime \prime })\right\}\}\le n·{max}_{v,z\in G}\left\{{min}_{u\in V}\{W_{vu}+W_{uv}\}\right\}+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 Equation (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 only need to be stored and accessed classically so that we avoid using unnecessary quantum data storage.

4.4. Triangle Finding

Given the results from Section 4.2 and Section 4.3, we 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 FindEdges subroutine. We state here a central result from [7]:

Proposition 2.

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

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

As a preliminary, we provide a message routing lemma of [5] for the congested clique, which will be used repeatedly:

Lemma 1.

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

We introduce the subproblem FindEdgesWithPromise (FEWP, 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}\left(V\right)$, with each node v knowing ${\mathcal{N}}_G\left(v\right)$ and S.
• Promise: For each $uv\in S,\Gamma (u,v)\le 90logn.$
• Output: For each node v, its outputs are the edges $vu\in S$ that satisfy $\Gamma (u,v)>0$.

We present here a description of the procedure of [7] to solve FindEdges, given an algorithm $\mathcal{A}$ to solve FEWP. Let ${\epsilon }_{\mathcal{A}}$ be the failure probability of algorithm $\mathcal{A}$ for an instance of FEWP.

FindEdgesViaFEWP

1:

$S:=\mathcal{P};M:=\varnothing ;i:=0$.

2:

WHILE $60·2^{i}logn\le n$:

(a):

Each node samples each of its edges with probability $\sqrt{\frac{60·2^{i}logn}{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^{″}$ 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\left(\frac{n}{60logn}\right)\rceil +1$ calls to the $\mathcal{A}$ subroutine to solve FEWP. Further, it succeeds with a probability of at least $1-c_n/n^3-c_n/n^{2}8-(c_n+1){\epsilon }_{\mathcal{A}}$. We refer the reader to ([7] Section 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}=\left[n^{1/4}\right]\times \left[n^{1/4}\right]\times \left[\sqrt{n}\right]$. Clearly, $|\mathcal{M}|=n$, and $\mathcal{M}$ admits a total ordering lexicographically. Since we assume each node $v_i\in V$ is labeled with a unique integer ID $i\in \left[n\right]$, $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)·n^{3/4},\dots ,i·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)·\sqrt{n},\dots ,i·\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 conducted in one round.

We present here the algorithm ComputePairs 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_k^{\prime })$ associated with each node as above, and a set $S\subset \mathcal{P}\left(V\right)$, such that for $uv\in S,\Gamma (u,v)\le 90logn.$

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·\frac{logn}{\sqrt{n}}$. If $|\{v\in U_1:uv\in {\Lambda }_k(U_i,U_j)\}|>100n^{1/4}logn$ 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 $Wuv$ 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 \left[m\right]$, whether there is some $U\in {\mathcal{U}}^{\prime }$ that contains a node w, such that $(u_l^k,v_l^k,w)$ forms a negative triangle, and outputs all pairs $u_l^k{v}_l^k$ for which a negative triangle was found.

With a probability of at least $1-2/n$, the algorithm ComputePairs 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 ([7] Lemma 2).

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

Define the following quantity:

Definition 8.

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 }\mathit{with}(u,v,w)\mathit{forming} \mathit{a} \mathit{negative} \mathit{triangle} \mathit{in} G\}$$

For simultaneous quantum searches, we divide the nodes into different classes based on the number of negative triangles that 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 FEWP.

Output: For each node v, a class $\alpha$ to which the node belongs.

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 \left(u\right)$ of sampled vertices. If ${max}_u|\Lambda \left(u\right)|>20logn$, abort the algorithm and report a failure. Otherwise, have each node broadcast $\Lambda \left(u\right)$ to all other nodes, and take $R:={\cup }_{u\in V}\{uv|v\in \Lambda \left(u\right)\}$.

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_k^{\prime }$, 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·2^{c}logn\}$.

This uses, at most, $20logn$ rounds (each node sends (at most) that many IDs to every other node) and can be implemented so that all exchanged messages consist solely of classical bits. Using a Chernoff bound, one can show that the procedure succeeds with a probability of at least $1-1/n$, as seen in ([18] 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 \le \frac{1}{2}logn$, so we can run successive searches for each $\alpha$ for nodes in class $\alpha$ in the general case. The general case is discussed in Appendix A.2 and can also be found in [7], 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 ComputePairs procedure.

3.1:

Each node executes the IdentifyClass procedure.

3.2:

For each $\alpha$, for every $l\in \left[m\right]$, 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_l^k,v_l^k,w)$ in G, and then reports all the pairs $u_l^k{v}_l^k$ for which such a $U_k^{\prime }$ is found.

This provides the basis of the triangle-searching strategy. To summarize the intuition of the asymptotic speedup in this paper: Since $U_k^{\prime }$ has size $\sqrt{n}$ (recall that $|{\mathcal{U}}^{\prime }|=\sqrt{n}$), if each node using a quantum search can search through its assigned $U_k^{\prime }$ in $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds, simultaneously, we will obtain our desired complexity. We will complete this argument in Section 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 [7] for distributed quantum searches. Let X denote a finite set throughout this subsection.

Theorem 3.

Let $g:X\to \{0,1\}$, if node u can compute $g\left(x\right)$ 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\left(x\right)=1$ with high probability, using $\tilde{\mathcal{O}}\left(r\sqrt{|X|}\right)$ rounds.

This basic theorem concerns only single searches; however, we need a framework that can perform multiple simultaneous searches. Let $g_1,\dots ,g_m:X\to \{0,1\}$ and

$$A_i^0:=\{x\in X:g_i\left(x\right)=0\},A_i^1:=\{x\in X:g_i\left(x\right)=1\},\forall i\in \left[m\right].$$

Assume that 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\left(x_1\right),\dots ,g_m\left(x_m\right))$. 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 carefully consider those $\chi \in X^m$ that have many repeated entries. We introduce a notation for this first. Define the quantity

$$\alpha \left(\chi \right):=\underset{I\subset \left[m\right]}{max}|\{{\chi }_i={\chi }_j\forall i,j\in I\}|,$$

as 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\left(x_1\right),\dots ,g_m\left(x_m\right)$ if $\alpha \left(\chi \right)\le \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.

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

The proof can be found in ([7] Theorem 3).

4.6. Final Steps of the Triangle Finding

We continue here to complete step 3.2 of the ComputePairs procedure, armed with Theorem 4. 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_k^{\prime }$. We provide a short lemma first that ensures the conditions for the quantum searches:

Lemma 2.

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

(i):

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

(ii):

$|{\Lambda }_k(U_i,U_j)\cap \Delta (i,j,k)|\le 100·\sqrt{n}logn$ for $i,j\in \left[n^{1/4}\right]$.

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

EvaluationA

Input: Every node $v_{(i,j,k)}$ receives m elements $(u_1^{i,j,k},\dots ,u_m^{i,j,k})$ of ${\mathcal{U}}^{\prime }$

Promise: For every node $v_{i,j,k}$ and every $\mathbf{w}\in {\mathcal{U}}^{\prime },|L_{\mathbf{w}}^{i,j,k}|\le 800\sqrt{n}logn$.

Output: Each node outputs a list of exactly those $u_l^{i,j,k}$, such that there is a negative triangle in $U_i\times U_j\times u_l^{i,j,k}$.

• Every node $v_{(i,j,k)}$ for each $r\in \sqrt{n}$ routes the list $L_{\mathbf{w}}^{i,j,t}$ to node $v_{(i,j,t)}$.
• Every node $v_{(i,j,k)}$ for each $vu$ it received in step 1 sends the truth value of the inequality

  $$\begin{array}{c}\hfill \underset{w\in U_k^{\prime }}{min}\{W_{uw}+W_{wv}\}\le W_{vu}\end{array}$$

  (3)

  to the node that sent $vu$.

Each node is the source and destination of up to $800nlogn$ messages in step 1, meaning that this step can be implemented in $1600logn$ rounds. The same goes for step 2, noting that the number of messages is the same, but they need to only be single-bit messages (the truth values of the inequalities). Hence, the evaluations for Theorem 4 can be implemented in $3200logn$ rounds. Now, applying the theorem with $X={\mathcal{U}}^{\prime },\beta =800\sqrt{n}logn$, noting that then the assumptions of the theorem hold with a probability of at least $1-2/n^2$ due to Lemma 2, implies that step 3.2 is implementable in $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ 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 IdentifyClass, covered in the appendix, one needs to modify the EvaluationA 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 a different evaluation procedure EvaluationB are described; more information can also be found in [7].

4.7. Complexity

As noted previously and in [7], this APSP scheme uses $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds. Let us characterize the constants and logarithmic factors involved to assess this algorithm’s practical utility. Suppose that in each round, $2·logn$ 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 us assume $W\ll n$ and drop W.

• APSP with routing tables needs $log\left(n\right)$ distance products with witness matrices.
• Computing the $i^{th}$ distance product square for Equation (2) with a witness matrix needs up to $log\left(2^i\right)=i$ calls to FindEdges, since the entries of the matrix being squared may double each iteration. APSP and distance products together make ${\sum }_{i=1}^{\lceil log n\rceil }i=\frac{\lceil log\left(n\right)\rceil (\lceil log\left(n\right)\rceil +1)}{2}$ calls to FindEdges.
• Solving FindEdges needs $log\left(\frac{n}{60 log n}\right)$ calls to FEWP, using FindEdgesViaFEWP.
• Step 1 of ComputePairs needs up to $2·n^{1/4}$ rounds and step 2 takes up to $200logn$ rounds.
• Step 1 of IdentifyClass needs up to $20logn$ rounds.
• In step 2 of IdentifyClass, the $c_{uvw}$ are up to $\frac{1}{2}logn$ large and, hence, $\alpha$ may range up to $\frac{1}{2}logn$.
• Step 0 of the EvaluationB procedure needs $n^{1/4}$ rounds. Steps 1 and 2 of EvaluationB (or EvaluationA, in the $\alpha =0$ case) procedure use a total of $3200logn$ rounds.
• The procedure, EvaluationB (or EvaluationA), is called up to $log\left(n\right)n^{1/4}$ times for each value of $\alpha$ in step 3.2 of ComputePairs.

Without any improvements, we have the following complexity, using $3n$ in place of n for the terms of steps 3–8 due to Corollary 1:

$$\begin{array}{c}\hfill \frac{\lceil log\left(n\right)\rceil (\lceil log\left(n\right)\rceil +1)}{2}log\left(\frac{3n}{60log3n}\right)(2{\left(3n\right)}^{1/4}+220log3n+2{\left(3n\right)}^{1/4}+\\ \hfill \frac{1}{2}log3n·log3n·{\left(3n\right)}^{1/4}3200(log3n)),\end{array}$$

(4)

which we will call $f\left(n\right)$, so that $f\left(n\right)=\mathcal{O}\left(n^{1/4}{log}^6\left(n\right)\right)$, with the largest term being about $800{log}^6\left(n\right)n^{1/4}$, and we drop W to just consider the case $W\ll n$. We can solve the problem trivially in the (quantum or classical) CONGEST-CLIQUE within $nlog\left(W\right)$ 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\left(n\right)<n,$$

which requires $n>{10}^{18}$ (even with the simpler under-approximation $800{log}^6\left(n\right)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 [7] computing only APSP distances, the first term in 4 becomes simply $\lceil logn\rceil$, so that when computing only APSP distances, the advantage over the trivial strategy begins at roughly $n\approx {10}^{16}$.

Remark 4.

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\left(n\right)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 the 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 1, we make no assumption on the memory capacities of each node, the trivial n-round strategy uses at least ${2log\left(n\right)|E|}^2·log\left(W\right)$ 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\left(n\right)·log\left(nW\right)$ 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\left(n\right)log\left(nW\right)$ needed in step 0 of the EvaluationB 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·{10}^{10}$.

4.7.2. Complexity of the Classical Analog

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 [12], which has complexity $\tilde{\mathcal{O}}\left(n^{1/3}\right)$. In their framework, the approach to finding witness matrices requires $\mathcal{O}(log{\left(n\right)}^3)$ calls to the distance product ([12] Section 3.4), and similar to our approach, $log\left(n\right)$ distance products are required. Their classical algorithm computes distance products in $\mathcal{O}\left(n^{1/3}\right)$ rounds, or under $2logn$ message bandwidth in up to

$$\begin{array}{c}\hfill 20n^{1/3}log{\left(n\right)}^4=:g\left(n\right)\end{array}$$

(5)

rounds, the details of which can be found in Appendix A.2. Then, $g\left(n\right)>n$, up until about $n\approx 2.6·{10}^{11}$. As with the quantum APSP, though this algorithm provides the best-known asymptotic complexity of $\tilde{\mathcal{O}}\left(n^{1/3}\right)$ 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 [2] or [3], suffer from the same problem of impracticality. However, the algorithm only requires $4n^{4/3}log\left(n\right)log\left(nW\right)+nlog\left(n\right)log\left(nW\right)$ memory per node, which is less than what is required for the trivial strategy, even for $n\ge 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 [7], and add an efficient routing table scheme via triangle finding in $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ rounds, with success probability $(1-1/poly(n\left)\right)$ (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 ([2] Section 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 ∞), 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}\left(1\right)$ rounds as in [6], 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 [13], 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 are found, we construct a shortest-path forest (SPF) based on the terminals of the Steiner tree.

Definition 9.

(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 \left[k\right]$.

(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\left(v\right)$ denote the parent node of v in that tree, $s\left(v\right)$ the Steiner terminal in the tree that v will be in, and $ID\left(v\right)\in \left[n\right]$ the ID of node $v\in V$. Let $\mathcal{Q}\left(v\right):=\{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\left(v\right):={\mathrm{argmin}}_{z\in \mathcal{Q}\left(v\right)}ID\left(z\right)$ using the APSP information.

2:

Each node v sets $par\left(v\right):=R_v\left(s\left(v\right)\right)$, $R_v$ being the routing table of v, and sends a message to $par\left(v\right)$ 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 DistributedSPF 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\left(v\right)$ in step 2 can also be conducted locally using routing table information and, thus, step 2 requires 1 round of communication in $n-|Z|$ classical messages, since all non-Steiner nodes send one message.

Claim 2.

After executing the DistributedSPF procedure, the trees

$T_{z_k}=(V_{z_k},E_{z_k},W)$ with $V_{z_k}:=\{v\in V:s\left(v\right)=z_k\}$ and $E_{z_k}:=\{v,par\left(v\right)\}: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\left(v\right)\in V_{z_k}$ and $\{v,par\left(v\right)\}\in E_{z_k}$ as well. Then, $par\left(par(\dots par\left(v\right)\dots )\right)=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 [13], whose steps can be implemented efficiently in the distributed setting, as in [2]. We first modify the edge weights as follows:

Partition the edges E into three sets: tree edges $E_F$, as in Definition 9, which are part of the edge set of the SPF; intra-tree edges $E_{IT}$, which are incident on two nodes in the same tree $T_i$ of the SPF; and inter-tree edges $E_{XT}$, which are incident on two nodes in different trees of the SPF. Ensuring that each node knows which of these edges it belongs to can be accomplished 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 it is part of. The edge weights are then 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\left(u\right))$ 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}\left(1\right)$ round algorithm proposed by [6]. 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 [6]. 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 conducted 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 Section 5.1, after step 1, steps 2 and 3 can each be conducted within 2 rounds. Walking through [6] reveals that the MST for step 4 can be found in 54 rounds, with an additional 2 rounds sufficing for the pruning. Hence, the overall complexity remains dominated by Equation (4). Hence, the round complexity is $\tilde{\mathcal{O}}\left(n^{1/4}\right)$, which is faster than any known classical CONGEST-CLIQUE algorithm capable of producing an approximate Steiner tree of the same approximation ratio. However, as a consequence of the full complexity obtained in Section 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 [2], making use of the APSP subroutine from [12], as discussed in Section 4.7.2, has its complexity mostly characterized by Equation (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 [13], which implements these steps in a classical, centralized manner.

6. Directed Minimum Spanning Tree Algorithm

This section focuses on establishing Theorem 2 for the directed minimum spanning tree (DMST) problem, in Definition 4. Similar to [3], we follow the algorithmic ideas first proposed by [14], implementing them in the quantum CONGEST-CLIQUE. Specifically, we will use $logn$ calls to the APSP and routing tables scheme described in Section 4, so that in our case, we retrieve complexity $\tilde{\mathcal{O}}\left(n^{1/4}\right)$ and success probability ${(1-\frac{1}{poly\left(n\right)})}^{log n}=1-\frac{1}{poly\left(n\right)}$.

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

Definition 10.

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 ∞ 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 [19], 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.

• 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$.
• 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$.

• 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}$.

• 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 step 2 is valid. Hence, at the beginning of step 3., $B_t$ is a DMST for $G_t$. The first iteration then 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}\left(n\right)$ steps of shrinking cycles. This shortcoming is remedied by a more efficient method of selecting how to shrink nodes into super vertices in [14], such that only the $logn$ shrinking cycle steps take place.

6.2. Lovasz’s Shrinking Iterations

We devote this subsection to discussing the shrinking step of [14] that will be repeated $logn$ times in place of step 2. of Edmonds’ algorithm to obtain Lovasz’s DMST algorithm.

Lovasz’s 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.

• 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.
• 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 reachable by dipaths in H from $H_j$.
• Compute the all-pairs shortest path distances in G.
• For each node $v\in V$, denote $d_j\left(v\right):=min\{d(v,u):u\in H_j\}$. For each $j=1,\dots ,C$, set ${\beta }_j:=min\{d_j\left(v\right):v\in V\left(G\right)\setminus {\mathbb{V}}_j\}$ and $U_j:=\{u\in V_j:d_j\left(u\right)\le {\beta }_j\}$.
• 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:

  $$\begin{array}{cc}\hfill W_{N^{*}{U}_j^{*}}^{*}& =min\{W_{vu}:v\in N^{*},u\in U_j^{*}\}-{\beta }_j+min\{d_j\left(u\right):u\in U_j^{*}\}\hfill \\ \hfill & \mathrm{for}\mathrm{all}j=1,\dots ,C,\mathrm{and}\hfill \\ \hfill W_{N^{*}{V}^{*}}^{*}& =min\{W_{v{V}^{*}}:v\in N^{*}\}\hfill \\ \hfill & \mathrm{for}\mathrm{all}\mathrm{the}\mathrm{simple}\mathrm{super}\mathrm{vertices}{V}^{*}\mathrm{of}{G}^{*}.\hfill \end{array}$$
• 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 [14] states that replacing (a) and (b) of step 2. in Edmonds’ DMST Algorithm, taking the new H obtained at each iteration as $H_{t+1}$ and $G^{*}$ as $G_{t+1}$, leads to no more than $\lceil logn\rceil$ shrinking iterations needed before 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}}\left(n^{1/4}\right)$ rounds by making use of quantum APSP from Section 4. In the distributed setting, processor nodes cannot directly be shrunk into super vertices. As in [3], 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 wish to merge into a super vertex involves maintaining a mapping $sID:V\to 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 11.

(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},sI{D}^{\prime })$ obtained by taking $G^{H_i}=(V,E,W^{\prime })$ with

• $W_{uv}^{\prime }=0$ if $sID\left(u\right)=sID\left(v\right)$
• $W_{uv}^{\prime }=W_{uv}+dis{t}_{G\left(A\right)}(v,C\left(H_i\right))-{\beta }_i$ if $u\in V\setminus A$ and $v\in A$
• $W_{uv}^{\prime }=W_{uv}$ otherwise

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

6.2.2. Quantum Distributed Implementation of Lovasz’s Iteration

We provide here a quantum distributed implementation of Lovasz’s iteration, which will form the core of our DMST algorithm.

Quantum distributed implementation of Lovasz’s 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 $sI{D}^{\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\left(H_i\right)$ the cycle of $H_i$. Let $c\left(H_i\right)$ be the node with maximal ID in $C\left(H_i\right)$, which each node can locally compute.

3:

Run the quantum algorithm for APSP and routing tables described in Section 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\left(H_i\right))$, 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\left(H_i\right)$ into one super vertex, with each contracted node updating its super vertex ID to $c\left(H_i\right)$

−

Add edge $v_i{u}_i$ to H, effectively merging $H_i$ with another active component of H

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

Lemma 3.

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

Lemma 4.

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

Lemmas 3 and 4 then together imply Theorem 2. Within $\lceil logn\rceil$ iterations, only one active component remains, i.e., the root component. This active component can then be expanded to a full DMST on G within $\lceil logn\rceil$ rounds, as detailed in ([3] Section 7) or the Unpacking procedure in Appendix A.3. All messages in the algorithm, other than those for computing the APSP in QDLSI, 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.

• 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 $sI{D}_0$ to be the identity mapping.
• WHILE: $H_t$ is not a single component

  (a)

  Run QDLSI with inputs $H_t$, $(G_t,sI{D}_t)$ to obtain $H_{t+1}$, $(G_{t+1},sIDt+1)$ as outputs. Increment $t\leftarrow t+1$.

• Let $T_t:=H_t$. For $k=t,\dots ,1$: For each super vertex of the $k^{th}$ iteration of QDLSI applied, simultaneously run the Unpacking procedure with input tree $T_k$ to obtain $T_{k-1}$.
• Return $T_0$ as the distributed minimum spanning tree.

6.3. Complexity

In QDLSI, 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\left(n\right)\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}}\left(n^{1/4}\right)$, a better asymptotic rate than any known classical CONGEST-CLIQUE algorithm. However, beyond the $\tilde{\mathcal{O}}$, the complexity is largely characterized by $log\left(n\right)·f\left(n\right)$, with $f\left(n\right)$, as in Equation (4). In order to have $log\left(n\right)f\left(n\right)<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 [12] in place of the quantum APSP of Section 4, as conducted in [3] to attain the $\tilde{\mathcal{O}}\left(n^{1/3}\right)$ complexity in the cCCM, one would need $log\left(n\right)·g\left(n\right)<n$ to beat the trivial strategy, with g, as in Equation (5), or more than $n>{10}^{14}$.

7. Discussion and Future Work

We 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 trees 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 [20]. 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. Reference [21] provides a classical distributed approximation algorithm for the problem. Additionally, we 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 in which the practicality of algorithms is affected by logarithmic factors that may be obscured by the $\tilde{\mathcal{O}}$ notation and, thus, encourage fellow researchers to present the full complexity of their algorithms beyond asymptotics. Particularly in a model such as 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?