KFU. Card publication. Quantum bounds for 2D-grid and Dyck language

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

QUANTUM BOUNDS FOR 2D-GRID AND DYCK LANGUAGE

Form of presentation

Articles in international journals and collections

Year of publication

2023

Язык

английский

Authors, employees of KFU

Khadiev Kamil Ravilevich, author

Bibliographic description in the original language

Ambainis, A., Balodis, K., Iraids, J., Khadiev, K., Kļevickis, V., Prūsis, K., Shen, Y., Smotrovs, J. and Vihrovs, J., Quantum bounds for 2D-grid and Dyck language//Quantum Information Processing. - 2023. - Vol.22, Is.5. - Art. №194.

Annotation

We study the quantum query complexity of two problems. First, we consider the problem of determining whether a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the DYCKk,n problem. We prove a lower bound of Ω(ckn) , showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n) query quantum algorithm was recently constructed by Aaronson et al. (Electron Colloquium Comput Complex (ECCC) 26:61, 2018). Their proof does not give rise to a general algorithm. When k is not a constant, DYCKk,n is not context-free. We give an algorithm with O(n(logn)0.5k) quantum queries for DYCKk,n for all k. This is better than the trivial upper bound n for k=o(log(n)loglogn) . Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the “balanced parentheses” problem into the grid, we show a lower bound of Ω (n1.5-ϵ) for the directed 2D grid and Ω (n2-ϵ) for the undirected 2D grid. We present two algorithms for particular cases of the problem. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

Keywords

quantum computing, dyck language, string processing

The name of the journal

Quantum Information Processing

URL

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85156269884&doi=10.1007%2fs11128-023-03910-9&partnerID=40&md5=a87d333eaf95368118123b062cb9ce97

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=281537&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Khadiev Kamil Ravilevich	ru_RU
dc.date.accessioned	2023-01-01T00:00:00Z	ru_RU
dc.date.available	2023-01-01T00:00:00Z	ru_RU
dc.date.issued	2023	ru_RU
dc.identifier.citation	Ambainis, A., Balodis, K., Iraids, J., Khadiev, K., Kļevickis, V., Prūsis, K., Shen, Y., Smotrovs, J. and Vihrovs, J., Quantum bounds for 2D-grid and Dyck language//Quantum Information Processing. - 2023. - Vol.22, Is.5. - Art. №194.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=281537&p_lang=2	ru_RU
dc.description.abstract	Quantum Information Processing	ru_RU
dc.description.abstract	We study the quantum query complexity of two problems. First, we consider the problem of determining whether a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the DYCKk,n problem. We prove a lower bound of Ω(ckn) , showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n) query quantum algorithm was recently constructed by Aaronson et al. (Electron Colloquium Comput Complex (ECCC) 26:61, 2018). Their proof does not give rise to a general algorithm. When k is not a constant, DYCKk,n is not context-free. We give an algorithm with O(n(logn)0.5k) quantum queries for DYCKk,n for all k. This is better than the trivial upper bound n for k=o(log(n)loglogn) . Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the “balanced parentheses” problem into the grid, we show a lower bound of Ω (n1.5-ϵ) for the directed 2D grid and Ω (n2-ϵ) for the undirected 2D grid. We present two algorithms for particular cases of the problem. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	quantum computing	ru_RU
dc.subject	dyck language	ru_RU
dc.subject	string processing	ru_RU
dc.title	Quantum bounds for 2D-grid and Dyck language	ru_RU
dc.type	Articles in international journals and collections	ru_RU