КФУ. Карточка публикации. Quantum bounds for 2D-grid and Dyck language

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

QUANTUM BOUNDS FOR 2D-GRID AND DYCK LANGUAGE

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2023

Язык

английский

Авторы, сотрудники КФУ

Хадиев Камиль Равилевич, автор

Библиографическое описание на языке оригинала

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.

Аннотация

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.

Ключевые слова

quantum computing, dyck language, string processing

Название журнала

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

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=281537

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Хадиев Камиль Равилевич	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/?p_id=281537	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	Статьи в зарубежных журналах и сборниках	ru_RU