String matching in O( n+ m) quantum time

DOI10.1016/S1570-8667(03)00010-8MaRDI QIDQ876699zbMATH OpenFDO

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

(26)

• Quantum pattern search with closed match
• Reconstructing strings from substrings with quantum queries
• Quantum algorithm for learning secret strings and its experimental demonstration
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Quantum string matching unfolded and extended
• Quantum algorithm for lexicographically minimal string rotation
• Classical and quantum algorithms for constructing text from dictionary problem
• Classical and Quantum Algorithms for Assembling a Text from a Dictionary
• Quantum property testing algorithm for the concatenation of two palindromes language
• A note on quantum divide and conquer for minimal string rotation
• Computing string covers in sublinear time
• Internal pattern matching queries in a text and applications
• Near-optimal quantum algorithms for string problems
• Quantum algorithms for learning hidden strings with applications to matroid problems
• Quantum algorithms for longest common and palindromic substrings in the circuit model
• Quantum path parallelism: a circuit-based approach to text searching
• Double-ended palindromic trees in linear time
• A general quantum circuit for string matching: unleashing quantum path parallelism
• Approximate circular pattern matching under edit distance
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer
• Quantum pattern matching fast on average
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• 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
• 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)