EN|RU

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).
 © Sobolev Institute of Mathematics, 2015