Недетерминированные квантовые OBDD большой ширины
DOI:
https://doi.org/10.17072/1993-0550-2024-4-117-131Ключевые слова:
ветвящаяся программа, упорядоченная ветвящаяся диаграмма решений, недетерминизм, квантовый алгоритм, cложность, класс сложности, вычислительная модель, иерархия сложностных классов, нижняя оценка, верхняя оценкаАннотация
В статье исследуются упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams) – модель для вычисления булевых функций. Целью работы является сравнительный сложностной анализ квантовых и классических недетерминированных OBDD большой ширины. Исследуется сложность вычисления булевой функции "Равенство" в недетерминированных квантовых OBDD для различных порядков считывания переменных в сравнении с классической сложностью. Показывается, что при использовании порядка чтения переменных, при котором ширина классической недетерминированной OBDD константна, ширина квантовой модели линейна, и что доказанная нижняя оценка точна. Определяется булева функция, для которой ширина квантовой недетерминированной OBDD экспоненциальна для любого порядка считывания. Предлагается квантовый алгоритм вычисления этой функции с нулевой ошибкой. Представляется результат о соотношении сложностных классов для квантовых и классических недетерминированных OBDD большой ширины.Библиографические ссылки
Манин Ю.И. Вычислимое и невычислимое. М.: Сов. Радио. 1980. 128 с.
Feynman R. Simulating physics with computers // International Journal of Theoretical Physics. 1982. Vol. 21, № 6, 7. С. 467−488.
Wegener I. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics. 2000. 408 p.
Cobham A. The recognition problem for the set of perfect squares // Proc. of the 7th Symposium on Switching an Automata Theory (SWAT). 1996. P. 78−87.
Pudlak P., Zak S. Space complexity of computations. Technical report, Univ. Prague. 1983.
Ablayev F., Gainutdinova A., Karpinski M. On Computational Power of Quantum Branching Programs // Proc. of the 13th Intern. Symposium, Fundamentals of Computation Theory, FCT2001. 2001. Vol. 2138. P. 59−70.
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: 6th Annual Intern. Conference, COCOON 2000, Proc. 2000. Vol. 2138. P. 467−476.
Sauerhoff M., Sieling D. Quantum branching programs and space-bounded nonuniform quantum complexity // Theoretical Computer Science. 2005. Vol. 334. № 1–3. P. 177–225.
Ablayev F., Karpinski M. On the power of randomized branching programs // Proc. ICALP96. 1996. Vol. 1099. P. 348–356.
Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C. On the computational power of probabilistic and quantum branching program // Information and Computation. 2005. Vol. 203, № 2. P. 145–162.
Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OB-DDs and width hierarchies for classical OBDDs // Lobachevskii Journal of Mathematics. 2016. Vol. 37. P. 670–682.
Gainutdinova A., Yakaryılmaz A. Nondeterministic unitary OBDDs // Computer Science – Theory and Applications: 12th Intern. Computer Science Symposium in Russia, CSR2017, Proceedings. 2017. P. 126–140.
Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications. Springer Science & Business Media, 1998. 279 p.
Ablayev F., Gainutdinova A. Complexity of quantum uniform and nonuniform automata // Developments in Language Theory: 9th Intern. Conference, DLT2005, Proceedings. 2005. P. 78–87.
Nielsen M. A., Chuang I. L. Quantum computation and quantum information. Cambridge university press, 2010. 710 p.
Кострикин А.И. Введение в алгебру: учебник: в 3 частях. Часть II: Линейная алгебра. М.: МЦНМО, 2020. 367 с.
Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OB-DDs and width hierarchies for classical OBDDs // Descriptional Complexity of Formal Systems: 16th Intern. Workshop DCFS2014, Proceedings. 2014. P. 53–64.
Khadiev K., Khadieva A. Reordering method and hierarchies for quantum and classical ordered binary decision diagrams // International computer science symposium in Russia, Springer International Publishing, 2017. P. 162–175.
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Copyright (c) 2024 Аида Фаритовна Гайнутдинова
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Публикация статьи в журнале осуществляется на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0).
