Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.02421 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917828687298560 |
|---|---|
| author | Lee, Tzu-Ching Lin, Han-Hsuan |
| author_facet | Lee, Tzu-Ching Lin, Han-Hsuan |
| contents | We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given.
Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tildeΩ(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS.
We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $Ω(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.
With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02421 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings Lee, Tzu-Ching Lin, Han-Hsuan Quantum Physics We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tildeΩ(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $Ω(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string. |
| title | Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.02421 |