Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory

2017/10/26 by Kamil Khadiev, Aliya Khadieva, Khadiev, Kamil +9 · 1 citation
Computer Science · Decision Sciences · Physics and Astronomy · #Advanced Bandit Algorithms Research #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #cs.CC #cs.DS #cs.FL #quant-ph

paper · pdf · doi:10.48550/arxiv.1710.09595

arxiv created 2019/06/20 · arxiv updated 2019/06/21

Abstract

We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.

Cited by

• Quantum versus Classical Online Streaming Algorithms with Advice

Related

• Quantum versus Classical Online Streaming Algorithms with Advice
• Quantum Online Algorithms with Respect to Space Complexity
• Quantum Request-Answer Game with Buffer Model for Online Algorithms
• A Quantum Advantage for a Natural Streaming Problem
• How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing