Quantum Request-Answer Game with Buffer Model for Online Algorithms

Abstract

We consider online algorithms as a request-answer game. An adversary that generates input requests, and an online algorithm answers. We consider a generalized version of the game that has a buffer of limited size. The adversary loads data to the buffer, and the algorithm has random access to elements of the buffer. We consider quantum and classical (deterministic or randomized) algorithms for the model. In the paper, we provide a specific problem (The Most Frequent Keyword Problem) and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm in terms of competitive ratio. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with buffer model.

More by Kamil Khadiev

• Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering PatharXiv · 2026
• Quantum k-means based on Quantum Local Sensitive Hashing with Application to Irrigation Machine Sensors Data ClusteringIEEE International Conference on Smart Computing Workshops and Other Affiliated Events · 2026
• Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity GrapharXiv · 2026
• Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs Based on 1-Cover PathInternational Conference on Quantum Communications, Networking, and Computing · 2026 · Citations: 1