## 4 APSP and Routing Tables
### Triangle Finding
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_{vv}\) for all \(uv\in\mathcal{P}(U_{i},U_{j})\) and \(vw\in\mathcal{P}(U_{j},U_{k}^{t})\). 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 \(Wu\) for all of those pairs. Denote those elements of \(\Lambda_{k}(U_{i},U_{j})\cap S\) as \(u_{1}^{k}v_{1}^{k},\ldots,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_{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{\log W}{\log n}\rceil\) rounds and can be fully implemented 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 the 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 conducted in \(\tilde{\mathcal{O}}(n^{1/4})\) 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}\text{ with }(u,v,w)\text{ forming a negative triangle 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(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:\;\exists w\in U_{k}^{t}\), 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 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\leq\frac{1}{2}\log n\), so we can run successive searches for each \(\alpha\) for nodes in class \(\alpha\) in the general case. The general case is discussed in A.2 and can also be found in [7], but this case is sufficient to convey the central ideas.