|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером
К. Р. Хадиевab, Д. И. Линbc a ООО «Квантовые интеллектуальные технологии», г. Казань, 420111, Россия
b Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
c Компания АО «Барс Груп», г. Казань, 420012, Россия
Аннотация:
В статье онлайн-алгоритмы представляются в качестве игры «запрос-ответ». Это игра двух игроков: алгоритма и противника. Противник, у которого хранятся входные данные, отдает их по частям, затем делает запрос, а алгоритм отвечает на него, отправляя выходные данные. Мы рассматриваем обобщенную модель, в которую добавлен буфер ограниченного размера. Противник загружает данные в буфер, а алгоритм считывает данные из буфера в произвольном порядке. В работе рассматриваются квантовые и классические (детерминированные и вероятностные) алгоритмы в рамках данной модели.
Специально была сконструирована задача, для которой квантовый алгоритм работает эффективнее, чем любой классический. Эффективность алгоритмов в работе рассматривается с точки зрения конкурентного соотношения. Заметим, что при рассмотрении классических алгоритмов стандартная модель онлайн-алгоритмов эквивалентна расширенной модели с буфером.
Ключевые слова:
квантовые вычисления, онлайн-алгоритмы, игра запрос-ответ, задача онлайн-минимизации, вычисления с буфером.
Поступила в редакцию: 04.08.2020
Образец цитирования:
К. Р. Хадиев, Д. И. Лин, “Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 162, № 3, Изд-во Казанского ун-та, Казань, 2020, 367–382
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzku1568 https://www.mathnet.ru/rus/uzku/v162/i3/p367
|
Статистика просмотров: |
Страница аннотации: | 188 | PDF полного текста: | 117 | Список литературы: | 10 |
|