## Appendix A
### 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_{k}^{t}\) before starting the search. To assign each node to a class, we use the routine IdentifyClass of [7], also described in the main text. The main body of this paper discusses 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}\) as the smallest nonnegative integer satisfying \(d_{i,j,k}<10\cdot 2^{c}\log n\), and  
\[V_{\alpha} :=\{v_{(i,j,k)}:c_{i,j,k}=\alpha\} \tag{11}\] \[V_{\alpha}[i,j] :=\{U_{k}^{\prime}\in\mathcal{U}^{\prime}:v_{(i,j,k)}\in V_{ \alpha}\} \tag{12}\]  
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\). The IdentifyClass algorithm and the resulting \(V_{\alpha}\) satisfy the following statements with a probability of at least \(1-2/n\):  
1. [label=()]
2. The algorithm does not abort
3. \(|\Delta(i,j,k)|\leq 2n\)
4. 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\). 5. \(|\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 2 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 EvaluationB procedure. For all \(\alpha\geq 0\) and \(i,j\in[n^{1/4}]\),  
\[|V_{\alpha}[i,j]|\leq\frac{720\sqrt{n}\log n}{2^{\alpha}} \tag{13}\]  
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 2, the conclusion follows. We now describe the implementation of step 3 of the ComputePairs procedure for the \(\alpha>0\) case. 1. [label=3.0]
2. Each node executes the IdentifyClass procedure. 3. 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_{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}\) was found. The \(\alpha=0\) case was described in the main text. We proceed to describe the classical procedure for invoking Theorem 4.2 to obtain the speedup for the general \(\alpha\) case, as in ([7] Section 5.3.2). Some technical precautions must be taken to avoid the congestion of messages between nodes. This crucially relies on information duplication to effectively increase the bandwidth between nodes. Lemma 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 labelingscheme is convenient. Suppose for simplicity that \(C_{\alpha}:=2^{\pi}/(720\log n)\) is an integer, and assign each node a label \((\mathbf{u},\mathbf{v},\mathbf{w},y)\in V_{\alpha}\times[C_{\alpha}]\), which is possible due to the bound of Lemma A2.