Quantum Algorithm for Dyck Language with Multiple Types of Brackets

Kamil Khadiev; Dmitry Kravchenko

Quantum Algorithm for Dyck Language with Multiple Types of Brackets

Kamil Khadiev
, Dmitry Kravchenko

Kazan Volga Region Federal University

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

8 Citations (Scopus)

Abstract

We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity O(n(logn)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 Ω(nck) for some constant c. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ from 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.

Original language	English
Title of host publication	Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings
Place of Publication	Cham
Publisher	Springer
Pages	68-83
Number of pages	16
Volume	12984 LNCS
ISBN (Print)	9783030879921
Publication status	Published - 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12984 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Dyck language
Quantum algorithms
Query complexity
Regular language
Strings

OECD Field of Science

1.2 Computer and Information Sciences

Cite this

Khadiev, K., & Kravchenko, D. (2021). Quantum Algorithm for Dyck Language with Multiple Types of Brackets. In Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings (Vol. 12984 LNCS, pp. 68-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12984 LNCS). Springer.

Khadiev, Kamil ; Kravchenko, Dmitry. / Quantum Algorithm for Dyck Language with Multiple Types of Brackets. Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings. Vol. 12984 LNCS Cham : Springer, 2021. pp. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c98f8b1fd2c24e9895bd51ab50f8f89e,

title = "Quantum Algorithm for Dyck Language with Multiple Types of Brackets",

abstract = "We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity O(n(logn)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 Ω(nck) for some constant c. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ from 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.",

keywords = "Dyck language, Quantum algorithms, Query complexity, Regular language, Strings",

author = "Kamil Khadiev and Dmitry Kravchenko",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",

year = "2021",

language = "English",

isbn = "9783030879921",

volume = "12984 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "68--83",

booktitle = "Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings",

address = "Germany",

}

Khadiev, K & Kravchenko, D 2021, Quantum Algorithm for Dyck Language with Multiple Types of Brackets. in Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings. vol. 12984 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12984 LNCS, Springer, Cham, pp. 68-83.

Quantum Algorithm for Dyck Language with Multiple Types of Brackets. / Khadiev, Kamil; Kravchenko, Dmitry.
Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings. Vol. 12984 LNCS Cham: Springer, 2021. p. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12984 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Quantum Algorithm for Dyck Language with Multiple Types of Brackets

AU - Khadiev, Kamil

AU - Kravchenko, Dmitry

PY - 2021

Y1 - 2021

N2 - We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity O(n(logn)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 Ω(nck) for some constant c. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ from 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.

AB - We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity O(n(logn)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 Ω(nck) for some constant c. Interestingly, classical algorithms solving the Dyck Language for multiple types of brackets substantially differ from 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.

KW - Dyck language

KW - Quantum algorithms

KW - Query complexity

KW - Regular language

KW - Strings

UR - https://link.springer.com/chapter/10.1007%252F978-3-030-87993-8_5

UR - https://www.scopus.com/pages/publications/85118138455

M3 - Conference paper

SN - 9783030879921

VL - 12984 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 68

EP - 83

BT - Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings

PB - Springer

CY - Cham

ER -

Khadiev K, Kravchenko D. Quantum Algorithm for Dyck Language with Multiple Types of Brackets. In Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings. Vol. 12984 LNCS. Cham: Springer. 2021. p. 68-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Quantum Algorithm for Dyck Language with Multiple Types of Brackets

Abstract

Publication series

Keywords

OECD Field of Science

Other files and links

Fingerprint

Cite this