# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 4 Scale Analysis  
Although an exact analytical description is prohibitive, in this section, we will provide some elements of analysis that will convince the reader of the robustness of the numerical results obtained in the previous section. Let's start from the eigenvalues given in Equation (31), and rescale them using Equation (33):  
\[E_{\pm}^{\prime}=\frac{1}{2}g\delta\pm\frac{1}{2}\sqrt{(g\delta)^{2}+4E^{2}(1 +cg\delta)^{2}} \tag{40}\]  
Setting \(g(N)=\log N/\pi\) and \(c(N)=\sqrt{\frac{N\log N}{16\pi}}\), as in our numerical simulation, we can clearly distinguish two different behaviours for the probability \(|a(t)|^{2}\):  
* A strictly linear regime, when \(\delta(t)=0\), which appears periodically with a period \[T_{0}\sim 1/\Delta\lambda\sim\frac{1}{E}=O(\sqrt{N\log N})\] (41)
* A nonlinear regime, when \(\delta(t)\) is maximum. In this case, \((1+cg\delta(t))\sim cg\delta(t)=O(\sqrt{N\log N})\) and consequently the period is constant: \[T_{1}\sim 1/\Delta\lambda=O(1).\] (42)  
Now, we have to characterize how the system goes from the first regime to the second one and under which conditions. With no loss of generality, and because we are solely interested in the first probability peak behaviour, we focus on the first half period of the dynamics. We propose the following ansatz:  
\[|a(t)|^{2}=\frac{A\pi}{\log N}\sin^{2}\left(\frac{C_{0}t}{T_{0}}+C_{1}|a(t)|^{ 2}\frac{t}{T_{1}}\right) \tag{43}\]  
where \(A\), \(C_{0}\) and \(C_{1}\) are three real constants.  
Notice that the above self-consistent equation describes both regimes for the probability \(|a(t)|^{2}\): indeed, when \(|a(t=0)|^{2}=0\), we recover the Equation (20). By choosing \(C_{0}=1\) and \(A=1\), and as soon as \(|a|^{2}\) increases, the argument in the sine increases as well, speeding up the dynamics, as observed in Figure 3. As \(T_{1}\ll T_{0}\), in the limit of large \(N\), there exists a critical time \(t_{s}\), at which the Equation (43) coincides with \(|a(t)|^{2}=\frac{A\pi}{\log N}\sin^{2}\left(C_{1}|a(t)|^{2}\frac{t}{T_{1}}\right)\).  
We may argue that \(t_{s}\) scales in the same way as the searching time \(T^{\prime}\) with \(N\). Numerical simulations show that this is approximately true and it is shown in Figure 6 for several values of \(c\). Along the first half period, the ansatz works surprisingly well.  
Figure 5: Searching times in the nonlinear and the linear algorithm (inset).  
Moreover, if we compute the characteristic time \(t_{s}\) at which the system transits from the first behavior with period \(T_{0}\) to the second one with period \(T_{1}\), we derive exactly the same scaling laws, we have for \(T\) and \(T^{\prime}\). Indeed, at \(t_{s}\), we have \(|\alpha(t_{s})|^{2}t_{s}/T_{1}\sim t_{s}/T_{0}\) and it follows:  
\[\frac{1}{\log N}\sin^{2}(t_{s}/T_{0})\sim T_{1}/T_{0}. \tag{44}\]  
In conclusion, by keeping only the first term in the development of \(\arcsin x\):  
\[t_{s}=O(\sqrt{T_{1}T_{0}\log N}) \tag{45}\]  
and using Equations (41) and (42), we finally recover  
\[t_{s}=O(N^{1/4}\log^{3/4}N), \tag{46}\]  
which is consistent with the fits realized in the previous section and confirms the time complexity of the nonlinear algorithm that we numerically assessed in Section 3.