3 Search Algorithms

A common application of walks is in search problems. In search problems, we generally have a black box function

\[ f(x) = \begin{cases} 0 & x \in G\\ 1 & x \in G^C \end{cases} \]

where $G \cup G^C = S$ which is the search space. We are interested in developing an algorithm to output some $x \in G$ by querying $f$.

Naively, one can run a stochastic process over the domain $G\cup G^C$ and observe the system until we see an element in $G$. The average time to succeed in this protocol is called the hitting time of $G$, and denoted as $HT(P, G)$. Naturally, we not only want high success rates, but we also want low mean hit times.

In the particular case of Markov chains, hitting times are a kind of stopping time (Appendix A), and are well studied in their own regard.

Formalism

Define the following

Denote the readout at the $n^{\text{th}}$ measurement (at $t=n\tau$) as $X_n$.
Select a target node $\delta$
Probability of first hit in $n$ steps $F_n = P(X_n = \delta | X_i \ne \delta \forall i \in [0, n-1])$
Mean hit time $\langle t_S \rangle = \sum_{i=0}^\infty i F_i$
Success probability in $n$ steps $S_n = \sum_{i=1}^{n}F_i = P(\exists i \in [0, n]| X_i = \delta)$
Survival probability $=$ Failure probability $= \mathcal{S}_n = 1 - S_n$
Asymptotic versions of these terms are given by taking $n\to \infty$

Readout in Walks

To identify whether a walker has hit the target node, we need to track the location of the walker as it evolves in time.

For the classical case, this poses no problem, as measurement does not disturb the system. In the quantum case however, we need to be a bit more careful.

A constantly measured walker will freeze the dynamics of a quantum walker. This is known as the Quantum Zeno effect. The solution for this is to measure after every $\tau$ steps.

Semi-quantum walk

This results in what is technically a semi-quantum walk¹, since measurement leads to a complete loss of coherence in the system. However, the walk between two measurement events is quantum in nature, and increasing $\tau$ leads to the quantum features of the walk dominating. We shall however keep this at the back of our minds and refer to this walk as the quantum walk, until we reach Chapter 6.

Reduction to classical random walk with $\tau=1$

The quantum $\tau = 1$ case reduces the discrete time quantum walk to a classical random walk with $\tau=1$. Effectively, we apply a dephasing operator on the density matrix, dropping all off diagonal terms. Thus, we lose all effects of superposition, causing the classical random walk.

Plotting the readout trajectories of walkers with different parameters in Figure 3.1, we see the very clear difference in the spread between the classical readout and the quantum readout for same $\tau$: The quantum walker spreads much faster than the classical walker, and thus scans a larger area. Similarly, note the spread between the quantum readouts for different $\tau$s: A larger $\tau$ value leads to the walk behaving more quantum-like, corresponding to a larger spread for the same number of measurements.

Figure 3.1: Trajectories of readouts in quantum and classical walks. The dependence on the spread of the walk on the time between measurement is clear, with larger $\tau$ values spreading more, and the quantum walks spreading faster than their classical counterparts.

Markov Chains and Walks

In the classical case, it is clear that the 1D SSRW is a Markov process. In Appendix B, we show that the quantum walk with measurement is also a Markov process. Consequently, we can use certain results from the theory of Markov processes to compare the two walks.

Irreducibilty and Recurrence

Under the usual definition of irreducibility (Appendix A), it is trivial that in the 1D chain, $n = m = |i-j|\tau$ satisfies the condition. It is a well known fact that the 1D SSRW is recurrent. It is just as well known a fact that the 3D SSRW is transient².

In the quantum case, it is not as clear whether any of the available definitions of the quantum Markov process is more or less good than the others. Thus, the transience of quantum walks depends on the exact definition we are working under³. In our definition however, it can be shown using symbolic computation⁴ that the walk is indeed transient. This poses an interesting problem which we shall discuss below.

Survival probability

We can thus measure and plot the $S_n - n$ curve for the quantum and classical walks to compare the efficiency of these walks in the first hit problem.

In previous work⁵, the analytical solution of the success rate as a function of time is found. An analytical result for discrete time walks is harder due to the nature of the walk. However, we reproduce the results for the discrete time case computationally. Figure 3.2 (a)⁵ shows the success rate for the continuous time quantum and classical walks, and Figure 3.2 (b) shows our results for the discrete time case.

(a) Success probability vs Time for both walks⁵, continuous time. $\tau=0.25, \delta=10$. Asymptotic success rate of the quantum walk is approximately 0.1, whereas the classical walk approaches 1.

Observations - The Tortoise and the Hare

In the continuous time case:

The quantum walk has a fast rise in the initial phase but saturates at ~0.1
The classical walk has a slow rise, but eventually reaches 1

In the discrete time case, solved computationally:

Both walks do eventually reach 1
The quantum walk shows a saturation for a while before suddenly rising again
The classical walk shows a slow rise in the beginning phases, in contrast to the sharper rise of the quantum walk.

There seems to be an apparent difference between the discrete and the continuous time walks, where in the discrete walk, the asymptotic success reaches 1 even in the quantum case, but this is only an artifact of the finite size of the walk space. It is well known that any irreducible finite chain is recurrent⁶. This claim can be verified by simply increasing the size of the state space, and noting that the saturation phase in the quantum walk lasts longer.

The observations in the continuous time case can be explained by the recurrence of the walk. While the quantum walker is faster (See Chapter 2), the transient nature (See Section 3.2.1) of the walk leads to a non-zero asymptomatic failure rate. Clearly this is a problem. What this means practically, is that for the first hit problem, if the quantum walk hits the target node, it does so faster than the classical walk, but a majority of the times, it doesn’t hit the target node at all. This is reminiscent of the age-old fable of a race between the Tortoise and the Hare. The Tortoise-like classical walk is slow, but trudges on to the finish line, whereas the Hare-like quantum walk speeds away in the beginning, but falls behind.

But we want a walk that is both fast, and with an asymptotic success rate of 1. Can we give something to our Hare so that it doesn’t fall asleep?

# Search Algorithms {#sec-search} ```{julia} #| echo: false using LinearAlgebra using Plots using QuantumInformation using Statistics using StatsBase using SparseArrays ``` A common application of walks is in search problems. In search problems, we generally have a black box function $$ f(x) = \begin{cases} 0 & x \in G\\ 1 & x \in G^C \end{cases} $$ where $G \cup G^C = S$ which is the search space. We are interested in developing an algorithm to output some $x \in G$ by querying $f$. Naively, one can run a stochastic process over the domain $G\cup G^C$ and observe the system until we see an element in $G$. The average time to succeed in this protocol is called the hitting time of $G$, and denoted as $HT(P, G)$. Naturally, we not only want high success rates, but we also want low mean hit times. In the particular case of Markov chains, hitting times are a kind of stopping time (@sec-markov), and are well studied in their own regard. ## Formalism Define the following - Denote the readout at the $n^{\text{th}}$ measurement (at $t=n\tau$) as $X_n$. - Select a target node $\delta$ - Probability of first hit in $n$ steps $F_n = P(X_n = \delta | X_i \ne \delta \forall i \in [0, n-1])$ - Mean hit time $\langle t_S \rangle = \sum_{i=0}^\infty i F_i$ - Success probability in $n$ steps $S_n = \sum_{i=1}^{n}F_i = P(\exists i \in [0, n]| X_i = \delta)$ - Survival probability $=$ Failure probability $= \mathcal{S}_n = 1 - S_n$ - Asymptotic versions of these terms are given by taking $n\to \infty$ ### Readout in Walks To identify whether a walker has hit the target node, we need to track the location of the walker as it evolves in time. For the classical case, this poses no problem, as measurement does not disturb the system. In the quantum case however, we need to be a bit more careful. A constantly measured walker will freeze the dynamics of a quantum walker. This is known as the Quantum Zeno effect. The solution for this is to measure after every $\tau$ steps. ::: {.callout-important} ## Semi-quantum walk This results in what is technically a semi-quantum walk @ortega_discrete-time_2023, since measurement leads to a complete loss of coherence in the system. However, the walk between two measurement events is quantum in nature, and increasing $\tau$ leads to the quantum features of the walk dominating. We shall however keep this at the back of our minds and refer to this walk as the quantum walk, until we reach @sec-szegedy. ::: ::: {.callout-note} ## Reduction to classical random walk with $\tau=1$ The quantum $\tau = 1$ case reduces the discrete time quantum walk to a classical random walk with $\tau=1$. Effectively, we apply a dephasing operator on the density matrix, dropping all off diagonal terms. Thus, we lose all effects of superposition, causing the classical random walk. ::: Plotting the readout trajectories of walkers with different parameters in @fig-trajs, we see the very clear difference in the spread between the classical readout and the quantum readout for same $\tau$: The quantum walker spreads much faster than the classical walker, and thus scans a larger area. Similarly, note the spread between the quantum readouts for different $\tau$s: A larger $\tau$ value leads to the walk behaving more quantum-like, corresponding to a larger spread for the same number of measurements. ```{julia} #| echo: false #| label: fig-trajs #| fig-cap: "Trajectories of readouts in quantum and classical walks. The dependence on the spread of the walk on the time between measurement is clear, with larger $\\tau$ values spreading more, and the quantum walks spreading faster than their classical counterparts." begin mqwts, mqwpaths = let R = collect(Tridiagonal(fill(1., 80), zeros(81), zeros(80))) R[1, end] = 1 L = collect(Tridiagonal(zeros(80), zeros(81), fill(1., 80))) L[end, 1] = 1 U = KrausOperators([sparse(proj(ket(1, 2)) ⊗ L + proj(ket(2, 2)) ⊗ R)]) init_coin = 1/√2 * (ket(1,2) - 1im * ket(2,2)) H = KrausOperators([sparse(hadamard(2)⊗I(81))]) init_state = proj(init_coin ⊗ ket(41,81)) k = 204 τ = 6 ys = map(1:15) do _ ψ = [[(41, init_state)]; accumulate(1:k, init=(41, init_state)) do (lr, old), t ψ′ = H(U(old)) if t % τ == 0 coin = ptrace(ψ′, [2, 81], [2]) lr = sample(1:81, Weights(real(diag(ptrace(ψ′, [2, 81], [1]))))) ψ′ = coin ⊗ proj(ket(lr, 81)) end (lr, ψ′) end] first.(ψ)[1:τ:k+1] .- 41 end 0:τ:τ*(length(first(ys))-1), ys end; mqwts_2, mqwpaths_2 = let R = collect(Tridiagonal(fill(1., 80), zeros(81), zeros(80))) R[1, end] = 1 L = collect(Tridiagonal(zeros(80), zeros(81), fill(1., 80))) L[end, 1] = 1 U = KrausOperators([sparse(proj(ket(1, 2)) ⊗ L + proj(ket(2, 2)) ⊗ R)]) init_coin = 1/√2 * (ket(1,2) - 1im * ket(2,2)) H = KrausOperators([sparse(hadamard(2)⊗I(81))]) init_state = proj(init_coin ⊗ ket(41,81)) k = 204 τ = 10 ys = map(1:15) do _ ψ = [[(41, init_state)]; accumulate(1:k, init=(41, init_state)) do (lr, old), t ψ′ = H(U(old)) if t % τ == 0 coin = ptrace(ψ′, [2, 81], [2]) lr = sample(1:81, Weights(real(diag(ptrace(ψ′, [2, 81], [1]))))) ψ′ = coin ⊗ proj(ket(lr, 81)) end (lr, ψ′) end] first.(ψ)[1:τ:k+1] .- 41 end 0:τ:τ*(length(first(ys))-1), ys end; mqwts_3, mqwpaths_3 = let R = collect(Tridiagonal(fill(1., 80), zeros(81), zeros(80))) R[1, end] = 1 L = collect(Tridiagonal(zeros(80), zeros(81), fill(1., 80))) L[end, 1] = 1 U = KrausOperators([sparse(proj(ket(1, 2)) ⊗ L + proj(ket(2, 2)) ⊗ R)]) init_coin = 1/√2 * (ket(1,2) - 1im * ket(2,2)) H = KrausOperators([sparse(hadamard(2)⊗I(81))]) init_state = proj(init_coin ⊗ ket(41,81)) k = 204 τ = 1 ys = map(1:15) do _ ψ = [[(41, init_state)]; accumulate(1:k, init=(41, init_state)) do (lr, old), t ψ′ = H(U(old)) if t % τ == 0 coin = ptrace(ψ′, [2, 81], [2]) lr = sample(1:81, Weights(real(diag(ptrace(ψ′, [2, 81], [1]))))) ψ′ = coin ⊗ proj(ket(lr, 81)) end (lr, ψ′) end] first.(ψ)[1:τ:k+1] .- 41 end 0:τ:τ*(length(first(ys))-1), ys end; end; bm2 = cumsum(rand([1, -1], (205, 15)), dims=1)[mqwts.+1, :]; let q = Plots.plot( mqwts, mqwpaths, ylims=(-40, 40), ylabel="\$n\$", xlabel="t", title="Quantum Readout Path, \$\\tau = 6\$", labels=reshape(map(i->"W $(i)", 1:length(mqwpaths)), 1, :), legend=:outerright, size=(700, 400) ) p = Plots.plot( mqwts, bm2, ylims=(-40, 40), ylabel="\$n\$", xlabel="t", title="Classical Readout Path, \$\\tau = 6\$", labels=reshape(map(i->"W $(i)", 1:length(mqwpaths)), 1, :), legend=:outerright, size=(700, 400) ) q2 = Plots.plot( mqwts_2, mqwpaths_2, ylims=(-40, 40), ylabel="\$n\$", xlabel="t", title="Quantum Readout Path, \$\\tau = 10\$", labels=reshape(map(i->"W $(i)", 1:length(mqwpaths)), 1, :), legend=:outerright, size=(700, 400) ) q3 = Plots.plot( mqwts_3, mqwpaths_3, ylims=(-40, 40), ylabel="\$n\$", xlabel="t", title="Classical Readout Path, \$\\tau = 1\$", labels=reshape(map(i->"W $(i)", 1:length(mqwpaths)), 1, :), legend=:outerright, size=(700, 400) ) k = Plots.plot(p, q, q2, q3, size=(1400, 800) .* 0.65) end ``` ## Markov Chains and Walks In the classical case, it is clear that the 1D SSRW is a Markov process. In @sec-meas-markov, we show that the quantum walk with measurement is also a Markov process. Consequently, we can use certain results from the theory of Markov processes to compare the two walks. ### Irreducibilty and Recurrence {#sec-recurrence} Under the usual definition of irreducibility (@sec-markov), it is trivial that in the 1D chain, $n = m = |i-j|\tau$ satisfies the condition. It is a well known fact that the 1D SSRW is recurrent. It is just as well known a fact that the 3D SSRW is transient @norris_markov_1998. In the quantum case, it is not as clear whether any of the available definitions of the quantum Markov process is more or less good than the others. Thus, the transience of quantum walks depends on the exact definition we are working under @stefanak_recurrence_2008. In our definition however, it can be shown using symbolic computation @friedman_quantum_2017 that the walk is indeed transient. This poses an interesting problem which we shall discuss below. ## Survival probability We can thus measure and plot the $S_n - n$ curve for the quantum and classical walks to compare the efficiency of these walks in the first hit problem. In previous work @yin_restart_2022, the analytical solution of the success rate as a function of time is found. An analytical result for discrete time walks is harder due to the nature of the walk. However, we reproduce the results for the discrete time case computationally. @Fig-barkai @yin_restart_2022 shows the success rate for the continuous time quantum and classical walks, and @fig-discrete shows our results for the discrete time case. ::: {#fig-succ_prob layout="[[1], [1]]"} ![Success probability vs Time for both walks @yin_restart_2022, continuous time. $\tau=0.25, \delta=10$. Asymptotic success rate of the quantum walk is approximately 0.1, whereas the classical walk approaches 1.](./images/11-26-00-48.png){#fig-barkai} ![Success probability vs Time for both walks, discrete time. $\delta=10$. See that more "quantumness" in the walk leads to a faster initial rise, but saturation at lower asymptotic success, allowing the slower classical walk to overtake.](./images/bar_curves_qc.png){#fig-discrete} Success probability vs Time for both walks, continuous and discrete time. ::: ### Observations - The Tortoise and the Hare In the _continuous time_ case: - The quantum walk has a fast rise in the initial phase but saturates at ~0.1 - The classical walk has a slow rise, but eventually reaches 1 In the _discrete time_ case, solved computationally: - Both walks do eventually reach 1 - The quantum walk shows a saturation for a while before suddenly rising again - The classical walk shows a slow rise in the beginning phases, in contrast to the sharper rise of the quantum walk. There seems to be an apparent difference between the discrete and the continuous time walks, where in the discrete walk, the asymptotic success reaches 1 even in the quantum case, but this is only an artifact of the finite size of the walk space. It is well known that any irreducible finite chain is recurrent @SO_297334. This claim can be verified by simply increasing the size of the state space, and noting that the saturation phase in the quantum walk lasts longer. The observations in the continuous time case can be explained by the recurrence of the walk. While the quantum walker is faster (See @sec-quantum), the transient nature (See @sec-recurrence) of the walk leads to a non-zero asymptomatic failure rate. Clearly this is a problem. What this means practically, is that for the first hit problem, if the quantum walk hits the target node, it does so faster than the classical walk, but a majority of the times, it doesn't hit the target node at all. This is reminiscent of the age-old fable of a race between the Tortoise and the Hare. The Tortoise-like classical walk is slow, but trudges on to the finish line, whereas the Hare-like quantum walk speeds away in the beginning, but falls behind. But we want a walk that is both fast, and with an asymptotic success rate of 1. Can we give something to our Hare so that it doesn't fall asleep?