RUS 
中文 
ES | Form of presentation | Articles in Russian journals and collections |
| Year of publication | 2024 |
| Язык | русский |
|
| |
| Bibliographic description in the original language | Gaynutdinova A. F. Nedeterminirovannye kvantovye OBDD bolshoy shiriny // Vestnik Permskogo universiteta. Matematika. Mekhanika. Informatika. 2024. Vyp. 4(67). S. 117–131. DOI: 10.17072/1993-0550-2024-4-117-131. https://elibrary.ru/tuqhho |
| Annotation | В статье исследуются упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams) – модель для вычисления булевых функций. Целью работы является сравнительный сложностной анализ квантовых и классических недетерминированных OBDD большой ширины. Исследуется сложность вычисления булевой функции ''Равенство'' в недетерминированных квантовых OBDD для различных порядков считывания переменных в сравнении с классической сложностью. Показывается, что при использовании порядка чтения переменных, при котором ширина классической недетерминированной OBDD константна, ширина квантовой модели линейна, и что доказанная нижняя оценка точна. Определяется булева функция, для которой ширина квантовой недетерминированной OBDD экспоненциальна для любого порядка считывания. Предлагается квантовый алгоритм вычисления этой функции с нулевой ошибкой. Представляется результат о соотношении сложностных классов для квантовых и классических недетерминированных OBDD большой ширины. |
| Keywords | ветвящаяся программа; упорядоченная ветвящаяся диаграмма решений; недетерминизм; квантовый алгоритм; cложность; класс сложности; вычислительная модель; иерархия сложностных классов; нижняя оценка; верхняя оценка |
| The name of the journal | Вестник Пермского университета. Математика. Механика. Информатика |
| Please use this ID to quote from or refer to the card | https://repository.kpfu.ru/eng/?p_id=308524&p_lang=2 |
Full metadata record  | |
Sitemap
