## Appendix A
### Expanding the DMST in the Distributed Setting  
We handle the expansion of the DMST in the same way as in ([3] Section 7), borrowing much of their discussion for our description here. However, as we have computed APSPdistances along the way in place of SSSP, 'unpacking' the DMST becomes a bit simpler in our case. Consider a component \(H_{i}\) in one of the iterations of \(\mathtt{DDLSI}\), with the input graph for the iteration being \(G_{i}\). For each contraction in \(\mathtt{DDLSI}\), we determined edges \(v_{i}u_{i}\), \(v_{i}\
Unpacking  
Input: A digraph \(G_{i+1}\) with a DMST \(T_{i+1}\) with root \(r\), a set of edges \(H_{i}\) as in Quantum DMST Algorithm, a node \(V^{*}_{H_{i},\beta_{i}}\) of \(G_{i+1}\), which is marked as a super vertex, a set \(c(H_{i})\) of the nodes contracted into it, and \(G_{i}\) is the graph before contracting \(c(H_{i})\). Output: A DMST \(T_{i}\) for \(G_{i}\) rooted at \(r\). ```
1: For any \(v_{1},v_{2}\
otin V^{*}_{H_{i},\beta_{i}}\), let edge \(v_{1}v_{2}\in T_{i}\) if \(v_{1}v_{2}\in T_{i+1}\). 2: For \(uV^{*}_{H_{i},\beta_{i}}\in T_{i+1}\), which exists since \(T_{i+1}\) is a DMST for \(G_{i+1}\), denote the edge \(uv^{*}:=argmin_{uv:v\in V^{*}_{H_{i},\beta_{i}}:u\coloneqq uv\in G_{i+1}}W_{ uu}+d_{G}(u,c(H_{i}))\). Add \(uv^{*}\) and the shortest path \(\zeta\) connecting \(v^{*}\) to \(c(H_{i})\) to \(T_{i}\). 3: For any edge \(V^{*}_{H_{i},\beta_{i}}u\in T_{i+1}\) outgoing from the contracted super vertex, add the edge \(argmin_{uv:v\in V^{*}_{H_{i},\beta_{i}}}W^{G_{i}}_{vui}\) to \(T_{i}\). 4: Add all edges \(H_{i}\setminus\delta^{in}(\zeta)\) to \(T_{i}\), where \(\delta^{in}(\zeta)\) denotes all edges incoming on \(\zeta\). ```  
At the end of this procedure, \(T_{i}\) is a DMST for \(G_{i}\) ([3], lemma 8). We now describe how it can be implemented distributedly, needing only classical messages and information. For every contracted super vertex, the following steps can be implemented at the same time, as will become clear in how the steps are executed for the nodes of each contracted super vertex. Let us focus on unpacking one super vertex \(V^{*}_{H_{i},\beta_{i}}\). Each node knows its neighbors in \(G_{i}\), and every node's super vertex ID in \(G_{i}\) and \(G_{i+1}\), since each node stores this information before the initial contraction to \(G_{i+1}\) in \(\mathtt{DDLSI}\) happens. Hence, step 1 can be conducted locally at each node without any communication. Step 2 can be conducted by first having each node \(v\in V^{*}_{H_{i},\beta_{i}}\) send \(\beta(u,v)\) to the other nodes in \(V^{*}_{H_{i},\beta_{i}}\), in one round, and then having each node of \(V^{*}_{H_{i},\beta_{i}}\) send to \(v^{*}\) the routing table entry corresponding to its shortest path to \(c(H_{i})\) in \(G_{i}\), also in one round (the nodes have already computed this information in \(\mathtt{DDLSI}\). \(v^{*}\) then notifies the nodes that are part of \(\zeta\), which can then add the appropriate edge to \(T_{i}\), needing yet another round, so that step 2 can be conducted in three rounds of classical communication only. Step 3 is handled similarly. For the outgoing edge, each node in \(V^{*}_{H_{i},\beta_{i}}\) sends \(W^{G_{i}}_{vui}\) to the other nodes in \(V^{*}_{H_{i},\beta_{i}}\) so that the appropriate edge to add to \(T_{i}\) can be determined (in case of a tie, the node with a smaller ID can be the one to add the edge), so this can be conducted in one round. For step 4, every node in \(\zeta\) notifies its neighbors that it is in \(\zeta\), after which, every node can determine which edges to add to \(T_{i}\). For the unpacking of \(V^{*}_{H_{i},\beta_{i}}\), the information and communication for implementing its unpacking is contained in the nodes of \(V^{*}_{H_{i},\beta_{i}}\), so we can indeed unpack all vertices synchronously to obtain \(G_{i}\), even when multiple super vertices are contracted to obtain \(G_{i+1}\).