Conserved Quantities in Linear and Nonlinear Quantum Search

Abstract In this tutorial, which contains some original results, we bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms for searching an unordered database of size N using a continuous-time quantum walk, which is the quantum analogue of a continuous-time random walk. The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1 when the jumping rate of the walk takes some critical value. We show that the expected value of its Hamiltonian H 0 is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian H (t) = H 0 + λ | ψ | 2, which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates. When the interactions between the bosons are repulsive, λ > 0, and there exists a range of fixed jumping rates such that the success probability reaches 1 with the same asymptotic runtime of the linear algorithm, but with a larger multiplicative constant. Rather than the effective Hamiltonian, we show that the expected value of H 0 + 1 2 λ | ψ | 2 H₀ + 1 2 | |² is conserved. The third algorithm utilizes attractive interactions, corresponding to λ < 0. In this case, there is a time-varying critical function for the jumping rate γ c (t) that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of H (t) / γ c (t) N is conserved.