String matching in O( n+ m) quantum time

DOI10.1016/S1570-8667(03)00010-8zbMATH Open1119.81317MaRDI QIDQ876699FDOQ876699

Authors H. Ramesh, V. Vinay 

Publication date 26 April 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0011049

zbMATH Keywords

algorithmquantum computingstring matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Abstract: We show how to determine whether a given pattern p of length m occurs in a given text t of length n in $ildeO(sqrtn+sqrtm)$footnote{$ildeO$ 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}.

Recommendations

• Quantum pattern matching fast on average
• Quantum pattern search with closed match
• Reconstructing strings from substrings with quantum queries
• Constant-Time Randomized Parallel String Matching
• Faster Parallel String Matching via Larger Deterministic Samples

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Deterministic Sampling–A New Technique for Fast Pattern Matching

Cited in

(18)

• Internal pattern matching queries in a text and applications
• Quantum string matching unfolded and extended
• Reconstructing strings from substrings with quantum queries
• Quantum algorithm for lexicographically minimal string rotation
• QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer
• Quantum pattern search with closed match
• Quantum algorithm for learning secret strings and its experimental demonstration
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Quantum speed-ups for string synchronizing sets, longest common substring, and \(k\)-mismatch matching
• Classical and quantum algorithms for constructing text from dictionary problem
• Quantum path parallelism: a circuit-based approach to text searching
• Quantum algorithms for learning hidden strings with applications to matroid problems
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Near-optimal quantum algorithms for string problems
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• Quantum pattern matching fast on average
• Classical and Quantum Algorithms for Assembling a Text from a Dictionary
• Quantum algorithms for string processing

This page was built for publication: String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876699)