Quantum Algorithm for the Shortest Superstring Problem

• URL: http://arxiv.org/abs/2112.13319v1
• Date: Sun, 26 Dec 2021 05:37:56 GMT
• Title: Quantum Algorithm for the Shortest Superstring Problem
• Authors: Kamil Khadiev and Carlos Manuel Bosch Machado
• Abstract summary: We consider the Shortest Superstring Problem''(SSP) or the Shortest Common Superstring Problem''(SCS)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). The problem is as follows. For a positive integer $n$, a sequence of n strings $S=(s^1,\dots,s^n)$ is given. We should construct the shortest string $t$ (we call it superstring) that contains each string from the given sequence as a substring. The problem is connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. We present a quantum algorithm with running time $O^*(1.728^n)$. Here $O^*$ notation does not consider polynomials of $n$ and the length of $t$.

Related papers

• Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings [0.8057006406834466]
  We give a near-optimal quantum algorithm for the longest common (LCS) problem between two run-length encoded (RLE) strings. Our algorithm costs $tildemathcalO(n2/3/d1/6-o(1)cdotmathrmpolylog(tilden))$ time, while the query lower bound for the problem is $tildeOmega(n2/3/d1/6)$.
  arXiv  Detail & Related papers  (2024-10-21T15:52:08Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings [0.951828574518325]
  We give a sublinear quantum algorithm for the longest common (LCS) problem on the run-length encoded (RLE) inputs. Our algorithm costs $tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ time, where $n$ and $tilden$ are the encoded and decoded length of the inputs, respectively.
  arXiv  Detail & Related papers  (2023-10-02T08:14:34Z)
• Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems [11.048346250166073]
  We consider two versions of the Text Assembling problem. We are given a sequence of strings $s1,dots,sn$ of total length $L$ that is a dictionary, and a string $t$ of length $m$ that is texts. For both problems, we suggest new quantum algorithms that work better than their classical counterparts.
  arXiv  Detail & Related papers  (2023-06-18T14:16:49Z)
• Can You Solve Closest String Faster than Exhaustive Search? [4.963483138661772]
  We study the fundamental problem of finding the best string to represent a given set. In this paper, we investigate whether the Closest String problem admits algorithms that are faster than the trivial exhaustive search algorithm.
  arXiv  Detail & Related papers  (2023-05-26T12:30:16Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• 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)

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.