# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 5 Discussion  
We provide numerical evidence that the nonlinear searching introduced by [PERSON] and [PERSON] [22] can be extended to the finite 2-dimensional grid, keeping the same computational advantage with respect to the classical algorithm. For this purpose, we have considered a different Hamiltonian, admitting a linear dispersion relation, as proven in [26]. The numerical simulations showed that the walker finds the marked vertex in \(O(N^{1/4}\log^{3/4}N)\) steps with probability \(O(1/\log N)\), for an overall complexity of \(O(N^{1/4}\log^{5/4}N)\), using amplitude amplification. These results are consistent with those proven by [PERSON] and [PERSON] in [22] using a nonlinear Schrodinger equation on a complete graph. However, the optimality of the above algorithm strongly depends on the time measurement  
Figure 6: \(N=900\)—Probability over \(|\Gamma\rangle\) for different values of \(c\) and numerical resolution of Equation (43).  
precision. As we mentioned earlier, the width of the probability peaks may affect the complexity of the algorithm, as already discussed in [22]. The narrower the peak, the less efficient the algorithm will be. The optimality of the nonlinear algorithm depends on the choice of \(g\) and \(c\). For instance, if we had chosen both \(c\) and \(g\) in \(O(\sqrt{N})\), we would end up with a runtime of \(t_{s}=O(\log^{5/4}N)\). However, the period \(T_{1}\) of the Equation (42) would no longer be a constant, it would rather decrease with \(N\):  
\[T_{2}=O\left(\frac{\log N}{\sqrt{N}}\right). \tag{47}\]  
The peak width at half maximum, shown in Figure 7, is given by :  
\[\sin^{2}(\Delta t/2T_{2})=\frac{1}{2}, \tag{48}\]  
which yields to  
\[\Delta t\sim T_{2}. \tag{49}\]  
Now, considering that \(n\) ions are required in an atomic clock to obtain a time precision of \(O(1/n)\)[40], we have to require an extra \(O(1/T_{2})\) temporal resource, which dramatically affects the total complexity, making us lose any kind of advantage over the linear algorithm.  
In conclusion, our work presents several advantages with respect to the previous ones: (i) quantum walks are easily implementable in our labs by several physical systems; (ii) graphs having sets of vertices of constant degree, are more natural and pave the way to a 3-dimensional generalisation. An extension of the above results to other kind of nonlinearities will deserve future investigation.  
**Author Contributions:** [PERSON] conceived the presented idea. [PERSON] and [PERSON] developed the theory and [PERSON] performed the numerical and analytical computations. [PERSON] supervised the findings of this work. All authors discussed the results and contributed to the final manuscript. All authors have read and agreed to the published version of the manuscript.  
Figure 7: Width of the probability peak—Insight: Searching time.  
**Funding:** This work was funded by the Pepiniere d'Excellence 2018, AMIDEX foundation, project DiTiQuS and the ID 60609 grant from the John Templeton Foundation, as part of the \"The Quantum Information Structure of Spacetime (QISS)\" Project.  
**Acknowledgments:** The authors acknowledge inspiring conversations with [PERSON] and [PERSON].  
**Conflicts of Interest:** The authors declare no conflict of interest.