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