Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems

• URL: http://arxiv.org/abs/2001.01914v1
• Date: Tue, 7 Jan 2020 07:22:02 GMT
• Title: Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
• Authors: Kamil Khadiev and Artem Ilikaev
• Abstract summary: 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$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The problem is the following. Assume that we have a sequence of $n$ strings of length $k$. The problem is finding the string that occurs in the sequence most often. We propose a quantum algorithm that has a query complexity $\tilde{O}(n \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm that requires $\Omega(nk)$ queries. The second one is searching intersection of two sequences of strings. All strings have the same length $k$. The size of the first set is $n$ and the size of the second set is $m$. We propose a quantum algorithm that has a query complexity $\tilde{O}((n+m) \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm that requires $\Omega((n+m)k)$ queries. The third problem is sorting of $n$ strings of length $k$. On the one hand, it is known that quantum algorithms cannot sort objects asymptotically faster than classical ones. On the other hand, we focus on sorting strings that are not arbitrary objects. We propose a quantum algorithm that has a query complexity $O(n (\log n)^2 \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm (radix sort) that requires $\Omega((n+d)k)$ queries, where $d$ is a size of the alphabet.

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)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Improved Algorithm and Lower Bound for Variable Time Quantum Search [1.2246649738388389]
  We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(sqrtTlog n)$. Our second result is a quantum lower bound of $Omega(sqrtTlog T)$.
  arXiv  Detail & Related papers  (2023-02-13T23:24:49Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Quantum Algorithms for String Processing [58.720142291102135]
  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.
  arXiv  Detail & Related papers  (2020-12-01T09:59:06Z)
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
  We consider online algorithms for the $k$-server problem on trees. Chrobak and Larmore proposed a $k$-competitive algorithm for this problem that has the optimal competitive ratio. We propose a new time-efficient implementation of this algorithm that has $O(nlog n)$ time complexity for preprocessing.
  arXiv  Detail & Related papers  (2020-08-01T14:21:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
  We study algorithms for solving the problem of constructing a text from a dictionary (sequence of small strings) The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments.
  arXiv  Detail & Related papers  (2020-05-28T22:44:01Z)
• Resonant Quantum Search with Monitor Qubits [0.0]
  We present an algorithm for the generalized search problem (searching $k$ marked items among $N$ items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity $O(sqrtN/k)$ as the Grover algorithm.
  arXiv  Detail & Related papers  (2020-02-21T19:31:34Z)

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.