Conserved Quantities in Linear and Nonlinear Quantum Search

David A. Meyer; Thomas G. Wong

doi:10.2478/qic-2025-0017

Introduction

1.

Conserved quantities play important roles in physics: energy, momentum, and angular momentum are conserved in systems that are time, translation, and rotation invariant, respectively. In quantum mechanics, the wave function ψ of a system with Hamiltonian H₀ evolves according to Schrödinger’s equation,

1

i ℏ \frac{\partial ψ}{\partial t} = H_{0} ψ,

where we will work in units where the reduced Planck constant ħ = 1 throughout this paper. The Hamiltonian H₀ must be Hermitian (i.e., self-adjoint), which causes the time evolution to be unitary. Then, |ψ|² = 〈ψ|ψ〉 is a conserved quantity, meaning a normalized wave function stays normalized, which is necessary for the probabilistic interpretation of the wave function à la the Born rule. This may not be the only conserved quantity, however. For example, if the Hamiltonian is time-independent, then the expected value of the Hamiltonian 〈H₀ = 〈ψ|H₀|ψ〉, i.e., the average energy of an ensemble of identically prepared systems, is also conserved [1]. The time-independence of the Hamiltonian and the conservation of its expected value hold for many quantum algorithms based on continuoustime quantum walks [2–4], where the particle walks on the vertices of a graph, and the kinetic energy of the system is proportional to the discrete Laplacian. For overviews of quantum walks, see [5–8]. In Section 2, we will give an example of this by reviewing how a continuous-time quantum walk searches the complete graph for a marked vertex [3,9], which is the combinatorial formulation of the unstructured search problem of Grover’s algorithm [10]. In the process, we will give a new derivation of the evolution of the algorithm for arbitrary jumping rates, as well as give a new derivation—using only elementary calculus—of the critical jumping rate that causes the algorithm to succeed with certainty. We will explicitly show that for the Hamiltonian used in the search algorithm, 〈H₀〉 is conserved.

Some many-body quantum systems are approximately described by an effectively nonlinear Schrödinger-type equation with a cubic nonlinearity proportional to |ψ|²ψ, i.e.,

2

i ℏ \frac{\partial ψ}{\partial t} = (H_{0} + λ | ψ |^{2}) ψ,

where the effective Hamiltonian

3

H (t) = H_{0} + λ | ψ |^{2}

depends on time because it depends on the state ψ, which evolves with time. A Bose-Einstein condensate [11–13] is an example of such a system, with the Gross-Pitaevskii equation [14,15] describing it in the mean-field limit and taking the form of the cubic nonlinear Schrödinger equation (2); for reviews, see [16,17]. As before, |ψ|² = 1 is conserved, but since H(t) is time-dependent, 〈H(t)〉 = 〈ψ|H(t)|ψ〉 is not conserved. When H₀ is a constant, however, then

〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉 = 〈 ψ | H_{0} + \frac{1}{2} λ | ψ |^{2} | ψ 〉

is conserved [18]. In Section 3, we will give an example of this by reviewing how a nonlinear quantum walk with λ > 0, which corresponds to a Bose-Einstein condensate with repulsive interactions, searches the complete graph for a marked vertex [19], and we will explicitly show that

〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉

is conserved for the algorithm.

If H₀ depends on time, however, then $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ is generally not conserved. In Section 4, we give an example of this by reviewing how a nonlinear quantum walk with λ < 0, which corresponds to a Bose-Einstein condensate with attractive interactions, searches a complete graph of N vertices for a marked vertex [20]. In this algorithm, the jumping rate of the quantum walk is a critical, time-dependent function γ_c(t), which causes H₀ to be time-dependent as well. While $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ is not conserved in this case, we show that the critical jumping rate is such that 〈H₀/[γ_c(t)N]〉 is conserved instead.

Thus, in this tutorial, we will review three continuous-time quantum walk algorithms for searching the complete graph: a linear algorithm in Section 2, a nonlinear algorithm corresponding to a Bose-Einstein condensate with repulsive interactions in Section 3, and a nonlinear algorithm corresponding to a Bose-Einstein condensate with attractive interactions in Section 4. For each, we will demonstrate a conserved quantity related to the (effective) Hamiltonian of the system, thus making connections between quantum algorithms, conservation laws, and manybody quantum systems. We conclude in Section 5.

Linear Quantum Search

2.

In quantum mechanics, the Hamiltonian H₀ is the operator corresponding to the total energy of the system, which consists of a kinetic energy term that is proportional to Laplace’s operator ▽² and a potential energy term V [1]:

H_{0} = - \frac{ℏ^{2}}{2 m} \nabla^{2} + V .

For a quantum walk on a graph of N vertices, the vertices label computational basis states |1〉, |2〉, …, |N〉, and in general, the state is a superposition or complex linear combination over the vertices. Then, Laplace’s operator in the continuum should be replaced by the discrete Laplacian L:

H_{0} = - γ L + V,

where L is an N × N matrix with L_ij = 1 if vertices i and j are adjacent, L_ii = – deg(i) is the negative of the number of neighbors of vertex i, and L_ij = 0 otherwise. For the complete graph of N vertices, an example of which is shown in Figure 1, the discrete Laplacian has 1 for each off-diagonal element and –(N – 1) on the diagonal. We have also written the coefficient of L as a parameter γ, which corresponds to the jumping rate of the quantum walk. To construct a quantum search algorithm [3], an oracle “marks” a particular vertex |a〉 that we want to find, which manifests as a potential energy term:

4

H_{0} = - γ L - | a 〉 〈 a | .

A complete graph of N = 6 vertices. A vertex is marked, as indicated by a double circle. In the search algorithm, vertices that evolve identically have the same label and color.

Initially, we have no knowledge of where the marked vertex might be, so we guess each vertex equally by beginning in a uniform superposition over all N vertices:

5

| ψ (0) 〉 = \frac{1}{\sqrt{N}} \sum_{i = 1}^{N} | i 〉 .

Then, the system evolves by Schrödinger’s equation (1), and since H₀ is time-independent,

6

| ψ (t) 〉 = e^{- i H_{0} t} | ψ (0) 〉,

where we have taken ħ = 1. The success probability at time t is the probability that measuring the position of the particle at time t results in it being found at the marked vertex, so the success probability is

7

p (t) = | 〈 a ∣ ψ (t) 〉 |^{2} .

The evolution of this success probability is plotted in Figure 2 for search on a complete graph of N = 100 vertices and with various values of the jumping rate γ. In Figure 2a, the jumping rate starts off small as γ = 0.001 in the solid black curve, and the success probability is relatively unchanged from its initial value of 1/100 = 0.01. As the jumping rate increases, however, the success probability evolves with a higher and higher peak, eventually reaching a peak success probability of 1 when γ = 0.01. In Figure 2b, γ is increased further, and the peak success probability decreases, with larger γ resulting in the success probability staying near its initial value.

Success probability versus time for (linear) quantum search on the complete graph with N = 100 vertices and various jumping rates. In (a), the solid black curve is γ = 0.001, the dashed red curve is γ = 0.005, the dotted green curve is γ = 0.008, the dot-dashed blue curve is γ = 0.009, and the dot-dot-dashed orange curve is γ = 0.01. In (b), the solid black curve is γ = 0.011, the dashed red curve is γ = 0.012, the dotted green curve is γ = 0.015, the dot-dashed blue curve is γ = 0.02, and the dot-dot-dashed orange curve is γ = 0.03.

To prove this behavior, we begin by noting that due to the symmetry of the problem, there are only two types of vertices: the marked vertex and the unmarked vertices, labeled in Figure 1 as a and b. Vertices of the same type evolve identically, so the system evolves in a two-dimensional (2D) subspace spanned by the marked vertex |a〉 and the uniform superposition of unmarked vertices, which we will call |b〉:

| b 〉 = \frac{1}{\sqrt{N - 1}} \sum_{i u n m a r k e d} | i 〉 .

In this basis, the initial state (5) is

8

| ψ (0) 〉 = \frac{1}{\sqrt{N}} | a 〉 + \sqrt{\frac{N - 1}{N}} | b 〉 = \frac{1}{\sqrt{N}} (\begin{matrix} 1 \\ \sqrt{N - 1} \end{matrix}),

and the Hamiltonian (4) is

9

= (\begin{matrix} γ (N - 1) - 1 & - γ \sqrt{N - 1} \\ - γ \sqrt{N - 1} & γ \end{matrix}) .

The (unnormalized) eigenvectors and eigenvalues of H₀ are

\begin{array}{l} ψ_{1} = (γ N - 2 γ - 1 - Δ E) | a 〉 - 2 γ \sqrt{N - 1} | b 〉, & E_{1} = \frac{γ N - 1 - Δ E}{2}, \\ ψ_{2} = (γ N - 2 γ - 1 + Δ E) | a 〉 - 2 γ \sqrt{N - 1} | b 〉, & E_{2} = \frac{γ N - 1 + Δ E}{2}, \end{array}

where

10

Δ E = E_{2} - E_{1} = \sqrt{γ^{2} N^{2} - 2 γ N + 4 γ + 1}

is the energy gap. Expressing the initial state (8) as a linear combination of these eigenvectors,

| ψ (0) 〉 = \frac{- γ N + 1 - Δ E}{4 γ \sqrt{N} Δ E} ψ_{1} + \frac{γ N - 1 - Δ E}{4 γ \sqrt{N} Δ E} ψ_{2} .

Then, using (6), the state of the system at time t is

11

\begin{array}{l} | ψ (t) 〉 & = e^{- i H_{0} t} (\frac{- γ N + 1 - Δ E}{4 γ \sqrt{N} Δ E} ψ_{1} + \frac{γ N - 1 - Δ E}{4 γ \sqrt{N} Δ E} ψ_{2}) \\ = \frac{- γ N + 1 - Δ E}{4 γ \sqrt{N} Δ E} e^{- i E_{1} t} ψ_{1} + \frac{γ N - 1 - Δ E}{4 γ \sqrt{N} Δ E} e^{- i E_{2} t} ψ_{2} \\ = \frac{e^{- i (γ N - 1) t / 2}}{4 γ \sqrt{N} Δ E} [(- γ N + 1 - Δ E) e^{i Δ E t / 2} ψ_{1} + (γ N - 1 - Δ E) e^{- i Δ E t / 2} ψ_{2}] \\ = \frac{e^{- i (γ N - 1) t / 2}}{4 γ \sqrt{N} Δ E} {(- γ N + 1 - Δ E) e^{i Δ E t / 2} [(γ N - 2 γ - 1 - Δ E) | a 〉 - 2 γ \sqrt{N - 1} | b 〉] + (γ N - 1 - Δ E) e^{- i Δ E t / 2} [(γ N - 2 γ - 1 + Δ E) | a 〉 - 2 γ \sqrt{N - 1} | b 〉]} \\ = \frac{e^{- i (γ N - 1) t / 2}}{4 γ \sqrt{N} Δ E} {[(e^{i Δ E t / 2} - e^{- i Δ E t / 2}) ((- γ N + 1) (γ N - 2 γ - 1) + {(Δ E)}^{2}) + (e^{i Δ E t / 2} + e^{- i Δ E t / 2}) (- Δ E (γ N - 2 γ - 1) + (γ N - 1) Δ E)] | a 〉 - 2 γ \sqrt{N - 1} [(e^{i Δ E t / 2} - e^{- i Δ E t / 2}) (- γ N + 1) + (e^{i Δ E t / 2} + e^{- i Δ E t / 2}) (- Δ E)] | b 〉} \\ = \frac{e^{- i (γ N - 1) t / 2}}{4 γ \sqrt{N} Δ E} {[2 i \sin (\frac{Δ E t}{2}) [(- γ N + 1) (γ N - 2 γ - 1) + {(Δ E)}^{2}] + 2 \cos (\frac{Δ E t}{2}) 2 γ Δ E] | a 〉 - 2 γ \sqrt{N - 1} [2 i \sin (\frac{Δ E t}{2}) (- γ N + 1) + 2 \cos (\frac{Δ E t}{2}) (- Δ E)] | b 〉} . \end{array}

Taking the norm-square of the amplitude of |a〉, the success probability (7) at time t is

12

\begin{array}{l} p (t) & = \frac{1}{16 γ^{2} N {(Δ E)}^{2}} {4 \sin^{2} (\frac{Δ E t}{2}) {[(- γ N + 1) (γ N - 2 γ - 1) + {(Δ E)}^{2}]}^{2} + 16 γ^{2} {(Δ E)}^{2} \cos^{2} (\frac{Δ E t}{2})} \\ = {(\frac{(- γ N + 1) (γ N - 2 γ - 1) + {(Δ E)}^{2}}{2 γ \sqrt{N} Δ E})}^{2} \sin^{2} (\frac{Δ E t}{2}) + \frac{1}{N} \cos^{2} (\frac{Δ E t}{2}) . \end{array}

This agrees with the curves in Figure 2 with N = 100 and various values of γ. The success probability reaches a maximum value when the sine is 1 and the cosine is 0, i.e., at time

13

t_{*} = \frac{π}{Δ E},

at which the success probability peaks at

14

p_{*} = {(\frac{(- γ N + 1) (γ N - 2 γ - 1) + {(Δ E)}^{2}}{2 γ \sqrt{N} Δ E})}^{2} .

To the best of our knowledge, the above results for |ψ(t)〉 (11), p(t) (12), t_* (13), and p_* (14) for arbitrary γ are new, as previous literature [9] focused on the specific case when γ = 1/N, motivated by minimizing the energy gap [3] or by degenerate perturbation theory [21]. Now, we will provide another way to arrive at the γ = 1/N case, namely, using elementary calculus to prove that it is the value of γ that maximizes the peak success probability p_* (14). Substituting the energy gap ΔE (10) into p_* (14) and differentiating the result with respect to γ, we get

\frac{d p_{*}}{d γ} = \frac{4 (N - 1) (γ^{2} N^{2} - 1)}{N {(γ^{2} N^{2} - 2 γ (N - 1) + 1)}^{2}} .

Setting this equal to 0 and solving for γ, the peak success probability p_* is maximized when γ takes a critical value of

γ_{c} = \frac{1}{N},

at which the energy gap (10) is

Δ E_{c} = \frac{2}{\sqrt{N}},

and the peak success probability (14) is

p_{* c} = 1.

That is, γ = γ_c = 1/N makes the algorithm deterministic, i.e., the marked vertex is found with certainty. Using (13), this occurs at time

t_{* c} = \frac{π}{2} \sqrt{N},

which is the expected

O (\sqrt{N})

scaling of Grover’s algorithm [10]. Furthermore, using (12), the success probability evolves with time as

p_{c} (t) = \sin^{2} (\frac{t}{\sqrt{N}}) + \frac{1}{N} \cos^{2} (\frac{t}{\sqrt{N}}),

which agrees with the dot-dot-dashed orange curve in Figure 2a, where N = 100 and γ = 1/100 = 0.01.

Moving on to conserved quantities, since the Hamiltonian (4) is time-independent, its expected value is conserved, i.e., 〈H〉 = 〈ψ(t)|H|ψ(t)〉 is constant in time [1]. We will explicitly show this in the 2D subspace of our algorithm for pedagogical purposes, as the calculation for the nonlinear algorithm in the next section will use similar methods. To begin, we write the state of the system in the {|a〉, |b〉} basis as

15

| ψ (t) 〉 = α (t) | a 〉 + β (t) | b 〉 = (\begin{matrix} α (t) \\ β (t) \end{matrix})

for complex α and β, where for convenience, we have stopped writing the explicit time-dependence of α and β. The Hamiltonian (9) takes the form

16

H_{0} = (\begin{matrix} a & b \\ b^{*} & d \end{matrix}),

where

17

a = γ (N - 1) - 1, b = - γ \sqrt{N - 1}, and d = γ

are real and time-independent, although we allow for b to be complex for greater generality. Then, the expected value of H₀ is

18

\begin{array}{l} 〈 H_{0} 〉 & = 〈 ψ | H_{0} | ψ 〉 \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a & b \\ b^{*} & d \end{matrix}) (\begin{matrix} α \\ β \end{matrix}) \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a α + b β \\ b^{*} α + d β \end{matrix}) \\ = a α^{*} α + b α^{*} β + b^{*} β^{*} α + d β^{*} β . \end{array}

We want to show that this is constant in time. Using the chain rule, its time-derivative is

19

\begin{array}{l} \frac{d 〈 H_{0} 〉}{d t} & = \frac{\partial 〈 H_{0} 〉}{\partial α} \frac{d α}{d t} + \frac{\partial 〈 H_{0} 〉}{\partial β} \frac{d β}{d t} + \frac{\partial 〈 H_{0} 〉}{\partial α^{*}} \frac{d α^{*}}{d t} + \frac{\partial 〈 H_{0} 〉}{\partial β^{*}} \frac{d β^{*}}{d t} \\ = \frac{\partial 〈 H_{0} 〉}{\partial α} \dot{α} + \frac{\partial 〈 H_{0} 〉}{\partial β} \dot{β} + \frac{\partial 〈 H_{0} 〉}{\partial α^{*}} {\dot{α}}^{*} + \frac{\partial 〈 H_{0} 〉}{\partial β^{*}} {\dot{β}}^{*}, \end{array}

where we used a dot to indicate a time derivative. Let us find the partial derivatives of 〈H₀〉 and then the time derivatives of α, β, and their conjugates. First, we differentiate (18) to get

20

\begin{array}{l} \frac{\partial 〈 H_{0} 〉}{\partial α} & = a α^{*} + b^{*} β^{*}, \\ \frac{\partial 〈 H_{0} 〉}{\partial β} & = b α^{*} + d β^{*}, \\ \frac{\partial 〈 H_{0} 〉}{\partial α^{*}} & = a α + b β, \\ \frac{\partial 〈 H_{0} 〉}{\partial β^{*}} & = b^{*} α + d β . \end{array}

Then, to find $\dot{α}, \dot{β}, {\dot{α}}^{*}$ , and ${\dot{β}}^{*}$ in (19), we use Schrödinger’s equation (1):

i (\begin{matrix} \dot{α} \\ \dot{β} \end{matrix}) = (\begin{matrix} a & b \\ b^{*} & d \end{matrix}) (\begin{matrix} α \\ β \end{matrix}),

which multiplied out is

\begin{array}{l} i \dot{α} = a α + b β, \\ i \dot{β} = b^{*} α + d β . \end{array}

Solving for $\dot{α}$ and $\dot{β}$ and taking the complex conjugate of each equation,

21

\begin{array}{l} \dot{α} = - i (a α + b β), \\ \dot{β} = - i (b^{*} α + d β), \\ {\dot{α}}^{*} = i (a α^{*} + b^{*} β^{*}), \\ {\dot{β}}^{*} = i (b α^{*} + d β^{*}) . \end{array}

Plugging (20) and (21) into (19), we get

22

\begin{array}{l} \frac{d 〈 H_{0} 〉}{d t} & = (a α^{*} + b^{*} β^{*}) [- i (a α + b β)] + (b α^{*} + d β^{*}) [- i (b^{*} α + d β)] \\ + (a α + b β) [i (a α^{*} + b^{*} β^{*})] + (b^{*} α + d β) [i (b α^{*} + d β^{*})] \\ = 0, \end{array}

so we have proved that the expected value of the Hamiltonian is constant.

Our derivation also shows that there is a relationship between the derivatives of the expected value of the Hamiltonian and the time derivatives of the amplitudes. Comparing (20) and (21),

23

\begin{array}{l} \frac{\partial 〈 H_{0} 〉}{\partial α} = - i {\dot{α}}^{*}, \\ \frac{\partial 〈 H_{0} 〉}{\partial β} = - i {\dot{β}}^{*}, \\ \frac{\partial 〈 H_{0} 〉}{\partial α^{*}} = i \dot{α}, \\ \frac{\partial 〈 H_{0} 〉}{\partial β^{*}} = i \dot{β} . \end{array}

Plugging these into (19), we get a cleaner proof that the expected value of the Hamiltonian is conserved:

\begin{array}{l} \frac{d 〈 H_{0} 〉}{d t} & = - i {\dot{α}}^{*} \dot{α} - i {\dot{β}}^{*} \dot{β} + i \dot{α} {\dot{α}}^{*} + i \dot{β} {\dot{β}}^{*} \\ = - i | α |^{2} - i | β |^{2} + i | α |^{2} + i | β |^{2} \\ = 0. \end{array}

Of course, the cleanest proof that the expected value of this time-independent Hamiltonian is conserved follows from the fact that the time evolution multiplies any eigenvector ψ_j of H₀ by the phase e^iE_jt. This leaves the norm-squared of the projection of the state onto each eigenspace invariant, and also, a fortiori, 〈H₀〉. This proof fails, however, for the time-dependent evolutions we will consider in the next two sections. This is why we gave the preceding argument, which can be translated into the nonlinear settings.

Nonlinear Quantum Search with Repulsive Interactions

3.

Many-body quantum systems can evolve by effective nonlinearities. Bose-Einstein condensates are a quintessential example, and for pairwise contact interactions in the mean field limit, they evolve by the Gross-Pitaevskii equation, which is a Schrödinger-type equation with a cubic nonlinearity (2). A nonlinear quantum search algorithm [20] can be constructed from this by taking H₀ = –γL – |a〉〈a| (4) so that the effective Hamiltonian (3) becomes

24

H (t) = - γ L - | a 〉 〈 a | + λ \sum_{i = 1}^{N} | 〈 i ∣ ψ (t) 〉 |^{2} | i 〉 〈 i | .

When the nonlinearity coefficient λ is positive, this physically corresponds to bosons with repulsive interactions, and when λ is negative, the interactions are attractive. The sign and strength of λ can be tuned, for example, by Feshbach resonance [22]. In this section, we consider λ > 0, and in the next section, we consider λ < 0.

As shown in [19], for large N, when γ takes a critical value of

γ_{c} = \frac{2 - λ}{2 N}

and the nonlinearity coefficient λ lies in the range 0 < λ < λ_c, where

λ_{c} = \frac{4}{2 + {\sqrt{N}}^{'}}

then the system evolves from the initial uniform superposition (5) to the marked vertex |a〉 in time roughly

t_{*} = \frac{π}{\sqrt{3}} \sqrt{N} .

This runtime is slower than the linear algorithm’s $π \sqrt{N} / 2$ (13) by a factor of $2 / \sqrt{3} \approx 1.155$ , i.e., it is slower by 15.5%. As discussed in [19], although this algorithm searches in the same $O (\sqrt{N})$ time as the linear quantum algorithm, but with a worse coefficient, it nonetheless shows that it is theoretically possible for a Bose-Einstein condensate with repulsive interactions evolving by an effective nonlinearity to implement a quantum search algorithm with an $O (\sqrt{N})$ scaling.

Note from [19] that λ_c is not a tight upper bound, i.e., there may exist some nonlinearity coefficient λ > λ_c for which the success probability reaches 1, but eventually as λ increases, the success probability stops reaching 1. This is shown in Figure 3 for search on a complete graph of N = 100 vertices, for which $λ_{c} = 4 / (2 + \sqrt{100}) = 4 / 12 = 1 / 3 \approx 0.333$ . The solid black curve is λ = 0.2, since 0 < 0.2 < 0.333, the success probability must evolve to 1, as it does. The dashed red curve is λ = 0.4, and while it is greater than λ_c = 0.333, the success probability still reaches 1. The dotted green curve is λ = 0.611, and while the success probability struggles to grow, it does eventually reach 1 off the right of the graph. In contrast, the dot-dashed blue curve is λ = 0.612, and the success probability does not reach 1 anymore. A larger nonlinearity coefficient reaches a smaller and smaller success probability, such as the dot-dot-dashed orange curve with λ = 0.8. A tight upper bound on λ such that the success probability reaches 1 remains an open question.

Success probability versus time for nonlinear quantum search on the complete graph with N = 100 vertices, λ = (2 – λ)/2N, and various values of λ. The solid black curve is γ = 0.2, the dashed red curve is λ = 0.6, the dotted green curve is λ = 0.611, the dot-dashed blue curve is λ = 0.612, and the dot-dot-dashed orange curve is λ = 0.8.

Since the effective Hamiltonian of the search algorithm depends on time, 〈H(t)〉 is generally not conserved. Instead, the expected value of H₀ plus half the nonlinear self-potential is conserved, i.e., $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ is conserved, as this is the quantity that corresponds to the total energy [18]. Conserved quantities for the Gross-Pitaevskii equation have been explored in some other contexts, including as a classical Hamiltonian [19], the focusing cubic and quintic Gross-Pitaevskii hierarchies [23], cubic Gross-Pitaevskii hierarchy on ℝ [24], and the one-dimensional Gross-Pitaevskii equation [25,26], but here we concentrate on conserved quantities related to the expected value of the effective Hamiltonian.

For instructional purposes, let us use the nonlinear search algorithm to explicitly show why 〈H(t)〉 = 〈H₀ + λ|ψ|²〉 is not conserved, while $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ is conserved. Even with the nonlinearity, as before, the system evolves in the same 2D subspace spanned by |a and |b〉, so the state |ψ(t)〉 can be written as (15). Now, the effective Hamiltonian (24) is

25

H (t) = (\begin{matrix} γ (N - 1) - 1 + λ | α |^{2} & - γ \sqrt{N - 1} \\ - γ \sqrt{N - 1} & γ + \frac{λ}{N - 1} | β |^{2} \end{matrix}) .

This takes the form

H (t) = (\begin{matrix} a + f | α |^{2} & b \\ b^{*} & d + g | β |^{2} \end{matrix}),

where a, b, and d are defined in (17), and

26

f = λ and g = \frac{λ}{N - 1}

are real and time independent. Now, the expected value of the effective Hamiltonian is

27

\begin{array}{l} 〈 H (t) 〉 & = 〈 ψ | H (t) | ψ 〉 \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a + f | α |^{2} & b \\ b^{*} & d + g | β |^{2} \end{matrix}) (\begin{matrix} α \\ β \end{matrix}) \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a α + b β + f | α |^{2} α \\ b^{*} α + d β + g | β |^{2} β \end{matrix}) \\ = a α^{*} α + b α^{*} β + f | α |^{4} + b^{*} β^{*} α + d β^{*} β + g | β |^{4} . \end{array}

Differentiating this with respect to time using the chain rule,

28

\begin{array}{l} \frac{d 〈 H (t) 〉}{d t} & = \frac{\partial 〈 H (t) 〉}{\partial α} \frac{d α}{d t} + \frac{\partial 〈 H (t) 〉}{\partial β} \frac{d β}{d t} + \frac{\partial 〈 H (t) 〉}{\partial α^{*}} \frac{d α^{*}}{d t} + \frac{\partial 〈 H (t) 〉}{\partial β^{*}} \frac{d β^{*}}{d t} \\ = \frac{\partial 〈 H (t) 〉}{\partial α} \dot{α} + \frac{\partial 〈 H (t) 〉}{\partial β} \dot{β} + \frac{\partial 〈 H (t) 〉}{\partial α^{*}} {\dot{α}}^{*} + \frac{\partial 〈 H (t) 〉}{\partial β^{*}} {\dot{β}}^{*} . \end{array}

The partial derivatives of the expected value of the effective Hamiltonian can be found by differentiating (27), noting that |α|⁴ = (α*)²α² and |β|⁴ = (β*)²β²:

29

\begin{array}{l} \frac{\partial 〈 H (t) 〉}{\partial α} = a α^{*} + b^{*} β^{*} + 2 f | α |^{2} α^{*}, \\ \frac{\partial 〈 H (t) 〉}{\partial β} = b α^{*} + d β^{*} + 2 g | β |^{2} β^{*}, \\ \frac{\partial 〈 H (t) 〉}{\partial α^{*}} = a α + b β + 2 f | α |^{2} α, \\ \frac{\partial 〈 H (t) 〉}{\partial β^{*}} = b^{*} α + d β + 2 g | β |^{2} β . \end{array}

To find $\dot{α}, \dot{β}, {\dot{α}}^{*}$ , and ${\dot{β}}^{*}$ in (28), we use the cubic nonlinear Schrödinger equation (2),

i (\begin{matrix} \dot{α} \\ \dot{β} \end{matrix}) = (\begin{matrix} a + f | α |^{2} & b \\ b^{*} & d + g | β |^{2} \end{matrix}) (\begin{matrix} α \\ β \end{matrix}),

which multiplied out is

\begin{array}{l} i \dot{α} = a α + b β + f | α |^{2} α, \\ i \dot{β} = b^{*} α + d β + g | β |^{2} β . \end{array}

Solving for $\dot{α}$ and $\dot{β}$ and taking the complex conjugate of each equation,

30

\begin{array}{l} \dot{α} = - i (a α + b β + f | α |^{2} α), \\ \dot{β} = - i (b^{*} α + d β + g | β |^{2} β), \\ {\dot{α}}^{*} = i (a α^{*} + b^{*} β^{*} + f | α |^{2} α^{*}), \\ {\dot{β}}^{*} = i (b α^{*} + d β^{*} + g | β |^{2} β^{*}) . \end{array}

Comparing (29) and (30), we see that these are no longer proportional to partial derivatives of the expected value of the Hamiltonian, i.e., (23) no longer holds. Then, (28) is not equal to zero, so the expected value of the effective Hamiltonian is not conserved.

The reason why (29) is not proportional to (30) is the extra factor of 2 in the last term. We can eliminate this factor of 2 by dividing the nonlinear self-potential by 2. That is, we consider

H_{0} + \frac{1}{2} λ | ψ |^{2} = (\begin{matrix} γ (N - 1) - 1 + \frac{1}{2} λ | α |^{2} & - γ \sqrt{N - 1} \\ - γ \sqrt{N - 1} & γ + \frac{λ}{2 (N - 1)} | β |^{2} \end{matrix}),

which takes the form

31

\begin{matrix} H_{0} + \frac{1}{2} λ | ψ |^{2} = (\begin{matrix} a + \frac{1}{2} f | α |^{2} & b \\ b^{*} & d + \frac{1}{2} g | β |^{2} \end{matrix}) \end{matrix},

where a, b, and d are defined in (17), and f and g are defined in (26). The expected value of this is

32

\begin{array}{l} 〈 {〈 H_{0} + \frac{1}{2} λ | ψ |}^{2} & = 〈 ψ | H_{0} + \frac{1}{2} λ | ψ |^{2} | ψ 〉 \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a + \frac{1}{2} f | α |^{2} & b \\ b^{*} & d + \frac{1}{2} g | β |^{2} \end{matrix}) (\begin{matrix} α \\ β \end{matrix}) \\ = (\begin{array}{l} α^{*} & β^{*} \end{array}) (\begin{matrix} a α + b β + \frac{1}{2} f | α |^{2} α \\ b^{*} α + d β + \frac{1}{2} g | β |^{2} β \end{matrix}) \\ = a α^{*} α + b α^{*} β + \frac{1}{2} f | α |^{4} + b β^{*} α + d β^{*} β + \frac{1}{2} g | β |^{4}, \end{array}

which has a time derivative of

33

\begin{array}{l} \frac{d 〈 H_{0} \frac{1}{2} λ | ψ |^{2} 〉}{d t} & = \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α} \frac{d α}{d t} + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β} \frac{d β}{d t} \\ + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α^{*}} \frac{d α^{*}}{d t} + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β^{*}} \frac{d β^{*}}{d t} \\ = \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α} \dot{α} + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β} \dot{β} \\ + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α^{*}} {\dot{α}}^{*} + \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β^{*}} {\dot{β}}^{*} . \end{array}

Now, when we take the partial derivatives of (32), the factors of 2 are eliminated:

\begin{array}{l} \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α} & = a α^{*} + b β^{*} + f | α |^{2} α^{*}, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β} & = b α^{*} + d β^{*} + g | β |^{2} β^{*}, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α^{*}} & = a α + b β + f | α |^{2} α, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β^{*}} & = b α + d β + g | β |^{2} β . \end{array}

Comparing these with (30), these are exactly proportional to the time derivatives of α*, β*, α, and β, i.e.,

\begin{array}{l} \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α} & = - i {\dot{α}}^{*}, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β} & = - i {\dot{β}}^{*}, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial α^{*}} & = i \dot{α}, \\ \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{\partial β^{*}} & = i \dot{β} . \end{array}

Then, substituting into (33), we get

\begin{array}{l} \frac{\partial 〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉}{d t} & = - i {\dot{α}}^{*} \dot{α} - i {\dot{β}}^{*} \dot{β} + i \dot{α} {\dot{α}}^{*} + i \dot{β} {\dot{β}}^{*} \\ = 0. \end{array}

Thus, $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ is conserved in the nonlinear quantum search algorithm with repulsive interactions.

Faster Nonlinear Quantum Search with Attractive Interactions

4.

In this section, we consider the nonlinear quantum search algorithm with negative values of λ, which corresponds to a Bose-Einstein condensate with attractive interactions. Intuitively, as the amplitude at the marked vertex builds up, the attractive interaction should draw additional amplitude, speeding up the algorithm. Indeed, as shown in [20], when the jumping rate is the time-varying critical function

34

γ_{c} (t) = \frac{1}{N} [1 - λ (| α |^{2} - \frac{| β |^{2}}{N - 1})]

[which is determined independently of the marked vertex |a〉, and whose time dependence comes from the amplitudes α and β (15)], then the algorithm evolves from the uniform superposition over all N vertices to the marked vertex in time

t_{*} = \frac{1}{\sqrt{1 - λ}} \frac{π}{2} \sqrt{N} .

This is demonstrated in Figure 4, where we plot the evolution of the success probability for search on the complete graph of N = 100 vertices. The solid black, dashed red, dotted green, and dot-dashed blue curves correspond to λ = 0, –1, –2, and –3, and they reach success probabilities of 1 at time $t_{*} = (1 / \sqrt{1 - λ}) (π / 2) \sqrt{N} \approx 15.708$ , 11.107, 9.069, and 7.854, respectively, and so the more negative the nonlinearity coefficient, the faster the algorithm.

Success probability versus time for nonlinear quantum search on the complete graph with N = 100 vertices, γ = *γ_c*(t), and various values of λ. The solid black curve is λ = 0, the dashed red curve is λ = –1, the dotted green curve is λ = –2, and the dot-dashed blue curve is λ = –3.

This speedup comes, however, at the expense of increasing the necessary time-measurement precision. In Figure 4, as the magnitude of the nonlinearity coefficient increases, the peak in success probability becomes more narrow, which necessitates greater time-measurement precision to catch the peak. This was quantified in [20], which showed that the width of the peak scales as $O (\sqrt{N} / (1 - λ))$ , and so the time-measurement precision is constant when $λ = Θ (\sqrt{N})$ , at which the runtime t_* = O(N^1/4), which is a quadratic improvement over the linear and nonlinear repulsive algorithms.

Since the effective Hamiltonian H(t) = H₀ + λ|ψ|² depends on time, its expected value is not conserved. $H_{0} + \frac{1}{2} λ | ψ |^{2}$ takes the form given in (31), but now a, b, and d depend on time because γ varies with time. Then, the time-derivative of $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ from (33) will include additional terms involving time-derivatives of a, b, and d, and $〈 H_{0} + \frac{1}{2} λ | ψ |^{2} 〉$ will not be conserved. Instead, let us show that another quantity is conserved.

First, we review from [20] that the critical function γ_c (t) for the jumping rate causes H(t) to be proportional to H₀. To begin,

\begin{array}{l} H (t) & = - γ_{c} (t) L - | a 〉 〈 a | + λ \sum_{i = 1}^{N} | 〈 i ∣ ψ (t) 〉 |^{2} | i 〉 〈 i | \\ = - γ_{c} (t) L - | a 〉 〈 a | + λ | 〈 a ∣ ψ (t) 〉 |^{2} | a 〉 〈 a | + λ \sum_{i \neq a} | 〈 i ∣ ψ (t) 〉 |^{2} | i 〉 〈 i | \\ = - γ_{c} (t) L - | a 〉 〈 a | + λ | α |^{2} | a 〉 〈 a | + λ \frac{| β |^{2}}{N - 1} \sum_{i \neq a} | i 〉 〈 i | \\ = - γ_{c} (t) L - (1 - λ | α |^{2}) | a 〉 〈 a | + λ \frac{| β |^{2}}{N - 1} \sum_{i \neq a} | i 〉 〈 i | . \end{array}

Now, recall that the jumping rate satisfies (34). Multiplying both sides of (34) by N and distributing λ yields

γ_{c} (t) N = 1 - λ | α |^{2} - λ \frac{| β |^{2}}{N - 1} .

Rearranging,

1 - λ | α |^{2} = γ_{c} (t) N + λ \frac{| β |^{2}}{N - 1} .

Substituting this into our previous expression for H(t),

\begin{array}{l} H (t) & = - γ_{c} (t) L - (γ_{c} (t) N + λ \frac{| β |^{2}}{N - 1}) | a 〉 〈 a | + λ \frac{| β |^{2}}{N - 1} \sum_{i \neq a} | i 〉 〈 i | \\ = - γ_{c} (t) L - γ_{c} (t) N | a 〉 〈 a | + λ \frac{| β |^{2}}{N - 1} \sum_{i = 1}^{N} | i 〉 〈 i | \\ = - γ_{c} (t) L - γ_{c} (t) N | a 〉 〈 a | + λ \frac{| β |^{2}}{N - 1} 𝕀 \end{array}

where 𝕀 is the identity matrix, which can be dropped since it corresponds to a rescaling of energy or a global, unobservable phase. Then,

\begin{array}{l} H (t) & = - γ_{c} (t) L - γ_{c} (t) N | a 〉 〈 a | \\ = γ_{c} (t) N (- \frac{1}{N} L - | a 〉 〈 a |) \\ = {γ_{c} (t) N H_{0} |}_{γ_{c}} . \end{array}

That is, the effective Hamiltonian for the nonlinear search algorithm with attractive interactions is a time-varying rescaling of the linear search algorithm’s Hamiltonian evaluated at its critical jumping rate of γ_c = 1/N. Solving for the linear algorithm’s Hamiltonian at its critical jumping rate,

{H_{0} |}_{γ_{c}} = \frac{H (t)}{γ_{c} (t) N} .

Since 〈H₀〉 is conserved for arbitrary constant γ, as we proved in (22), we have that

〈 \frac{H (t)}{γ_{c} (t) N} 〉 = 0,

and we have proved a conserved quantity for the nonlinear search algorithm with attractive interactions.

Conclusion

5.

We have reviewed three quantum search algorithms governed by continuous-time quantum walks. The first used a linear quantum walk, and we derived the evolution of the system for arbitrary jumping rates. We used elementary calculus to prove that there is a critical jumping rate γ_c that causes the success probability to reach 1 in time $π \sqrt{N} / 2$ . We showed that the expected value of the Hamiltonian H₀ is conserved, which is an example of the fact that all time-independent Hamiltonians have constant expected values. Second, we considered a nonlinear quantum walk with repulsive interactions, whose effective Hamiltonian was H(t) = H₀ + λ|ψ|² with λ > 0. For a range of possible critical jumping rates, the success probability reaches 1 in time $π \sqrt{N / 3}$ , which is slower than the linear algorithm by a constant factor, and we showed that the expected value of $H_{0} + \frac{1}{2} λ | ψ |^{2}$ is conserved. Third, for the nonlinear quantum walk with attractive interactions, the effective Hamiltonian has λ < 0, and when the jumping rate takes a critical function γ_c (t), the success probability reaches 1 in time $π \sqrt{N / (1 - λ)} / 2$ , which is faster than the other algorithms for all λ < 0. The jumping rate varies such that the effective Hamiltonian H(t) is equal to a time-dependent rescaling of the linear algorithm’s Hamiltonian H₀ evaluated at its critical jumping rate γ_c, namely, H(t) = γ_c(t)NH₀|_γc, and since the expected value of the time-independent linear Hamiltonian H₀ is conserved for an arbitrary constant jumping rate, the expected value of H(t)/[γ_c (t)N] is conserved for the third algorithm. These results provide a perspective on quantum walk search algorithms through the lens of conservation laws and many-body quantum theory.

Notes

[1] Contributed by Author Contributions

D.A.M. and T.G.W. contributed to the conceptualization of the research, investigation of the results, and writing of the manuscript. All authors have read and agreed to the published version of the manuscript.

[2] Conflicts of interest Conflicts of Interest

The authors declare no conflicts of interest.

[3] Data Availability Statement

No data were created or analyzed in this study.

Conserved Quantities in Linear and Nonlinear Quantum Search

Full Article

Introduction

1.

1

2

3

Linear Quantum Search

2.

4

Figure 1.

5

6

7

Figure 2.

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

Nonlinear Quantum Search with Repulsive Interactions

3.

24

Figure 3.

25

26

27

28

29

30

31

32

33

Faster Nonlinear Quantum Search with Attractive Interactions

4.

34

Figure 4.

Conclusion

5.

Notes