Faster quantum walk algorithm for the two dimensional spatial search

Abstract

We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\times \sqrt{N}$. The previous quantum walk based algorithms take $O(\sqrt{N}\log N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present a new algorithm which solves the problem in $O(\sqrt{N\log N})$ steps, thus giving an $O(\sqrt{\log N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

7 pages, 1 figure. Accepted for publication in PRA

References in corpus (6)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Spatial search and the Dirac equation
• General framework for quantum search algorithms

Cited by in corpus (96)

• Quantum walks: a comprehensive review
• Universal quantum computation using the discrete time quantum walk
• On the relationship between continuous- and discrete-time quantum walk
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Search via Quantum Walk
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• Optimized quantum random-walk search algorithms
• Mimicking the probability distribution of a two-dimensional Grover walk with a single-qubit coin
• Quantum walk approach to search on fractal structures
• Quantum walks can find a marked element on any graph
• Experimental realisation of a delayed-choice quantum walk
• Quantum Computation and Quantum Information
• Alternate two-dimensional quantum walk with a single-qubit coin
• Decoherence in one-dimensional Quantum Walk
• Quantum state engineering using one-dimensional discrete-time quantum walks
• Quantum Walks
• Faster Search by Lackadaisical Quantum Walk
• Spatial search by continuous-time quantum walks on crystal lattices
• Asymptotic entanglement in a two-dimensional quantum walk
• Quantum search algorithms on a regular lattice
• Spatial search in a honeycomb network
• Quantum walks of two correlated photons in a 2D synthetic lattice
• Quantum walks with memory - goldfish, elephants and wise old men
• Quantum search on graphene lattices
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Search on a Fractal Lattice using a Quantum Random Walk
• Quantum walk speedup of backtracking algorithms
• From classical to quantum walks with stochastic resetting on networks
• Quantum walks and quantum search on graphene lattices
• On the adiabatic condition and the quantum hitting time of Markov chains
• The Grover search as a naturally occurring phenomenon
• General framework for quantum search algorithms
• Quantum spatial search in two-dimensional waveguide arrays
• Quantum walk-based search algorithms with multiple marked vertices
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
• Extraordinary behaviors in two-dimensional decoherent alternative quantum walk
• Mixing Times in Quantum Walks on Two-Dimensional Grids
• Spatial quantum search in a triangular network
• Lackadaisical quantum walk for spatial search
• Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
• Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs
• Connecting velocity and entanglement in quantum walks
• Asymptotic properties of the Dirac quantum cellular automaton
• Engineering topological states and quantum-inspired information processing using classical circuits
• Exceptional Quantum Walk Search on the Cycle
• Quantum search with a continuous-time quantum walk in momentum space
• Localization-like effect in two-dimensional alternate quantum walks with periodic coin operations
• Quantum Search on the Spatial Grid
• Quantum search with interacting Bose-Einstein condensates
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
• Faster quantum searching with almost arbitrary operators
• The quantum walk search algorithm: Factors affecting efficiency
• Spatial Search Algorithms on Hanoi Networks
• Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
• Probability distributions for Markov chains based quantum walks
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
• Quantum walk, entanglement and thermodynamic laws
• New Developments in Quantum Algorithms
• Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
• Quantum walk search by Grover search on coin space
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Decoherence in Search Algorithms
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
• Quantum walk search on a two-dimensional grid with extra edges
• Tunneling effects in a one-dimensional quantum walk
• Pseudo-Hermitian continuous-time quantum walks
• Coined quantum walks on the line: Disorder, entanglement, and localization
• Quantum search on Hanoi network
• Staggered Quantum Walk on Hexagonal Lattices
• Efficient quantum walk on the grid with multiple marked elements
• Quantum Corralling
• Postprocessing can speed up general quantum search algorithms
• A Complete Characterization of Pretty Good State Transfer on Paths
• Quantum search algorithm tailored to clause satisfaction problems
• Improving the query complexity of quantum spatial search in two dimensions
• Quantum Search Algorithms on Hierarchical Networks
• Superdiffusivity of quantum walks: A Feynman sum-over-paths description
• Quantum spatial search with electric potential : long-time dynamics and robustness to noise
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Quantum Algorithms: Database Search and its Variations
• On Hitting Times for General Quantum Markov Processes
• Quantum walk search for exceptional configurations
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Spatial search using the discrete time quantum walk
• Quantum Hitting Time on the Complete Graph
• Quantum walk on a square lattice with identical particles
• Lackadaisical quantum walks on triangular and honeycomb 2D grids
• Absorption-based qubit estimation in discrete-time quantum walks
• Search Via quantum walks with intermediate measurements
• Quantum Search on Simplicial Complexes
• Continuous-time quantum walks on a defective lattice: Boosting the spreading of delocalized states through Parrondo's strategy