Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSearching via nonlinear quantum walk on the 2D-grid
124
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer cite{meyer2013nonlinear}, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage BHg{with} respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge cite{Childs_2014}. 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^{7/4}N)$. We also proved that there exists an optimal choice of the walker parameters to avoid that the time measurement precision affects the complexity searching time of the algorithm.
rate research
Read More
We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as $widetilde{O}(m^{1/3} delta^{-1/3})$, with $m$ the number of edges and $delta$ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for $st$-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an $n$-node graph in time $widetilde{O}(2^{n/3})$, surpassing the $Omega(2^{n/2})$ barrier set by index erasure.
The main results on quantum walk search are scattered over different, incomparable frameworks, most notably the hitting time framework, originally by Szegedy, the electric network framework by Belovs, and the MNRS framework by Magniez, Nayak, Roland and Santha. As a result, a number of pieces are currently missing. For instance, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. In recent work by Ambainis et al., this problem was resolved for the more restricted hitting time framework, in which quantum walks must start from the stationary distribution. We present a new quantum walk search framework that unifies and strengthens these frameworks. This leads to a number of new results. For instance, the new framework not only detects, but finds marked elements in the electric network setting. The new framework also allows one to interpolate between the hitting time framework, which minimizes the number of walk steps, and the MNRS framework, which minimizes the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. Whereas the original frameworks only rely on quantum walks and phase estimation, our new algorithm makes use of a technique called quantum fast-forwarding, similar to the recent results by Ambainis et al. As a final result we show how in certain cases we can simplify this more involved algorithm to merely applying the quantum walk operator some number of times. This answers an open question of Ambainis et al.
Multi-dimensional quantum walks can exhibit highly non-trivial topological structure, providing a powerful tool for simulating quantum information and transport systems. We present a flexible implementation of a 2D optical quantum walk on a lattice, demonstrating a scalable quantum walk on a non-trivial graph structure. We realized a coherent quantum walk over 12 steps and 169 positions using an optical fiber network. With our broad spectrum of quantum coins we were able to simulate the creation of entanglement in bipartite systems with conditioned interactions. Introducing dynamic control allowed for the investigation of effects such as strong non-linearities or two-particle scattering. Our results illustrate the potential of quantum walks as a route for simulating and understanding complex quantum systems.
Properties of the probability distribution generated by a discrete-time quantum walk, such as the number of peaks it contains, depend strongly on the choice of the initial condition. In the present paper we discuss from this point of view the model of the two-dimensional quantum walk analyzed in K. Watabe et al., Phys. Rev. A 77, 062331, (2008). We show that the limit density can be altered in such a way that it vanishes on the boundary or some line. Using this result one can suppress certain peaks in the probability distribution. The analysis is simplified considerably by choosing a more suitable basis of the coin space, namely the one formed by the eigenvectors of the coin operator.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
