Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

• URL: http://arxiv.org/abs/2410.06808v1
• Date: Wed, 9 Oct 2024 12:05:26 GMT
• Title: Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
• Authors: Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz,
• Abstract summary: We consider the two most common distances: Hamming distance in Pattern Matching with Mismatches and edit distance in Pattern Matching with Edits. We present quantum algorithms with a time complexity of $tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatches and $hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Edits.
• Score: 2.4167127333650202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to identify the fragments of $T$ that are at distance at most $k$ to $P$. We consider the two most common distances: Hamming distance (the number of character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting. Our recent work [STOC'24] shows that $\hat{O}(\sqrt{nk})$ quantum queries are sufficient to solve (the decision version of) Pattern Matching with Edits. However, the quantum time complexity of the underlying solution does not provide any improvement over classical computation. On the other hand, the state-of-the-art algorithm for Pattern Matching with Mismatches [Jin and Nogler; SODA'23] achieves query complexity $\hat{O}(\sqrt{nk^{3/2}})$ and time complexity $\tilde{O}(\sqrt{nk^2})$, falling short of an unconditional lower bound of $\Omega(\sqrt{nk})$ queries. In this work, we present quantum algorithms with a time complexity of $\tilde{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^2)$ for Pattern Matching with Mismatches and $\hat{O}(\sqrt{nk}+\sqrt{n/m}\cdot k^{3.5})$ for Pattern Matching with Edits; both solutions use $\hat{O}(\sqrt{nk})$ queries. The running times are near-optimal for $k\ll m^{1/3}$ and $k\ll m^{1/6}$, respectively, and offer advantage over classical algorithms for $k\ll (mn)^{1/4}$ and $k\ll (mn)^{1/7}$, respectively. Our solutions can also report the starting positions of approximate occurrences of $P$ in $T$ (represented as collections of arithmetic progressions); in this case, the unconditional lower bound and the complexities of our algorithms increase by a $\Theta(\sqrt{n/m})$ factor.

Related papers

• On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
  We prove an upper bound of $O(n/m cdot k log2 m)$ bits, thus establishing the optimal communication complexity up to logarithmic factors. We also show that $O(n/m cdot k log2 m)$ bits allow encoding, for each $k$-error occurrence of $P$ in $T$, the shortest sequence of edits needed to make the occurrence exact.
  arXiv  Detail & Related papers  (2024-03-27T17:57:16Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• 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)
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
  We consider online algorithms for the $k$-server problem on trees. Chrobak and Larmore proposed a $k$-competitive algorithm for this problem that has the optimal competitive ratio. We propose a new time-efficient implementation of this algorithm that has $O(nlog n)$ time complexity for preprocessing.
  arXiv  Detail & Related papers  (2020-08-01T14:21:45Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• 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.