String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time

DOI10.1016/S1570-8667(03)00010-8zbMath1119.81317arXivquant-ph/0011049MaRDI QIDQ876699

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)

Related Items (12)

Classical and quantum algorithms for constructing text from dictionary problem ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ Classical and Quantum Algorithms for Assembling a Text from a Dictionary ⋮ QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer ⋮ Quantum string matching unfolded and extended ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum algorithms for learning hidden strings with applications to matroid problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Quantum pattern matching fast on average ⋮ Quantum algorithms for string processing ⋮ Quantum algorithm for learning secret strings and its experimental demonstration

Cites Work

• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Unnamed Item

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