RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз., 2017, том 138, страницы 60–75 (Mi into214)  

Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера

Е. А. Маркевичa, А. С. Трушечкинbac

a Национальный исследовательский ядерный университет "МИФИ", г. Москва
b Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
c Национальный исследовательский технологический университет "МИСиС"

Аннотация: Предложен квантовый алгоритм ветвей и границ на основе сочетания общей схемы метода ветвей и границ с квантовым алгоритмом вложенного поиска. Исследуется его вычислительная эффективность в сравнении с аналогичным классическим алгоритмом на примере задачи коммивояжера. Показывается, что в подавляющем большинстве задач классический алгоритм превосходит по скорости квантовый за счет большей адаптивности. Тем не менее, время работы квантового алгоритма постоянно для всех задач, тогда как классический алгоритм на некоторых задачах работает очень медленно. В результате для наихудшего случая квантовый алгоритм ветвей и границ оказался в несколько раз эффективнее классического алгоритма.

Ключевые слова: квантовые вычисления, квантовый компьютер, квантовый поиск, алгоритм Гровера, метод ветвей и границ, задача коммивояжера.

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации МК-2815.2017.1
Исследование выполнено при поддержке гранта Президента Российской Федерации (проект МК-2815.2017.1).


Полный текст: PDF файл (261 kB)

Реферативные базы данных:

Тип публикации: Статья
УДК: 517.958:530.145, 519.85
MSC: 81P68, 68Q12

Образец цитирования: Е. А. Маркевич, А. С. Трушечкин, “Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера”, Квантовые вычисления, Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз., 138, ВИНИТИ РАН, Москва, 2017, 60–75

Цитирование в формате AMSBIB
\RBibitem{MarTru17}
\by Е.~А.~Маркевич, А.~С.~Трушечкин
\paper Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера
\inbook Квантовые вычисления
\serial Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз.
\yr 2017
\vol 138
\pages 60--75
\publ ВИНИТИ РАН
\publaddr Москва
\mathnet{http://mi.mathnet.ru/into214}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3801251}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/into214
  • http://mi.mathnet.ru/rus/into/v138/p60

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры» Итоги науки и техники. Серия «Современная математика и ее приложения. Тематические обзоры»
    Просмотров:
    Эта страница:827
    Полный текст:103
    Первая стр.:38

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019