Quantum Algorithms for String Processing

Abstract

In the paper, we investigate two problems on strings. The first one is the String matching problem, and the second one is the String comparing problem. We provide a quantum algorithm for the String matching problem that uses exponentially less quantum memory than existing ones. The algorithm uses the hashing technique for string matching, quantum parallelism, and ideas of Grover's search algorithm. Using the same ideas, we provide two algorithms for the String comparing problem. These algorithms also use exponentially less quantum memory than existing ones. Additionally, the second algorithm works exponentially faster than the existing one.

arXiv comment13 pages

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Tight bounds on quantum searching
• A Quantum Algorithm for Finding the Minimum
• Quantum Search on Bounded-Error Inputs
• Quantum query complexity of some graph problems
• Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees

Cited by in corpus (4)

• Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata
• Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs
• Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems