Недетерминированные квантовые OBDD большой ширины
Автор: Аида Фаритовна Гайнутдинова
Журнал: Вестник Пермского университета. Серия: Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Компьютерные науки и информатика
Статья в выпуске: 4 (67), 2024 года.
Бесплатный доступ
В статье исследуются упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams) – модель для вычисления булевых функций. Целью работы является сравнительный сложностной анализ квантовых и классических недетерминированных OBDD большой ширины. Исследуется сложность вычисления булевой функции "Равенство" в недетерминированных квантовых OBDD для различных порядков считывания переменных в сравнении с классической сложностью. Показывается, что при использовании порядка чтения переменных, при котором ширина классической недетерминированной OBDD константна, ширина квантовой модели линейна, и что доказанная нижняя оценка точна. Определяется булева функция, для которой ширина квантовой недетерминированной OBDD экспоненциальна для любого порядка считывания. Предлагается квантовый алгоритм вычисления этой функции с нулевой ошибкой. Представляется результат о соотношении сложностных классов для квантовых и классических недетерминированных OBDD большой ширины.
Ветвящаяся программа, упорядоченная ветвящаяся диаграмма решений, недетерминизм, квантовый алгоритм, cложность, класс сложности, вычислительная модель, иерархия сложностных классов, нижняя оценка, верхняя оценка
Короткий адрес: https://sciup.org/147247341
IDR: 147247341 | DOI: 10.17072/1993-0550-2024-4-117-131
Список литературы Недетерминированные квантовые 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.
