← Back to papers
Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
K. Khadiev, Artem Ilikaev·December 9, 2019·DOI: 10.1007/978-3-030-34500-6_17
MathematicsComputer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The problem is the following. Assume that we have a sequence of n strings of length k. The problem is finding the string that occurs in the sequence most often. We propose a quantum algorithm that has a query complexity \(\tilde{O}(n \sqrt{k})\). This algorithm shows speed-up comparing with the deterministic algorithm that requires \(\varOmega (nk)\) queries.