# Searching via Nonlinear Quantum Walk on the 2D-Grid
## 1 Introduction  
Searching for an element among an unstructured database of size \(N\) takes \(O(N)\) iterations, resulting in a linear complexity time. In 1996, [PERSON] came up with a quantum algorithm that speeds up this brute force \(O(N)\) problem into a \(O(\sqrt{N})\) problem [1]. The algorithm comes in many variants and has been rephrased in many ways, including quantum walks [2]. Quantum walks (QW) are essentially local unitary gates that drive the evolution of a particle on a graph [3], and although they may appear defined in a discrete and in a continuous time setting, it has been recently shown that a new family of \"plastic\" QW unifies and encompasses both systems [4, 5]. They have been used as a mathematical framework to express many quantum algorithms, e.g., [6, 7, 8], but also many quantum simulation schemes e.g., [9, 10]. In particular, it has been shown that many of these QWs admit, as their continuum limit, the Dirac equation [11, 12], providing 'quantum simulation schemes', for the future quantum computers, to simulate all free spin-1/2 fermions. More interestingly, it has been recently proven by one of the authors, that the Grover algorithm is indeed a naturally occurring phenomenon, i.e., spontaneously implemented by some kind of particles in nature [13] over arbitrary surfaces with topological defects. From a theoretical perspective, a Grover search on a graph, rephrased in terms of QW, is an alternation of a diffusion step and an oracle step. The nodes of the graph represent elements of the configuration space of a problem, and whose edges represent the existence of a local transformation between two configurations. So far, the QW search has only been used to look for'marked nodes', i.e., good configurations within the configuration space, as specified by an oracle. In [13], it has been proven that instead of using them to look for 'good' solutions within the configuration space of a problem, we could use them to look for topological properties of the entire configuration space. The generalisation to an interacting multi-walkers scenario has already been explored in quantum algorithmics [14], showing that such systems are capable of universal quantum computation. Moreover, there exist many physical systems which may be described by a nonlinear effective equation,such as Bose-Einstein condensates (BEC) [15; 16]. Quite interestingly, the experimental setup proposed by [PERSON] and [PERSON] in [17] showed that a spinor BEC can simulate, in quasi-momentum space, a 1D QW with weak non-linearities. Notice that such results do not aim to suggest a scheme for implementing nonlinear quantum mechanics, which we know is linear. However, it paves the way to simulate, via a mean-field approach, one particle nonlinear dynamics, where nonlinearities come from the weakly interacting BEC. In the following, in order to avoid confusion, we will introduce nonlinearities in the very same spirit of [18]. [PERSON] and [PERSON] consider a hypothetical nonlinear quantum mechanics equation, i.e., a nonlinear Schrodinger equation for closed single quantum mechanical systems. In particular, they show that nonlinearity in quantum computation could make quantum systems solve NP-complete problems in polynomial time. Nonlinearity in quantum walks has been considered in several recent studies and may appear either under the form of nonlinear phases (e.g., in Kerr medium [19; 20]) or via a feed-forward quantum diffusion operator [21]. In this manuscript, we will give numerical and analytical evidence that nonlinearity leads to a clear computational advantage on the two dimensional grid with respect to the linear case, consistently with previous results on complete graph [22], paving the way to extend our nonlinear scheme to higher dimensional physical dimensional grids.