Необходимо зарегистрироваться, чтобы получить доступ к полным текстам статей и выпусков журналов!
- Название статьи
- КВАНТОВОЕ РЕШЕНИЕ БУЛЕВЫХ УРАВНЕНИЙ И ПРОБЛЕМА P =? NP
- Авторы
- Правильщиков Павел Алексеевич pavelp@ipu.ru, канд. техн. наук; ведущий научный сотрудник, Федеральное государственное бюджетное учреждение науки "Институт проблем управления им. В. А. Трапезникова РАН", Москва, Россия
- В разделе
- ПРИКЛАДНЫЕ ЗАДАЧИ ПРИМЕНЕНИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
- Ключевые слова
- квантовые компьютеры / квантовые процессоры-ускорители / квантовые алгоритмы / матричное D-исчисление / кубиты / кутриты / куквадриты / куниты / SAT-задача / проблема P =? NP
- Год
- 2018 номер журнала 1 Страницы 50 - 64
- Индекс УДК
- 004.38+004.9
- Код EDN
- Код DOI
- Тип статьи
- Научная статья
- Аннотация
- Приводится описание квантового D-алгоритма ( QD-алгоритма ) на примерах решения булевых уравнений. Предполагается, что QD-алгоритм функционирует на платформе квантового процессора-ускорителя (КвУ) с новым механизмом квантового параллелизма. Для простоты вместо процессора-ускорителя рассматривается его вычислительная модель в виде квантового генератора тестов (КГТ) . Для данного случая выведены оценки временной и пространственной сложности решений булевых уравнений ( в частности, SAT-задачи ). Указано на связь SAT-задачи с другими NP-полными задачами и общей проблемой " P =? NP ". Показано, что при использовании QD-алгоритмов и новой вычислительной модели с новым механизмом квантового параллелизма для решения SAT-задачи требуются полиномиальные вычислительные ресурсы.
- Полный текст статьи
- Необходимо зарегистрироваться, чтобы получить доступ к полным текстам статей и выпусков журналов!
- Список цитируемой литературы
-
Дойч Д. Структура реальности. - Москва-Ижевск: РХД, 2001.
Ильин В. В. Критерии научности знания. - М.: Высшая школа, 1989. - 128 с.
Правильщиков П. А. Новый механизм квантового параллелизма и его физические и математические основания // Информационные технологии в проектировании и производстве. 2017. № 4. С. 15-26.
Правильщиков П. А. Теоретико-множественные основания новой модели вычислений - квантового генератора тестов // Информационные технологии в проектировании и производстве. 2017. № 3. С. 20-28.
Правильщиков П. А. Использование квантовых компьютеров и квантовых ускорителей в информационных технологиях // Информационные технологии в проектировании и производстве. 2016. № 2. С. 3-12.
Правильщиков П. А. Использование квантовых алгоритмов в информационных технологиях и задачах управления (Обзор) // Информационные технологии в проектировании и производстве. 2016. № 2. С. 13-22.
Правильщиков П. А. Новая квантовая математика: матричное исчисление кубических комплексов и квантовые D-алгоритмы // Информационные технологии в проектировании и производстве. 2017. № 2. С. 21-32.
Cook S. The complexity of theorem-proving procedures: Сonference Record of Third Annual ACM Symposium on Theory of Computing, 1971. P. 151-158.
Правильщиков П. А. Симметрия диагностического лабиринта и закон сохранения перебора // Оборонный комплекс - научно-техническому прогрессу России. 1996. № 3. С. 38-52.
Правильщиков П. А. Закон сохранения перебора и естественный параллелизм D-алгоритмов для построения тестов и моделирования в технической диагностике // Автоматика и телемеханика. 2004. № 7. С. 156-199.
Правильщиков П. А. "Физическая" теорема Нетер в фотонике и computer science. Ч. I // Прикладная физика. 2005. № 6. С. 144-154.
Правильщиков П.А. "Физическая" теорема Нетер в фотонике и computer science (Часть II). // Прикладная физика, 2006. № 1. С. 95-109.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 584 с.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.
Крупский В. Н. Введение в сложность вычислений. - М.: Факториал пресс, 2006. - 128 с.
Roth J.P. Diagnosis of automata failures: a calculus and method // IBM J. Research and Development. 1966. No. 7. P. 18-32.
Правильщиков П. А. Фундаментальные проблемы управления и гипервычисления: тр. Пятой межд. конф. "Параллельные вычисления и проблемы управления". - М.: Институт проблем управления. 26-28 октября 2010. С. 709-757.
Нильсен М., Чанг И. Квантовые вычисления и квантовая информация / Пер. с англ. - М.: Мир, 2006. - 824 с.
Бортаковский А. С., Пантелеев А. В. Линейная алгебра в примерах и задачах. - М.: Высшая школа, 2010. - 591 с.
Карибский В. В., Пархоменко П. П., Согомонян Е. С., Халчев В. Ф. Основы технической диагностики: кн. 1. - М.: Энергия, 1976. - 346 с.
Перри Р. Элементарное введение в квантовые вычисления: учеб. пособие / Пер. с англ. - Долгопрудный: Изд. дом "Интеллект", 2015. - 208 с.
Прескилл Дж. Квантовая информация и квантовые вычисления. - Москва-Ижевск: ИКИ (НИЦ Регулярная и хаотическая динамика), 2008. С. 30.
Правильщиков П. А. О решении проблемы подготовки к измерению кунитов в регистре квантового компьютера // Информационные технологии в проектировании и производстве. 2016. № 3. С. 34-41.
Wigderson A. P. NP and mathematics - a computational complexity perspective. - MIT Press and McGraw-Hill, 2016. P. 3-86. URL: http://www.math.ias.edu/~avi/ PUBLICATIONS/MYPAPERS/W06/W06.pdf
Правильщиков П. А. Центральная проблема современной дискретной математики и квантовый генератор тестов: тр. 14-й Межд. конф. "CAD/CAM/PDM-2014". ФГБУ науки Институт проблем управления РАН им. Трапезникова, 2014. С. 15-20.
- Купить
