Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913393435213824 |
|---|---|
| author | Khadiev, Kamil Serov, Danil |
| author_facet | Khadiev, Kamil Serov, Danil |
| contents | 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 $Θ^*(\sqrt{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 $Θ^*(\sqrt{n})$. So, we obtain polynomial speed-up for both cases (general and property testing). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_11270 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language Khadiev, Kamil Serov, Danil Quantum Physics Computational Complexity Data Structures and Algorithms 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 $Θ^*(\sqrt{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 $Θ^*(\sqrt{n})$. So, we obtain polynomial speed-up for both cases (general and property testing). |
| title | Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.11270 |