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

Procedia Computer Science

Pattern Matching: A Quantum Oriented Approach

Kapil Kumar Soni, Akhtar Rasool

Published Jan 1, 2020• 15 citations
Publisher

Abstract

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.

DOI
10.1016/j.procs.2020.03.230

Related papers

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

Quantum-effective exact multiple patterns matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in $O((m/C)\sqrt{N})$ and $O((m/C)\sqrt{t})$ time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.

PeerJ Computer Science•May 12, 2022•6 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 Long-algorithm Based Variational Quantum Scheme for Pattern Matching Problem

Lu Liu, Xingyu Wu, Chuan Wang

Grover algorithm is a popular model in quantum computation field and has the advantage of outperforming its classical counterpart in terms of searching speed, hence it has been applied in various domains such as pattern matching. Unfortunately, there are two central issue for this quantum search algorithm, i.e., Grover algorithm, in practical application that firstly it can only achieve a probability nearing 100% rather than exactly, secondly it tends to require a deep quantum circuit. In this work, we propose a Long-algorithm based quantum scheme for pattern matching problem, which can effectively enhance the success probability of quantum pattern matching and mitigate the needs for quantum computing resources. The performance of this scheme is demonstrated numerically, validating our design.

International Conference on Intelligent Computing and Next Generation Networks (ICNGN)•Nov 17, 2023•0 citations

Quantum‐based exact pattern matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.

ETRI Journal•May 11, 2021•13 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
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.
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 presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in O((m/C)N)O((m/C)\sqrt{N})O((m/C)N​) and O((m/C)t)O((m/C)\sqrt{t})O((m/C)t​) time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.
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.
Grover algorithm is a popular model in quantum computation field and has the advantage of outperforming its classical counterpart in terms of searching speed, hence it has been applied in various domains such as pattern matching. Unfortunately, there are two central issue for this quantum search algorithm, i.e., Grover algorithm, in practical application that firstly it can only achieve a probability nearing 100% rather than exactly, secondly it tends to require a deep quantum circuit. In this work, we propose a Long-algorithm based quantum scheme for pattern matching problem, which can effectively enhance the success probability of quantum pattern matching and mitigate the needs for quantum computing resources. The performance of this scheme is demonstrated numerically, validating our design.
In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.
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.