arXiv:0801.0497 · Physical Review A

Faster quantum-walk algorithm for the two-dimensional spatial search

Avatar Tulsi

Published Jul 9, 2008• 185 citations

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}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

DOI: 10.1103/physreva.78.012310

Related papers

Spatial search by quantum walk

Andrew M. Childs, Jeffrey Goldstone

arXiv:quant-ph/0306054Physical Review AAug 23, 2004726 citations

Spatial search and the Dirac equation

Andrew M. Childs, Jeffrey Goldstone

arXiv:quant-ph/0405120Physical Review AOct 19, 2004145 citations

Robust quantum spatial search

Avatar Tulsi

arXiv:1508.00207Aug 2, 20150 citations

Search on a hypercubic lattice using a quantum random walk. II. d=2

Apoorva D. Patel, K. S. Raghunathan, Md. Aminoor Rahaman

arXiv:1003.5564Physical Review ASep 28, 201023 citations

Search on a Hypercubic Lattice using Quantum Random Walk

Apoorva Patel, Md. Aminoor Rahaman

Jun 5, 20092 citations

Improving quantum spatial search in two dimensions

Abhijith Jayakumar, Apoorva D. Patel

Quantum Information and ComputationJun 1, 20190 citations

arXiv:0801.0497 · Physical Review A

Faster quantum-walk algorithm for the two-dimensional spatial search

Avatar Tulsi

Published Jul 9, 2008• 185 citations

arXiv HTML PDF

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}\ifmmode\times\else\texttimes\fi{}\sqrt{N}

. The previous quantum-walk based algorithms take

O(\sqrt{N}\text{ }\text{ln}\text{ }N)

steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in

O(\sqrt{N\text{ }\text{ln}\text{ }N})

steps, thus giving an

O(\sqrt{\text{ln}\text{ }N})

improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

DOI: 10.1103/physreva.78.012310

Related papers

Spatial search by quantum walk

Andrew M. Childs, Jeffrey Goldstone

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d>2$ , and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$ . We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$ -dimensional periodic lattice for $d>4$ . In $d=4$ , the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ , and in $d<4$ , the algorithm does not provide substantial speedup.Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d>2$, and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$-dimensional periodic lattice for $d>4$. In $d=4$, the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$, and in $d<4$, the algorithm does not provide substantial speedup.

arXiv:quant-ph/0306054Physical Review AAug 23, 2004726 citations

Spatial search and the Dirac equation

Andrew M. Childs, Jeffrey Goldstone

We consider the problem of searching a $d$ -dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$ . This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$ ), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.We consider the problem of searching a $d$-dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.

arXiv:quant-ph/0405120Physical Review AOct 19, 2004145 citations

Robust quantum spatial search

Avatar Tulsi

Quantum spatial search has been widely studied with most of the study focusing on quantum walk algorithms. We show that quantum walk algorithms are extremely sensitive to systematic errors. We present a recursive algorithm which offers significant robustness to certain systematic errors. To search N items, our recursive algorithm can tolerate errors of size O(1/\sqrt{\ln N}) which is exponentially better than quantum walk algorithms for which tolerable error size is only O(\ln N/\sqrt{N}). Also, our algorithm does not need any ancilla qubit. Thus our algorithm is much easier to implement experimentally compared to quantum walk algorithms.Quantum spatial search has been widely studied with most of the study focusing on quantum walk algorithms. We show that quantum walk algorithms are extremely sensitive to systematic errors. We present a recursive algorithm which offers significant robustness to certain systematic errors. To search N items, our recursive algorithm can tolerate errors of size O(1/\sqrt{\ln N}) which is exponentially better than quantum walk algorithms for which tolerable error size is only O(\ln N/\sqrt{N}). Also, our algorithm does not need any ancilla qubit. Thus our algorithm is much easier to implement experimentally compared to quantum walk algorithms.

arXiv:1508.00207Aug 2, 20150 citations

Search on a hypercubic lattice using a quantum random walk. II. d=2

Apoorva D. Patel, K. S. Raghunathan, Md. Aminoor Rahaman

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. $d=2$ is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an $O(\sqrt{N}\mathrm{ln}N)$ algorithm, which is not optimal. The scaling behavior can be improved to $O(\sqrt{N\mathrm{ln}N})$ by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi [Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. $d=2$ is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an $O(\sqrt{N}\mathrm{ln}N)$ algorithm, which is not optimal. The scaling behavior can be improved to $O(\sqrt{N\mathrm{ln}N})$ by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi [Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

arXiv:1003.5564Physical Review ASep 28, 201023 citations

Search on a Hypercubic Lattice using Quantum Random Walk

Apoorva Patel, Md. Aminoor Rahaman

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

Jun 5, 20092 citations

Improving quantum spatial search in two dimensions

Abhijith Jayakumar, Apoorva D. Patel

The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.

Quantum Information and ComputationJun 1, 20190 citations

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}\ifmmode\times\else\texttimes\fi{}\sqrt{N}

. The previous quantum-walk based algorithms take

O(\sqrt{N}\text{ }\text{ln}\text{ }N)

steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in

O(\sqrt{N\text{ }\text{ln}\text{ }N})

steps, thus giving an

O(\sqrt{\text{ln}\text{ }N})

improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

N

items laid out in

d

spatial dimensions can be searched in time of order

\sqrt{N}

for

d>2

, and in time of order

\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)

for

d=2

. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that

\sqrt{N}

speedup can also be achieved on the hypercube. We show that full

\sqrt{N}

speedup can be achieved on a

d

-dimensional periodic lattice for

d>4

. In

d=4

, the quantum walk search algorithm takes time of order

\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)

, and in

d<4

, the algorithm does not provide substantial speedup.

We consider the problem of searching a

d

-dimensional lattice of

N

sites for a single marked location. We present a Hamiltonian that solves this problem in time of order

\sqrt{N}

for

d>2

and of order

\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N

in the critical dimension

d=2

. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of

d=4

), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism.

d=2

is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an

O(\sqrt{N}\mathrm{ln}N)

algorithm, which is not optimal. The scaling behavior can be improved to

O(\sqrt{N\mathrm{ln}N})

by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi [Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.