The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$ .The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$ .

arXiv:1001.1139Mathematical Structures in Computer ScienceNov 8, 201044 citations

Enhanced algorithms for Local Search

Yves F. Verhoeven

arXiv:quant-ph/0506019Information Processing LettersDec 6, 200510 citations

Deterministic spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$ -vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv:2104.03806Physical Review AAug 24, 202115 citations

Cluster algorithms

Ferenc Niedermayer A

arXiv:hep-lat/9704009Springer eBooksApr 7, 20084 citations

Recursive quantum spatial search does not need ancilla qubit

Avatar Tulsi

Spatial search is a widely studied application of quantum algorithms. Several algorithms have been proposed for spatial search without using ancilla qubits which are easier to implement physically. All such algorithms are based on the widely studied quantum walk approach. Here we consider another approach by Aaronson and Ambainis based on the recursive application of Grover's algorithm rather than quantum walks. Their algorithm needs one ancilla qubit for successful implementation. We present a different recursive algorithm which does not need any ancilla qubit and hence it offers physical implementation advantages.Spatial search is a widely studied application of quantum algorithms. Several algorithms have been proposed for spatial search without using ancilla qubits which are easier to implement physically. All such algorithms are based on the widely studied quantum walk approach. Here we consider another approach by Aaronson and Ambainis based on the recursive application of Grover's algorithm rather than quantum walks. Their algorithm needs one ancilla qubit for successful implementation. We present a different recursive algorithm which does not need any ancilla qubit and hence it offers physical implementation advantages.

Aug 2, 20150 citations

O(\sqrt{N \log N})

N

-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.