Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size
Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
We study the effect of magnetic vector potentials on periodic Grover walks on finite graphs. The magnetic vector potential is introduced through the framework of quantum graphs, which induces the Grover walk as a special case. We regard the magnetic vector potential as a perturbation of a periodic Grover walk and investigate the robustness of its periodicity. Our analysis reveals that the response to such perturbations depends on the spectral structure of the underlying graph. In particular, when the graph possesses at least one non-simple eigenvalue, we derive a Hermitian matrix that characterizes the robustness of its periodicity. As a consequence, for initial states orthogonal to the eigenspaces of the unperturbed Grover walk corresponding to the eigenvalues
±1, we show that the perturbed dynamics is asymptotically described by a continuous-time quantum walk generated by this Hermitian matrix.
We investigate the scattering properties of quantum walks by considering single and double position defects on a one-dimensional line. This corresponds to introducing, at designated positions, delta potential defects for continuous-time quantum walks and phase-defect Hadamard coins for discrete time quantum walks. The delta potential defects can be readily considered as potential barriers in discrete position space, which affect the time evolution of the system in a similar way as the quantum wave-packet dynamics in a continuous position space governed by Schr\"odinger's equation. Although there is no direct analogy of potential barriers in the theoretical formulation of discrete time quantum walks, in this paper we show that the phase defects in the coin space can be utilized to provide similar scattering effects. This study provides means of controlling the scattering properties of quantum walks by introducing designated position-dependent defects.