Quantum algorithm for Dyck Language with Multiple Types of Brackets

2021/06/17 by Kamil Khadiev, Khadiev, Kamil, Dmitry Kravchenko +1 · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Quantum Physics (quant-ph) #cs.CC #cs.FL #quant-ph

paper · pdf · doi:10.48550/arxiv.2106.09374

arxiv created 2021/06/17 · arxiv updated 2021/06/18

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)(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(√(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.

Cited by

• Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle

Related

• Quantum Query Complexity of Dyck Languages with Bounded Height
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
• Quantum Lower Bounds for 2D-Grid and Dyck Language
• Quantum Algorithm for the Multiple String Matching Problem
• A Quantum Query Complexity Trichotomy for Regular Languages