Quantum-walk-based state-transfer algorithms on the complete $M$-partite graph

We investigate coined quantum-walk search and state-transfer algorithms, focusing on the complete $M$-partite graph with $N$ vertices in each partition. First, it is shown that by adding a loop to each vertex, the search algorithm finds the marked vertex with unit probability in the limit of a large graph. Next, we employ the evolution operator of the search with two marked vertices to perform a state transfer between the sender and the receiver. We show that when the sender and the receiver are in different partitions, the algorithm succeeds with fidelity approaching unity for a large graph. However, when the sender and the receiver are in the same partition, the fidelity does not reach exactly 1. To solve this problem, we propose a state-transfer algorithm with an active switch, whose fidelity can be estimated based on the single vertex search alone.

Figure 1

Overall success probability of the SA (black dots) and the probability to find the walker in the target state $|{\nu }_1\rangle$ (blue squares) as a function of the number of steps $t$ for $N=40$ and $M=100$. Red curves correspond to the analytical results [the dashed line corresponds to Eq. (21) and the full line corresponds to Eq. (23)]. Green diamonds denote the probability that the walker is on the marked vertex but not in the loop, which follows the curve (22). The success probability is close to 1 after $T\approx 100$ steps, in accordance with (24).

Figure 2

Overall success probability of the SA as a function of the number of partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles), and $N=100$ (brown diamonds). For a given $N$ and $M$, we evaluate numerically the evolution of the SA for the optimal number of steps $T$ given by (24), and we determine $P_m\left(T\right)$ from the formula (20). To unravel the scaling of the success probability, we plot $1-P_m\left(T\right)$ on the log-log scale. Independent of the value of $N$, the sets of data points fit well onto the $1/M$ slope indicated by the red line.

Figure 3

The evolution of the fidelity $\mathcal{F}$ of the state transfer during 1000 steps for $N=40$ and $M=100$. Sender and receiver are in the same part. The initial state $|s\rangle$ is the equal-weight superposition on the sender vertex $|{\mathrm{\Omega }}_s\rangle$. We see that the fidelity does not grow over 0.35.

Figure 4

Fidelity of the state transfer as a function of the number of steps $t$ for $N=40$ and $M=100$. The sender and the receiver vertices are in the same partition. Black dots are obtained from the numerical simulation, and the full red curve corresponds to (37). Since the frequencies (30) and (32) are not integer multiples, the fidelity behaves anharmonically. At the time of the first maximum (39), the walker is with high probability in the receiver state $|r\rangle$, which is depicted by the blue squares. The probability to be in the receiver state follows the curve (35) represented by the red dashed curve. The green diamonds correspond to the probability that the walker is at the marked vertex but not in the loop, which follows the curve (36).

Figure 5

Overall fidelity of the STA as a function of the number of partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles), and $N=100$ (brown diamonds). The sender and the receiver vertices are in the same partition. For a given $N$ and $M$, we evaluate numerically the evolution of the STA for the number of steps $T^{\left(\text{st}\right)}$ needed to reach the first maximum (39) and determine $\mathcal{F}\left(T^{\left(\text{st}\right)}\right)$ according to (34). To unravel the scaling of the fidelity, we plot ${\mathcal{F}}_1-\mathcal{F}\left(T^{\left(\text{st}\right)}\right)$ on the log-log scale. The data points follow the $1/M$ slope indicated by the red line, with almost no dependence on $N$.

Figure 6

Overall fidelity of the STA as a function of the number of steps $t$ for $N=40$ and $M=100$. The sender and the receiver vertices are in different partitions. Black dots are obtained from the numerical simulation, and the full red curve corresponds to (58). The walker is transferred to the receiver vertex with fidelity close to 1 after $T^{\left(\text{st}\right)}\approx 140$ steps, in accordance with (59). At this time, the walker is found with high probability in the loop (blue squares), as follows from the analytical prediction (56) depicted by the red dashed curve. Green diamonds represent the probability that the walker is at the marked vertex but not in the loop, which follows the curve (57).

Figure 7

Overall fidelity of the STA as a function of the number of partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles), and $N=100$ (brown diamonds). The sender and the receiver vertices are in different partitions. For a given $N$ and $M$, we evaluate numerically the evolution of the STA for the optimal number of steps $T^{\left(\text{st}\right)}$ given by (59), and we determine $\mathcal{F}\left(T^{\left(\text{st}\right)}\right)$ from the formula (54). To unravel the scaling of the fidelity, we plot $1-\mathcal{F}\left(T^{\left(\text{st}\right)}\right)$ on the log-log scale. The full red line has a $1/M$ slope, while the dashed red line follows $1/M^2$. The plot indicates that $O(1/M)>1-\mathcal{F}\left(T^{\left(\text{st}\right)}\right)>O(1/M^2)$, and that the fluctuations decrease with increasing $N$.

Figure 8

Comparison of fidelity of the original STA (37) (red diamonds) with fidelity of the STA with an active switch (black dots) as a function of the number of steps $t$ for $N=40$ and $M=100$. The sender and the receiver vertices are in the same partition. The switch between ${\widehat{U}}_s$ and ${\widehat{U}}_r$ is done after $T\approx 100$ steps, corresponding to the run time of the SA.

Figure 9

Overall fidelity of the STA with an active switch as a function of the number of partitions $M$ for $N=10$ (gray circles), $N=50$ (blue triangles), and $N=100$ (brown diamonds). The walk is initialized at the sender vertex in the loop. For a given $N$ and $M$ we evaluate numerically the evolution operator ${\widehat{U}}_s$ of the SA with marked vertex $s$, and we apply it for the optimal number of steps $T$ given by (24). Then we repeat the same steps with ${\widehat{U}}_r$. Finally, we make a measurement at the receiver vertex $r$ and determine the fidelity $\mathcal{F}\left(2T\right)$. To unravel the scaling of the fidelity, we plot $1-\mathcal{F}\left(2T\right)$ on the log-log scale. The full red line has a $1/M$ slope, while the dashed red line follows $1/M^2$. The plot indicates that $O(1/M)>1-\mathcal{F}\left(2T\right)>O(1/M^2)$.