Alternative Coins for Quantum Random Walk Search Optimized for a Hypercube

Hristo Tonchev^*

Department of Physics, Sofia University, Sofia, Bulgaria.

DOI: 10.4236/jqis.2015.51002                

Abstract

The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. This method changes the quantum coins, while the shift operator remains unchanged and sustains the hypercube topology. The results discussed in this paper are obtained by both theoretical calculations and numerical simulations.

Keywords

Quantum Information, Quantum Random, Quantum Random Walk Search

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Grover, L. (1996) A Fast Quantum Mechanical Algorithm for Database Search. arXiv:/9605043 [quant-ph].
[2]	Yamaguchi, F., Milman, P., Brune, M., Raimond, J. and Haroche, S. (2002) Quantum Search with Two-Atom Collisions in Cavity QED. Physical Review A, 66, Article ID: 010302. arXiv:quant-ph/0203146v1. http://dx.doi.org/10.1103/PhysRevA.66.010302
[3]	Vandersypen, L., Steffen, M., Sherwood, M., Yannoni, C., Breyta, G., and Chuang, I. (2000) Implementation of a Three-Quantum-Bit Search Algorithm. Applied Physics Letters, 76, 646-648. arXiv:quant-ph/9910075v2. http://dx.doi.org/10.1063/1.125846
[4]	Gent, I. and Walsh, T. (1994) Easy Problems Are Sometimes Hard. Artificial Intelligence, 70, 335-345. http://dx.doi.org/10.1016/0004-3702(94)90109-0
[5]	Sze, S. and Pevzner, P. (1997) Las Vegas Algorithms for Gene Recognition: Suboptimal and Error-Tolerant Spliced Alignment. RECOMB’97 Proceedings of the 1st Annual International Conference on Computational Molecular Biology, Santa Fe, 20-23 January 1997, 300-309. http://dx.doi.org/10.1145/267521.267889
[6]	Clark, M. and Kennedy, A. (2007) Accelerating Dynamical-Fermion Computations Using the Rational Hybrid Monte Carlo Algorithm with Multiple Pseudofermion Fields. Physical Review Letters, 98, Article ID: 051601. http://dx.doi.org/10.1103/PhysRevLett.98.051601
[7]	Newman, M. and Ziff, R. (2001) Fast Monte Carlo Algorithm for Site or Bond Percolation. Physical Review E, 64, Article ID: 016706. http://dx.doi.org/10.1103/PhysRevE.64.016706
[8]	Houdayer, J. (2001) A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses. The European Physical Journal B—Condensed Matter and Complex Systems, 22, 479-484. arXiv:condmat/0101116 [cond-mat.dis-nn].
[9]	Farhi, E. and Gutmann, S. (1998) Quantum Computation and Decision Trees. Physical Review A, 58, 915-928. http://dx.doi.org/10.1103/PhysRevA.58.915
[10]	Childs, A., Farhi, E. and Gutmann, S. (2001) An Example of the Difference between Quantum and Classical Random Walks. Quantum Information Processing, 1, 35-43. arXiv:quantph/0103020.
[11]	Childs, A., Cleve, R., Deotto, E., Farhi, E., Gutmann, S. and Spielman, D.A. (2002) Exponential Algorithmic Speedup by Quantum Walk. arXiv:quant-ph/0209131v2.
[12]	Childs, A. and Goldstone, J. (2004) Spatial Search by Quantum Walk. Physical Review A, 70, Article ID: 022314. arXiv:quant-ph/0306054v2. http://dx.doi.org/10.1103/PhysRevA.70.022314
[13]	Aharonov, Y., Davidovich, L. and Zagury, N. (1993) Quantum Random Walks. Physical Review A, 48, 1687-1690. http://dx.doi.org/10.1103/PhysRevA.48.1687
[14]	Ambainis, A. (2003) Quantum Walk Algorithm for Element Distinctness. arXiv:quant-ph/0311001.
[15]	Shenvi, N., Kempe, J. and Whaley, K. (2003) Quantum Random-Walk Search Algorithm. Physical Review A, 67, Article ID: 052307. http://dx.doi.org/10.1103/PhysRevA.67.052307
[16]	Hein, B. and Tanner, G. (2009) Quantum Search Algorithms on the Hypercube. Journal of Physics A: Mathematical and Theoretical, 42, Article ID: 085303. arXiv:0906.3094v1 [quant-ph]. http://dx.doi.org/10.1088/1751-8113/42/8/085303
[17]	Potocek, V., Gabris, A., Kiss, T. and Jex, I. (2009) Optimized Quantum Random-Walk Search Algorithms on the Hypercube. Physical Review A, 79, Article ID: 012325. http://dx.doi.org/10.1103/PhysRevA.79.012325
[18]	Tulsi, A. (2008) Faster Quantum Walk Algorithm for the Two Dimensional Spatial Search. Physical Review A, 78, Article ID: 012310. arXiv:0801.0497v2 [quantph].
[19]	Long, G. (2001) Grover Algorithm with Zero Theoretical Failure Rate. Physical Review A, 64, Article ID: 022307. http://dx.doi.org/10.1103/PhysRevA.64.022307
[20]	Hoyer, S. (2008) Quantum Random Walk Search on Satisfiability Problems. PhD Thesis, Swarthmore College, Swarthmore.
[21]	Ambainis, A., Kempe, J. and Rivosh, A. (2004) Coins Make Quantum Walks Faster. arXiv:quantph/0402107.
[22]	Nayak, A. and Vishwanath, A. (2000) Quantum Walk on the Line. arXiv:quant-ph/0010117v1.
[23]	Kempe, J. (2003) Quantum Random Walks—An Introductory Overview. Contemporary Physics, 44, 307-327. arXiv:quant-ph/0303081. http://dx.doi.org/10.1080/00107151031000110776