Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory

October 26, 2017 · The Ethereal · 🏛 arXiv.org

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Kamil Khadiev, Aliya Khadieva, Dmitry Kravchenko, Alexander Rivosh, Ramis Yamilov, Ilnaz Mannapov arXiv ID 1710.09595 Category cs.CC: Computational Complexity Cross-listed cs.DS, cs.FL, quant-ph Citations 6 Venue arXiv.org Last Checked 6 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity