7 Unitary Quantum Reset Quantum Walk

Armed with the Szegedy formalism from the previous chapter, we can define the unitary quantum reset quantum walk by quantising the stochastic reset classical walk (Section 4.1.2). It is obvious that the stochastic reset classical walk is not symmetric ($p_{i0} \ne p_{0i}\forall i\ne 0$), so we cannot use the original Szegedy walk, but we can use the generalized Szegedy formalism if we show that our process is ergodic.

Ergodicity of the Stochastic Reset Classical Walk

Graph of the Stochastic Reset Classical Walk. Green edges represent walk edges, and red edges represent reset edges.

To show ergodicity, we need to show that the walk is irreducible, aperiodic and positive recurrent.

Irreducibility follows from the irreducibility of the 1D walk (Appendix A) $\forall \gamma < 1$. For the trivial case of $\gamma = 1$, the chain is not irreducible, and we cannot use the Szegedy formalism.

Aperiodicity (Appendix A) of the chain follows from the irreducibility of the chain and aperiodicity of node $0$ which is obvious due to the existence of the self loop.

Recurrence is obvious from $p_{00}^{(n)} \ge \gamma \forall i$ and irreducibility. Positive recurrence is harder to show, but we can solve the recurrence relation (Chapter 5).

Thus, the stochastic reset classical walk is ergodic and is a viable candidate for quantisation via the Szegedy walk.

Implementation and Results

The implementation of the Szegedy walk is simplified by the use of QuantumWalk.jl¹ and LightGraphs.jl²

First we define a function that returns the underlying graph and the transition matrix

MyGraph(n, γ=0.5) =
    let
        temp = CycleGraph(n) |> adjacency_matrix |> collect
        reset = zero(temp)
        reset[:, n÷2] .= 1
        stochastic = ((1 - γ) / 2) * temp + γ * reset
        temp = sign.(temp + reset)
        DiGraph(temp), sparse(transpose(stochastic))
    end

Then we define and run the search algorithm.

function run_search_mygraph(n, δ, T, γ)
    graph, stochastic = MyGraph(n, γ)
    qwe = QWSearch(Szegedy(graph, stochastic), [n÷2 + δ])
    first.(measure.(Ref(qwe), execute_all(qwe, T), Ref([n÷2 + δ])))
end

QuantumWalk.jl uses the Grover-like search algorithm³.

struct Simulation
    n::Int64
    δ::Int64
    T::Int64
    γ::Float64
    data::Vector{Float64}
    function Simulation(n, δ, T, γ)
        new(n, δ, T, γ, run_search_mygraph(n, δ, T, γ))
    end
end

mean_hit(s::Simulation) = mean(0:s.T, Weights(success(s)))

success(s::Simulation) = accumulate(s.data, init=0) do old, curr
    (1-old) * curr + old
end

We can scan over $\gamma \in [0, 1]$ and plot the instantaneous probability of measuring in $\delta$, success probability and the mean hitting time in Figure 7.1.

Alternative Definition of the Mean Hitting Time

Although the definition of mean hitting time we have defined until now is only valid for a measure and continue semi-quantum walk, we adopt a similar definition for this walk, only without actual measurements. In this section, (particularly Figure 7.1 and Figure 7.2), we use a measure and rerun protocol, and define the success probability $S_n$ on the basis of $F_i$ of the unmeasured quantum walk until each time $i < n$

res = map(0:0.01:1) do γ
    Simulation.(100, 10, 100, γ)
end;

(a) Probability of measuring in $\delta$

(b) Success Probability

Figure 7.1: Unitary Quantum Reset. These results are for a walk on $n=100, \delta=10, T_{max}=100$. This is a very small state space, run for a short time, so results should only be considered qualitatively, but we can still see the effect of unitary resetting on the success probability.

Results

Exceptional Quantum Walk on the Cycle

For the non reset ($\gamma = 0$) case, we see that the success rate does not increase with time. While this is initially surprising, this is a known result⁴, caused due to the fact that the initial state evolves by phase flips, and the amplitude does not increase.

In the reset case, we see that the walk is no longer exceptional (at least, not in this sense), which allows for an amplitude amplification on the marked node.

Mean hitting time vs $\gamma$

Plotting the mean hitting time (the alternative definition (Section 7.2)) versus $\gamma$ for $500$ nodes and $500$ steps, we get the curve in Figure 7.2.

As we can see, there is a clear non-monotonous effect of $\gamma$ on the mean hitting time of the walk. For values a bit more than $\gamma = 0.5$, we see that the mean hitting time is much lower than that for the no reset $\gamma = 0$ case. Also of note is that as $\gamma \to 1$ the mean hitting rate approaches that of the no reset case.

Numerically, the exact time for mean hit changes according to the amount of time that we run the simulation for. This is obvious from the way that the mean hit time is calculated, where if the walk has not succeeded within the time of running the simulation, we assume that it succeeds in the next step. However, we recover the same qualitative curve for large number of steps.

Eigenvalue analysis

In Section 6.3, we saw how the quadratic increase in the eigen-gap ($\Delta P$) leads to an associated speedup in the search problem. Thus, if we can show that the eigen-gap increases in for the reset case, we can show that the search protocol requires fewer steps to complete. Furthermore, the space cost of the circuit goes as $\left\lceil \log_2 \left(\frac{2\pi}{\Delta P}\right)\right\rceil$

We see that the transition matrix is extremely sparse, especially for larger system sizes (goes as $\mathcal{O}(3N)$, so the density goes as $\mathcal{O}(1/N)$), and that we do not require the entire eigen spectrum to find the eigen-gap. Thus, we can use specialized methods such as the Arnoldi method provided in Julia by the KrylovKit.jl⁵ package.

using KrylovKit

function eigen_gap(M)
    v = real(eigsolve(M, 2, :LR)[1]) # get real(eigval)
    v[1] - v[2]
end

γs = 0.:0.01:(1-0.01)

ΔP = eigen_gap.(getindex.(MyGraph.(512, γs), 2))

(a) Eigen Gap

(b) Space complexity

Figure 7.3: Analysis by Eigen Gap of the Reset Walk. See that the eigengap increases with $\gamma$, and therefore, there is a corresponding decrease in the space requirement of the protocol. $n=500, \delta=50, T_{max}=1000$

Plotting $\Delta P$ vs $\gamma$ in Figure 7.3, we see that increasing $\gamma$ leads to an equal increase in $\Delta P$, which corresponds to a faster convergence under the Grover-like search protocol. Note however that we do not have a quantitative characterization of what the final probability of success is. Therefore, despite the faster convergence, the non-monotonic nature of the mean hitting time against $\gamma$ can be explained by a loss in final success probability. The interplay of these two effects may be the cause of the existence of an optimal reset parameter.

Discussions

A particular advantage of the Unitary quantum reset is that we are not limited to only resets on 1D chains. We can define the unitary reset walk on any irreducible graph that one can come up with, even periodic graphs, since resetting a periodic graph leads to an aperiodic graph (Appendix D), and the corresponding walk can be quantised by the Szegedy formalism.

While it is clear that there is an obvious speedup compared to the walk without reset, we cannot directly compare these results with the stochastic reset quantum walk due to the different definitions of $F_n$. The quantification of the quantum hitting time for Szegedy walks is an area of very active research⁶. Another possible approach would be via the semi-quantum Szegedy walk⁷. These methods have been left as a possible future work.

# Unitary Quantum Reset Quantum Walk {#sec-uqreset} Armed with the Szegedy formalism from the previous chapter, we can define the unitary quantum reset quantum walk by quantising the stochastic reset classical walk (@sec-reset-cw). It is obvious that the stochastic reset classical walk is not symmetric ($p_{i0} \ne p_{0i}\forall i\ne 0$), so we cannot use the original Szegedy walk, but we can use the generalized Szegedy formalism if we show that our process is ergodic. ## Ergodicity of the Stochastic Reset Classical Walk ```{julia} #| echo: false #| fig-cap: "Graph of the Stochastic Reset Classical Walk. Green edges represent walk edges, and red edges represent reset edges." #| layout: "[-15,70,-15]" using GraphPlot import Graphs using Colors function m(n) m = Graphs.CycleGraph(n) |> Graphs.adjacency_matrix m[:, n÷2+1] .= 1 Graphs.DiGraph(m) end function colors(g) c = fill(colorant"green", length(Graphs.edges(g))) n = length(Graphs.vertices(g)) args = findall(x->x.dst==n÷2+1, collect(Graphs.edges(g))) c[args] .= colorant"red" c end gr = m(11) gp = gplot(gr, layout=circular_layout, linetype="curve", nodefillc=colorant"gray", nodelabel=string.(-5:5), NODESIZE=0.075, nodestrokelw=0.1, edgestrokec=colors(gr), nodestrokec=colorant"white", NODELABELSIZE=7, EDGELINEWIDTH=0.3, arrowlengthfrac=0.05) ``` To show ergodicity, we need to show that the walk is irreducible, aperiodic and positive recurrent. Irreducibility follows from the irreducibility of the 1D walk (@sec-markov) $\forall \gamma < 1$. For the trivial case of $\gamma = 1$, the chain is not irreducible, and we cannot use the Szegedy formalism. Aperiodicity (@sec-markov) of the chain follows from the irreducibility of the chain and aperiodicity of node $0$ which is obvious due to the existence of the self loop. Recurrence is obvious from $p_{00}^{(n)} \ge \gamma \forall i$ and irreducibility. Positive recurrence is harder to show, but we can solve the recurrence relation (@sec-qreset). Thus, the stochastic reset classical walk is ergodic and is a viable candidate for quantisation via the Szegedy walk. ## Implementation and Results {#sec-umht} The implementation of the Szegedy walk is simplified by the use of `QuantumWalk.jl` @glos_iitisquantumwalkjl_2018 and `LightGraphs.jl` @bromberger_juliagraphslightgraphsjl_2017 ```{julia} #| echo: false #| warning: false using LightGraphs using QuantumWalk using SparseArrays using StatsBase using Plots ``` First we define a function that returns the underlying graph and the transition matrix ```{julia} #| output: false MyGraph(n, γ=0.5) = let temp = CycleGraph(n) |> adjacency_matrix |> collect reset = zero(temp) reset[:, n÷2] .= 1 stochastic = ((1 - γ) / 2) * temp + γ * reset temp = sign.(temp + reset) DiGraph(temp), sparse(transpose(stochastic)) end ``` Then we define and run the search algorithm. ```{julia} #| output: false function run_search_mygraph(n, δ, T, γ) graph, stochastic = MyGraph(n, γ) qwe = QWSearch(Szegedy(graph, stochastic), [n÷2 + δ]) first.(measure.(Ref(qwe), execute_all(qwe, T), Ref([n÷2 + δ]))) end ``` `QuantumWalk.jl` uses the Grover-like search algorithm @wong_equivalence_2017. ```{julia} #| output: false struct Simulation n::Int64 δ::Int64 T::Int64 γ::Float64 data::Vector{Float64} function Simulation(n, δ, T, γ) new(n, δ, T, γ, run_search_mygraph(n, δ, T, γ)) end end mean_hit(s::Simulation) = mean(0:s.T, Weights(success(s))) success(s::Simulation) = accumulate(s.data, init=0) do old, curr (1-old) * curr + old end ``` We can scan over $\gamma \in [0, 1]$ and plot the instantaneous probability of measuring in $\delta$, success probability and the mean hitting time in @fig-uqreset. :::{.callout-tip} ## Alternative Definition of the Mean Hitting Time Although the definition of mean hitting time we have defined until now is only valid for a measure and continue semi-quantum walk, we adopt a similar definition for this walk, only without actual measurements. In this section, (particularly @fig-uqreset and @fig-uqreset-full), we use a measure and rerun protocol, and define the success probability $S_n$ on the basis of $F_i$ of the unmeasured quantum walk until each time $i < n$ ::: ```{julia} res = map(0:0.01:1) do γ Simulation.(100, 10, 100, γ) end; ``` ```{julia} #| echo: false #| label: fig-uqreset #| layout: [[1,1], [1]] #| fig-cap: "Unitary Quantum Reset. These results are for a walk on $n=100, \\delta=10, T_{max}=100$. This is a very small state space, run for a short time, so results should only be considered qualitatively, but we can still see the effect of unitary resetting on the success probability." #| fig-subcap: #| - "Probability of measuring in $\\delta$" #| - "Success Probability" #| - "Mean hit time vs time" p1 = plot() for r in res[1:20:end] plot!( p1, r.data, label="$(r.γ)", xlabel="\$t\$", ylabel="\$P_\\delta(t)\$", title="n=$(res[1].n), T=$(res[1].T), δ = $(res[1].δ)", legend=:outerright ) end p2 = plot() for r in res[1:20:end] plot!( p2, success(r), label="$(r.γ)", xlabel="\$t\$", ylabel="\$S_\\delta(t)\$", title="n=$(res[1].n), T=$(res[1].T), δ = $(res[1].δ)", legend=:outerright ) end k = map(res) do r (r.γ, mean_hit(r)) end p3 = plot( k, xlabel="\$\\gamma\$", ylabel="\$\\langle hit \\rangle\$", title="n=$(res[1].n), T=$(res[1].T), δ = $(res[1].δ)" ) display(p1) display(p2) display(p3) ``` ## Results ### Exceptional Quantum Walk on the Cycle For the non reset ($\gamma = 0$) case, we see that the success rate does not increase with time. While this is initially surprising, this is a known result @wong_exceptional_2017, caused due to the fact that the initial state evolves by phase flips, and the amplitude does not increase. In the reset case, we see that the walk is no longer exceptional (at least, not in this sense), which allows for an amplitude amplification on the marked node. ### Mean hitting time vs $\gamma$ Plotting the mean hitting time (the alternative definition (@sec-umht)) versus $\gamma$ for $500$ nodes and $500$ steps, we get the curve in @fig-uqreset-full. ![Mean hitting time vs $\gamma$ for the Unitary Quantum Reset. We observe a non-monotonic curve for the mean hitting time, and a speed-up compared to the non-reset case. This was run for $n=500, \delta=50, T_{max}=1000$](./images/uqreset-full.png){#fig-uqreset-full width=75%} As we can see, there is a clear non-monotonous effect of $\gamma$ on the mean hitting time of the walk. For values a bit more than $\gamma = 0.5$, we see that the mean hitting time is much lower than that for the no reset $\gamma = 0$ case. Also of note is that as $\gamma \to 1$ the mean hitting rate approaches that of the no reset case. Numerically, the exact time for mean hit changes according to the amount of time that we run the simulation for. This is obvious from the way that the mean hit time is calculated, where if the walk has not succeeded within the time of running the simulation, we assume that it succeeds in the next step. However, we recover the same qualitative curve for large number of steps. ### Eigenvalue analysis In @sec-qht, we saw how the quadratic increase in the eigen-gap ($\Delta P$) leads to an associated speedup in the search problem. Thus, if we can show that the eigen-gap increases in for the reset case, we can show that the search protocol requires fewer steps to complete. Furthermore, the space cost of the circuit goes as $\left\lceil \log_2 \left(\frac{2\pi}{\Delta P}\right)\right\rceil$ We see that the transition matrix is extremely sparse, especially for larger system sizes (goes as $\mathcal{O}(3N)$, so the density goes as $\mathcal{O}(1/N)$), and that we do not require the entire eigen spectrum to find the eigen-gap. Thus, we can use specialized methods such as the Arnoldi method provided in Julia by the `KrylovKit.jl` @jutho_juthokrylovkitjl_nodate package. ```{julia} #| output: false using KrylovKit function eigen_gap(M) v = real(eigsolve(M, 2, :LR)[1]) # get real(eigval) v[1] - v[2] end γs = 0.:0.01:(1-0.01) ΔP = eigen_gap.(getindex.(MyGraph.(512, γs), 2)) ``` ```{julia} #| echo: false #| label: fig-eigengap #| layout-ncol: 2 #| fig-cap: "Analysis by Eigen Gap of the Reset Walk. See that the eigengap increases with $\\gamma$, and therefore, there is a corresponding decrease in the space requirement of the protocol. $n=500, \\delta=50, T_{max}=1000$" #| fig-subcap: #| - "Eigen Gap" #| - "Space complexity" display( plot( γs, ΔP, lims=(0,1), xlabel="\$\\gamma\$", ylabel="\$\\Delta P\$", title="Eigen Gap vs \\gamma" ) ) display( plot( γs, ceil.(log2.(2π ./ ΔP)), xlabel="\$\\gamma\$", ylabel="\$s\$", title="Space complexity vs \$\\gamma\$" ) ) ``` Plotting $\Delta P$ vs $\gamma$ in @fig-eigengap, we see that increasing $\gamma$ leads to an equal increase in $\Delta P$, which corresponds to a faster convergence under the Grover-like search protocol. Note however that we do not have a quantitative characterization of what the final probability of success is. Therefore, despite the faster convergence, the non-monotonic nature of the mean hitting time against $\gamma$ can be explained by a loss in final success probability. The interplay of these two effects may be the cause of the existence of an optimal reset parameter. ## Discussions A particular advantage of the Unitary quantum reset is that we are not limited to only resets on 1D chains. We can define the unitary reset walk on any irreducible graph that one can come up with, even periodic graphs, since resetting a periodic graph leads to an aperiodic graph (@sec-reset-periodicity), and the corresponding walk can be quantised by the Szegedy formalism. While it is clear that there is an obvious speedup compared to the walk without reset, we cannot directly compare these results with the stochastic reset quantum walk due to the different definitions of $F_n$. The quantification of the quantum hitting time for Szegedy walks is an area of very active research @boito_quantum_2023. Another possible approach would be via the semi-quantum Szegedy walk @ortega_discrete-time_2023. These methods have been left as a possible future work.