Quantum pattern matching fast on average

DOI10.1007/s00453-015-0060-4zbMath1359.68093arXiv1408.1816OpenAlexW2118172634MaRDI QIDQ513289

Ashley Montanaro

Publication date: 6 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.1816

zbMATH Keywords

quantum algorithmspattern matchingaverage-case complexityquantum query complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Quantum walk and its application domains: a systematic review, Classical and quantum algorithms for constructing text from dictionary problem, Classical and Quantum Algorithms for Assembling a Text from a Dictionary, 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, T-count optimized Wallace tree integer multiplier for quantum computing, Quantum algorithms for string processing, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, Quantum algorithm for learning secret strings and its experimental demonstration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
• Sublinear approximate string matching and biological applications
• The quantum query complexity of the hidden subgroup problem is polynomial
• A hidden shift quantum algorithm
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Quantum Algorithm for the Boolean Hidden Shift Problem
• A fast string searching algorithm
• Quantum Random Access Memory
• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Quantum Algorithms for Some Hidden Shift Problems
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• A sublinear algorithm for weakly approximating edit distance
• Hidden translation and orbit coset in quantum computing
• The Complexity of Pattern Matching for a Random String
• Fast Pattern Matching in Strings
• Strengths and Weaknesses of Quantum Computing
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• Algorithms on Strings
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Shift Finding in Sub-linear Time
• Quantum rejection sampling
• Quantum lower bounds by quantum arguments