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 (13)

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 the most frequently string search, intersection of two string sequences and sorting of strings problems ⋮ Quantum path parallelism: a circuit-based approach to text searching ⋮ 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

This page was built for publication: Quantum pattern matching fast on average