Том 22, номер 1, 2015 г., cтр. 86-99
УДК 519.178
И. М. Хузиев
О поиске антиподальных вершин в симметричном графе Кэли группы булева куба
Аннотация:
Вводится отношение антиподальности в графе и задача поиска антиподальной вершины. Приводится вероятностный алгоритм решения оракульной задачи для симметричного графа Кэли над группой $\mathbb Z_2^n$, когда число запросов к оракулу полиномиально по степени вершин.
Ил. 1, библиогр. 5.
Ключевые слова: граф, автоморфизм, антиподальность, оракул.
DOI: 10.17377/daio.2015.22.443
Ильнур Масхудович Хузиев 1
1. Московский физико-технический институт,
ул. Первомайская, 5, корп. 2, 141700 Долгопрудный, Россия
е-mail: ilnur.khuziev@yandex.ru
Статья поступила 3 марта 2014 г.
Исправленный вариант — 26 августа 2014 г.
Литература
[1] Красин В. Ю. О слабых изометриях булева куба // Дискрет. анализ и исслед. операций. Cер. 1. 2006. Т. 13, №4. C. 26–32.
[2] Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. М.: Мир, 2006. 824 с.
[3] Childs A. M., Cleve R., Deotto E., Farhi E., Gutmann S., Spielman D. A. Exponential algorithmic speedup by quantum walk // Proc. 35th ACM Symp. Theory of Computing (STOC 2003). P. 59–68.
[4] Kempe J. Discrete quantum walks hit exponentially faster // Proc. 7th Int. Workshop Randomization and Approximation Techniques in Computer Science (RANDOM’03). 2003. P. 354–369. (Lect. Notes Comput. Sci.; Vol. 2764).
[5] Khuziev I. Quantum walk in symmetric Cayley graph over
