Quantum pattern matching fast on average

DOI10.1007/S00453-015-0060-4MaRDI QIDQ513289zbMATH OpenOpenAlexFDO

Authors 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

pattern matchingquantum algorithmsquantum query complexityaverage-case complexity

Mathematics Subject Classification ID

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

Abstract: The $d$-dimensional pattern matching problem is to find an occurrence of a pattern of length $mimesdotsimesm$ within a text of length $nimesdotsimesn$, with $ngem$. This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time $widetildeO((n/m{)}^{d/2}{2}^{O(d^{3/2}sqrtlogm)})$. For large $m$ this is super-polynomially faster than the best possible classical algorithm, which requires time $widetildeOmega((n/m{)}^d+n^{d/2})$. The algorithm is based on the use of a quantum subroutine for finding hidden shifts in $d$ dimensions, which is a variant of algorithms proposed by Kuperberg.

Recommendations

• String matching in O( n+ m) quantum time
• Quantum pattern search with closed match
• Quantum algorithm for a generalized hidden shift problem
• A panoply of quantum algorithms
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Cites work

• scientific article; zbMATH DE number 6679846 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 6297720 (Why is no real title available?)
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• A fast string searching algorithm
• A hidden shift quantum algorithm
• A sublinear algorithm for weakly approximating edit distance
• Algorithms on Strings
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Fast Pattern Matching in Strings
• Hidden translation and orbit coset in quantum computing
• Quantum Algorithm for the Boolean Hidden Shift Problem
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• Quantum algorithm for a generalized hidden shift problem
• Quantum lower bounds by quantum arguments
• Quantum random access memory
• Shift finding in sub-linear time
• Strengths and Weaknesses of Quantum Computing
• String matching in O( n+ m) quantum time
• Sublinear approximate string matching and biological applications
• The Complexity of Pattern Matching for a Random String
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• The quantum query complexity of the hidden subgroup problem is polynomial
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time

Cited in

(20)

• Quantum pattern search with closed match
• T-count optimized Wallace tree integer multiplier for quantum computing
• Quantum algorithm for learning secret strings and its experimental demonstration
• Quantum walk and its application domains: a systematic review
• 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
• Quantum property testing algorithm for the concatenation of two palindromes language
• A note on quantum divide and conquer for minimal string rotation
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Near-optimal quantum algorithms for string problems
• Quantum algorithms for learning hidden strings with applications to matroid problems
• Quantum algorithms for longest common and palindromic substrings in the circuit model
• Quantum path parallelism: a circuit-based approach to text searching
• Double-ended palindromic trees in linear time
• Quantum pattern recognition with probability of 100\%
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• String matching in O( n+ m) quantum time
• Quantum algorithms for string processing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513289)