Steer AGI

Page 1: Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism Simone Faro /envel⌢pe/h⌢me Università di Catania, Dipartimento di Matematica e Informatica, Catania, Italia Arianna Pavone /envel⌢pe Department of Mathematics and Computer Science, University of Palermo, via Archirafi n.34, 90123, Palermo, Italy Caterina Viola /envel⌢pe/h⌢me Università di Catania, Dipartimento di Matematica e Informatica, Catania, Italia 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 to ˜O(√n), 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 kerrors. 2012 ACM Subject Classification Theory of computation →Pattern matching; Information systems →Information retrieval Keywords and phrases string matching, bit-parallelism, quantum computing Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23 Funding Simone Faro : Supported by ICSC – Centro Nazionale di Ricerca in High-Performance Computing, Big Data and Quantum Computing; and by University of Catania, progetto PIACERI 2024-2026 - Linea di Intervento 1. Arianna Pavone : Supported by PNRR project ITSERR - Italian Strengthening of the ESFRI RI RESILIENCE Caterina Viola : Supported by ICSC – Centro Nazionale di Ricerca in High-Performance Computing, Big Data and Quantum Computing. ©Simone Faro, Arianna Pavone and Caterina Viola; licensed under Creative Commons License CC-BY 4.0 42nd Conference on Very Important Topics (CVIT 2016). Editors: John Q. Open and Joan R. Access; Article No.23; pp.23:1–23:15 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, GermanyarXiv:2503.05596v1 [cs.DS] 7 Mar 2025 Page 2: 23:2 A Computational Reformulation of Bit-Parallelism 1 Introduction String matching is a fundamental problem in computer science, playing a key role in text processing, information retrieval, and computational biology. It involves identifying exact or approximate occurrences of a string within a text and serves as a core component in various software and operating systems. The importance of efficient string matching algorithms arises from the widespread use of text as a primary medium for data exchange. In large-scale text analysis, these algorithms are essential for processing vast corpora. In computer science, they facilitate data retrieval in linear file structures, while in molecular biology, they enable sequence analysis by identifying patterns in nucleotide and amino acid sequences. Formally, given a pattern xof lengthmand a text yof lengthn, the string matching problem consists of the following tasks: (1) determining whether xappears iny; (2) counting the total number of occurrences; (3) identifying the positions of all occurrences. In the case of approximate matching, an additional objective is: (4) identifying the pattern configurations for each occurrence in the text. In classical computation, the exact matching problem has a time complexity of Ω(n)for problems (1), (2) and (3), while the aprroximate case can have different solutions depending on the allowed approximations. Among the numerous solutions available in the literature [ 14], one of the most significant advancements in practical text searching was the introduction, in the early 1990s, of bit-parallelism for simulating non-deterministic finite-state automata [ 2]. By making use of bitwise operations within a word RAM model, this approach reduces the time complexity of the search phase by a factor proportional to the word size. This technique has inspired extensive research in both standard and non-standard string matching [14]. Three decades later, quantum computing is once again having a significant impact on text processing [ 16,9] and text searching [ 27,21,24,15]. The first quantum solution to exact string matching, developed by Ramesh and Vinay [ 27], combines Grover’s search [ 19] with a parallel string matching technique. Their algorithm operates in the quantum query model [10] and addresses problem (1) with ˜O(√n)queries. Thus, problems (2) and (3) can be solved in ˜O(√ρn)time,∗whereρis the number of occurrences of xiny, providing a real quantum advantage when ρ=o(n). For the average case, Montanaro [ 21] demonstrated a super-polynomial separation between quantum and classical complexity. The first solution in the quantum circuit model [ 31] with a ˜O(√n)-time complexity for (1) was presented by Niroula and Nam in 2021 [ 24], then extended [ 8] to swap matching with a ˜O(√ρn2m) complexity for (4). In this paper, we demonstrate how a classical bit-parallelism-based algorithm with linear complexity can be transformed into a quantum algorithm that solves the same problem in ˜O(√n)time. While this result does not improve the complexity of the standard exact string matching problem—matching the result of Ramesh and Vinay [ 27]—it introduces a more general framework that extends to any bit-parallel text searching algorithm, including those designed for non-standard matching problems. To showcase the effectiveness of our approach, we apply it to two of the most well- known bit-parallel algorithms: Shift-And for exact matching and Shift-Add for approximate matching with up to kerrors. This technique paves the way for translating a wide range of bit-parallelism-based algorithms into the quantum domain, enabling quantum speedups in specific scenarios. ∗Whenever the number of solutions is ρ>1, and we would like to find all of them, Θ(√ρn)iterations of Grover’s search are sufficient and necessary. Page 3: S.Faro, A.Pavone and C.Viola 23:3 2 String Matching and Bit-Parallelism Finite-state automata play a central role in both standard and non-standard string matching, enabling efficient text scanning strategies. The Knuth-Morris-Pratt algorithm, for example, recognizes substrings of the pattern using a deterministic automaton, achieving worst-case linear time complexity. Conversely, the Backward-DAWG-Matching algorithm processes text substrings in reverse, attaining optimal average-case complexity. While deterministic automata provide strong theoretical guarantees, non-deterministic automata offer a more compact and efficient representation for string matching, though their simulation in the word-RAM model is generally inefficient. To address this, bit-parallelism was introduced [ 13] and later refined [ 2,30] to efficiently simulate non-deterministic finite-state automata. Using the parallelism of bitwise operations, this technique reduces the number of operations required by a factor of up to ω, whereωis the word size of the computer. Algorithms designed in the bit-parallelism framework represent each state of the auto- maton using a single bit within a memory register so that the entire automaton can be represented by the bit vector stored in a computer word, provided that the number of states does not exceed its size. Then, they use bitwise operations, i.e., operations that manipulate one or more bit vectors at the level of their individual bits, to simulate the automaton’s transitions in parallel across all states. This allows these algorithms to reduce their execution time by a factor of w, wherewis the size of a computer word. On modern architectures bitwise operations have the same speed as addition but are significantly faster than multiplication and division. In this paper we use the C-like notations in order to represent bitwise operations. In particular, for the purpose of our discussion, we mention the following bitwise operations: “ |” represents the bitwise op- eration Or(01101101|10101100 =11101101 ); “&” represents the bitwise operation And(01101101 &10101100 =00101100 ); and “≪” represents the bitwise left shift (01101101≪2 =10110100 ). These operations are executed within a single CPU cycle. The Shift-And algorithm [ 2] solves the exact string matching problem using bit-parallelism to simulate the behavior of a non-deterministic string matching automaton (NFA) that recognizes the language Σ∗xfor a the input pattern xof lengthm. Formally, this NFA is defined as the 5-tuple NSMA (x) = (Q,Σ,δ,q 0,F). The set of states of the automaton is given by Q={q0,q1,...,qm}, whereq0represents the initial state and qmis the unique final state, i.e., F={qm}. The automaton processes symbols from the input alphabet Σ, and its behavior is governed by the transition function δ:Q×Σ→Q. The structure of the automaton consists of a linear sequence of transitions that advance through its states. Specifically, for each position iin the pattern, the transition function is defined asδ(qi,x[i]) =qi+1, ensuring that the automaton progresses deterministically when reading a matching character. In addition to these transitions, a self-loop is defined at the initial state, such that δ(q0,c) =q0for allc∈Σ, introducing non-determinism and allowing the automaton to start matching the pattern at any position in the input text. The bit-parallel representation of the automaton is implemented using an array bof|Σ| bit-vectors, each of length m. Thei-th bit ofb[c]is set if and only if the transition function satisfiesδ(qi,c) =qi+1, or equivalently, if x[i] =c, forc∈Σand0≤i<m. The configuration of the automaton at any given step is stored in a bit-vector dofmbits. Since the initial state q0is always active, it does not need to be explicitly represented. The i-th bit ofdis set if and only if the corresponding state qi+1is active, for i= 0,...,m−1. At the beginning of the search, the bit-vector dis initialized to 0m, indicating that no states beyondq0are initially active. As the text is processed sequentially from left to right, state CVIT 2016 Page 4: 23:4 A Computational Reformulation of Bit-Parallelism transitions in the automaton are efficiently computed using bitwise operations. Specifically, given a current configuration d, a transition on an input character cis performed using the bitwise update d←((d≪1)|1) &b[c], where the bitwise OR with 1(represented as 0m−11) ensures that the self-loop at the initial state q0is correctly handled. If, after processing the character at position j, the final state qmis active, a match is reported at position j−m+ 1. If the pattern length does not exceed the word size, the automaton fits within a single register, allowing the algorithm to run in linear time. Otherwise, each transition requires ⌈m/w⌉operations, leading to a time complexity of Θ(n⌈m/w⌉). The Shift-Add algorithm [ 2] is a natural generalization of the Shift-And algorithm to the problem of approximate string matching with at most kerrors. More formally, a pattern x occurs at position jin a textyif the substrings xandy[j...j +m−1]differ in at most k positions. As a consequence, in contrast to Shift-And, the Shift-Add algorithm requires logm bits per position to track the number of mismatches encountered so far. This additional information enables the algorithm to determine whether the number of errors remains within the allowed threshold k. Given a configuration dthat represents the current state of the automaton, a transition on an input character cis computed by adding the corresponding bit-vector b[c]to the shifted state vector. Fomally we perform the bitwise operation d←(d≪1) +b[c]. This addition allows the algorithm to track mismatches, as each entry in daccumulates the number of errors encountered up to that position. At the beginning of the search, dis initialized to zero. As the text is processed from left to right, dis updated at each step. A match is detected at positionj−m+ 1if, aftermcomparisons, the final entry of dcontains a value less than or equal tok. That is, a match occurs if d[m−1]≤k. SimilartotheShift-Andalgorithm, theShift-Addalgorithmrunsin O(n⌈m/ω⌉)worst-case time and requires O(σ⌈mlogm/ω⌉)extra space, where ωis the word size of the machine. 3Bitwise Operations: A Bridge from Classical to Quantum Computing Quantum computing makes use of quantum mechanics to build powerful computing systems. Unlikeclassicalcomputersusingbinarybits(0or1), quantumcomputersusequbits, whichcan exist in multiple states simultaneously. This superposition, along with entanglement—where qubits perform coordinated operations—sets quantum computing apart. Before delving into the details of our implementation, we need to briefly introduce the fundamental principles of quantum computing and the quantum model adopted in this work. The fundamental unit in quantum computation is the qubit. A qubit is a coherent superposition of the two orthonormal computational basis states, denoted by |0⟩and|1⟩, using the conventional bra–ketnotation. Formally, a single qubit is an element from the state spaceH, which is the two-dimensional Hilbert space over the complex numbers equipped with aninnerproduct. Therefore, themathematicalexpressionofaqubit |ψ⟩isalinearcombination of the two basis states, i.e., |ψ⟩=α|0⟩+β|1⟩. The values αandβ, calledamplitudes , are complex numbers such that |α|2+|β|2= 1. These values represent the probabilities of measuring the qubit in the state |0⟩or|1⟩, respectively. A quantum measurement is the only operation that reveals information about the state of a qubit; however, this operation causes the qubit to collapse to one of the two basis states. When multiple qubits are considered together, they form a quantum register . A quantum register |ψ⟩=|q0,q1,...,qn−1⟩of sizenis an element from the tensor product of nstate spaces,H⊗n. It is expressed as a linear combination of the 2nstates in{0,1}n, i.e.,|ψ⟩=/summationtext2n−1 k=0αk|k⟩, where the values αk represent the probabilities of measuring the register in the state |k⟩, and/summationtext2n−1 k=0|αk|2= 1. Page 5: S.Faro, A.Pavone and C.Viola 23:5 Letkbe an integer that can be represented by a binary string of length n. The symbol |k⟩denotes the register of size nsuch that|k⟩=/circlemultiplytextn−1 i=0|ki⟩, where|ki⟩is thei-th least significant binary digit of k. For example, the quantum register |9⟩with 5 qubits is given by |9⟩=|0⟩⊗|1⟩⊗|0⟩⊗|0⟩⊗|1⟩. We use|q⟩⊕nto denote a quantum register of size nwhere each qubit is in the state |q⟩. In this paper, we adopt the circuit model of computation [10], introduced by Deutsch [ 12] as thequantum network model. A quantum circuit consists of qubits moving linearly through a sequence of quantum gates, with inputs on the left and outputs on the right. At each time step, a qubit interacts with at most one gate. The quantum circuit model extends its classical counterpart by leveraging superposition, entanglement, and parallelism [ 22,18]. While classical computation applies one gate at a time, quantum gates can operate simultaneously on different qubits. Given nqubits, up to noperations can occur per time step, enabling potential speedups analogous to a classical system with nprocessors. The sizeof a quantum circuit, defined by the number of gates, measures computational complexity. However, circuit depth—the number of sequential gate layers—better characterizes execution time [ 7]. Depth is crucial for practical implementations, as quantum gates have finite operation times, and decoherence limits qubit longevity. Shallow circuits maximize qubit coherence and improve feasibility. Thus, in this work we adopt circuit depth as a measure of complexity. 3.1 Basic Quantum Operators Operators in quantum computing are mathematical entities (also referred as Gates) that change the state of a quantum register. While any quantum operator can be realized for a fixed-size register, variable-size operators require the composition of elementary gates. Quantum operators must be reversible , meaning that their transformation can be uniquely inverted. This reversibility is ensured by unitary evolution, and when ancillary qubits are used, they must be properly managed to prevent loss of information, typically by uncomputing intermediate states. In this section, we briefly list some basic components for building a quantum circuit, focusing on those relevant to this paper. ThePauli-X (orXor NOT) gate is the quantum equivalent of the classical NOT gate. It operates on a single qubit, mapping |0⟩to|1⟩and|1⟩to|0⟩. TheHadamard (orH) gate maps the basis states |0⟩and|1⟩to1√ 2(|0⟩+|1⟩)and1√ 2(|0⟩−|1⟩), respectively, creating a superposition with equal amplitudes. The controlled-NOT (CNOT) gate operates on a two-qubit register |q0,q1⟩. If the control qubit |q0⟩is 1, it inverts the target qubit |q1⟩, otherwise, the qubits remain the same. Formally, it maps |q0,q1⟩to|q0,q0⊕q1⟩. TheToffoli gate(CCNOT) is a universal reversible gate that operates on three qubits. If the first two qubits are both 1, it inverts the third qubit. Otherwise, the qubits remain unchanged. It maps|q0,q1,q2⟩to|q0,q1,q0q1⊕q2⟩. TheSwap gate is a two-qubit operator that swaps the states of the two qubits, mapping |q0,q1⟩to|q1,q0⟩. A multi-controlled NOT (M-CNOT) gate, operating on nqubits, flips the target qubit |qn−1⟩when alln−1control qubits|qi⟩(for0≤i<n−2) are set to|1⟩. Formally, it applies thetransformation |q0,q1,...,qn−1⟩∝⇕⊣√∫⊔≀→|q0,q1,...,qn−2,(q0·q1···qn−2)⊕qn−1⟩.Toffoli(1980) showed that classical multi-controlled gates require ancillary bits [ 29], whereas their quantum counterparts avoid this need but require an exponential number of gates, limiting practicality beyond five controls. The standard M-CNOT implementation follows Boolean logic and requiresn−2ancillary qubits, resulting in linear circuit depth [ 4]. Alternative approaches reduce depth to logarithmic [20, 3] or achieve constant time in specific architectures [28]. A key operator in computational models which makes use of a Quantum Random Access CVIT 2016 Page 6: 23:6 A Computational Reformulation of Bit-Parallelism Memory (QRAM) is the quantum memory access operator, which enables coherent retrieval of quantum data. Given an address register in superposition, it retrieves the corresponding data while preserving quantum coherence, allowing parallel access to multiple memory locations within a single operation [ 17]. A QRAM system consists of a quantum-controlled addressing mechanism and a quantum memory that stores and retrieves data without collapsing superpositions. A common model employs a binary tree structure, where each level encodes an address bit, and quantum-controlled operations traverse the tree coherently. Given an address superposition/summationtext jαj|j⟩, the QRAM operator Qmaps it to a superposi- tion of stored data, formally Q/summationdisplay jαj|j⟩|0⟩=/summationdisplay jαj|j⟩|Dj⟩, where|Dj⟩is the data at memory location j. This transformation preserves quantum coherence, enabling efficient quantum data retrieval. In principle, the size of a quantum memory register, defined as the number of qubits it comprises, is not inherently limited. However, state of the art QRAM implementations face challenges such as decoherence, noise, scalability limitations, and gate errors. 3.2 Adapting Classical Bitwise Operations for Quantum Computation Due to the no-cloning theorem, quantum information cannot be copied or arbitrarily deleted; it can only be transferred within the circuit while maintaining reversibility. This fundamental constraint implies that classical logical operations such as AND and OR cannot be directly applied to overwrite the value of a single qubit, as in the classical operations (a←a∧b) or(a←a∨b), since they are inherently non-reversible. In contrast, the XOR operation preserves reversibility, allowing transformations such as b←a⊕b, which can be implemented using the CNOT gate. To effectively manipulate quantum information, a qubit can be conditionally flipped using anXgate controlled by another qubit, thereby encoding a controlled copy of the state. Moreover, qubit states can be exchanged using the SWAP gate, which ensures that information is transferred without violating unitarity. These operations form the basis for implementing quantum circuits while respecting the principles of quantum mechanics. Bitwise AND between two registers. Let|d⟩=|d0d1...dn−1⟩and|b⟩=|b0b1...bn−1⟩ be two quantum registers of size n. In light of the above considerations, the operation |di⟩←|di⟩∧|bi⟩, for 0≤i < n, must be implemented using an ancillary qubit |ai⟩, initially set to|0⟩. First, the state of |di⟩is swapped with|ai⟩to preserve reversibility. Then, a Toffoli gate is applied with |ai⟩and|bi⟩as control qubits and |di⟩as the target, effectively implementing the operation |di⟩←|ai⟩∧|bi⟩. Since all AND operations can be executed in parallel across the nqubits, the entire bitwise operation is performed in constant time and requires a register |a⟩=|a0a1...an−1⟩ofnancillary qubits. Generalized disjunction. The logical OR operation between two qubits |b⟩and|d⟩ stores their disjunction in a third qubit |c⟩. This can be implemented using a Toffoli gate, which efficiently realizes conjunction, making use of the identity b∨d=¬(¬b∧¬d). As a consequence, the generalized OR operation over the states of an n-qubit quantum register can be implemented using a multiple-CNOT operator, where the qubits in the register act as controls and a result qubit |c⟩serves as the target. This requires negating the qubit states before applying the operator and restoring them to their original values afterward. Additionally, the final state of |c⟩must be negated to obtain the correct result. The complexity of this operator matches that of the multiple-CNOT, which is O(logn). Page 7: S.Faro, A.Pavone and C.Viola 23:7 Bitwise shift of a register. In the classical setting, a bitwise shift of an n-bit register runsinO(⌈n/w⌉)timebutisnotreversible, makingitunsuitableforquantumcomputation. Instead, cyclic rotation must be used, preserving all qubit states by permuting them within the register. A quantum rotation operator can be implemented in O(logn)time using parallel SWAP gates [ 24], though a systematic construction for arbitrary register sizes and shifts has been developed only recently [25]. However, Moore and Nilsson [23] showed that any permutation, including shifts, can be realized in constant depth, making use of the dihedral group structure. A concrete method for implementing cyclic shifts in constant time has been recently proposed in [26]. Incrementing the value of a register. A carry-free increment operator for an n-qubit quantum register can be implemented using a sequence of nmultiple-CNOT gates. In this sequence, the i-th multiple-CNOT targets the i-th least significant qubit, with control qubits ranging from position 0 to i−1. Since a multiple-CNOT gate has a depth of O(logn), the total depth of the increment operator is O(nlogn). Integer comparison of two registers. A quantum operator for adding two quantum registers can be implemented with linear depth relative to the size of the registers. With a slight modification, the addition operator can be adapted to perform a comparison operation while maintaining the same depth [11]. 4 Quantum String Matching Algorithms in ˜O(n) In this section, we introduce two quantum algorithms that adapt the classical bit-parallel approaches, Shift-And and Shift-Add, to the quantum computing framework. The solutions described in this section do not provide any computational speedup compared to their classical counterparts. However, they demonstrate how the bit-parallelism paradigm can be translated into a quantum algorithm, and how they serve as a basis for the more advanced quantum procedures discussed in the next sections. The algorithms described in this section utilize QRAM to access the input text y, on which the search is performed, as well as the table bof sizeσused to simulate the non-deterministic automaton. Specifically, QRAM yis employed to access each of the ncharacters composing the textyvia an address register |j⟩of size⌈log(n)⌉. Furthermore, assuming that the underlying alphabet is ordered and that each of its characters can be mapped to an integer in the range [0,σ−1], QRAMbis used to retrieve the memory registers b[c]for anyc∈Σ, using a register of size ⌈log(σ)⌉, containing the value of c, to address the information. It is assumed that these quantum memory structures are precomputed (ore initialized) before the algorithm is executed. However, it is straightforward to observe that such precomputations can be performed in time ˜O(n)and ˜O(m), respectively. 4.1 Quantum Shift-And The Quantum Shift-And ( QSAnd) algorithm extends the classical SA approach to a quantum computational framework. The algorithm (see Figure 1) utilizes a quantum register |d⟩ofm qubits, initialized to |0⟩m, to encode the automaton configurations, where active states in process are represented by qubits set to |1⟩, while non-active states are set to |0⟩. A register|b⟩of sizemis used to store transition vector registers during the automaton simulation. Additionally, an ancillary register |a⟩ofnmqubits, initialized to |0⟩nm, is employed to store intermediate computational states. A result qubit |r⟩, initialized to|0⟩, is used to detect occurrences of the pattern. CVIT 2016 Page 8: 23:8 A Computational Reformulation of Bit-Parallelism Quantum-Shift-And Algorithm: Input: - aqramoperator to access a text yof lengthn - aqramoperator to access the transition vector Bof lengthσ Circuit Registers: - a register|a⟩of sizenm, initialized to|0⟩nm; (the ancillary register ) - a register|b⟩of sizem, initialized to|0⟩m; (the transition vector register ) - a register|d⟩of sizem, initialized to|0⟩m; (the automaton configuration register ) - a register|c⟩of size⌈log(σ)⌉, initialized to|0⟩log(σ); (the character address register ) - a register|j⟩of size⌈log(n)⌉, initialized to|0⟩log(n); (the shift address register ) - a qubit|r⟩, initialized to|0⟩; (the output register ) Circuit Procedure: 1.repeatntimes the following sequence 2.|c⟩←get a register from QRAM ywith address|j⟩ 3.|b⟩←get a register from QRAM Bwith address|c⟩ 4. swap|di⟩and|ai⟩, forifrom 0tom−1(in parallel) 5. perform|di+1⟩←|bi⟩and|ai⟩, forifrom 0tom−2(in parallel) 6. set|d0⟩to|b0⟩using the cx operator 7. right rotate|a⟩bympositions 8. increment|j⟩ 9.perform|r⟩←generalized-or (|A[0]m−1⟩,|A[1]m−1⟩,...,|A[n−1]m−1⟩) 10.measure|r⟩and return the corresponding bit Figure 1 The Quantum Shift-And algorithm, which translates the classical bit-parallel Shift-And algorithm into a quantum framework. (Top) High-level pseudocode describing the procedure executed by the circuit. (Bottom) The quantum circuit implementing the algorithm. To address characters in the text of length n, a register|j⟩of⌈log(n)⌉qubits is used to retrieve them via QRAM y. Similarly, a register |c⟩of⌈log(σ)⌉qubits is employed to access the transition vector registers through QRAM b. At the beginning of the procedure, the register |j⟩is initialized to|0⟩. The algorithm consists of niterations of a fixed sequence of instructions, with |j⟩being incremented at the end of each iteration. At the start of each iteration, the register |d⟩stores the current automaton configuration, while the first mqubits of the ancillary register |a⟩are set to|0⟩m. In each iteration, the algorithm executes the following sequence of operations. First, the quantum register |y[j]⟩, representing the current character of the text, is retrieved from QRAM yand stored in|c⟩. The value of|c⟩is then used to address QRAM b, retrieving the quantum register |b[y[j]]⟩, which encodes the transition information for the current character. This information is stored in the register |b⟩. Page 9: S.Faro, A.Pavone and C.Viola 23:9 To correctly simulate the transition, the mqubits of the automaton register |d⟩are swapped with the first mqubits of the ancillary register |a⟩, which are in the state |0⟩m. This ensures that the previous automaton configuration is preserved. Next, a bitwise AND operation is performed in parallel for all 0≤i<m−1between |bi⟩and|ai⟩, updating|di+1⟩accordingly. This operation effectively shifts the automaton states one position to the right, leaving the first state in |0⟩. It is implemented using a set of parallel Toffoli gates, where |bi⟩and|ai⟩act as controls, and |di+1⟩serves as the target. Finally, the first qubit of the automaton configuration, |d0⟩, is updated to|b0⟩to simulate the transition from the initial state, which is always active. This is achieved by applying a controlled-X(CX) gate, using |b0⟩as the control and |d0⟩as the target. To ensure proper automaton evolution, the register |a⟩is rotated by mpositions, resetting the qubits involved in the next transition to |0⟩. Additionally, to ensure the reversibility of this procedure, it is necessary to restore the values of the involved registers for the next iteration. As previously discussed, this is achieved through an uncompute operation, which in this context corresponds to the application of the two QRAM access operators. We observe that this process preserves the ndifferent configurations of the automaton within the auxiliary register |a⟩, whose total size is nm. By decomposing this register into nsub-registers of size m, denoted as|Ai⟩for0≤i<n, each sub-register |Ai⟩contains the automaton configuration after the i-th iteration of the procedure. Since the final state of each configuration determines whether the pattern occurs, we can conclude that the pattern xappears at position jin the text yif them-th qubit of register |Aj⟩is in the state|1⟩. Thus, once the entire text has been processed (i.e. at the end of the niterations), a generalized OR is performed between the m-th qubits of the registers |Ai⟩for0≤i<nand the result id stored in |r⟩. Finally, the register |r⟩is measured. If the measurement outcome is|1⟩, it confirms at least one occurrence of the pattern within the text. To analyze the asymptotic time complexity of the algorithm in terms of quantum circuit depth, we make the following observations. The QRAM access operations at lines 2 and 3 have a depth ofO(logn)andO(logσ), respectively. The swap and bitwise AND operations at lines 4 and 5 are executed in parallel across all qubits of the quantum register, resulting in constant depth. Similarly, the rotation operation at line 7 can be performed with constant depth, whereas the increment operation on register |j⟩has a complexity of O(logm). Finally, the generalized OR operation over the nelements of register |a⟩has a depth of O(logn). Therefore, the overall depth complexity of the algorithm for solving formulation (1) of the problem is ˜O(n). In addition, it is straightforward to see that problem formulations (2) and (3) can also be solved in ˜O(n)time. However, we do not elaborate on these details due to space constraints and their limited relevance to the following discussion. 4.2 Quantum Shift-Add The Quantum Shift-Add ( QSAdd) algorithm extends the classical bit-parallel Shift-Add method to a quantum computational framework, enabling approximate string matching with at mostkerrors. Unlike the QSAnd algorithm, which uses a single qubit per position to track state transitions, QSAdd requires⌈logm⌉qubits per position to count mismatches dynamically. This allows the algorithm to determine whether the number of mismatches remains within the allowed threshold kduring execution. Along the same lines of QSAnd, The QSAdd algorithm (depicted in Figure 2) begins with the initialization of multiple quantum registers that store the state of the automaton |d⟩, the transition vectors |b⟩, and shift occurrence register |s⟩. The automaton register |d⟩ has sizem⌈log(m)⌉and we assume it is the concatenation of nsub-registers of size ⌈log(m)⌉, CVIT 2016 Page 10: 23:10 A Computational Reformulation of Bit-Parallelism Quantum-Shift-Add Algorithm: Input: - a QRAM operator to access a text yof lengthn - a QRAM operator to access the transition vector Bof lengthσ Circuit Registers: - a register|a⟩of size⌈log(m)⌉, initialized to|k⟩; (the bound register ) - a register|b⟩of sizem, initialized to|0⟩m; (the transition vector register ) - a register|d⟩of sizen⌈log(m)⌉, initialized to|0⟩nlog(m); (the automaton configuration register ) - a register|c⟩of size⌈log(σ)⌉, initialized to|0⟩log(σ); (the character address register ) - a register|j⟩of size⌈log(n)⌉, initialized to|0⟩log(n); (the shift address register ) - a register|s⟩of sizen, initialized to|0⟩n; (the shift occurrence register ) - a qubit|r⟩, initialized to|0⟩; (the output register ) Circuit Procedure: 1.repeatntimes the following sequence 2.|c⟩←get the register from QRAM ywith address|j⟩ 3.|b⟩←get the register from QRAM Bwith address|c⟩ 4. increment|Di⟩if|bi⟩=|1⟩, forifrom 0tom−1(in parallel) 5. set|sm−1⟩=|1⟩if|Dm−1⟩≥|a⟩ 6. right rotate|d⟩by⌈log(m)⌉position 7. right rotate|s⟩by1position 8. increment|j⟩ 9.perform|r⟩←generslized-or (|r0⟩,|r1⟩,...,|rn−1⟩) 10.measure|r⟩and return the corresponding bit Figure 2 The Quantum Shift-Add algorithm, which translates the classical bit-parallel Shift-Add algorithm into a quantum framework. (Top) High-level pseudocode describing the procedure executed by the circuit. (Bottom) The quantum circuit implementing the algorithm. which we refer as Di, for 0≤i < n. A bound register |a⟩, of size⌈log(m)⌉, is initialized with the value of the bound kand is used to detect approximate occurrences of the pattern. The algorithm works iteratively, processing one character of the text at a time until the entire input string has been examined. At each iteration, the algorithm retrieves the current character|c⟩from the text using a QRAM lookup and maps it to a corresponding transition vector|b⟩, which encodes the state transitions of the automaton. Once the transition vector |b⟩is loaded, the automaton’s internal state |d⟩is updated. This is achieved through a parallelized increment operation, which modifies the configuration of the automaton whenever a transition is valid. A crucial step in this process is checking whether the automaton has reached a final accepting state, i.e. if |Dm−1⟩≤|a⟩, which would indicate a successful match. If this condition is met, the corresponding position in Page 11: S.Faro, A.Pavone and C.Viola 23:11 the shift register |s⟩is marked. After processing the character, the automaton state |d⟩ is shifted to the right of ⌈log(m)⌉positions, effectively propagating its configuration for the next step. Similarly, the shift occurrence register is rotated, ensuring that valid match positions are updated consistently throughout the execution. The text index register |j⟩is then incremented, advancing the scanning process. Once all characters in the text have been processed, the algorithm performs a final quantum OR operation across the shift register |s⟩, collapsing the information into a single output qubit |r⟩. This final step determines whether at least one match has been found in the text. A measurement of this qubit provides the final result, indicating the presence or absence of the pattern in the text. The time complexity of the algorithm can be analyzed by considering the sequence of operations performed at each iteration. Since the main procedure consists of niterations, the key computational costs arise from the fundamental steps executed in each cycle. First, the algorithm retrieves data from QRAM, an operation that incurs a cost of O(logn)for accessing the text and O(logm)for retrieving the transition vector. The automaton update involves mcontrolled increments applied in parallel to registers of size logm, contributing an overall cost of O(logm)per iteration. Additionally, the comparison between the register |Dm−1⟩and the bound register |a⟩, both of size logm, introduces anotherO(logm)operation. Once all niterations are completed, a generalized quantum OR operation is applied to aggregate the results across nqubits, which adds a cost of O(logn). As a result, the total time complexity, in terms of circuit depth, is given by O(nlogm+logn) to solve formulation (1) of the problem. This simplifies to ˜O(n), indicating that the algorithm is near-linear. 5 Enhancing Quantum String Matching via Grover’s Search In the previous section, we demonstrated how a quantum algorithm can be implemented to verify the presence of a pattern xof lengthmwithin a text yof lengthnin time ˜O(n). This result, which addresses formulation (1) of the string matching problem, is achieved by directly translating a bit-parallelism-based algorithm into the quantum computing framework. In this section, we use this operator as the base for developing a new quantum algorithm that solves the same problem in time ˜O(m√n). We also demonstrate how this approach can be further refined to achieve a complexity of ˜O(√n). Such solutions make use of the well-known unstructured search algorithm, introduced by Grover in 1996. Specifically, Grover’s algorithm is a fundamental quantum search technique that locates a unique element within an unstructured dataset of size ninO(√n)operations [ 19], providing a quadratic speedup over classical brute-force methods. Formally, the algorithm addresses the problem of identifying a unique solution wto a given function f:{0,1}log(n)→{0,1}, wheref(w) = 1for exactly one input w. The core idea is to iteratively amplify the probability of obtaining the correct solution through iterative quantum rotations. It starts with an equal superposition of all inputs and incrementally rotates the quantum state towards the target state, where the solution whas amplitude 1. Each iteration consists of two main operations: the Phase Oracle Uf, which flips the amplitude of w, and the Grover Diffusion Operator, which reflects the state around the uniform superposition |+⟩⊗n, reinforcing the amplitude of w. The total rotation per iteration is approximately 2/√n, requiring aboutπ 4√niterations to maximize the probability of measuring w. From a computational complexity perspective, each iteration consists of one application of the phase oracle and one application of the diffusion operator. Since the latter requires a multi-controlled Zgate acting on nqubits, its circuit depth scales as O(logn). CVIT 2016 Page 12: 23:12 A Computational Reformulation of Bit-Parallelism Quantum Procedure A: 1.divide the text into n−moverlapping blocks of size m; 2.set|j⟩as the superposition of all value between |0⟩and|n⟩; 3.repeatπ/4√ntimes the following sequence: 4. run the QSAnd algorithm on the block beginning at position |j⟩ 5. execute the Grover Diffuser operator 6.Measure|j⟩to identify a shift iof the text where the pattern occurs; 7.Returni Figure 3 The Quantum String Matching algorithm which makes use of the Grover unstructured search, working in ˜O(m√n)time. Therefore, the overall complexity of Grover’s search is given by O(√n(T(n) +logn)), where T(n)denotes the time complexity of implementing the oracle. The algorithm generalizes to cases where fhas multiple valid solutions. If there are r solutions, the number of required iterations remains O(√n)but is more precisely given by π 4/radicalbig n/r[6], which is known to be optimal [ 5]. However, when ris unknown, it must be estimated, often requiring techniques based on Quantum Phase Estimation. Finally, if the goal is to find all rsolutions, the number of required queries is Θ(√nr)[1]. 5.1 A First Jump From ˜O(n)to˜O(m√n) We observe that the string matching problem can be reformulated as a quantum database search problem, where the objective is to determine whether a given pattern appears within a set of substrings of the text. This reformulation enables the use of Grover’s algorithm to solve the problem, making use of quantum parallelism to reduce the computational complexity. The resulting algorithm, whose high level pseudocode is schematized in Figure 3, operates by dividing the text into n−moverlapping blocks, each of size m, wheremcorresponds to the length of the pattern, and where each block shares m−1characters with the next block. With this text partitioned, a quantum search is performed in parallel across all blocks to determine whether the pattern is present in any of them. If the search identifies at least one block containing the pattern, the corresponding index is returned, solving problem (1). The key advantage of this method lies in the quadratic speedup provided by Grover’s algorithm. Using QSAnd orQSAdd, verifying the presence of an occurrence of the pattern within a single block of length mrequires ˜O(m)operations andO(m2)auxiliary qubits. However, the algorithm executes the Grover search over the set of substrings performing O(√n)queries. Since each search requires ˜O(m)time, the total complexity of the quantum algorithm is ˜O(m√n), representing a significant improvement over the classical methods. 5.2 A Final Shift From ˜O(m√n)to˜O(√n) In this section, we present our final solution to the problem, which aims to reduce the search space of Grover’s algorithm, thereby decreasing the number of iterations required to amplify the result vector. This reduction is achieved by partitioning the text into blocks larger than m, leading to a lower number of substrings to be searched. However, while this approach reduces the search space, it also increases the size of the blocks on which linear-time algorithms must be applied during each iteration, introducing a trade-off between search space reduction and computational overhead per iteration. Formally, let Kbe the size of each block into which the text is partitioned, with K >m. The number of blocks to search in the text will be n/(K−m+1), as adjacent blocks must share Page 13: S.Faro, A.Pavone and C.Viola 23:13 Quantum Procedure B: 1.divide the text into n/(K−m+ 1)overlapping blocks of size K; 2.set|j⟩as the superposition of all value between |0⟩and|n/K⟩; 3.repeatπ/4/radicalbig n/K times the following sequence: 4. run the QSAand algorithm on the j-th block of the text 5. execute the Grover Diffuser operator 6.Measure|j⟩to identify a block iof the text where the pattern occurs; 7.UseQuantum Procedure A to search in the i-th block for a valid shift h 8.ReturnKi+h Figure 4 The Quantum String Matching algorithm which makes use of the Grover unstructured search, working in ˜O(√n)time. m−1characters to avoid skipping valid shifts. However, for Ksignificantly larger than m, this value approximates to n/K. Thus, Grover’s algorithm will search a space of n/Kelements, requiring ˜O(/radicalbig n/K)iterations. Each iteration now takes O(K+log(K))time, so the overall depth of the circuit implementing the algorithm will be ˜O((K+log(K))/radicalbig n/K) =˜O(√ nK). Therefore, by partitioning the text into segments of size K=log(n), we achieve a depth of ˜O(√nlog1/2(n)) = ˜O(√n). Observe that, in this context, each iteration of the search algorithm checks for the presence of the pattern within blocks larger than m, allowing the possibility of multiple occurrences within the same block. This is consistent with the resolution of case (1) of the problem. Thus, if Grover’s search algorithm can identify the index iof a block where the pattern occurs, determining the exact position of the pattern within the text requires executing the quantum string matching algorithm on such block using K=m. This step will return the offsetjwithin the block where the pattern is found. This will allow us to state that the pattern occurs at position Ki+jin the text. The depth of the circuit for this additional refined search is ˜O(mlog1/2(n)), ensuring that the overall depth remains ˜O(√n). 6 Final Discussion In this work, we have shown how a string matching algorithm based on bit-parallelism can be efficiently translated into the quantum computing framework while preserving its computational complexity, up to a logarithmic factor, in terms of circuit depth. Additionally, by making of Grover’s search algorithm, we have developed a quantum solution that solves formulation (1) of the problem in ˜O(√n)time. Although we have omitted implementation details due to space constraints, we observe that formulation (2) could be addressed using Quantum Phase Estimation applied to the bit-parallelism-based operator. Similarly, for formulation (3), when rsolutions are present, Grover’s algorithm requires O(√nr)iterations to identify all occurrences, leading to a complexity of ˜O(√nr), which provides a quantum advantage when r=o(n). While similar complexity results exist in the literature, our approach offers a systematic way to translate bit-parallelism-based algorithms into the quantum framework, demonstrating that a broad class of classical string matching techniques can benefit from quantum parallelism, achieving a quadratic speedup. Moreover, its simplicity allows direct implementation as a quantum circuit. Given the extensive research on bit- parallelism techniques for non-standard string matching problems, our results pave the way for further studies and applications, extending quantum speedups to a broader range of text-searching challenges. CVIT 2016 Page 14: 23:14 A Computational Reformulation of Bit-Parallelism References 1Andris Ambainis. Quantum search algorithms. SIGACT News , 35(2):22–35, 2004. doi: 10.1145/992287.992296 . 2R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Commun. ACM , 35(10):74–82, 1992. doi:http://doi.acm.org/10.1145/135239.135243 . 3Stefan Balauca and Andreea Arusoaie. Efficient constructions for simulating multi controlled quantum gates. In Computational Science - ICCS 2022 , volume 13353 of LNCS, pages 179–194. Springer, 2022. doi:10.1007/978-3-031-08760-8\_16 . 4Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A , 52(5):3457–3467, nov 1995. URL: https: //doi.org/10.1103%2Fphysreva.52.3457 ,doi:10.1103/physreva.52.3457 . 5Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik , 46(4-5):493–505, 1998. URL: https://onlinelibrary. wiley.com/doi/abs/10.1002/%28SICI%291521-3978%28199806%2946%3A4/5%3C493%3A% 3AAID-PROP493%3E3.0.CO%3B2-P , doi:10.1002/(SICI)1521-3978(199806)46:4/5<493:: AID-PROP493>3.0.CO;2-P . 6Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplific- ation and estimation. In Samuel G. Lo Monaco and Howard E. Brandt, editors, Quantum Computation and Information , volume 305 of Contemporary Mathematics , pages 53–74. Amer- ican Mathematical Society, 2002. URL: https://doi.org/10.1090%2Fconm%2F305%2F05215 , doi:10.1090/conm/305/05215 . 7Anne Broadbent and Elham Kashefi. Parallelizing quantum circuits. Theor. Comput. Sci., 410(26):2489–2510, 2009. URL: https://doi.org/10.1016/j.tcs.2008.12.046 ,doi: 10.1016/J.TCS.2008.12.046 . 8Domenico Cantone, Simone Faro, and Arianna Pavone. Quantum string matching unfolded and extended. In Reversible Computation - Proceedings , volume 13960 of LNCS, pages 117–133. Springer, 2023. doi:10.1007/978-3-031-38100-3\_9 . 9Domenico Cantone, Simone Faro, Arianna Pavone, and Caterina Viola. Quantum circuit based longest common substring. In Ugo de’Liguoro, Matteo Palazzo, and Luca Roversi, editors,Proceedings of the 25th Italian Conference on Theoretical Computer Science, Torino, Italy, September 11-13, 2024 , volume 3811 of CEUR Workshop Proceedings , pages 1–15. CEUR-WS.org, 2024. URL: https://ceur-ws.org/Vol-3811/paper090.pdf . 10Richard Cleve. An introduction to quantum complexity theory. In Quantum Computation and Quantum Information Theory , pages 103–127. WORLD SCIENTIFIC, jan 2001. doi: 10.1142/9789810248185_0004 . 11Steven A. Cuccaro, Thomas G. Draper, Samuel Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv: Quantum Physics , 2004. 12David Deutsch. Quantum computational networks. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences , 425:73 – 90, 1989. URL: https://api. semanticscholar.org/CorpusID:123073680 . 13B. Dömölki. A universal compiler system based on production rules. BIT Numerical Mathem- atics, 8:262–275, 1968. 14Simone Faro and Thierry Lecroq. The exact online string matching problem: A review of the most recent results. ACM Comput. Surv. , 45(2):13:1–13:42, 2013. doi:10.1145/2431211. 2431212. 15Simone Faro, Arianna Pavone, and Caterina Viola. Quantum path parallelism: A circuit-based approach to text searching. In Xujin Chen and Bo Li, editors, Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13-15, 2024, Proceedings , volume 14637 of Lecture Notes in Computer Science , pages 247–259. Springer, 2024. doi:10.1007/978-981-97-2340-9\_21 . Page 15: S.Faro, A.Pavone and C.Viola 23:15 16François Le Gall and Saeed Seddighin. Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. Algorithmica , 85(5):1251–1286, 2023. doi: 10.1007/s00453-022-01066-z . 17Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters , 100(16), apr 2008. URL: https://doi.org/10.1103%2Fphysrevlett. 100.160501 ,doi:10.1103/physrevlett.100.160501 . 18Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. Counting, fanout and the complexity of quantum ACC. Quantum Inf. Comput. , 2(1):35–65, 2002. doi: 10.26421/QIC2.1-3 . 19Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC ’96, pages 212–219. ACM, 1996. doi:10.1145/237814.237866 . 20Yong He, Mingxing Luo, E. Zhang, Hong-Ke Wang, and Xiao-Feng Wang. Decompositions ofn-qubit Toffoli gates with linear circuit complexity. International Journal of Theoretical Physics, 56, 07 2017. doi:10.1007/s10773-017-3389-4 . 21Ashley Montanaro. Quantum pattern matching fast on average. Algorithmica , 77(1):16–39, 2017. doi:10.1007/s00453-015-0060-4 . 22Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM J. Comput. , 31(3):799–815, 2001. doi:10.1137/S0097539799355053 . 23Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM Journal on Computing , 31(3):799–815, 2001. doi:10.1137/S0097539799355053 . 24Pradeep Niroula and Yunseong Nam. A quantum algorithm for string matching. npj Quantum Information , 7:37, 02 2021. doi:10.1038/s41534-021-00369-3 . 25Arianna Pavone and Caterina Viola. The quantum cyclic rotation gate. In Giuseppa Castiglione and Marinella Sciortino, editors, Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023 , volume 3587 of CEUR Workshop Proceedings , pages 206–218. CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3587/ 4071.pdf . 26Arianna Pavone and Caterina Viola. The quantum cyclic rotation gate. SN Comput. Sci., 5(7):830, 2024. URL: https://doi.org/10.1007/s42979-024-03141-4 ,doi:10.1007/ S42979-024-03141-4 . 27H Ramesh and V Vinay. String matching in O(n+m)quantum time. Journal of Discrete Algorithms , 1(1):103–110, 2003. doi:10.1016/S1570-8667(03)00010-8 . 28S. E. Rasmussen, K. Groenland, R. Gerritsma, K. Schoutens, and N. T. Zinner. Single-step implementation of high-fidelity n-bit Toffoli gates. Phys. Rev. A , 101:022308, Feb 2020. URL: https://link.aps.org/doi/10.1103/PhysRevA.101.022308 ,doi:10.1103/PhysRevA. 101.022308 . 29Tommaso Toffoli. Reversible computing. In J. W. de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming , volume 85 of LNCS, pages 632–644. Springer, 1980. doi:10.1007/3-540-10003-2\_104 . 30S. Wu and U. Manber. Fast text searching allowing errors. Commun. ACM , 35(10):83–91, 1992. 31AndrewChi-ChihYao. Quantumcircuitcomplexity. In 34th Annual Symposium on Foundations of Computer Science , pages 352–361. IEEE Computer Society, 1993. doi:10.1109/SFCS.1993. 366852. CVIT 2016