Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings

• URL: http://arxiv.org/abs/2411.02421v1
• Date: Mon, 21 Oct 2024 15:52:08 GMT
• Title: Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings
• Authors: Tzu-Ching Lee, Han-Hsuan Lin,
• Abstract summary: We give a near-optimal quantum algorithm for the longest common (LCS) problem between two run-length encoded (RLE) strings. Our algorithm costs $tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ time, while the query lower bound for the problem is $tildeOmega(n2/3/d1/6)$.
• Score: 0.8057006406834466
• License:
• Abstract: 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{\Omega}(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 $\Omega(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.

Related papers

• Quantum Algorithm for the Multiple String Matching Problem [0.0]
  We consider a sequence of $m$ strings, denoted by $S$, which we refer to as a dictionary. The objective is to identify all instances of strings from the dictionary within the text. We propose a quantum algorithm with $O(n+sqrtmLlog nlog n)$ query complexity and $O(n+sqrtmLlog n)=O*(n+sqrtmL)$ time complexity.
  arXiv  Detail & Related papers  (2024-11-22T10:50:43Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings [0.951828574518325]
  We give a sublinear quantum algorithm for the longest common (LCS) problem on the run-length encoded (RLE) inputs. Our algorithm costs $tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ time, where $n$ and $tilden$ are the encoded and decoded length of the inputs, respectively.
  arXiv  Detail & Related papers  (2023-10-02T08:14:34Z)
• Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
  The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science. We present a quantum algorithm for both LCS and LPS working in the circuit model of computation.
  arXiv  Detail & Related papers  (2023-09-03T19:27:57Z)
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems [11.048346250166073]
  We consider two versions of the Text Assembling problem. We are given a sequence of strings $s1,dots,sn$ of total length $L$ that is a dictionary, and a string $t$ of length $m$ that is texts. For both problems, we suggest new quantum algorithms that work better than their classical counterparts.
  arXiv  Detail & Related papers  (2023-06-18T14:16:49Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  We study algorithms for solving the problem of constructing a text from a dictionary (sequence of small strings) The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments.
  arXiv  Detail & Related papers  (2020-05-28T22:44:01Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.