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

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

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


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




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

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

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

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

a Национальный исследовательский ядерный университет "МИФИ", г. Москва
b Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
c Национальный исследовательский технологический университет "МИСиС"
PDF полного текста (261 kB) Список цитирования (3)
Аннотация: Предложен квантовый алгоритм ветвей и границ на основе сочетания общей схемы метода ветвей и границ с квантовым алгоритмом вложенного поиска. Исследуется его вычислительная эффективность в сравнении с аналогичным классическим алгоритмом на примере задачи коммивояжера. Показывается, что в подавляющем большинстве задач классический алгоритм превосходит по скорости квантовый за счет большей адаптивности. Тем не менее, время работы квантового алгоритма постоянно для всех задач, тогда как классический алгоритм на некоторых задачах работает очень медленно. В результате для наихудшего случая квантовый алгоритм ветвей и границ оказался в несколько раз эффективнее классического алгоритма.
Ключевые слова: квантовые вычисления, квантовый компьютер, квантовый поиск, алгоритм Гровера, метод ветвей и границ, задача коммивояжера.
Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации МК-2815.2017.1
Исследование выполнено при поддержке гранта Президента Российской Федерации (проект МК-2815.2017.1).
Англоязычная версия:
Journal of Mathematical Sciences, 2019, Volume 241, Issue 2, Pages 168–184
DOI: https://doi.org/10.1007/s10958-019-04415-6
Реферативные базы данных:
Тип публикации: Статья
УДК: 517.958:530.145, 519.85
MSC: 81P68, 68Q12
Образец цитирования: Е. А. Маркевич, А. С. Трушечкин, “Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера”, Квантовые вычисления, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 138, ВИНИТИ РАН, Москва, 2017, 60–75; Journal of Mathematical Sciences, 241:2 (2019), 168–184
Цитирование в формате AMSBIB
\RBibitem{MarTru17}
\by Е.~А.~Маркевич, А.~С.~Трушечкин
\paper Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера
\inbook Квантовые вычисления
\serial Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз.
\yr 2017
\vol 138
\pages 60--75
\publ ВИНИТИ РАН
\publaddr Москва
\mathnet{http://mi.mathnet.ru/into214}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3801251}
\zmath{https://zbmath.org/?q=an:07123790}
\transl
\jour Journal of Mathematical Sciences
\yr 2019
\vol 241
\issue 2
\pages 168--184
\crossref{https://doi.org/10.1007/s10958-019-04415-6}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/into214
  • https://www.mathnet.ru/rus/into/v138/p60
    • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024