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
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
is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian
) =
+
, 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
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
) that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of
)/[
] is conserved.