Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Circuit Design Gate Engineering Quantum Simulation Quantum Machine Learning Entanglement Theory Quantum Correlations

A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

arXiv
Authors: Tzu-Ching Lee, Han-Hsuan Lin

Year

2023

Paper ID

54236

Status

Preprint

Abstract Read

~2 min

Abstract Words

101

Citations

N/A

Abstract

We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs {O}\(n5/6\)cdot O\(polylog({n}\)) time, where n and {n} are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a Ω\(n/log2n\) lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of mathsf{PARITY} to the problem.

Why This Paper Matters

  • This paper contributes to the Quantum Machine Learning research area in the Quantum Articles archive.
  • It adds a 2023 reference point for readers tracking recent quantum research.
  • We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the...

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:2310.00966 [2] arXiv https://arxiv.org/abs/2310.00966 [3] Publisher https://arxiv.org/abs/2310.00966

Local Citation Graph (Related-Paper Links)

Current Paper #54236 #69593 Local correlations in long-rang... #69591 Compact graphs and quantum auto... #69577 Real-time pseudo entropy and mo... #69569 Spin disorder competing with po...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.