EN 
中文 
ES | Форма представления | Статьи в российских журналах и сборниках |
| Год публикации | 2024 |
| Язык | русский |
|
| |
| Библиографическое описание на языке оригинала | Гайнутдинова А. Ф. Недетерминированные квантовые OBDD большой ширины // Вестник Пермского университета. Математика. Механика. Информатика. 2024. Вып. 4(67). С. 117–131. DOI: 10.17072/1993-0550-2024-4-117-131. https://elibrary.ru/tuqhho |
| Аннотация | В статье исследуются упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams) – модель для вычисления булевых функций. Целью работы является сравнительный сложностной анализ квантовых и классических недетерминированных OBDD большой ширины. Исследуется сложность вычисления булевой функции ''Равенство'' в недетерминированных квантовых OBDD для различных порядков считывания переменных в сравнении с классической сложностью. Показывается, что при использовании порядка чтения переменных, при котором ширина классической недетерминированной OBDD константна, ширина квантовой модели линейна, и что доказанная нижняя оценка точна. Определяется булева функция, для которой ширина квантовой недетерминированной OBDD экспоненциальна для любого порядка считывания. Предлагается квантовый алгоритм вычисления этой функции с нулевой ошибкой. Представляется результат о соотношении сложностных классов для квантовых и классических недетерминированных OBDD большой ширины. |
| Ключевые слова | ветвящаяся программа; упорядоченная ветвящаяся диаграмма решений; недетерминизм; квантовый алгоритм; cложность; класс сложности; вычислительная модель; иерархия сложностных классов; нижняя оценка; верхняя оценка |
| Название журнала | Вестник Пермского университета. Математика. Механика. Информатика |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку | https://repository.kpfu.ru/?p_id=308524 |
Полная запись метаданных  | |
Карта сайта
