Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
<|reference_start|>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 $\Theta^*(\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^*(\sqrt{n})$. So, we obtain polynomial speed-up for both cases (general and property testing).<|reference_end|>
@article{khadiev2024quantum,
    title={Quantum Property Testing Algorithm for the Concatenation of Two
  Palindromes Language},
    author={Kamil Khadiev and Danil Serov},
    journal={LNCS, Vol. 14776, 2024},
    year={2024},
    doi={10.1007/978-3-031-63742-1_10},
    archivePrefix={arXiv},
    eprint={2406.11270},
    primaryClass={quant-ph cs.CC cs.DS}
}