Quantum algorithm for Dyck Language with Multiple Types of Brackets
Quantum algorithm for Dyck Language with Multiple Types of Brackets
复制标题
具有多种类型括号的 Dyck 语言的量子算法
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Dmitry Kravchenko
中科院分区：
文献类型：
--
作者：
K. Khadiev;Dmitry Kravchenko
We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity $O(sqrt{n}(log n)^{0.5k})$, where $n$ is the length of input and $k$ is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is $O(sqrt{n}c^{k})$ for some constant $c$. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ form the algorithm solving the original Dyck language. At the same time, quantum algorithms for solving both kinds of the Dyck language are of similar nature and requirements.
