# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 2 Model
### The Linear Algorithm
\begin{split} H_{0}\ket{\mathbf{v}}&=(-1)^{v_{x}}( \ket{\mathbf{v}+\mathbf{e_{x}}}-\ket{\mathbf{v}-\mathbf{e_{x}}})\\ +&(-1)^{v_{x}+v_{y}}(\ket{\mathbf{v}+\mathbf{e_{y}}}-\ket{ \mathbf{v}-\mathbf{e_{y}}})\end{split}  \tag{5}\]  
with \(\mathbf{e_{i}}\), the unit vector in the \(i\)-direction, is translation invariant of length 2, and, due to the periodic conditions, the above Hamiltonian is well defined on the border of the lattice. More formally:  
\[[H_{0},T_{i}]=0\hskip 14.226378 ptT_{i}\ket{\mathbf{v}}=\ket{\mathbf{v}+2\mathbf{e_{i}}}. \tag{6}\]  
Because, the 2D-grid is now factorised into cells, each composed by four vertices, it is convenient to introduce a new coordinates system. The cell will be labeled by \(\mathbf{r}\), such that \(\mathbf{r}\in[l]^{2}\) with \(l=L/2\), and each of the four internal vertices will be labeled by \(\mathbf{\sigma}\in\mathbb{Z}_{2}^{2}\). In particular, we can write the following transformations, which map the vertices coordinates into cell ones :  
\[r_{i} =\left\lfloor\frac{v_{i}}{2}\right\rfloor, \tag{7}\] \[\sigma_{i} =v_{i}-2r_{i} \tag{8}\]  
where \(\lfloor.\rfloor\) denoting the floor function. Now, the Hilbert space is spanned by \(\ket{\mathbf{r},\mathbf{\sigma}}\) and the Hamiltonian reads:  
\[ \begin{split} H_{0}\ket{\mathbf{r},\mathbf{\sigma}}=\sum_{i=x,y}(-1)^{s_ {i}(\mathbf{\sigma})}(\ket{\mathbf{r}+\sigma_{i}e_{i},\mathbf{\sigma}+e_{i}}-\\ \ket{\mathbf{r}-\sigma_{i}e_{i},\mathbf{\sigma}+e_{i}})\end{split}  \tag{9}\]  
where \(s_{x}(\mathbf{\sigma})=\sigma_{x}\), \(s_{y}(\mathbf{\sigma})=\sigma_{x}+\sigma_{y}\) and \(\tilde{\sigma}_{i}=1-\sigma_{i}\). In this new setting, the searched vertex is :  
\[\left|\mathbf{v}\right\rangle=\left|\mathbf{w},\mathbf{\alpha}\right\rangle \tag{10}\]  
with \(\mathbf{w}\in[l]^{2}\) and \(\mathbf{\alpha}\in\mathbb{Z}_{2}^{2}\). We now define the oracle Hamiltonian, previously introduced in [26], by:  
\[H_{oracle}=-\left|\mathbf{w},\mathbf{\alpha}\right\rangle\left\langle\mathbf{w},\mathbf{ \alpha}\right|H_{0}-H_{0}\left|\mathbf{w},\mathbf{\alpha}\right\rangle\left\langle\bm {w},\mathbf{\alpha}\right| \tag{11}\]  
Notice that the above oracle Hamiltonian, \(H_{oracle}\), added to \(H_{0}\), has the effect of disconnecting the marked vertex from its neighborhood, as in Figure 1. Indeed, by the definition, for any \(\mathbf{v}\), we have \(\left\langle\mathbf{v}\right|H_{0}\left|\mathbf{v}\right\rangle=\left\langle\mathbf{w}, \mathbf{\alpha}\right|H_{0}\left|\mathbf{w},\mathbf{\alpha}\right\rangle=0\), and it follows that  
\[H_{L}\left|\mathbf{w},\mathbf{\alpha}\right\rangle = \left(H_{oracle}+H_{0}\right)\left|\mathbf{w},\mathbf{\alpha}\right\rangle=\] \[-\left|\mathbf{w},\mathbf{\alpha}\right\rangle\!\left\langle\mathbf{w},\mathbf{ \alpha}\right| H_{0} \left|\mathbf{w},\mathbf{\alpha}\right\rangle-H_{0}\left|\mathbf{w},\mathbf{ \alpha}\right\rangle+H_{0}\left|\mathbf{w},\mathbf{\alpha}\right\rangle=0.\]  
As a consequence, one cannot reach the neighbors of \(\left|\mathbf{w},\mathbf{\alpha}\right\rangle\) from itself. Moreover, one cannot reach \(\left|\mathbf{w},\mathbf{\alpha}\right\rangle\) from its neighbors, neither because the total Hamiltonian \(H_{L}\) is real and then it has to be symmetric. Note that this oracle Hamiltonian is different from the one usually used, for example in [2], \(H_{oracle}\propto\left|\mathbf{w},\mathbf{\alpha}\right\rangle\!\left\langle\mathbf{w},\bm {\alpha}\right|\). Indeed, it has been proven in [25; 26; 28] that this redefinition is justified by the \(2^{2}\) cell-partition of the lattice and the consequent linear behavior of the dispersion relation near the ground state of \(H_{0}\). Moreover, the disconnection of the marked vertex from the rest of the lattice and the on-site potentials at the neighbours of the marked item is reminiscent of the natural occurring searching algorithm studied in [13], in the discrete time setting.