Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism
String matching is a fundamental problem in computer science, with critical applications in text retrieval, bioinformatics, and data analysis. Among the numerous solutions that have emerged for this problem in recent decades, bit-parallelism has significantly enhanced their practical efficiency, leading to the development of several optimized approaches for both exact and approximate string matching. However, their potential in quantum computing remains largely unexplored. This paper presents a novel pathway that not only translates bit-parallel string matching algorithms into the quantum framework but also enhances their performance to achieve a quadratic speedup through Grover's search. By embedding quantum search within a bit-parallel model, we reduce the time complexity of string matching, establishing a structured pathway for transforming classical algorithms into quantum solutions with provable computational advantages. Beyond exact matching, this technique offers a foundation for tackling a wide range of non-standard string matching problems, opening new avenues for efficient text searching in the quantum era. To demonstrate the simplicity and adaptability of the technique presented in this paper, we apply this translation and adaptation process to two landmark bit-parallel algorithms: Shift-And for exact pattern matching and Shift-Add for approximate string matching with up to k errors.
Code (0)
등록된 구현이 없습니다.
Tasks
Text RetrievalSimilar Papers 제목 키워드 기반
Bridging quantum and classical computing for partial differential equations through multifidelity machine learning
Quantum algorithms for partial differential equations (PDEs) face severe practical constraints on near-term hardware: limited qubit counts restrict spatial resolution to coarse grids, while circuit depth limitations prev…
Transparallel mind: Classical computing with quantum power
Inspired by the extraordinary computing power promised by quantum computers, the quantum mind hypothesis postulated that quantum mechanical phenomena are the source of neuronal synchronization, which, in turn, might unde…
Quantum Supervised Learning
Recent advancements in quantum computing have positioned it as a prospective solution for tackling intricate computational challenges, with supervised learning emerging as a promising domain for its application. Despite …
Quantum Machine LearningBridging Classical and Quantum Machine Learning: Knowledge Transfer From Classical to Quantum Neural Networks Using Knowledge Distillation
Quantum neural networks (QNNs), harnessing superposition and entanglement, have shown potential to surpass classical methods in complex learning tasks but remain limited by hardware constraints and noisy conditions. In t…
Dimensionality ReductionImage ClassificationKnowledge DistillationQuantum Machine Learning+1Quantum Generative Adversarial Networks: Bridging Classical and Quantum Realms
In this pioneering research paper, we present a groundbreaking exploration into the synergistic fusion of classical and quantum computing paradigms within the realm of Generative Adversarial Networks (GANs). Our objectiv…
Quantum Machine Learning