Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism

• URL: http://arxiv.org/abs/2503.05596v1
• Date: Fri, 07 Mar 2025 17:24:00 GMT
• Title: Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism
• Authors: Simone Faro, Arianna Pavone, Caterina Viola,
• Abstract summary: This paper presents a novel pathway that translates bit-parallel string matching algorithms into the quantum framework.<n>By embedding quantum search within a bit-parallel model, we reduce the time complexity of string matching.<n>We also enhance their performance to achieve a quadratic speedup through Grover's search.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Data Loading [7.88657961743755]
  We present a novel algorithm "Adaptive Circuit Learning of Born Machine" (ACLBM) Our algorithm is tailored to selectively integrate two-qubit entangled gates that best capture the complex entanglement present within the target state. Empirical results underscore the proficiency of our approach in encoding real-world data through amplitude embedding.
  arXiv  Detail & Related papers  (2023-11-29T16:47:31Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Grover search revisited; application to image pattern matching [0.8367938108534343]
  We propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit.
  arXiv  Detail & Related papers  (2021-08-24T17:30:41Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.