Квантовые и классические недетерминированные OBDD
https://doi.org/10.26907/2541-7746.2024.4.470-484
Аннотация
Исследована модель недетерминированных упорядоченных ветвящихся диаграмм решений (NOBDD). Дан метод доказательства нижней оценки сложности квантовой NOBDD. Представлены функция, имеющая линейную сложность в квантовой NOBDD и константную сложность в классической NOBDD, а также функция, имеющая одинаковую сложность в квантовой и классической моделях. Описано соотношение сложностных классов, определенных для модели OBDD.
Ключевые слова
ветвящаяся программа,
упорядоченная ветвящаяся диаграмма решений,
OBDD,
сложность,
квантовый алгоритм,
недетерминизм,
иерархия классов сложности
При поддержке: Работа выполнена за счет средств Программы стратегического академического лидерства Казанского (Приволжского) федерального университета («ПРИОРИТЕТ-2030»)
Об авторе
А. Ф. Гайнутдинова
Казанский (Приволжский) федеральный университет
Россия
Россия
Аида Фаритовна Гайнутдинова, кандидат физико-математических наук, доцент
Институт вычислительной математики и информационных технологий; кафедрА теоретической кибернетики
420008; ул. Кремлевская, д. 18; Казань
Список литературы
1. Wegener I. Branching Programs and Binary Decision Diagrams: Theory and Applications. Ser.: Discrete Mathematics and Applications / Hammer P.L. (Ed.). Philadelphia, PA: Soc. Ind. Appl. Math., 2000. 396 p. doi: 10.1137/1.9780898719789.
2. Nakanishi M., Hamaguchi K., Kashiwabara T. Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction // Computing and Combinatorics (COCOON 2000): Proc. 6<sup>th</sup> Annu. Int. Conf. / Du D.-Z., Eades P., Estivill-Castro V., Lin X., Sharma A. (Eds.). Ser.: Lecture Notes in Computer Science. V. 1858. Berlin, Heidelberg: Springer, 2000. P. 467–476. doi: 10.1007/3-540-44968-X_46.
3. Sauerhoff M., Sieling D. Quantum branching programs and space-bounded nonuniform quantum complexity // Theor. Comput. Sci. 2005. V. 334, Nos 1–3. P. 177–225. doi: 10.1016/j.tcs.2004.12.031.
4. Ablayev F.M., Karpinski M. On the power of randomized branching programs // Automata, Languages and Programming (ICALP’ 96): Proc. 23<sup>rd</sup> Int. Colloq. / Meyer F., Monien B. (Eds.). Ser.: Lecture Notes in Computer Science. V. 1099. Berlin, Heidelberg: Springer, 1996. P. 348–356. doi: 10.1007/3-540-61440-0_141.
5. Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C. On the computational power of probabilistic and quantum branching program // Inf. Comput. 2005. V. 203, No 2. P. 145–162. doi: 10.1016/j.ic.2005.04.003.
6. Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs // Lobachevskii J. Math. 2016. V. 37, No 6. P. 670–682. doi: 10.1134/S199508021606007X.
7. Gainutdinova A., Yakaryılmaz A. Nondeterministic unitary OBDDs // Computer Science – Theory and Applications (CSR 2017): Proc. 12<sup>th</sup> Int. Comput. Sci. Symp. in Russia / Weil P. (Ed.). Ser.: Lecture Notes in Computer Science. V. 10304. Cham: Springer, 2017. P. 126–140. doi: 10.1007/978-3-319-58747-9_13.
8. Гайнутдинова А.Ф. Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций // Изв. вузов. Матем. 2015. № 11. С. 32–43.
9. Ablayev F., Gainutdinova A. Complexity of quantum uniform and nonuniform automata // Developments in Language Theory (DLT 2005): Proc. 9<sup>th</sup> Int. Conf. / De Felice C., Restivo A. (Eds.). Ser.: Lecture Notes in Computer Science. V. 3572. Berlin, Heidelberg: Springer, 2005. P. 78–87. doi: 10.1007/11505877_7.
10. Nielsen M.A., Chuang I. Quantum Computation and Quantum Information. Ser.: Cambridge Series on Information and the Natural Sciences. V. 2. Cambridge, Cambridge Univ. Press, 2000. 676 p.
11. Кострикин А.И. Введение в алгебру. В 3-х ч. Ч. 2: Линейная алгебра. М.: МЦНМО, 2020. 368 с.
12. Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs // Descriptional Complexity of Formal Systems (DCFS 2014): Proc. 16<sup>th</sup> Int. Wokshop / J¨urgensen H., Karhum¨aki J., Okhotin A. (Eds.). Ser.: Lecture Notes in Computer Science. V. 8614. Cham: Springer, 2014. P. 53–64. doi: 10.1007/978-3-319-09704-6_6.
Рецензия
Для цитирования:
Гайнутдинова А.Ф. Квантовые и классические недетерминированные OBDD. Ученые записки Казанского университета. Серия Физико-математические науки. 2024;166(4):470-484. https://doi.org/10.26907/2541-7746.2024.4.470-484
For citation:
Gainutdinova A.F. Quantum and classical nondeterministic OBDDs. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2024;166(4):470-484. (In Russ.) https://doi.org/10.26907/2541-7746.2024.4.470-484
Просмотров:
122
Послать статью по эл. почте 