Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language

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}{\varepsilon }n^{1/3}\log n)\) , where n is the length of an input. It is better than the classical complexity that is \(\varTheta ^*(\sqrt{n})\) . At the same time, in the general setting, the picture is different a little. Classical query complexity is \(\varTheta (n)\) , and quantum query complexity is \(\varTheta ^*(\sqrt{n})\) . So, we obtain polynomial speed-up for both cases (general and property testing).