## 4 APSP and Routing Tables
### Complexity  
As noted previously and in [7], this APSP scheme uses \(\hat{\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 us assume \(W\ll n\) and drop \(W\).  
1. APSP with routing tables needs \(\log(n)\) distance products with witness matrices.
2. Computing the \(i^{th}\) distance product square for Equation (2) with a witness matrix needs up to \(\log\bigl{(}2^{i}\bigr{)}=i\) calls to FindEdges, since the entries of the matrix beingsquared may double each iteration. 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 FindEdges.
3. Solving FindEdges needs \(\log\Bigl{(}\frac{n}{60\log n}\Bigr{)}\) calls to FEWP, using FindEdgesViaFEWP.
4. Step 1 of ComputePairs needs up to \(2\cdot n^{1/4}\) rounds and step 2 takes up to \(200\log n\) rounds.
5. Step 1 of IdentifyClass needs up to \(20\log n\) rounds.
6. In step 2 of IdentifyClass, 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. 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 \(3200\log n\) rounds.
8. The procedure, EvaluationB (or EvaluationA), is called up to \(\log(n)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:  
\[\frac{\lceil\log(n)\rceil(\lceil\log(n)\rceil+1)}{2}\log \biggl{(}\frac{3n}{60\log 3n}\biggr{)}\Bigl{(}2(3n)^{1/4}+220\log 3n+2(3n)^{1/4}+\] \[\frac{1}{2}\log 3n\cdot\log 3n\cdot(3n)^{1/4}3200(\log 3n) \Bigr{)}, \tag{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 drop \(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 [7] computing only APSP _distances_, the first term in 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: _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 the practicality of algorithms, and researchers should be encouraged to fully write out the exact complexities of their algorithms for the same reason._