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

International Conference on Computing, Communication and Networking Technologies (ICCCNT)

Classical Equivalent Quantum Based Pattern Matching Algorithms

Kapil Kumar Soni, Akhtar Rasool

Published Jul 1, 2019• 0 citations
Publisher

Abstract

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.

DOI
10.1109/icccnt45670.2019.8944416

Related papers

Pattern Matching: A Quantum Oriented Approach

Kapil Kumar Soni, Akhtar Rasool

This article influences the quantum based solutions for traditional pattern matching problem, as the quantum machines can accelerate the computation speed by inherently supporting the parallel executions. The problem identifies solution by suggesting effective algorithms, and as per the classical machines several algorithms are qualified and become criterion for other, importantly noted as Knuth Morris Pratt and Boyer Moore which solves such problem in O(M + N) time. A quantum identical pattern matching algorithms are based upon the principle of high speed Grover's quantum search method which searches an element over unstructured database of "N" elements in O(√N) time. The standard quantum algorithm was proposed by Ramesh and Vinay that could obtain computational speed and provides solution in O(√M + √N) time. We review two already existing quantum based exact and approximate pattern matching algorithms and then by combining the logic of both, a new exact pattern matching algorithm is being proposed which overcomes the algorithmic constraints and substantially proves to be equivalently better than the existing classical and quantum benchmark algorithms. So, this article includes existing and proposed quantum pattern matching algorithms, their flowcharts and examples, mathematical justification over complexity analysis. At last we discuss suitable application domains and further possible variations over the proposed work.

Procedia Computer Science•Jan 1, 2020•15 citations

Evolution of Quantum Computing Based on Grover's Search Algorithm

Prakhar Shrivastava, Kapil Kumar Soni, Akhtar Rasool

Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.

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

A general quantum circuit for string matching: Unleashing quantum path parallelism

Simone Faro, Arianna Pavone, Caterina Viola

Text searching is a fundamental problem in computer science, and it finds applications in several scientific fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n . This paper introduces the quantum path parallelism approach, that is, a general strategy based on quantum computation, which is easily adapted to a variety of nonstandard text-searching problems. Our method translates a text-searching problem into an automata-based string-recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favorable conditions, our algorithm solves an approximate search problem in O ( n m log ( n ) ) -time, yielding a quadratic speed-up over classical solutions. In other cases, such a speed-up is achieved only for short patterns, i.e. whenever m = O ( log ( n ) ) . We show the flexibility of our method, giving explicit adaptations to some specific approximate string matching problems.

Theoretical Computer Science•May 25, 2026•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 Computation Based Grover’s Search Algorithm and its Variations

Kapil Kumar Soni, Akhtar Rasool

Background: The future computations need parallelism, and a way to achieve the same is through quantum-based specific properties. Quantum computation supports exponential operation to be performed in parallel over a single execution step and hence achieves computational speedup. Objective: One of the quantum-based algorithms allows to search the key element over an index based unstructured database and succeeds to obtain the speedup. In the whole context of article writing, our approach reviews the significance of quantum computing, the basics required for quantum computation and their quantum logic-based circuit operations. Method: The article focuses on Grover’s search algorithm and its variations, and then illustrates the relevant amplitude amplification & phase matching techniques in accordance with the advantages and limitation to the specific perspective. Results: We made the comparative analysis between the amplitude amplification-based static & dynamic Grover’s searching and phase estimation technique. Along with this, we justified the possibilities of the empirical results and observed facts over Grover’s variant approaches. Conclusion: Finally, we conclude the analytical comparison between quantum-based searching techniques along with the applicability of Grover’s algorithm in practical computational science.

Recent Patents on Engineering•Jul 16, 2020•0 citations

Practical Implementation of a Quantum String Matching Algorithm

Francesco Pio Marino, Simone Faro, Antonio Scardace

String matching stands as a cornerstone problem in computer science, finding extensive application in many fields, such as data mining, text retrieval, and bioinformatics, just to cite a few. Its essence lies in identifying all occurrences of a specified pattern, typically denoted by length m, within a text of length n. Despite its seemingly straightforward formulation, the problem has sparked a plethora of solutions, stemming from diverse computational paradigms and approaches. Classical solutions exhibit a worst-case time complexity of Θ(n), contrasting with the capability of quantum computation to achieve a [EQUATION] complexity using Grover search, thereby realizing a quadratic speed-up compared to classical methods. This article presents a first practical implementation of a quantum circuit tailored to address string matching, particularly focusing on binary strings. The exposition delves into the technical intricacies of the implementation, which leverages the Qiskit open-source toolkit developed by IBM. By elucidating various algorithmic nuances overlooked in prior theoretical formulations, our solution serves as a conduit between the realms of text processing and quantum computing, fostering cross-disciplinary dialogue and innovation. While current real-world hardware lacks the capability to execute the proposed circuit, particularly when dealing with lengthy texts, this study presents experimental results from a simulation of the circuit on classical hardware, serving to validate the efficacy of the proposed implementation.

•Jun 3, 2024•5 citations
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.
This article influences the quantum based solutions for traditional pattern matching problem, as the quantum machines can accelerate the computation speed by inherently supporting the parallel executions. The problem identifies solution by suggesting effective algorithms, and as per the classical machines several algorithms are qualified and become criterion for other, importantly noted as Knuth Morris Pratt and Boyer Moore which solves such problem in O(M + N) time. A quantum identical pattern matching algorithms are based upon the principle of high speed Grover's quantum search method which searches an element over unstructured database of "N" elements in O(√N) time. The standard quantum algorithm was proposed by Ramesh and Vinay that could obtain computational speed and provides solution in O(√M + √N) time. We review two already existing quantum based exact and approximate pattern matching algorithms and then by combining the logic of both, a new exact pattern matching algorithm is being proposed which overcomes the algorithmic constraints and substantially proves to be equivalently better than the existing classical and quantum benchmark algorithms. So, this article includes existing and proposed quantum pattern matching algorithms, their flowcharts and examples, mathematical justification over complexity analysis. At last we discuss suitable application domains and further possible variations over the proposed work.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.
Text searching is a fundamental problem in computer science, and it finds applications in several scientific fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n . This paper introduces the quantum path parallelism approach, that is, a general strategy based on quantum computation, which is easily adapted to a variety of nonstandard text-searching problems. Our method translates a text-searching problem into an automata-based string-recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favorable conditions, our algorithm solves an approximate search problem in O ( n m log ( n ) ) -time, yielding a quadratic speed-up over classical solutions. In other cases, such a speed-up is achieved only for short patterns, i.e. whenever m = O ( log ( n ) ) . We show the flexibility of our method, giving explicit adaptations to some specific approximate string matching problems.
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.
Background: The future computations need parallelism, and a way to achieve the same is through quantum-based specific properties. Quantum computation supports exponential operation to be performed in parallel over a single execution step and hence achieves computational speedup. Objective: One of the quantum-based algorithms allows to search the key element over an index based unstructured database and succeeds to obtain the speedup. In the whole context of article writing, our approach reviews the significance of quantum computing, the basics required for quantum computation and their quantum logic-based circuit operations. Method: The article focuses on Grover’s search algorithm and its variations, and then illustrates the relevant amplitude amplification & phase matching techniques in accordance with the advantages and limitation to the specific perspective. Results: We made the comparative analysis between the amplitude amplification-based static & dynamic Grover’s searching and phase estimation technique. Along with this, we justified the possibilities of the empirical results and observed facts over Grover’s variant approaches. Conclusion: Finally, we conclude the analytical comparison between quantum-based searching techniques along with the applicability of Grover’s algorithm in practical computational science.
String matching stands as a cornerstone problem in computer science, finding extensive application in many fields, such as data mining, text retrieval, and bioinformatics, just to cite a few. Its essence lies in identifying all occurrences of a specified pattern, typically denoted by length m, within a text of length n. Despite its seemingly straightforward formulation, the problem has sparked a plethora of solutions, stemming from diverse computational paradigms and approaches. Classical solutions exhibit a worst-case time complexity of Θ(n), contrasting with the capability of quantum computation to achieve a [EQUATION] complexity using Grover search, thereby realizing a quadratic speed-up compared to classical methods. This article presents a first practical implementation of a quantum circuit tailored to address string matching, particularly focusing on binary strings. The exposition delves into the technical intricacies of the implementation, which leverages the Qiskit open-source toolkit developed by IBM. By elucidating various algorithmic nuances overlooked in prior theoretical formulations, our solution serves as a conduit between the realms of text processing and quantum computing, fostering cross-disciplinary dialogue and innovation. While current real-world hardware lacks the capability to execute the proposed circuit, particularly when dealing with lengthy texts, this study presents experimental results from a simulation of the circuit on classical hardware, serving to validate the efficacy of the proposed implementation.