Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems

• URL: http://arxiv.org/abs/2010.12122v2
• Date: Tue, 24 May 2022 03:19:41 GMT
• Title: Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
• Authors: Fran\c{c}ois Le Gall and Saeed Seddighin
• Abstract summary: 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.
• Score: 5.490993287665715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact $\tilde O(\sqrt{n})$ time algorithm for LPS, we prove that LCS needs at least time $\tilde \Omega(n^{2/3})$ even for 0/1 strings.

Related papers

• 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)
• 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)
• Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
  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.
  arXiv  Detail & Related papers  (2023-09-03T19:27:57Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• 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)
• 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)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.