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

В статье онлайн-алгоритмы представляются в качестве игры «запрос-ответ». Это игра двух игроков: алгоритма и противника. Противник, у которого хранятся входные данные, отдает их по частям, затем делает запрос, а алгоритм отвечает на него, отправляя выходные данные. Мы рассматриваем обобщенную модель, в которую добавлен буфер ограниченного размера. Противник загружает данные в буфер, а алгоритм считывает данные из буфера в произвольном порядке. В работе рассматриваются квантовые и классические (детерминированные и вероятностные) алгоритмы в рамках данной модели.
Специально была сконструирована задача, для которой квантовый алгоритм работает эффективнее, чем любой классический. Эффективность алгоритмов в работе рассматривается с точки зрения конкурентного соотношения. Заметим, что при рассмотрении классических алгоритмов стандартная модель онлайн-алгоритмов эквивалентна расширенной модели с буфером.