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

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

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


Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки:
Год:
Том:
Выпуск:
Страница:
Найти




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

Ученые записки Казанского университета. Серия Физико-математические науки, 2020, том 162, книга 3, страницы 367–382
DOI: https://doi.org/10.26907/2541-7746.2020.3.367-382 (Mi uzku1568) 		 
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером

К. Р. Хадиевab, Д. И. Линbc

a ООО «Квантовые интеллектуальные технологии», г. Казань, 420111, Россия
b Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
c Компания АО «Барс Груп», г. Казань, 420012, Россия
PDF полного текста (766 kB) Список цитирования (4)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.26907/2541-7746.2020.3.367-382
Аннотация: В статье онлайн-алгоритмы представляются в качестве игры «запрос-ответ». Это игра двух игроков: алгоритма и противника. Противник, у которого хранятся входные данные, отдает их по частям, затем делает запрос, а алгоритм отвечает на него, отправляя выходные данные. Мы рассматриваем обобщенную модель, в которую добавлен буфер ограниченного размера. Противник загружает данные в буфер, а алгоритм считывает данные из буфера в произвольном порядке. В работе рассматриваются квантовые и классические (детерминированные и вероятностные) алгоритмы в рамках данной модели.
Специально была сконструирована задача, для которой квантовый алгоритм работает эффективнее, чем любой классический. Эффективность алгоритмов в работе рассматривается с точки зрения конкурентного соотношения. Заметим, что при рассмотрении классических алгоритмов стандартная модель онлайн-алгоритмов эквивалентна расширенной модели с буфером.
Ключевые слова: квантовые вычисления, онлайн-алгоритмы, игра запрос-ответ, задача онлайн-минимизации, вычисления с буфером.
Финансовая поддержка Номер гранта
Российский научный фонд 19-71-00149
Исследование выполнено за счет гранта Российского научного фонда (проект № 19-71-00149).
Поступила в редакцию: 04.08.2020
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.712.3
Образец цитирования: К. Р. Хадиев, Д. И. Лин, “Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 367–382
Цитирование в формате AMSBIB
\RBibitem{KhaLin20}
\by К.~Р.~Хадиев, Д.~И.~Лин
\paper Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером
\serial Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки
\yr 2020
\vol 162
\issue 3
\pages 367--382
\publ Изд-во Казанского ун-та
\publaddr Казань
\mathnet{http://mi.mathnet.ru/uzku1568}
\crossref{https://doi.org/10.26907/2541-7746.2020.3.367-382}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/uzku1568
  • https://www.mathnet.ru/rus/uzku/v162/i3/p367
    • Эта публикация цитируется в следующих 4 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Ученые записки Казанского университета. Серия Физико-математические науки
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025