Abstract
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
In this paper, we show that despite a small probability to find a marked location, the probability to be within \(O(\sqrt{N})\) neighbourhood (at \(O(\sqrt[4]{N})\) distance) of the marked location is Θ(1). This allows to skip amplitude amplification step and leads to \(O(\sqrt{\log{N}})\) speed-up.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aaronson, S., Ambainis, A.: Quantum search of spatial regions. In: Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 200–209 (2003)
Ambainis, A., Backurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Search by quantum walks on two-dimensional grid without amplitude amplification. arXiv:quant-ph/1112.3337, 22 pages (2011)
Ambainis, A.: Quantum walks and their algorithmic applications. International Journal of Quantum Information 1, 507–518 (2003)
Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1) 2007, 210–239 (2007, 2001)
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of SODA 2005, pp. 1099–1108 (2005)
Ambainis, A., Rivosh, A.: Quantum Walks with Multiple or Moving Marked Locations. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 485–496. Springer, Heidelberg (2008)
Benioff, P.: Space searches with a quantum robot. In: Quantum Computation and Information, Washington, DC. Contemp. Math., vol. 305, pp. 1–12. Amer. Math. Soc., Providence (2002)
Buhrman, H., Spalek, R.: Quantum Verification of Matrix Products. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, pp. 880–889 (2006)
Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM Journal on Computing 26, 1411–1473 (1997)
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of the 35th ACM STOC, pp. 59–68 (2003)
Childs, A., Goldstone, J.: Spatial search and the Dirac equation. Physical Review A 70, 042312 (2004)
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM STOC, Philadelphia, Pennsylvania, pp. 212–219. ACM Press (1996)
Kempe, J.: Quantum random walks - an introductory overview. Contemporary Physics 44(4), 302–327 (2003)
Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding Is as Easy as Detecting for Quantum Walks. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 540–551. Springer, Heidelberg (2010)
Meyer, D.A.: From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics 85, 551–574 (1996)
Marquezino, F.L., Portugal, R., Abal, G.: Mixing times in quantum walks on two-dimensional grids. arxiv:1006.4625
Magniez, F., Santha, M., Szegedy, M.: An O(n 1.3) quantum algorithm for the triangle problem. In: Proceedings of SODA 2005, pp. 1109–1117 (2005); SIAM J. Comput. 37(2), 413–424 (2007)
Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Physical Review A 67(5), 052307 (2003)
Szegedy, M.: Quantum speed-up of Markov Chain based algorithms. In: Proceedings of IEEE FOCS 2004, pp. 32–41 (2004)
Tulsi, A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78, 012310 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., Rivosh, A. (2013). Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. In: Iwama, K., Kawano, Y., Murao, M. (eds) Theory of Quantum Computation, Communication, and Cryptography. TQC 2012. Lecture Notes in Computer Science, vol 7582. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35656-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-35656-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35655-1
Online ISBN: 978-3-642-35656-8
eBook Packages: Computer ScienceComputer Science (R0)