## 4 APSP and Routing Tables
### Triangle Finding  
Given the results from Sections 4.2 and 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}}(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 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}(\log n)\) 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\). 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}{60\log n}\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)\varepsilon_{\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}=[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 a 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},\ldots,i\cdot n^{3/4}\}\}\) for \(i=1,\ldots,n^{1/4}\), and \(\mathcal{U}:=\{U_{1},\ldots,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^{\prime}_{i}:=\{v_{j}:j\in\{(i-1)\cdot\sqrt{n},\ldots,i\cdot\sqrt{n}\}\}\) for \(i=1,\ldots,\sqrt{n}\), and \(\mathcal{U}:=\{U_{1},\ldots,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. 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}^{t})\) 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\).