Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time

• URL: http://arxiv.org/abs/2309.01250v1
• Date: Sun, 3 Sep 2023 19:27:57 GMT
• Title: Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time
• Authors: Domenico Cantone, Simone Faro, Arianna Pavone and Caterina Viola
• Abstract summary: The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science. We present a quantum algorithm for both LCS and LPS working in the circuit model of computation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and $\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a $\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in $\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time, respectively.

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)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• 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)
• Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems [5.490993287665715]
  Longest common (LCS), longest palindrome (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. We present sublinear time quantum algorithms for these problems along with quantum lower bounds.
  arXiv  Detail & Related papers  (2020-10-23T01:00:50Z)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.