15 citations · 38 across the 21 of their papers we have counts for
4 papers · 1 filter
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +6
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a d…
Classical and Quantum Algorithms for Constructing Text from Dictionary Problem
Kamil Khadiev, Vladislav Remidovskii
We study algorithms for solving the problem of constructing a text (long string) from a dictionary (sequence of small strings). The problem has an application in bioinformatics and…
Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
Kamil Khadiev, Liliya Safina
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}…
Quantum versus Classical Online Streaming Algorithms with Advice
Kamil Khadiev, Aliya Khadieva, Mansur Ziatdinov +4
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 algorit…