## 2 Background and Setting
### Quantum Versions of CONGEST and CONGEST-CLIQUE  
The quantum models we work in are obtained via the following modification: Instead of restricting to messages of \(\mathcal{O}(\log(n))\) classical bits, we allow messages to consist of \(\mathcal{O}(\log(n))\) quantum bits, i.e., qubits. For background on qubits and the fundamentals of quantum computing, we refer the reader to [16]. We formally define the qCCM, the setting for our algorithms, as follows:  
**Definition 1** (Quantum CONGEST-CLIQUE). : _The quantum CONGEST-CLIQUE model (qCCM) is a distributed computation model in which an input graph \(G=(V,E,W)\) is distributed over a network of \(n\) processors, where each processor is represented by a node in \(V\). Each node is assigned a unique ID number in \([n]\). Time passes in rounds, each of which consists of the following:_  
1. _Each node may execute unlimited local computation._
2. _Each node may send a message consisting of either a register of_ \(\mathcal{O}(\log n)\) _qubits or a string of_ \(\mathcal{O}(\log n)\) _classical bits to every other node in the network. Each of those messages may be distinct._
3. _Each node receives and saves the messages the other nodes send it._  
_The input graph \(G\) is distributed across the nodes as follows: Each node knows its own ID number, the ID numbers of its neighbors in \(G\), the number of nodes \(n\) in \(G\), and the weights corresponding to the edges it is incident upon. The output solution to a problem must be given by having each node \(v\in V\) return the restriction of the global output to \(\mathcal{N}_{G}(u):=\{v:uv\in E\}\), its neighborhood in \(G\). No entanglement is shared across nodes initially._  
This is an analog of the cCCM, except that quantum bits may be sent in place of classical bits. To clarify the output requirement, in the Steiner tree problem, we require node \(u\) to output the edges of the solution tree that are incident upon \(u\). Since many messages in our algorithms need not be sent as qubits, we define the qCCM slightly unconventionally, allowing either quantum or classical bits to be sent. We specify those that may be sent classically. However, even without this modification, the quantum versions of CONGEST and cCCM are at least as powerful as their classical counterparts. This is because any \(n\)-bit classical message can be instead sent as an \(n\)-qubit message of unentangled qubits; for a classical bit reading \(0\) or \(1\), we can send a qubit in the state \(|0\rangle\) or \(|1\rangle\), respectively, and then take measurements with respect to the \(\{|0\rangle,|1\rangle\}\) basis to read the same message the classical bits would have communicated. Hence, one can also freely make use of existing classical algorithms in the qCCM. Further, the assumption that IDs are in \([n]\), with \(n\) known, is not necessary but is convenient; without this assumption, we could have all nodes broadcast their IDs to the entire network and then assign a new label in \([n]\) to each node according to an ordering of the original IDs, resulting in our assumed situation. Remark 1: _Definition 1 does not account for how the information needs to be stored. In this paper, it suffices for all information regarding the input graph to be stored classically as long as there is quantum access to that data. We provide some details on this in Appendix A.4._  
Remark 2: _No initial entanglement being shared across nodes, as outlined in Definition 1, results in quantum teleportation not being a straightforward method to solve problems in the qCCM._  
Example 1: _To provide some intuition on how allowing communication through qubits in this distributed setting can be helpful, we now describe and give an example of the distributed Grover search, first described in [11]. The high-level intuition for why quantum computing provides an advantage for search is that quantum operations use quantum interference effects to have canceling effects among non-solutions.