Spatial quantum search in a triangular network

Abstract

The spatial search problem consists in minimizing the number of steps required to find a given site in a network, under the restriction that only oracle queries or translations to neighboring sites are allowed. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algortithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh [AKR05] (AKR) and Tulsi [Tulsi08], applied to a triangular network. The AKR-Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is O(sqrt(N logN)).

10 pages, 4 Postscript figures, uses sbc-template.sty, appeared in Annals of WECIQ 2010, III Workshop of Quantum Computation and Quantum Information

References in corpus (3)

• A Quantum Random Walk Search Algorithm
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search in a honeycomb network

Cited by in corpus (10)

• The Dirac equation as a quantum walk over the honeycomb and triangular lattices
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Quantum spatial search in two-dimensional waveguide arrays
• Spatial Search Algorithms on Hanoi Networks
• Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Quantum search on Hanoi network
• Staggered Quantum Walk on Hexagonal Lattices
• Lackadaisical quantum walks on triangular and honeycomb 2D grids
• Quantum Search on Simplicial Complexes