Fetching the paper…

Reading the bibliography…

2008

Faster quantum walk algorithm for the two dimensional spatial search

Tulsi, Avatar

Original
PDF
Post on X

Understand

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.

Faster quantum walk algorithm for the two dimensional spatial search · Around

Built on

L.K.Grover, Phys. Rev. Lett. 79
1997
Earlier work this paper cites.
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM Journal on Computing, 26
1997
Earlier work this paper cites.
P.Benioff, AMS Contemporary Mathematics, 305
2002
Earlier work this paper cites.
G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, AMS Contemporary Mathematics, 305
2002
Earlier work this paper cites.

Similar

S. Aaronson and A. Ambainis, Proc. 44th
2003
Cited alongside, same era.
N. Shenvi, J. Kempe, and K.B. Whaley, Phys. Rev. A 67
2003
Cited alongside, same era.
A. Childs and J. Goldstone, Phys. Rev. A 70
2004
Cited alongside, same era.
A. Tulsi, A general framework for quantum search algorithms
Cited in the paper.

Then

A. Childs and J.Goldstone, Phys. Rev. A 70
2004
Later among the works it cites.
A. Ambainis, J. Kempe, and A. Rivosh, Proc. 16th
2005
Later among the works it cites.
A. Patel, Poster presented at QIP-2008, New Delhi, December 2007, unpublished
Original
2007
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…