# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 2 Model  
### The Linear Algorithm  
Let us consider a quantum walk in continuous time, over a two dimensional grid of size \(L\times L\), where \(N=L^{2}\) is the number of vertices \(v\in V=\{1,...,N\}\). The Hilbert space of the quantum walk is spanned by the set of vertices, such that:  
\[\mathcal{H}:=span\{|v\rangle:v\in V\}. \tag{1}\]  
A general state of the walker \(|\psi(t)\rangle\) is a vector, whose complex components \(\psi_{v}=\langle v\rangle\,\psi\) evolve according to the Schrodinger equation:  
\[i\frac{d\psi_{v}(t)}{dt}=\sum_{w}H_{vw}\psi_{w}(t), \tag{2}\]  
where \(H_{vw}\) are the coefficients of the Hamiltonian. We consider that \(H\) is local, or in other terms that \(H_{vw}\
eq 0\), if and only if, \(v\) and \(w\) are adjacent. In this framework, the search problem corresponds to find a marked vertex \(|\bar{v}\rangle\), given an initial state \(|\psi(t=0)\rangle\), usually constructed as a uniform superposition over all vertices :  
\[|\psi(0)\rangle=\frac{1}{\sqrt{N}}\sum_{v\in V}|v\rangle\,. \tag{3}\]  
The main idea is to let the quantum walker evolve on the grid for such a time that a measure of his state, on the computational basis, can be used to find the marked element with constant probability. Thus, we need to find the shortest time \(T\), such that the probability \(p(t)=|\,\langle\bar{v}|\,e^{-iHt}\,|\psi(0)\rangle\,|^{2}\) is maximised. In the following, we refer to \(T\) as the searching time and \(\bar{p}=p(T)\) as the success probability. In a continuous time setting, in order to search a single marked node, we let the walker evolve under the action of the following Hamiltonian:  
\[H_{L}=H_{0}+H_{grade}, \tag{4}\]where \(H_{0}\) is the lattice free Hamiltonian of the walker and \(H_{\textit{oracle}}\) is the oracle Hamiltonian which is used to perturb the walker free Hamiltonian upon the marked vertex. In the original work by [PERSON] and [PERSON] [PERSON] and [PERSON] (2018), it has been proven that, for a two-dimensional lattice, the quadratic speed up with respect to the classical search algorithm is lost. Later, the same authors proved in [PERSON] and [PERSON] (2018) that by introducing a second register, the coin state, as in the discrete time quantum walk, the quantum speedup \(O(\sqrt{N}\log N)\) is achieved even for a two-dimensional lattice. The reason has been investigated in [PERSON] and [PERSON] (2018), where again [PERSON] and [PERSON], inspired by [PERSON], [PERSON] and [PERSON] (2018) pointed out that the optimality loss in two spatial dimension for a continuous time quantum walk came from the quadratic dispersion relation of the free Hamiltonian. Since that, several other results confirmed this interpretation, as for example in [PERSON] and [PERSON] (2018), where a coinless walker with linear dispersion relation over a honeycomb lattice led to the same quantum speedup. In this paper, we will use the same model introduced by [PERSON] and [PERSON] [PERSON] and [PERSON] (2018), where a linear dispersion law is achieved introducing periodic inhomogeneities into the lattice Hamiltonian: the idea is to group, periodically, multiple neighbouring vertices into cells, as in Figure 1. In order to compare this model with the coined quantum walk, similarly to the staggered fermion model [PERSON] and [PERSON] (2018), we can notice that the coin states may be seen as embedded into the cells. The dimension of the coinspace is mimicked by the number of nodes grouped in each cell. Although this construct may suggest that now the searching algorithm will look for a marked cell and no longer for a specific vertex, we will show that an opportune choice of the oracle \(H_{\textit{oracle}}\) allows us to look for any single vertex as a possible marked item, keeping the advantage of the Hamiltonian over the cells. Let us now review more formally the model, as introduced in [PERSON] and [PERSON] (2018). Consider the lattice partitioned in \(n:=N/4\) cells, as in Figure 1, with even \(L\) and periodic boundary conditions. The free lattice Hamiltonian,  
\[