# A quantum walk-based scheme for distributed searching on arbitrary graphs

Mathieu Roget, Giuseppe Di Molfetta

► To cite this version:

Mathieu Roget, Giuseppe Di Molfetta. A quantum walk-based scheme for distributed searching on arbitrary graphs. 2025. hal-05068072

HAL Id: hal-05068072

https://hal.science/hal-05068072v1

Preprint submitted on 14 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A quantum walk-based scheme for distributed searching on arbitrary graphs

Mathieu Roget¹,²[0000-0003-3890-1552] and Giuseppe Di Molfetta¹,²[0000-0002-1261-7476]

¹ Laboratoire d'Informatique et Systèmes, Marseille, France

² Université Aix-Merseille, Marseille, France

**Abstract.** A discrete time quantum walk is known to be the single-particle sector of a quantum cellular automaton. Searching in this mathematical framework has interested the community since a long time. However, most results consider spatial search on regular graphs. This work introduces a new quantum walk-based searching scheme, designed to search nodes or edges on arbitrary graphs. As byproduct, such new model allows to generalise quantum cellular automata, usually defined on regular grids, to quantum anonymous networks, allowing a new physics-like mathematical environment for distributed quantum computing.

**Keywords:** Quantum Distributed Algorithm · Quantum Walk · Quantum Cellular Automata · Quantum Anonymous Network · Searching Algorithm

## Introduction

Quantum Walks (QW), from a mathematical point of view, coincide with the single-particle sector of quantum cellular automata (QCA), namely a spatially distributed network of local quantum gates. Usually defined on a *d*-dimensional grid of cell, they are known to be capable of universal computation [1]. Both quantum walks and quantum cellular automata, with their beginnings in digital simulations of fundamental physics [4, 6], come into their own in algorithmic search and optimization applications [12]. Searching using QW has been extensively studied in the past decades, with a wide range of applications, including optimisation [13] and machine learning [10]. On the other hand, search algorithms as a field independent of quantum walks have recently been used, as subroutines, to solve distributed computational tasks [7–9]. However, in all these examples, some global information is supposed to be known by each node of the network, such as the size, and usually the network is not anonymous, namely every node has a unique label. Note that, the absence of anonymity and the quantum properties of the algorithm successfully solves the incalculability of certain problems such as the leader election problem. However, encoding global information within a quantum state is generally problematic. In order to address such issue, here we first introduce a new QW-based scheme on arbitrary
graphs for rephrasing search algorithms. Then we move to the multi-states generalisation, which successfully implement a QCA-based distributed anonymous protocol for searching problems, avoiding any use of global information.

*Contribution* Section 1 of this work introduces a Quantum Walk model well suited to search indifferently a node or an edge in arbitrary graphs. In this model the walker's amplitudes are defined onto the graph's edges and ensures 2-dimensional coin everywhere. We detail how this Quantum Walk can be used to search a node or an edge and we show examples of this Quantum Walk on several graphs. In this first part, the Quantum Walk is introduced formally as a discrete dynamical system. In Section 2 we move to the multi-particle sector, allowing a many quantum states-dynamics over the network, based on the previous model, and leading to a distributed search protocol 2. For the coin and the scattering, local quantum circuits and distributed algorithms are provided. The implementation proposed conserves the graph locality and does not require a node or an edge to have global information like the graph size. The nodes (and edges) do not have unique label, and no leader is needed.

# 1 Mathematical model of quantum walk on graphs

This section introduces the quantum walk searching algorithm on undirected connected graphs. First we introduce the quantum walk model on graph and give an example. Then we explain how such a quantum walk can be used to search a marked edge or a marked node. Finally, we show two examples of searching : in the first one we look for an edge and in the second one we look for a node. Finally we derive the asymptotic complexities.

## 1.1 Quantum walk model on graphs

We consider an undirected connected graph $G = (V, E)$, where $V$ is the set of vertices and $E$ the set of edges. We define the walker's position on the graph's edges and a coin register of dimension two (either + or -). The full state of the walker at step $t$ is noted :

$$|\Phi_t\rangle = \sum_{(u,v) \in E} \psi_{u,v}^{+} |(u,v)\rangle|+\rangle + \psi_{u,v}^{-} |(u,v)\rangle|-\rangle.$$

The graph is undirected so we indifferently use $|(u, v)\rangle$ and $|(v, u)\rangle$ to name the same state. Similarly for the complex amplitudes $\psi_{u,v}^{+}(t) = \psi_{u,v}^{-}(t)$. We also introduce a polarity for every edge of $G$. For each of them, we have a polarity function $\sigma$, such that : $\forall(u, v) \in E$, $\sigma(u, v) \in \{+, -\}$ and $\sigma(u, v) \neq \sigma(v, u)$. Figure 1 illustrates how amplitudes and polarity are placed with edge $(u, v)$ of polarity $\sigma(u, v) = 1$. The polarity is a necessary and arbitrary choice made at the algorithm's initialization *independently for every edge*. We discuss why it is necessary and a way to make that choice at the end of this section. The full
<figure><img src="image_2.png" /><figcaption>Fig. 1: The edge $(u, v)$ and how are placed the amplitudes for the two possible polarities.</figcaption></figure>

unitary evolution of the walk reads: $|\Phi_{t+1}\rangle = S \times (I \otimes C) \times |\Phi_t\rangle$, where C is the local coin operation acting on the coin register:

$$ \forall (u, v) \in E, \quad |(u, v)\rangle|\pm\rangle \xrightarrow{\text{coin}} (I \otimes C) \times |(u, v)\rangle|\pm\rangle = |(u, v)\rangle\langle C|\pm\rangle. $$

and S is the scattering which moves the complex amplitudes $\alpha_{u,v}^{\pm}$ according to the coin state:

$$ \forall u \in V, \quad (\psi_{u,v}^{\sigma(u,v)})_{v \in V} \xrightarrow{\text{scattering}} D_{\text{deg}(u)} \times (\psi_{u,v}^{\sigma(u,v)})_{v \in V}, $$

where $D_n = \begin{pmatrix} 2 \\ n \end{pmatrix}_{i,j} - I_n$.

As an example of the above dynamics, one can consider the path of size 3 with the nodes $\{u, v, w\}$, with polarity $\sigma(u, v) = \sigma(v, w) = +$. Figure 2 shows the unitary evolution of the walker from step t to step t + 1, when the coin coincide the first Pauli matrix X.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Example of a walk on a path of size 3.</figcaption></figure>

*Polarity: why and how* There are two reasons we need polarity. First, if the coin operator acts differently on $|+\rangle$ and $|-\rangle$, then different polarities lead to
that characterize the above algorithm : the probability of success *P* of returning the marked edge and the hitting time *T*. The number of oracle calls of this algorithm is *O*(*T*). In practice, we want to choose *T* such that *P* is maximal. The previous algorithm can easily be made into a Las Vegas algorithm whose answer is always correct but the running time random. Algorithm 2 shows such transformation. Interestingly, the expected number of times Algorithm 2 calls Algorithm 1 is *O*(1/*P*) where *P* is the probability of success of Algorithm 1. The expected complexity of Algorithm 2 is *O*(*T*/*P*). The complexity of our algorithm

<caption>**Algorithm 2** Search a marked edge with guaranteed success</caption>

Require: $G = (V, E)$ undirected, connected graph
Require: $f$, the classical oracle
Require: $T \in \mathbb{N}$ the hitting time
1: **function** GUARANTEEDSEARCH(G, $f, T$)
2: &nbsp;&nbsp;&nbsp;&nbsp;$(u, v) \leftarrow (\mathbf{nil}, \mathbf{nil})$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Initial value
3: &nbsp;&nbsp;&nbsp;&nbsp;**while** $f((u, v)) \neq 1$ **do** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Until we find the marked edge ...
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(u, v) \leftarrow \text{SEARCH}(G, f, T)$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ ... search again.
5: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
6: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(u, v)$
7: **end function**

is limited by the optimal complexity of $O(\sqrt{K})$ for searching problem where $K$ is the total number of elements. This is the complexity of the Grover algorithm which has been shown to be optimal [15]. However Grover's algorithm assume full connectivity between elements which is not our case. The quantum walk presented here is on the edge of $G$, which means that the optimal complexity is $O(\sqrt{|E|})$.

1.3 Example : Searching an edge in the star graph

In this example we consider the star graph with *M* edges and *M* + 1 nodes; a graph with *M* + 1 nodes where every node (other than node *u*₀) is connected to node *u*₀. Our searching algorithm performs well on this graph, as shown by Theorem 1. In this section, we show the proof of Theorem 1 which is mainly spectral analysis on a simplified dynamic.

**Theorem 1.** Let $G$ be the star graph with $M$ edges. Algorithm 1 has an optimal hitting time $T = O(\sqrt{M})$ and a probability of success $O(1)$ for $G$. Algorithm 2 has expected complexity $O(\sqrt{M})$.

*Proof.* We consider the star graph $G = (V, E)$ of size $M + 1$ such that $V = \{u_0, \dots, u_M\}$ and $E = \{(u_0, u_i) | 1 \le i \le M\}$. We assume without a loss of generality that the marked edge is $(u_0, u_1)$ and that the polarity is $\forall i >$
1, $\sigma(u_0, u_i) = +$. At any time step $t$, the state of the walk reads $|\Phi_t\rangle = \sum_{i=1}^M \psi_{u_0, u_i}^+(t) |(u_0, u_i)\rangle|+\rangle + \psi_{u_0, u_i}^-(t) |(u_0, u_i)\rangle|-\rangle$. We first show that $\forall t \in \mathbb{N}$, $\forall i > 1$, $\psi_{u_0, u_i}^+(t) = \alpha_t^+$ and $\psi_{u_0, u_i}^-(t) = \alpha_t^-$ for all $t \in \mathbb{N}$.

The initial state $|\Psi_0\rangle$ is diagonal on the basis states :

$$|\Phi\rangle \leftarrow \frac{1}{\sqrt{2|E|}} \sum_{(u,v) \in E} |(u,v)\rangle|+\rangle + |(u,v)\rangle|-\rangle.$$

All $(\psi_{u_0, u_i}^{\pm}(0))_{i \ge 1}$ are equals so the property $Q_0$ is satisfied with $\alpha_t^+ = \alpha_t^- = \frac{1}{\sqrt{2M}}$. Now, we assume that $Q_t$ is true and use the walk dynamic to show that $Q_{t+1}$ is also true. The state $|\Psi_{t+1}\rangle$ is described in Table 1 and show that $Q_{t+1}$ is true.

<table><caption>Table 1: Detailed dynamic of the quantum walk for star graphs.</caption><thead><tr><th></th><th>Step t</th><th>After oracle</th><th>After coin</th><th>After Scattering</th></tr></thead><tbody><tr><td>$\alpha^+$</td><td>$\alpha_t^+$</td><td>$\alpha_t^+$</td><td>$\alpha_t^-$</td><td>$\alpha_{t+1}^+ = \frac{(M-2)\alpha_t^- - 2\psi_{u_0,u_1}^+}{M}(t)$</td></tr><tr><td>$\alpha^-$</td><td>$\alpha_t^-$</td><td>$\alpha_t^-$</td><td>$\alpha_t^+$</td><td>$\alpha_{t+1}^- = \alpha_t^+$</td></tr><tr><td>$\psi_{u_0,u_1}^+$</td><td>$\psi_{u_0,u_1}^+(t)$</td><td>$-\psi_{u_0,u_1}^-(t)$</td><td>$-\psi_{u_0,u_1}^+(t)$</td><td>$\psi_{u_0,u_1}^+(t+1) = \frac{(2M-2)\alpha_t^- + (M-2)\psi_{u_0,u_1}^+}{M}(t)$</td></tr><tr><td>$\psi_{u_0,u_1}^-$</td><td>$\psi_{u_0,u_1}^-(t)$</td><td>$-\psi_{u_0,u_1}^+(t)$</td><td>$-\psi_{u_0,u_1}^-(t)$</td><td>$\psi_{u_0,u_1}^-(t+1) = -\psi_{u_0,u_1}^-(t)$</td></tr></tbody></table>

Using the recurrence in Table 1, we can put the dynamic of the walk into a matrix form.

$$\psi_{u_0, u_1}^{-}(t) = \frac{(-1)}{\sqrt{2M}} \quad \text{and} \quad X_{t+1} = AX_t,$$

where

$$X_t = \begin{pmatrix} \alpha_t^+ \\ \alpha_t^- \\ \psi_{u_0, u_1}^+(t) \end{pmatrix} \quad \text{and} \quad A = \begin{pmatrix} 0 & \frac{M-2}{M} & \frac{-2}{M} \\ 1 & 0 & 0 \\ 0 & 2\frac{M-1}{M} & \frac{M-2}{M} \end{pmatrix}.$$

After diagonalizing $A$, the eigenvalues are $\{-1, e^{i\lambda}, e^{-i\lambda}\}$, where $e^{i\lambda} = \frac{M-1+i\sqrt{2M-1}}{M}$. This leads to $\psi_{u_0, u_1}^+(t) \sim \frac{i}{2}(e^{-i\lambda t} - e^{i\lambda t}) \sim \sin(\lambda t)$, which allows us to deduce the probability $p_t$ of hitting the marked edge $p_t \sim \sin^2(\lambda t)$, and then the optimal hitting time by solving $p_T = 1$:

$$T = \frac{\pi}{2} \frac{1}{\lambda} \sim \frac{\pi}{2} \sqrt{\frac{M}{2}} \sim \frac{\pi}{2\sqrt{2}} \sqrt{M} = O(\sqrt{M}).$$
Finally we have a probability of success $P \sim 1$ for the optimal hitting time
$T \sim \frac{\pi}{2\sqrt{2}}\sqrt{M} = O(\sqrt{M})$.

## 1.4 Searching nodes

The searching quantum walk presented in the previous section can search one marked edge in a graph. In order to search a node instead, we need to transform the graph we walk on. We call this transformation STARIFY.

**Definition 1.** STARIFY

Let us consider an undirected graph $G = (V, E)$. The transformation STARIFY on $G$ returns a graph $\tilde{G}$ for which

- every node and edge in $G$ is in $\tilde{G}$ (we call them real nodes and real edges).

- for every node $u \in V$, we add a node $\tilde{u}$ (we call these new nodes virtual nodes).

- for every node $u \in V$, we add the edge $(u, \tilde{u})$ (we call these new edges virtual edges).

We call the resulting graph $\tilde{G}$ the starified graph of $G$.

**Searching nodes** Starifying a graph $G$ allows us to search a marked node $u$ instead of an edge. We can then use the previous searching walk to search the virtual edge and then deduce without ambiguity the marked node $u$ of the initial graph $G$. This procedure implies that we have to increase the size of the graph (number of edges and nodes). In particular, increasing the number of edges is significant since we increase the dimension of the walker (this can be significant for sparse graphs) and one must be careful of this when computing the complexity. A reassuring result is that searching a node on the complete graph (the strongest possible connectivity) has optimal complexity. As stated in Theorem 2, the complexity is $O(\sqrt{M})$, which is optimal when searching over the edges. Compared to a classical algorithm in $O(M)$ (a depth first search for instance), we do have a quadratic speedup.

**Theorem 2.** When using the quantum algorithm to search one marked node in the starified graph $\tilde{G}$ of the complete graph $G$ of size $N$, the probability of success is $P \sim 1$ and the hitting time $T \sim \frac{\pi}{4}N$.

*Proof.* The proof is very similar to the one of Theorem 1. We show that several edges have the same states to reduce the dynamic to a simple recursive equation. We then solve it numerically and derive asymptotic values for the probability of success. A detailed proof shall be provided in the supplementary materials.
## 2 Distributed Implementation

In this section we move to the multi-particle states dynamics, allowing a distributed implementation of the above searching protocol. We assume that both nodes and edges have quantum and classical registers. They can transmit classical bit and apply controlled operations over the local neighborhood. The nodes need to know their degree but do not require a unique label. We first explain how the quantum registers are dispatched along the graph, then we introduce a distributed protocol to reproduce the dynamic of the walk. In this section we assume that we want to implement the walk on a graph $G = (V, E)$ with polarity $\sigma$.

### 2.1 Positioning the qubits

The implementation proposed uses $W$ states [5]; i.e. a state of the form ($|001\rangle + |010\rangle + |100\rangle)/\sqrt{3}$. Basically the superposition of all the unary digits. We use two qubits per edge, one for the + state and one for the - state. For every node $u \in V$, we use $\ln(\deg(u)) + 1$ qubits to apply the diffusion across all the neighborhood.

**Edges register** The edge register represents the position of the walker and is the one measured at the end of the algorithm. It consists of two qubits per edge, corresponding respectively to the + and - polarity amplitudes. To represent a unary state in this register, we need to introduce the notation $\delta_k^n = \underbrace{0\dots0}_{k-1 \text{ times}} \underbrace{1 \ 0\dots0}_{n-k \text{ times}}$ for the string of $n$ digit with 0 everywhere except at position $k$ where it has 1. For instance, $\delta_2^4 = 0100$. For the sake of simplifying the notations, let us arbitrary enumerate the edges of $E$ such that we have $E = \{e_1, \dots, e_{|E|}\}$. The full state of the walk is a linear combination of all the $\left(|\delta_k^{2|E|}\rangle\right)_{k \in 2|E|}$, where $|\delta_{2k}^{2|E|}\rangle$ corresponds to amplitude $|e_k\rangle|+\rangle$ of the mathematical model, and $|\delta_{2k+1}^{2|E|}\rangle$ corresponds to amplitude $|e_k\rangle|-\rangle$. It is important that the global state of the register remains a superposition of $\left(|\delta_k^{2|E|}\rangle\right)_{k \in 2|E|}$, as this allows us to obtain a valid solution to the search problem during measurement. In fact, no matter which state $\delta_k^{2|E|}$ is measured, all the edges are measuring state 0 except one, which is measuring state 1.

**Nodes register** The node register consists of $\log \deg + 1$ qubits per node. This register is made up exclusively of auxiliary qubits used for the scattering operation. During the scattering operation, the amplitudes of the edges around a given node $u$ are moved to $u$'s auxiliary qubits. The $u$'s qubits then holds the local amplitudes in binary format, applies the scattering operation and finally transfers these amplitudes back to the local edges. After every step of the quantum walk, the nodes register is in state $|0\dots0\rangle$ without any entanglement with the edges register.
## 2.2 Distributed protocol

The various quantum registers, their sizes, and how they are positioned on the network has been made clear in the previous section. We know give distributed schemes for every operation of the mathematical model: oracle, coin and scattering.

*Oracle* In the mathematical model, the oracle applies *R* on the marked edge only. A definition on the basis of this operator when *e*₁ is marked would be

$$ \left( \begin{array}{c|c} |e_1\rangle|+\rangle & \\ |e_1\rangle|-\rangle & \end{array} \right) \stackrel{\text{oracle}}{\mapsto} R \left( \begin{array}{c|c} |e_1\rangle|+\rangle & \\ |e_1\rangle|-\rangle & \end{array} \right). $$

and

$$ |e_k\rangle|s\rangle \stackrel{\text{oracle}}{\mapsto} |e_k\rangle|s\rangle $$

for all $2 \le k \le |E|$, $\forall s = \pm$.

Translated to the distributed registers it means that

$$ \left( \begin{array}{c|c} |\delta_{2k}^{2|E|}\rangle & \\ |\delta_{2k+1}^{2|E|}\rangle & \end{array} \right) \stackrel{\text{oracle}}{\mapsto} R \left( \begin{array}{c|c} |\delta_{2k}^{2|E|}\rangle & \\ |\delta_{2k+1}^{2|E|}\rangle & \end{array} \right), \quad \text{and identity everywhere else.} $$

We recall that in our searching algorithm, $R = -X$. This operation can be achieved by two *Z* gates and a swap applied only to the marked edge.

*Coin* The coin operation is very similar to the oracle. We want to apply $C = X$ to all edge states. In the mathematical model, it can be written as

$$ \forall k, \left( \begin{array}{c|c} |e_k\rangle|+\rangle & \\ |e_k\rangle|-\rangle & \end{array} \right) \stackrel{\text{oracle}}{\mapsto} C \left( \begin{array}{c|c} |e_k\rangle|+\rangle & \\ |e_k\rangle|-\rangle & \end{array} \right). $$

This can be realized by a swap applied on all edges.

*Scattering* The scattering operation consists in applying a diffusion operator *D* locally around the nodes. Since scattering around each node is affecting distinct qubits, we only need to design the circuit for one node *u* of degree *d*. We note *a*₁, ..., *a*ₗ the local edges connected to *u*. For this section we call *η*ₖ the qubits of edge *a*ₖ accessible to *u* following the polarity. Note that, while the local edges (and their qubits) are indexed, this is completely arbitrary and is not changing the final result of the scattering. This nice property is due to the shift invariance of diffusion operator *D*. The log *d* first qubits of *u* are storing the amplitudes of the local edges in a binary format, while the last one is marking the states we need to act on. We note *k*⁽²⁾ the binary representation of *k*. We define the operator Trₖ between qubits *η*ₖ and *u* register such that

$$ |0\rangle |0^{(2)}\rangle |0\rangle \stackrel{\text{Tr}_k}{\mapsto} |0\rangle |0^{(2)}\rangle |0\rangle \quad \text{and} \quad |1\rangle |0^{(2)}\rangle |0\rangle \stackrel{\text{Tr}_k}{\mapsto} |0\rangle |(k-1)^{(2)}\rangle |1\rangle. $$
This operator $\text{Tr}_k$ admits a circuit depending of $k$ composed of X, CNOT and multi controlled Tofolli gates. Algorithm 3 shows a distributed scheme for realizing this circuit. It is running on the node and uses two communication methods: **RequestCnot**(edge, target) which applies a Not on target controlled by the qubit in edge accessible according to polarity; and **ApplyMCT**(edge) which applies a Not on the edge's qubit controlled by the full node register. In the worst case, this algorithm require $\log d + 1$ calls to **RequestCnot** and one call to **ApplyMCT**. We define $\text{Tr}_k$ by the successive applications of $\text{Tr}_k$ between edge $a_k$ and node $u$ for all $k$. It is worth to note that, while one has to apply every $\text{Tr}_k$ successively, the application order does not matter. On the direct basis, the complete scattering operation we want to achieve can be written as

$$ \underbrace{ |\delta_k^d\rangle |0^{(2)}\rangle |0\rangle \xrightarrow{\text{Tr}} |0\rangle |k^{(2)}\rangle |1\rangle \xrightarrow{D} |0\rangle D |k^{(2)}\rangle |1\rangle \xrightarrow{\text{Tr}^{-1}} \underbrace{\left( \sum_{j=1}^d D_{k,j} |\delta_j^d\rangle \right)}_{\text{walker scattered}} \otimes |0^{(2)}\rangle |0\rangle }_{\text{edges}} $$

The last qubit allows us to apply $D$ only when the walker was actually on edge $k$. Following this global idea, Algorithm 4 provides a distributed implementation for the scattering operator. Every node needs a total of $O(d \log d)$ controlled operations (**RequestCnot** or **ApplyMCT**) with the local edges.

Finally, Figure 3 shows an example of this distributed design of the path graph of five nodes. The path graph has the particularity of having the same topology as a circuit (a qubit being connected to the preceding and following qubit). Notice that such circuit coincided with a partitioned QCA, each operation is local and translationally invariant.

<caption>**Algorithm 3** Distributed scheme for $\text{Tr}_k$ on node $u$ of degree $d$</caption>

**Require:** $e$ an edge connected to $u$
**Require:** $1 \le k \le d$
1: **function** $\text{TR}_k(e, k)$
2: &nbsp;&nbsp;&nbsp;&nbsp; $r \leftarrow \lfloor \log d \rfloor$ &nbsp;&nbsp;&nbsp;&nbsp; ▷ The size of $u$'s register is $r+1$
3: &nbsp;&nbsp;&nbsp;&nbsp; **for** $0 \le i < r$ $\mid$ $((k-1)^{(2)})_i = 1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\text{REQUESTCNOT}(e, q_i)$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ▷ CNOT on the $i^{\text{th}}$ qubit of $u$
5: &nbsp;&nbsp;&nbsp;&nbsp; **end for**
6: &nbsp;&nbsp;&nbsp;&nbsp; $\text{REQUESTCNOT}(e, q_r)$
7: &nbsp;&nbsp;&nbsp;&nbsp; Apply $X$ gate on all qubits $q_i$ of $u$ such that $((k-1)^{(2)})_i = 0$.
8: &nbsp;&nbsp;&nbsp;&nbsp; $\text{APPLYMCT}(e)$
9: &nbsp;&nbsp;&nbsp;&nbsp; Apply $X$ gate on all qubits $q_i$ of $u$ such that $((k-1)^{(2)})_i = 0$.
10: **end function**
<caption>**Algorithm 4** Distributed scheme for Tr on node *u* of degree *d*</caption>

**Require:** $\mathcal{N}$ the set of all edges connected to $u$
1: **function** TR($u$)
2: &nbsp;&nbsp;&nbsp;&nbsp;{$a_1, \dots, a_d$} = $\mathcal{N}$ ▷ Random or arbitrary enumeration of the edges
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $1 \le k \le d$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TR$_k(a_k, k)$
5: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
6: **end function**

<figure><img src="image_4.png" /><figcaption>Fig. 3: Circuit of one step of the quantum walk for the path graph $u - v - w$. Dashed lines signal Tr₁ circuit and its inverse while dotted lines Tr₂. The circuit applies successively the oracle on (u, v), the coin, Tr, D, Tr⁻¹.</figcaption></figure>

Discussion

The distributed algorithm described in Section 2 is based on the quantum walker
dynamics introduced earlier for the single particle sector. The most important
feature of the above model is that it does not require a leader or unique iden-
tifiers. Once the measure is done, all edges measure 0 except one that measure
1, giving us a valid solution; i.e. a solution where every edge agrees on who is
marked. The edge who measured 1 can then send the answer to some hypervi-
sor or broadcast it across the network, depending of the context. Notice that
this distributed scheme requires that the network be in a *W* state, which is
very common and widely studied in the distributed algorithm community [5,14].
To study the performances of this algorithm, one should use the mathematical
model from Section 1. In general, it is hard to study analytically this model,
except in some rare cases, where a lot of edges have the same state during the
whole execution. Indeed, the topology of the dynamics, which is different from
that of the graph, makes its analysis mathematically difficult. In fact, we have to
consider a topology based on edges, where two edges are neighbors if they share
a node. As such, regular lattices like a grid do not actually have the topology of a
grid. However, one could also study this algorithm numerically; preliminary non
published work on this aspect have already shown promising results for popular
lattices and random graphs. To conclude, it is also important to note that the
distributed model recover a QCA-like dynamics on an arbitrary graph. Indeed,
in the case of a linear graph, it coincides with the standard partitioned QCA.
Overall each operation are node- and edge-independent, so they are transla-
tionally invariant. And all operations are local. A byproduct of these properties
is a promising distributed architecture which naturally gives a degree of fault
tolerance because of local interactions, limiting error propagation.

*Acknowledgement*
This work is supported by the PEPR EPiQ ANR-22-PETQ-0007, by the ANR JCJC DisQC ANR-22-CE47-0002-01.

References

1. Arrighi, P.: An overview of quantum cellular automata. Natural Computing 18(4), 885-899 (2019)

2. Arrighi, P., Di Molfetta, G., Márquez-Martín, I., Pérez, A.: Dirac equation as a quantum walk over the honeycomb and triangular lattices. Physical Review A 97(6), 062111 (2018)

3. Bezerra, G., Lugão, P.H., Portugal, R.: Quantum-walk-based search algorithms with multiple marked vertices. Physical Review A 103(6), 062202 (2021)

4. Bisio, A., D'Ariano, G.M., Perinotti, P.: Quantum walks, deformed relativity and hopf algebra symmetries. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 374(2068), 20150232 (2016)

5. Cruz, D., Fournier, R., Gremion, F., Jeannerot, A., Komagata, K., Tosic, T., Thiesbrummel, J., Chan, C.L., Macris, N., Dupertuis, M.A., et al.: Efficient quantum algorithms for ghz and w states, and implementation on the ibm quantum computer. Advanced Quantum Technologies 2(5-6), 1900015 (2019)

6. Di Molfetta, G., Brachet, M., Debbasch, F.: Quantum walks as massless dirac fermions in curved space-time. Physical Review A 88(4), 042301 (2013)

7. Gall, F.L., Nishimura, H., Rosmanis, A.: Quantum advantage for the local model in distributed computing. arXiv preprint arXiv:1810.10838 (2018)

8. Izumi, T., Gall, F.L., Magniez, F.: Quantum distributed algorithm for triangle finding in the congest model. arXiv preprint arXiv:1908.11488 (2019)

9. Le Gall, F., Magniez, F.: Sublinear-time quantum computation of the diameter in congest networks. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. pp. 337-346 (2018)

10. Melnikov, A.A., Fedichkin, L.E., Alodjants, A.: Predicting quantum advantage by quantum walk with convolutional neural networks. New Journal of Physics 21(12), 125002 (2019)

11. Roget, M., Guillet, S., Arrighi, P., Di Molfetta, G.: Grover search as a naturally occurring phenomenon. Physical Review Letters 124(18), 180501 (2020)

12. Santha, M.: Quantum walk based search algorithms. In: International Conference on Theory and Applications of Models of Computation. pp. 31–46. Springer (2008)

13. Slate, N., Matwiejew, E., Marsh, S., Wang, J.B.: Quantum walk-based portfolio optimisation. Quantum 5, 513 (2021)

14. Tani, S., Kobayashi, H., Matsumoto, K.: Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory (TOCT) 4(1), 1–24 (2012)

15. Zalka, C.: Grover’s quantum searching algorithm is optimal. Physical Review A 60(4), 2746 (1999)