Abstract
Classical tree search algorithms mimic the problem solving capabilities traditionally performed by humans. In this work we propose a unitary operator, based on the principles of reversible computation, focusing on hierarchical tree search concepts for sorting purposes. These concepts are then extended in order to build a quantum oracle which, combined with Grover’s quantum algorithm, can be employed as a quantum hierarchical search mechanism whilst taking advantage of a quadratic speedup. Finally, we show how the developed model can be extended in order to perform a N-level depth-limited search.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York (1996)
Deutsch, D.: Quantum computational networks. Proceedings of the Royal Society of London A 425, 73–90 (1989)
Hirvensalo, M.: Quantum Computing. Springer, Heidelberg (2004)
Kaye, P.R., Laflamme, R., Mosca, M.: An Introduction to Quantum Computing. Oxford University Press, USA (2007)
Tarrataca, L., Wichert, A.: Tree search and quantum computation. Quantum Information Processing, 1–26 (2010), doi:10.1007/s11128-010-0212-z
Hughes, B.D.: Random Walks and Random Environments. Random Walks, vol. 1. Oxford University Press, USA (1995)
Aharonov, Y., Davidovich, L., Zagury, N.: Quantum random walks. Phys. Rev. A 48(2), 1687–1690 (1993)
Meyer, D.: From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics 85(5), 551–574 (1996)
Nayak, A., Vishwanath, A.: Quantum walk on the line. Technical report, DIMACS Technical Report (2000)
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58(2), 915–928 (1998)
Hogg, T.: A framework for structured quantum search. Physica D 120, 102 (1998)
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of ACM Symposium on Theory of Computation (STOC 2001), pp. 50–59 (July 2001)
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.: Exponential algoritmic speedup by quantum walk. In: Proceedings of the 35th ACM Symposium on Theory of Computing (STOC 2003), pp. 59–68 (September 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tarrataca, L., Wichert, A. (2011). A Hierarchical Sorting Oracle. In: Song, D., Melucci, M., Frommholz, I., Zhang, P., Wang, L., Arafat, S. (eds) Quantum Interaction. QI 2011. Lecture Notes in Computer Science, vol 7052. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24971-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-24971-6_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24970-9
Online ISBN: 978-3-642-24971-6
eBook Packages: Computer ScienceComputer Science (R0)