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:2203.00164

Quantum jumbled pattern matching

Julio Juárez-Xochitemol, Edgar Chávez

Published Mar 1, 2022• 2 citations
arXivHTMLPDF

Abstract

Let $S_1, S_2 \in Σ^*$ strings, we say that $S_1$ {\em jumble match} $S_2$ if they are permutations of each other. Given a text $T$ of size $N$ and a string $S \in Σ^*$, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in $T$ jumbled matching $S$. In classical computing, a widespread conjecture is that JPM requires $Ω(N^{2-ε})$ preprocessing time and space for $O(1)$ query time, or $Ω(N^{1-δ})$ query time in the online version, with $ε, δ>0$. In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.

DOI
10.48550/arxiv.2203.00164

Related papers

Quantum Pattern Matching

Paulo Mateus, Yasser Omar

We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods, which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern of size $M$ with non-negligible probability in $O(\sqrt{N})$ queries, where $N$ is the size of the string. Furthermore, we give the full recipe to implement our algorithm (together with its total circuit complexity), thus offering an oracle-based quantum algorithm ready to be implemented.

arXiv:quant-ph/0508237•Aug 31, 2005•17 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

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

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•44 citations

Quantum algorithms for SCS and text assembling problems

Kamil Ravilevich Khadiev, Carlos Manuel Bosch Machado, Zeyu Chen +1 more

In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings $s^1,\dots,s^n$ of total length $L$ that is a dictionary, and a string $t$ of length $m$ that is a text. The first version of the problem is assembling $t$ from the dictionary. The second version is the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). In this case, $t$ is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring.These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with $O(m+\log m\sqrt{nL})$ query complexity. In the case of SSP, we present a quantum algorithm with $\tilde{O}(n^3 1.728^n +L +n^{1.5}\sqrt{L})$ query complexity. Here $\tilde{O}$ hides not only constants but logarithms of $L$ and $n$ also.

arXiv:2306.10572•Quantum Information and Computation•Mar 1, 2024•2 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
Let S1,S2∈Σ∗S_1, S_2 \in Σ^*S1​,S2​∈Σ∗ strings, we say that S1S_1S1​ {\em jumble match} S2S_2S2​ if they are permutations of each other. Given a text TTT of size NNN and a string S∈Σ∗S \in Σ^*S∈Σ∗, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in TTT jumbled matching SSS. In classical computing, a widespread conjecture is that JPM requires Ω(N2−ε)Ω(N^{2-ε})Ω(N2−ε) preprocessing time and space for O(1)O(1)O(1) query time, or Ω(N1−δ)Ω(N^{1-δ})Ω(N1−δ) query time in the online version, with ε,δ>0ε, δ>0ε,δ>0. In this paper, we present a quantum algorithm for the online JPM in O(N)O(\sqrt{N})O(N​) time.
We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods, which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern of size MMM with non-negligible probability in O(N)O(\sqrt{N})O(N​) queries, where NNN is the size of the string. Furthermore, we give the full recipe to implement our algorithm (together with its total circuit complexity), thus offering an oracle-based quantum algorithm ready to be implemented.
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.
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​​).
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.
In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s1,…,sns^1,\dots,s^ns1,…,sn of total length LLL that is a dictionary, and a string ttt of length mmm that is a text. The first version of the problem is assembling ttt from the dictionary. The second version is the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). In this case, ttt is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring.These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with O(m+log⁡mnL)O(m+\log m\sqrt{nL})O(m+logmnL​) query complexity. In the case of SSP, we present a quantum algorithm with O~(n31.728n+L+n1.5L)\tilde{O}(n^3 1.728^n +L +n^{1.5}\sqrt{L})O~(n31.728n+L+n1.5L​) query complexity. Here O~\tilde{O}O~ hides not only constants but logarithms of LLL and nnn also.
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.