## 2 Background and Setting
### Quantum Versions of CONGEST and CONGEST-CLIQUE
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\rightarrow\{0,1\}\), suppose that there exists a classical procedure \(\mathcal{C}\) in the cCCM that allows \(u\) to compute \(g(x)\), 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(x)=i\}\), for \(i=0,1\), and suppose that \(0<|A_{1}|\leq|X|/2\). Classically, node \(u\) can then find an \(x\in A_{1}\) in \(\mathcal{O}(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 \(\mathcal{O}(r\sqrt{|X|})\) 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}(u)\), we denote by \(\mathcal{I}_{v}:V\rightarrow\{0,1\}\) the indicator function of \(\mathcal{N}_{G}(v)\), and by \(g_{uv}:\mathcal{N}_{G}(u)\rightarrow\{0,1\}\) its restriction to inputs in \(\mathcal{N}_{G}(u)\). Classically, node \(u\) can evaluate \(g_{uv}(w)\) in two rounds for any \(w\in\mathcal{N}_{G}(u)\) by sending the ID of \(w\) (of length \(\log n\)) to \(v\), and having \(v\) send back the answer \(\mathcal{I}_{v}(w)\). \(u\) can then check \(g_{uv}(w)\) for each \(w\in\mathcal{N}_{G}(u)\) one at a time to determine whether \(uv\) is part of a triangle in \(G\) or not in \(2\cdot|\mathcal{N}_{G}(u)|\) rounds. For the distributed quantum implementation, \(u\) can instead initialize a register of \(\log n\) qubits as \(|\psi\rangle_{0}:=\frac{1}{\sqrt{|\mathcal{N}_{G}(u)|}}\sum_{x\in\mathcal{N}_ {G}(u)}|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}(x)\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}(u)\) satisfying \(g_{uv}(w)=1\) with high probability in \(\tilde{\mathcal{O}}(r\sqrt{|\mathcal{N}_{G}(u)|})\) 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}(u)\) (and sending this information to \(v\) would take \(|\mathcal{N}_{G}(u)|\) rounds), though it is able to evaluate \(\mathcal{I}_{v}\) in superposition for any \(w\in\mathcal{N}_{G}(u)\). 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.