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

Lecture notes in networks and systems

Practical Quantum Combinatorial String Matching

Domenico Aldo Cantone, Claudio Caudullo, Simone Faro, Francesco Pio Marino, Arianna Pavone, Caterina Viola

Published Jan 1, 2024• 2 citations
Publisher
DOI
10.1007/978-3-031-73125-9_42

Related papers

Quantum Algorithm for the Multiple String Matching Problem

Kamil Ravilevich Khadiev, Danil Serov

arXiv:2411.14850•Lecture notes in computer science•Jan 1, 2025•3 citations

Quantum String Matching Unfolded and Extended

Domenico Aldo Cantone, Simone Faro, Arianna Pavone

Lecture notes in computer science•Jan 1, 2023•8 citations

String matching in O(n+m) quantum time

H. Ramesh, V Vinay

Journal of Discrete Algorithms•Feb 1, 2003•113 citations

A quantum algorithm for string matching.

Evangelos Tzanis

IADIS AC•Jan 1, 2005•0 citations

Reducing T-Count In Quantum String Matching Algorithm Using Relative-Phase Fredkin Gate

Byeongyong Park, Hansol Noh, Doyeol Ahn

Abstract The string-matching problem, ubiquitous in computer science, can significantly benefit from quantum algorithms due to their potential for greater efficiency compared to classical approaches. The practical implementation of the quantum string matching (QSM) algorithm requires fault-tolerant quantum computation due to the fragility of quantum information. A major obstacle in implementing fault-tolerant quantum computation is the high cost associated with executing T gates. This paper introduces the relative-phase Fredkin gate as a strategy to notably reduce the number of T gates (T-count) necessary for the QSM algorithm. This reduces the T-count from 14 N 3/2 log 2 N – O ( N 3/2 ) to 8 N 3/2 log 2 N – O ( N 3/2 ), where N represents the size of the database to be searched. Additionally, we demonstrate that our method is advantageous in terms of other circuit costs, such as the depth of T gates and the number of CNOT gates. This advancement contributes to the ongoing development of the QSM algorithm, paving the way for more efficient solutions in the field of computer science.

arXiv:2411.01283•Quantum Information and Computation•Aug 1, 2025•2 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•7 citations
Abstract The string-matching problem, ubiquitous in computer science, can significantly benefit from quantum algorithms due to their potential for greater efficiency compared to classical approaches. The practical implementation of the quantum string matching (QSM) algorithm requires fault-tolerant quantum computation due to the fragility of quantum information. A major obstacle in implementing fault-tolerant quantum computation is the high cost associated with executing T gates. This paper introduces the relative-phase Fredkin gate as a strategy to notably reduce the number of T gates (T-count) necessary for the QSM algorithm. This reduces the T-count from 14 N 3/2 log 2 N – O ( N 3/2 ) to 8 N 3/2 log 2 N – O ( N 3/2 ), where N represents the size of the database to be searched. Additionally, we demonstrate that our method is advantageous in terms of other circuit costs, such as the depth of T gates and the number of CNOT gates. This advancement contributes to the ongoing development of the QSM algorithm, paving the way for more efficient solutions in the field of computer 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.