Related papers: Quantum Algorithms for String Processing

Quantum Algorithms for String Processing

URL: http://arxiv.org/abs/2012.00372v1
Date: Tue, 1 Dec 2020 09:59:06 GMT
Title: Quantum Algorithms for String Processing
Authors: Farid Ablayev, Marat Ablayev, Kamil Khadiev, Nailya Salihova and Alexander Vasiliev
Abstract summary: We provide a quantum algorithm for the String matching problem that uses exponentially less quantum memory than existing ones. Using the same ideas, we provide two algorithms for the String comparing problem. The second algorithm works exponentially faster than the existing one.
Score: 58.720142291102135
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z)
Hybrid classical-quantum text search based on hashing [0.0]
It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given. We propose a hybrid classical-quantum algorithm that implements Grover's search to find a given in a text.
arXiv Detail & Related papers (2023-11-02T13:16:07Z)
Quantum counting, and a relevant sign [0.0]
Two indispensable algorithms in an introductory course on Quantum Computing are Grover's search algorithm and quantum phase estimation. We briefly review these algorithms, highlighting the aforementioned sign.
arXiv Detail & Related papers (2023-10-11T12:29:31Z)
Quantum multi-programming for Grover's search [6.359294579761927]
We propose a quantum multi-programming (QMP) algorithm for Grover's search. Our algorithm decomposes Grover's algorithm by the partial diffusion operator and executes the decomposed circuits in parallel by QMP. We prove that this new algorithm increases the rotation angle of the Grover operator which, as a result, increases the success probability.
arXiv Detail & Related papers (2022-07-29T04:05:46Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z)
Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
We give quantum algorithms for fundamental string problems with near-optimal query complexities and time complexities. These problems include Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
arXiv Detail & Related papers (2021-10-19T02:32:18Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z)
Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems [0.0]
We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The second is searching intersection of two sequences of strings. The third problem is sorting of $n$ strings of length $k$.
arXiv Detail & Related papers (2020-01-07T07:22:02Z)

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