Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T10:57:21.781Z Has data issue: false hasContentIssue false
  • English
  • Français

Spatial search on a honeycomb network

Published online by Cambridge University Press:  08 November 2010

G. ABAL ,
R. DONANGELO ,
F. L. MARQUEZINO  and
R. PORTUGAL
G. ABAL
Affiliation:
Instituto de Física, Facultad de Ingeniería, UdelaR, Herrera y Reissig 565, C.C. 30, C.P. 11300, Montevideo, Uruguay Email: abal@fing.edu.uy, donangel@fing.edu.uy
R. DONANGELO
Affiliation:
Instituto de Física, Facultad de Ingeniería, UdelaR, Herrera y Reissig 565, C.C. 30, C.P. 11300, Montevideo, Uruguay Email: abal@fing.edu.uy, donangel@fing.edu.uy
F. L. MARQUEZINO
Affiliation:
Laboratório Nacional de Computação Científica - LNCC, Av. Getúlio Vargas 333, Petrópolis, RJ, 25651-075, Brazil Email: franklin.marquezino@gmail.com, portugal@lncc.br
R. PORTUGAL
Affiliation:
Laboratório Nacional de Computação Científica - LNCC, Av. Getúlio Vargas 333, Petrópolis, RJ, 25651-075, Brazil Email: franklin.marquezino@gmail.com, portugal@lncc.br
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 with N sites 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 (Ambainis et al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 999 - 1009
Copyright
Copyright © Cambridge University Press 2010

References

Aaronson, S. and Ambainis, A. (2003) Quantum Search of Spatial Regions. In: FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science 200–203.CrossRefGoogle Scholar
Aharonov, Y., Davidovich, L. and Zagury, N. (1993) Quantum Random Walks. Physical Review A 48 1687–1690.CrossRefGoogle ScholarPubMed
Ambainis, A. (2004) Quantum walk algorithm for element distinctness. In: Proceedings 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS) 22–31.CrossRefGoogle Scholar
Ambainis, A., Kempe, J. and Rivosh, A. (2005) Coins make quantum walks faster. In: SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms 1099–1108.Google Scholar
Benioff, P. (2002) Space Searches with a Quantum Robot. In: Lomonaco, S. J. and Brandt, H. E. (eds.) Quantum Computation and Quantum Information: A millenium volume. AMS Contemporary Math. Series 305 1–12. Available at arXiv:quant-ph/0003006.CrossRefGoogle Scholar
Bennett, C. H., Bernstein, E., Brassard, G. and Vazirani, U. V. (1997) Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing 26 1510–1523.CrossRefGoogle Scholar
Brassard, G., Hoyer, P., Mosca, M. and Tapp, A. (2002) Quantum amplitude amplification and estimation. In: Lomonaco, S. J. and Brandt, H. E. (eds.) Quantum Computation and Quantum Information: A millenium volume. AMS Contemporary Math. Series 305 53–74 (2002).CrossRefGoogle Scholar
Childs, A. M. and Goldstone, J. (2004) Spatial search by quantum walk. Physical Review A 70 022314.CrossRefGoogle Scholar
Farhi, E. and Gutmann, S. (1998) Quantum computation and decision trees. Physical Review A 58 915–928.CrossRefGoogle Scholar
Geim, A. K. and MacDonald, A. H. (2007) Graphene: exploring carbon flatland Phys. Today 35–41.CrossRefGoogle Scholar
Grover, L. (1996) A fast quantum mechanical algorithm for database search. In: Proc. 28th Annual ACM Symposium on the Theory of Computation, (New York, NY), ACM Press 212–219.Google Scholar
Kittel, C. (1995) Introduction to Solid State Physics, 7th edition, Wiley.Google Scholar
Shenvi, N., Kempe, J. and Whaley, K. B. (2003) A quantum random walk search algorithm. Physical Review A 67 052307.CrossRefGoogle Scholar
Tulsi, A. (2008) Faster quantum walk algorithm for the two dimensional spatial search. Physical Review A 78 (1)012310.CrossRefGoogle Scholar
Van den Nest, M., Miyake, A., Dür, W. and Briegel, H. J. (2006) Universal Resources for Measurement-Based Quantum Computation. Physical Review Letters 97 150504.CrossRefGoogle ScholarPubMed
Wallace, P. R. (1947) The band theory of graphite. Physical Review 71 622–634.CrossRefGoogle Scholar