Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
From MaRDI portal
Publication:2701384
DOI10.1007/s00453-022-01066-zOpenAlexW3093792486MaRDI QIDQ2701384
François Le Gall, Saeed Seddighin
Publication date: 28 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.12122
Related Items (4)
Quantum algorithm for lexicographically minimal string rotation ⋮ Quantum complexity for vector domination problem ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum algorithms for learning hidden strings with applications to matroid problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
- An Erdős-Rényi law with shifts
- A faster algorithm computing string edit distances
- On computing the length of longest increasing subsequences
- Reconstructing Strings from Substrings with Quantum Queries
- Sublinear Space Algorithms for the Longest Common Substring Problem
- Search via Quantum Walk
- Quantum lower bounds for the collision and the element distinctness problems
- Oblivious string embeddings and edit distance approximations
- Quantum verification of matrix products
- Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- Longest common substring made fully dynamic
- Dynamic algorithms for LIS and distance to monotonicity
- Constant-factor approximation of near-linear edit distance in near-linear time
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- Estimating the Longest Increasing Sequence in Polylogarithmic Time
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
