5 Quantum Resetting by Superposition

From the previous discussion, it seems fruitful to consider a quantum reset of quantum walks. Just as we harnessed the power of quantum superposition to speed up the walk, can we similarly have a superposition between the reset and evolution to increase the efficiency of hitting a node? The concept is similar to that of the quantisation of the classical walk: let the resetting occur on probability amplitudes rather than probabilities, allowing for interference in areas we do not want the walker to be on. In this case however, the superposition is on the level of operations, not the walker position directly.

Our first protocol is motivated by the quantum resetting of quantum systems introduced in Anubhav Srivastava’s¹ master thesis, where a similar formalism was applied to a qubit system. The faster convergence of the quantum reset system acts as the primary indicator that such a speed-up may also be visible in quantum walks.

Formalism

On a finite 1D chain of length $2N + 1$, define the following -

Reset operation - $\mathcal{R}$ by the Kraus operators $\{\mathcal{R_i} = |r_0\rangle\langle i|\}_{i\in [-N, N]}$ on $\mathcal{H}_W$
Evolve operation - $\mathcal{U}$ by the unitary operation $S\circ H$ on $\mathcal{H}_C\otimes\mathcal{H}_W$
Attach another two level coin - states denoted by $|0\rangle$ and $|1\rangle$. Resulting state lies in $\mathcal{H}_R\otimes\mathcal{H}_C\otimes\mathcal{H}_W$
Controlled reset operation - $\mathcal{E}$ by the Kraus operators $\{\mathcal{E}_i = |0\rangle\langle 0|\otimes I_2 \otimes \mathcal{R}_i + \frac{1}{\sqrt N} |1\rangle\langle 1|\otimes \mathcal{U}\}_{i\in [-N, N]}$. See Appendix C for proof that this set of Kraus operators represents a CPTP map.
A reset coin operator $\Gamma(\gamma) = \begin{bmatrix}\sqrt{1-\gamma} & \sqrt{\gamma} \\ \sqrt{\gamma} & -\sqrt{1- \gamma}\end{bmatrix}$ on $\mathcal{H}_R$

Quantum Reset

One step of the resulting walk is defined as

\[\mathcal{E} \circ \left(\Gamma \otimes I_2 \otimes I_{2N+1}\right)\]

Once again, the hitting protocol is found by measuring the walker position after $\tau$ time steps.

Although the protocol is similar to the motivation, the current problem we are considering of the first hit time has drastically changed the methods of exploration and the property we want to optimize. Where previously we only probed the convergence time, here we also want to maximize the probability of hitting the target node.

Interpretation of $\gamma$ and dependence on initial condition of the coin

In the stochastic resetting $\gamma$ is understood as the “rate” of resetting. However, this is no longer accurate for the quantum case. Consider the case for $\gamma = 0$. Then, the Gammamard operator $\Gamma = \begin{bmatrix}1 & 0\\ 0 & -1\end{bmatrix}$. This does not automatically imply that the reset never occurs; we also require that the initial state of the reset coin is $|0\rangle$. If the initial state of the reset coin is $|1\rangle$, this corresponds to the always reset case. Thus, $\gamma$ is better understood as the probability that given the last step was a Reset, what is the probability this step is an Evolve, and vice versa. Thus, it is not immediately obvious how we can compare the reset mechanisms for a given $\gamma$. Nor is it obvious how the initial state of the reset coin finally affects the success probability and such, and needs to be numerically checked.

Resetting of the walker coin

In our specific formalism (Section 5.1), we have only applied the reset operation on the walker $\mathcal{H}_W$. One could also reset the walker coin $\mathcal{H}_C$ and see what happens. In our current formalism, there is no entanglement broken between the two coins, but there is no a priori understanding of how this may (or may not) affect the walk.

Computational Implementation

Implementations of $\mathcal{U}, U, H$ follow as before. The $\mathcal{E}$ operation is implemented as

function €(n, r₀)
    ks = map(1:n) do i
        (1/√n * [1 0; 0 0] ⊗ (S(n)*H(n))) +
        [0 0; 0 1] ⊗ I(2) ⊗ real(ket(r₀,n)*bra(i,n))
    end
    return KrausOperators(sparse.(ks))
end;

The Gammamard operation $\Gamma$ is defined as

Γ(γ) = [
    √(1-γ)  √γ;
    √γ      -√(1-γ)];

We take the initial reset coin to be $(S(-\pi/2)\circ\Gamma(\gamma))|0\rangle$ for the same reason as in the quantum walk

reset_init(γ) = [1 0; 0 -1im]*gammamard(γ)*ket(1, 2);

Results

What the walk looks like

For the specific choice of initial reset coin as $1/\sqrt{2}\left(|0\rangle - i|1\rangle\right)$ and $\gamma=0.2$, the quantum reset walk looks like Figure 5.1.

Figure 5.1: Probability distribution of the walker in Quantum Reset Walk. We see a markedly different stable distribution as compared to the stochastic reset case Figure 4.2, with a much sharper cusp, but also a much more spread out walker.

Results and Discussion

As discussed in Section 5.1.1, we need to vary the three parameters, $(\alpha, \phi, \gamma)$, and see what happens. Thus, we plot the success curves for a few sets of parameters (Figure 5.2), and find the minimum mean time of hit for each fixed parameter (Figure 5.3).

As we can see, the mean time of hit even for the best set of parameters (within the ranges explored) is not better than the optimal time for the stochastic reset protocol. This result however may not hold true for other values of $\tau$, and more work is necessary to conclusively state that there isn’t (or is) any speedup achieved here.

Optimal Parameter Values

Table 5.1: Optimal Parameter Values
$\alpha$	$\phi$	$\gamma$
$0.0$	$0.0$	$10^{-5}$

The Issue of Non-Unitarity

One drawback of this formalism is its complexity. Whereas the stochastic reset proceeded by a unitary evolution between measurement events, the quantum reset protocol is inherently a non-unitary operation. This makes analysis more complicated.

The difficulty doesn’t only lie in analytical complexity, but also in simulations, where simulating the quantum reset quantum walk takes much longer. This can be attributed to the larger system size (size of $\rho = 16N^2$), and due to the increased number of matrix multiplications and additions ($2N$ matrix multiplications of size $4N\times 4N$ ($64N^3$ multiplications and $64N^3 - 16N^2$ additions) followed by $N$ matrix additions ($16N^2 additions) which finally consists of $128N^4$ multiplications and $128N^4$ additions for one step of the quantum reset walk, as compared to $2\cdot 8N^3$ multiplications and $2 \cdot 8N^3 - 4N^2$ additions. Even ignoring the additions, the quantum reset walk is $\mathcal{O}(N^4)$ whereas the stochastic reset walk is $\mathcal{O}(N^3)$ to simulate. For any reasonably large cycle (to avoid finite size effects), this cost makes simulating the walk for different parameters extremely tedious.

Therefore, although we have been able to introduce a superposition between the two operations, and we have decoupled the resetting from the measurement, we require a unitary protocol to efficiently perform the walk.

# Quantum Resetting by Superposition {#sec-qreset} ```{julia} #| echo: false using QuantumInformation using Plots using LinearAlgebra using SparseArrays ``` From the previous discussion, it seems fruitful to consider a quantum reset of quantum walks. Just as we harnessed the power of quantum superposition to speed up the walk, can we similarly have a superposition between the reset and evolution to increase the efficiency of hitting a node? The concept is similar to that of the quantisation of the classical walk: let the resetting occur on probability amplitudes rather than probabilities, allowing for interference in areas we do not want the walker to be on. In this case however, the superposition is on the level of operations, not the walker position directly. Our first protocol is motivated by the quantum resetting of quantum systems introduced in Anubhav Srivastava's @srivastava_resetting_2021 master thesis, where a similar formalism was applied to a qubit system. The faster convergence of the quantum reset system acts as the primary indicator that such a speed-up may also be visible in quantum walks. ## Formalism {#sec-qreset-formalism} On a finite 1D chain of length $2N + 1$, define the following - - Reset operation - $\mathcal{R}$ by the Kraus operators $\{\mathcal{R_i} = |r_0\rangle\langle i|\}_{i\in [-N, N]}$ on $\mathcal{H}_W$ - Evolve operation - $\mathcal{U}$ by the unitary operation $S\circ H$ on $\mathcal{H}_C\otimes\mathcal{H}_W$ - Attach another two level coin - states denoted by $|0\rangle$ and $|1\rangle$. Resulting state lies in $\mathcal{H}_R\otimes\mathcal{H}_C\otimes\mathcal{H}_W$ - Controlled reset operation - $\mathcal{E}$ by the Kraus operators $\{\mathcal{E}_i = |0\rangle\langle 0|\otimes I_2 \otimes \mathcal{R}_i + \frac{1}{\sqrt N} |1\rangle\langle 1|\otimes \mathcal{U}\}_{i\in [-N, N]}$. See @sec-appqreset for proof that this set of Kraus operators represents a CPTP map. - A reset coin operator $\Gamma(\gamma) = \begin{bmatrix}\sqrt{1-\gamma} & \sqrt{\gamma} \\ \sqrt{\gamma} & -\sqrt{1- \gamma}\end{bmatrix}$ on $\mathcal{H}_R$ ::: {.callout-tip} ## Quantum Reset One step of the resulting walk is defined as $$\mathcal{E} \circ \left(\Gamma \otimes I_2 \otimes I_{2N+1}\right)$$ Once again, the hitting protocol is found by measuring the walker position after $\tau$ time steps. ::: Although the protocol is similar to the motivation, the current problem we are considering of the first hit time has drastically changed the methods of exploration and the property we want to optimize. Where previously we only probed the convergence time, here we also want to maximize the probability of hitting the target node. ### Interpretation of $\gamma$ and dependence on initial condition of the coin {#sec-interpretation} In the stochastic resetting $\gamma$ is understood as the "rate" of resetting. However, this is no longer accurate for the quantum case. Consider the case for $\gamma = 0$. Then, the Gammamard operator $\Gamma = \begin{bmatrix}1 & 0\\ 0 & -1\end{bmatrix}$. This does not automatically imply that the reset never occurs; we also require that the initial state of the reset coin is $|0\rangle$. If the initial state of the reset coin is $|1\rangle$, this corresponds to the always reset case. Thus, $\gamma$ is better understood as the probability that given the last step was a Reset, what is the probability this step is an Evolve, and vice versa. Thus, it is not immediately obvious how we can compare the reset mechanisms for a given $\gamma$. Nor is it obvious how the initial state of the reset coin finally affects the success probability and such, and needs to be numerically checked. ### Resetting of the walker coin In our specific formalism (@sec-qreset-formalism), we have only applied the reset operation on the walker $\mathcal{H}_W$. One could also reset the walker coin $\mathcal{H}_C$ and see what happens. In our current formalism, there is no entanglement broken between the two coins, but there is no a priori understanding of how this may (or may not) affect the walk. ## Computational Implementation Implementations of $\mathcal{U}, U, H$ follow as before. The $\mathcal{E}$ operation is implemented as ```{julia} function €(n, r₀) ks = map(1:n) do i (1/√n * [1 0; 0 0] ⊗ (S(n)*H(n))) + [0 0; 0 1] ⊗ I(2) ⊗ real(ket(r₀,n)*bra(i,n)) end return KrausOperators(sparse.(ks)) end; ``` The Gammamard operation $\Gamma$ is defined as ```{julia} Γ(γ) = [ √(1-γ) √γ; √γ -√(1-γ)]; ``` We take the initial reset coin to be $(S(-\pi/2)\circ\Gamma(\gamma))|0\rangle$ for the same reason as in the quantum walk ```{julia} reset_init(γ) = [1 0; 0 -1im]*gammamard(γ)*ket(1, 2); ``` ## Results ### What the walk looks like For the specific choice of initial reset coin as $1/\sqrt{2}\left(|0\rangle - i|1\rangle\right)$ and $\gamma=0.2$, the quantum reset walk looks like @fig-qrwalk. ```{julia} #| echo: false #| label: fig-qrwalk #| fig-cap: "Probability distribution of the walker in Quantum Reset Walk. We see a markedly different stable distribution as compared to the stochastic reset case @fig-qwsr, with a much sharper cusp, but also a much more spread out walker." let Sₗ(n) = sum(1:n) do i ket(mod1(i-1, n), n) * bra(i, n) end Sᵣ(n) = sum(1:n) do i ket(mod1(i+1, n), n) * bra(i, n) end S(n) = proj(ket(1, 2)) ⊗ Sₗ(n) + proj(ket(2, 2)) ⊗ Sᵣ(n) H(n) = hadamard(2) ⊗ I(n) gammamard(γ) = [ √(1-γ) √γ; √γ -√(1-γ) ] function R(n, m) ks = map(1:n) do i (1/√n * [1 0; 0 0] ⊗ (S(n)*H(n))) + [0 0; 0 1] ⊗ I(2) ⊗ real(ket(6,n)*bra(i,n)) end return KrausOperators(sparse.(ks)) end Γᵣ(γ, n) = KrausOperators([sparse(gammamard(γ) ⊗ I(2) ⊗ I(n))]) init_coin = (1/√2*(ket(1,2) - ket(2,2)*1im)) function RepR(n, m, γ, j, decohᵣ) Rn = R(n, m) Γ = Γᵣ(γ, n) dyn = if decohᵣ Dᵣ(n) ∘ Rn ∘ Γ else Rn ∘ Γ end reset_init = [1 0; 0 -1im]*gammamard(γ)*ket(1, 2) accumulate(1:j, init=(reset_init ⊗ init_coin ⊗ ket(1,n))) do old, _ dyn(old) end end function simulate(num_nodes, m, γ, num_steps, decohᵣ) raw_data = RepR(num_nodes, m, γ, num_steps, decohᵣ) data = raw_data .|> Array .|> (x->ptrace(x, [2,2,num_nodes], [1,2])) .|> diag .|> x -> real.(x) data, raw_data end struct Simulation data::Vector{Vector{Float64}} raw_data::Vector{Matrix{ComplexF64}} num_nodes::Int64 m::Float64 γ::Float64 num_steps::Int64 decohᵣ::Bool function Simulation( num_nodes::Int64, m::Int64, γ::Float64, num_steps::Int64, decohᵣ::Bool=false ) new( simulate(num_nodes, m, γ, num_steps, decohᵣ)..., num_nodes, m, γ, num_steps, decohᵣ ) end end function rotate_center(arr) n = length(arr) arr[mod1.((1:n).+(n÷2 + 1), n)] end plot_walk(s::Simulation, time_step) = Plots.plot( length(s.data[1]) |> d-> -d÷2+1:d÷2, rotate_center(s.data[time_step]), ylims=(0,1), xlabel="\$i\$", ylabel="\$\\langle i|\\psi\\rangle\$", title="\$t=$(time_step), \\gamma=$(s.γ), r_0 = |5\\rangle \$", legend=false ) s1 = Simulation(30, 1, 0.2, 100) Plots.plot( plot_walk(s1, 1), plot_walk(s1, 3), plot_walk(s1, 6), plot_walk(s1, 16), size=(400, 300).*1.25 ) end ``` ## Results and Discussion As discussed in @sec-interpretation, we need to vary the three parameters, $(\alpha, \phi, \gamma)$, and see what happens. Thus, we plot the success curves for a few sets of parameters (@fig-qreset), and find the minimum mean time of hit for each fixed parameter (@fig-qreset-optim). ::: {#fig-qreset layout="[[50,50], [-25,50,-25]]"} ![Parameter set 1](./images/qreset_1.png){#fig-qra} ![Parameter set 2](./images/qreset_2.png){#fig-qrb} ![Parameter set 3](./images/qreset_3.png){#fig-qrc} Mean hitting time for some parameter sets. We see a nontrivial dependence on the initial state of the coin. ::: ::: {#fig-qreset-optim layout="[[50,50], [-25,50,-25]]"} ![$\alpha$ vs $\phi$](./images/fix_alpha_phi.png){#fig-qroa} ![$\alpha$ vs $\gamma$](./images/fix_alpha_gamma.png){#fig-qrob} ![$\phi$ vs $\gamma$](./images/fix_phi_gamma.png){#fig-qroc} Value of the third parameter for optimal mean hitting rate, found by fixing the other two parameters. We surprisingly see that $\gamma=0$ or $1$ is the optimal value for all initial conditions. Furthermore, the effect of $\phi$ is symmetric about $\pi$ ::: As we can see, the mean time of hit even for the best set of parameters (within the ranges explored) is not better than the optimal time for the stochastic reset protocol. This result however may not hold true for other values of $\tau$, and more work is necessary to conclusively state that there isn't (or is) any speedup achieved here. ### Optimal Parameter Values | $\alpha$ | $\phi$ | $\gamma$ | | :------: | :----: | :-------: | | $0.0$ | $0.0$ | $10^{-5}$ | : Optimal Parameter Values {#tbl-qresetresults} ### The Issue of Non-Unitarity One drawback of this formalism is its complexity. Whereas the stochastic reset proceeded by a unitary evolution between measurement events, the quantum reset protocol is inherently a non-unitary operation. This makes analysis more complicated. The difficulty doesn't only lie in analytical complexity, but also in simulations, where simulating the quantum reset quantum walk takes much longer. This can be attributed to the larger system size (size of $\rho = 16N^2$), and due to the increased number of matrix multiplications and additions ($2N$ matrix multiplications of size $4N\times 4N$ ($64N^3$ multiplications and $64N^3 - 16N^2$ additions) followed by $N$ matrix additions ($16N^2 additions) which finally consists of $128N^4$ multiplications and $128N^4$ additions for one step of the quantum reset walk, as compared to $2\cdot 8N^3$ multiplications and $2 \cdot 8N^3 - 4N^2$ additions. Even ignoring the additions, the quantum reset walk is $\mathcal{O}(N^4)$ whereas the stochastic reset walk is $\mathcal{O}(N^3)$ to simulate. For any reasonably large cycle (to avoid finite size effects), this cost makes simulating the walk for different parameters extremely tedious. Therefore, although we have been able to introduce a superposition between the two operations, and we have decoupled the resetting from the measurement, we require a unitary protocol to efficiently perform the walk.

Formalism

Interpretation of \(\gamma\) and dependence on initial condition of the coin

Resetting of the walker coin

Computational Implementation

Results

What the walk looks like

Results and Discussion

Optimal Parameter Values

The Issue of Non-Unitarity