Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1408.1816

Quantum pattern matching fast on average

Ashley Montanaro

Published Aug 8, 2014• 1 citation
arXivHTMLPDF

Abstract

The $d$-dimensional pattern matching problem is to find an occurrence of a pattern of length $m \times \dots \times m$ within a text of length $n \times \dots \times n$, with $n \ge m$. 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 $\widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2}\sqrt{\log m})})$. For large $m$ this is super-polynomially faster than the best possible classical algorithm, which requires time $\widetildeΩ( (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.

DOI
10.48550/arxiv.1408.1816

Related papers

Simple Quantum Algorithm for Approximate kkk-Mismatch Problem

Ruhan Habib, Shahriar, Shadman

In the $k$-mismatch problem, given a pattern and a text of length $n$ and $m$ respectively, we have to find if the text has a sub-string with a Hamming distance of at most $k$ from the pattern. This has been studied in the classical setting since 1982 and recently in the quantum computational setting by Jin and Nogler and Kociumaka, Nogler, and Wellnitz. We provide a simple quantum algorithm that solves the problem in an approximate manner, given a parameter $ε\in (0, 1]$. It returns an occurrence as a match only if it is a $\left(1+ε\right)k$-mismatch. If it does not return any occurrence, then there is no $k$-mismatch. This algorithm has a time (size) complexity of $\tilde{O}\left( ε^{-1} \sqrt{\frac{mn}{k}} \right)$.

arXiv:2510.02399•Oct 1, 2025•0 citations

Classical Equivalent Quantum Based Pattern Matching Algorithms

Kapil Kumar Soni, Akhtar Rasool

The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•0 citations

A quantum algorithm for string matching

Pradeep Niroula, Yunseong Nam

Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N . Our algorithm has a time complexity of $$\tilde{O}(\sqrt{N})$$ O ̃ ( N ) , while the space complexity remains modest at O ( N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.

npj Quantum Information•Feb 16, 2021•42 citations

Quantum Pattern Matching in Generalised Degenerate Strings

Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in $O(mn+N)$ time (Ascone et al., WABI 2024), where $m$ is the pattern length, $n$ is the number of strings and $N$ the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time $\tilde{O}(\sqrt{mnN})$, thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.

quant-pharXiv:2603.16297•Mar 18, 2026•0 citations

Quantum Pattern Matching with Wildcards

Masoud Seddighin, Saeed Seddighin

Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time $\tilde O(n)$ using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time $\tilde O(\sqrt{n}\sqrt{k})$ when the number of wildcards is bounded by $k$ for $k \geq \sqrt{n}$. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.

arXiv:2507.13885•Jul 18, 2025•0 citations

Analysis of Quantum Pattern Matching for Generalized Degenerate Strings

Md Rabiul Islam Khan

This work presents a comprehensive analysis of quantum algorithms for the Generalized Degenerate String Matching (SMGD) problem, which involves finding occurrences of a pattern P of length m in a generalized degenerate text \(\mathcal{T}\) consisting of n sets containing s strings of total length N. The proposed work first explores an algorithm combining existing approaches such as the Aho-Corasick automaton and quantum techniques like Grover search to achieve a query complexity of \(O(m + N + m\sqrt{sHn})\), where H is the maximum number of strings in any set of \(\mathcal{T}\). To demonstrate a definitive quantum advantage over the state-of-the-art classical algorithm which has a running time of O(mn + N) (Ascone et al., WABI 2024), this work extends to a strategy based on alignment-shift that fully exploits the quantum model of computation by simulating parallel shifts. This algorithm achieves a running time of \(\tilde{O}(\sqrt{mnN})\), which represents a sub-linear query complexity and establishes a potential theoretical quantum speed-up for generalized degenerate strings.

Työväentutkimus Vuosikirja•May 20, 2026•0 citations
The ddd-dimensional pattern matching problem is to find an occurrence of a pattern of length m×⋯×mm \times \dots \times mm×⋯×m within a text of length n×⋯×nn \times \dots \times nn×⋯×n, with n≥mn \ge mn≥m. 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 O~((n/m)d/22O(d3/2log⁡m))\widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2}\sqrt{\log m})})O((n/m)d/22O(d3/2logm​)). For large mmm this is super-polynomially faster than the best possible classical algorithm, which requires time Ω~((n/m)d+nd/2)\widetildeΩ( (n/m)^d + n^{d/2} )Ω((n/m)d+nd/2). The algorithm is based on the use of a quantum subroutine for finding hidden shifts in ddd dimensions, which is a variant of algorithms proposed by Kuperberg.
In the kkk-mismatch problem, given a pattern and a text of length nnn and mmm respectively, we have to find if the text has a sub-string with a Hamming distance of at most kkk from the pattern. This has been studied in the classical setting since 1982 and recently in the quantum computational setting by Jin and Nogler and Kociumaka, Nogler, and Wellnitz. We provide a simple quantum algorithm that solves the problem in an approximate manner, given a parameter ε∈(0,1]ε\in (0, 1]ε∈(0,1]. It returns an occurrence as a match only if it is a (1+ε)k\left(1+ε\right)k(1+ε)k-mismatch. If it does not return any occurrence, then there is no kkk-mismatch. This algorithm has a time (size) complexity of O~(ε−1mnk)\tilde{O}\left( ε^{-1} \sqrt{\frac{mn}{k}} \right)O~(ε−1kmn​​).
The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.
Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N . Our algorithm has a time complexity of O~(N)\tilde{O}(\sqrt{N})O~(N​) O ̃ ( N ) , while the space complexity remains modest at O ( N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in O(mn+N)O(mn+N)O(mn+N) time (Ascone et al., WABI 2024), where mmm is the pattern length, nnn is the number of strings and NNN the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time O~(mnN)\tilde{O}(\sqrt{mnN})O~(mnN​), thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.
Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time O~(n)\tilde O(n)O~(n) using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time O~(nk)\tilde O(\sqrt{n}\sqrt{k})O~(n​k​) when the number of wildcards is bounded by kkk for k≥nk \geq \sqrt{n}k≥n​. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.
This work presents a comprehensive analysis of quantum algorithms for the Generalized Degenerate String Matching (SMGD) problem, which involves finding occurrences of a pattern P of length m in a generalized degenerate text T\mathcal{T}T consisting of n sets containing s strings of total length N. The proposed work first explores an algorithm combining existing approaches such as the Aho-Corasick automaton and quantum techniques like Grover search to achieve a query complexity of O(m+N+msHn)O(m + N + m\sqrt{sHn})O(m+N+msHn​), where H is the maximum number of strings in any set of T\mathcal{T}T. To demonstrate a definitive quantum advantage over the state-of-the-art classical algorithm which has a running time of O(mn + N) (Ascone et al., WABI 2024), this work extends to a strategy based on alignment-shift that fully exploits the quantum model of computation by simulating parallel shifts. This algorithm achieves a running time of O~(mnN)\tilde{O}(\sqrt{mnN})O~(mnN​), which represents a sub-linear query complexity and establishes a potential theoretical quantum speed-up for generalized degenerate strings.