String matching in O( n+ m) quantum time

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

H. Ramesh, V. Vinay

Publication date: 26 April 2007

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

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}.

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)

Cites Work

• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Title not available (Why is that?)

Cited In (15)

• Quantum algorithm for learning secret strings and its experimental demonstration
• 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
• 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 path parallelism: a circuit-based approach to text searching
• 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 algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum algorithms for string processing

   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 👍 👎

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)