## 6 Directed Minimum Spanning Tree Algorithm
### Edmonds' Centralized DMST Algorithm
#### 6.2.2 Quantum Distributed Implementation of [PERSON]'s Iteration  
We provide here a quantum distributed implementation of [PERSON]'s iteration, which will form the core of our DMST algorithm.  
Quantum distributed implementation of [PERSON]'s iteration QDLSI  
Input: A directed, weighted, graph \(G=(V,E,W)\) with annotations \(sID\) and a subgraph \(H\).  
Output: A new graph \(G^{*}\) with annotations \(sID^{\prime}\), or a success flag and a DMST \(H\) of \(G\).  
1: Have all nodes learn all edges of \(H\), as well as the current super vertices.
2: For each connected component \(H_{i}\subset H\), denote by \(C(H_{i})\) the cycle of \(H_{i}\). Let \(c(H_{i})\) be the node with maximal ID in \(C(H_{i})\), which each node can locally compute.
3: Run the quantum algorithm for APSP and routing tables described in Section 4 on this graph, or report a failure if it fails.
4: For each \(i\), determine an edge \(v_{i}u_{i}\), \(v_{i}\
otin H_{i},u_{i}\in H_{i}\) minimizing \(\beta_{i}:=W_{v_{i}u_{i}}+d_{G}(u_{i},c(H_{i}))\), and broadcast both to all nodes in \(H_{i}\).
5: Each node \(v_{i}\) in each \(H_{i}\) applies the following updates _locally_: * Soft contract \(H_{i}\) at level \(\beta_{i}\) to soft-contract all super vertices with distance \(\beta_{i}\) to \(C(H_{i})\) into one super vertex, with each contracted node updating its super vertex ID to \(c(H_{i})\) * Add edge \(v_{i}u_{i}\) to \(H\), effectively merging \(H_{i}\) with another active component of \(H\)  
We can follow the steps of [PERSON]'s DMST algorithm, distributedly, by replacing steps 2-5 with LSI with this quantum-distributed version. The following ensues:  
Lemma 3: _If none of the APSP and routing table subroutines fail, within \(\lceil\log n\rceil\) iterations of QDLSI, \(H\) is a single connected component._  
Lemma 4: _With probability \((1-\frac{1}{poly(n)})^{\log n}\), all the APSP and routing table subroutines in step 3 succeed._  
Lemmas 3 and 4 then together imply Theorem 2. Within \(\lceil\log n\rceil\) iterations, only one active component remains, i.e., the root component. This active component can then be expanded to a full DMST on \(G\) within \(\lceil\log n\rceil\) rounds, as detailed in ([3] Section 7) or the Unpacking procedure in Appendix A.3. All messages in the algorithm, other than those for computing the APSP in QDLSI, may be classical. We provide here the full algorithm for completeness:Quantum DMST Algorithm  
Input: An integer-weighted digraph and a root node \(r\).  
Output: A DMST for \(G\) rooted at \(r\).  
1. Initialize a subgraph \(H\) with the same vertex set as G by subtracting for each node the minimum incoming edge weight from all its incoming edges, and selecting exactly one incoming zero-weight edge for each non-root node of \(G\). Set \(t=0,H_{0}=H\), and \(G_{0}=G\) with annotations \(sID_{0}\) to be the identity mapping.
2. WHILE: \(H_{t}\) is not a single component 1. Run QDLSI with inputs \(H_{t}\), \((G_{t},sID_{t})\) to obtain \(H_{t+1}\), \((G_{t+1},sIDt+1)\) as outputs. Increment \(t\gets t+1\).
3. Let \(T_{t}:=H_{t}\). For \(k=t,\ldots,1\): For each super vertex of the \(k^{th}\) iteration of QDLSI applied, simultaneously run the Unpacking procedure with input tree \(T_{k}\) to obtain \(T_{k-1}\).
4. Return \(T_{0}\) as the distributed minimum spanning tree.