String Matching in ${\tilde O}(\sqrt{n}+\sqrt{m})$ Quantum Time

H. Ramesh; V. Vinay

paper

String Matching in $O ~ (n + m)$ Quantum Time

arXiv:quant-ph/0011049

Abstract

We show how to determine whether a given pattern p of length m occurs in a given text t of length n in $O ~ (n + m)$ \footnote{ $O ~$ allows for logarithmic factors in m and $n / m$ } time, with inverse polynomial failure probability. This algorithm combines quantum searching algorithms with a technique from parallel string matching, called {\em Deterministic Sampling}.

7 pages Latex2e file

String Matching in O~(n​+m​) Quantum Time

Abstract

String Matching in $O ~ (n + m)$ Quantum Time