Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language

Abstract

In this paper, we present a quantum property testing algorithm for recognizing a context-free language that is a concatenation of two palindromes $L_{REV}$. The query complexity of our algorithm is $O(\frac{1}{\epsilon }{n}^{1/3}\log n)$, where $n$ is the length of an input. It is better than the classical complexity that is ${\Theta }^{\ast }(\sqrt{n})$. At the same time, in the general setting, the picture is different a little. Classical query complexity is $\Theta (n)$, and quantum query complexity is ${\Theta }^{\ast }(\sqrt{n})$. So, we obtain polynomial speed-up for both cases (general and property testing).

Proceedings of UCNC 2024

References in corpus (2)

• Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language