# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 2 Model
### Adding a Nonlinearity  
Here, we will consider the hypothetical nonlinear quantum mechanics in the same spirit of [18]. However, let us notice that there are physical systems, in which multiple interacting quantum particles, under particular conditions, can be effectively described as a single particle obeying the nonlinear Schrodinger equation:  
\[\partial_{t}\psi(\mathbf{r},t)=(H_{0}-g|\psi(\mathbf{r},t)|^{2})\psi(\mathbf{r},t), \tag{21}\]  
where \(H_{0}\) is the free Hamiltonian of the single particle and \(g\) is the coupling constant of the non linear systems. The nonlinear term corresponds to a Kerr law [29; 30], acting as a self-potential. One concrete example of this family of quantum systems is the Bose-Einstein condensate (BEC) [31; 32], effectively described by Equation (21) in the limit of large particle number [33]. In the recent years, BECs have been realised in several experimental setups [34; 35; 36] and some of them inspired the experimental realisation of quantum walks [17; 37]. In the following, we will consider a BEC with attractive interaction, i.e., \(g>0\), in the context of quantum algorithms. [PERSON] and [PERSON] have previously investigated such systems applied to spatial search [22; 38] on complete graphs. Although they found a reasonable improvement in time complexity over the linear case, their algorithm is not directly reducible to the 2-dimensional grid, keeping the same quantum speedup with respect to the classical case. In fact, [PERSON] and [PERSON] used the same linear Hamiltonian introduced by [PERSON] and [PERSON] [39], which is not optimal on the square grid, as rigorously proven in [2]. In the following, we will show that the same nonlinear spatial search introduced by [PERSON] and [PERSON] can be optimal, even in 2D, considering the free Hamiltonian (9). The basic idea is to modify Equation (4), including a self-potential of the kind:  
\[H_{NL}=-g\sum_{\mathbf{r},\sigma}\left|\left\langle\mathbf{r},\sigma\right\rangle\psi (t)\right|^{2}\left|\mathbf{r},\sigma\right\rangle\!\!\left\langle\mathbf{r},\sigma\right| \tag{22}\]  
where the coupling positive constant \(g\) amplifies the accumulation of the probability at the marked state due to \(H_{oracle}\), speeding up the search. The overall time-dependent Hamiltonian now reads:  
\[H=H_{L}+H_{NL}. \tag{23}\]  
Similarly to the linear algorithm, here we have to compute the success probability \(p\), or equivalently we have to find a searching time for which the overlap between \(\Gamma\) and the evolved state \(\psi(t)\) is maximised. Before doing so, we must ensure that the non-linear contribution is as reasonable as possible. In other words, we wonder whether it is possible for the system to continue to evolve in the subspace generated by \(\left|\Gamma\right\rangle\) and \(  
and,  
\[ \begin{split} H_{NL}\left|\Gamma\right>&=-g\sum_{\mathbf{r}, \mathbf{\sigma}}\left|\left<\mathbf{r},\mathbf{\sigma}\right>\Gamma\right|^{2}\left|\mathbf{r}, \mathbf{\sigma}\right>\left<\mathbf{r},\mathbf{\sigma}\right>\Gamma\\ &=-g\sum_{\mathbf{r},\mathbf{\sigma}}\frac{1}{4}\left|\mathbf{r},\mathbf{\sigma }\right>\ \left<\mathbf{r},\mathbf{\sigma}\right|\frac{H_{0}}{2}\left|\mathbf{w},\mathbf{\sigma} \right>=-g\frac{1}{4}\left|\Gamma\right>.\end{split}  \tag{26}\]  
In this subspace, the nonlinear Schrodinger equation reads:  
\[\partial_{t} \begin{pmatrix}a\\ b\end{pmatrix} =-iH \begin{pmatrix}a\\ b\end{pmatrix}  \tag{27}\]  
where we have dropped \(t\) parameter from the amplitudes to lighten the notation. The total Hamiltonian is represented by the following matrix:  
\[H=\left( \begin{array}{cc}\frac{-g|a|^{2}}{4}&E\\ E&\frac{-4g|b|^{2}}{N}\end{array} \right), \tag{28}\]  
where \(E=|E_{\pm}|\). Remark that, by adding \(\frac{g|a|^{2}}{4}\) to the diagonal coefficients, we only introduce a global phase, which does not change the dynamics. Thus, the rescaled total Hamiltonian is :  
\[H^{\prime}=\left( \begin{array}{cc}0&E\\ E&g\delta\end{array}