Volume 22, No 1, 2015, P. 86–99
UDC 519.178
I. M. Khuziev
About searching for antipodal vertexes in symmetric Cayley graphs
Abstract:
We present the antipodality relation and search for an antipodal vertex. We also give a randomized algorithm solving the oracle problem in symmetric Cayley graphs over group $\mathbb Z_2^n$. The number of queries is polynomial over the graph’s degree.
Ill. 1, bibliogr. 5.
Keywords: graph, automorphism, antipodality, oracle
DOI: 10.17377/daio.2015.22.443
Ilnur M. Khuziev 1
1. Moscow Institute of Physics and Technology,
5/2 Pervomaiskaya St., 141700 Dolgoprudnyi, Russia
å-mail: ilnur.khuziev@yandex.ru
Received 3 March 2014
Revised 26 August 2014
References
[1] V. Yu. Krasin, On the weak isometries of the Boolean cube, J. Appl. Ind. Math., 1, No. 4, 463–467, 2007.[2] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge Univ. Press, Cambridge, 2000.
[3] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk, in Proc. 35th ACM Symp. Theory of Computing, San Diego, CA, USA, June
9–11, 2003, 59–68, ACM, New York, 2003.
[4] J. Kempe, Discrete quantum walks hit exponentially faster, in S. Arora, K. Jansen, J. D. P. Rolim, and A. Sahai, eds., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Proc. 7th Int. Workshop on Randomization and Approximation Techniques in Comp. Sci., Princeton, NJ, USA, Aug. 24–26, 2003), 354–369, Springer-Verl., Berlin, 2003 (Lect. Notes Comput. Sci., Vol. 2764).
[5] I. M. Khuziev, Quantum walk in symmetric Cayley graph over $\mathbb Z_2^n$ , 2013 (Cornell Univ. Libr. e-Print Archive, arXiv:1305.6849).
