Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 5076264 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- A faster algorithm computing string edit distances
- Accurate and nearly optimal sublinear approximations to Ulam distance
- An Erdős-Rényi law with shifts
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- Approximating edit distance in truly subquadratic time: quantum and MapReduce
- Concentration of Measure for the Analysis of Randomized Algorithms
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Constant-factor approximation of near-linear edit distance in near-linear time
- Dynamic algorithms for LIS and distance to monotonicity
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Embedding the Ulam metric into \(\ell_{1}\)
- Estimating the longest increasing sequence in polylogarithmic time
- Introduction to algorithms.
- Longest common substring made fully dynamic
- Near-optimal sublinear time algorithms for Ulam distance
- Oblivious string embeddings and edit distance approximations
- On computing the length of longest increasing subsequences
- Polylogarithmic approximation for edit distance and the asymmetric query complexity
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- Quantum lower bound for the collision problem with small range
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum speedups for exponential-time dynamic programming algorithms
- Quantum verification of matrix products
- Reconstructing strings from substrings with quantum queries
- Search via Quantum Walk
- Strengths and Weaknesses of Quantum Computing
- String matching in O( n+ m) quantum time
- Sublinear space algorithms for the longest common substring problem
- Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
Cited in
(14)- Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
- Quantum algorithm for lexicographically minimal string rotation
- A note on quantum divide and conquer for minimal string rotation
- Near-optimal quantum algorithms for string problems
- Quantum algorithms for learning hidden strings with applications to matroid problems
- Quantum data structure for range minimum query
- Parameterized quantum query algorithms for graph problems
- Quantum algorithms for longest common and palindromic substrings in the circuit model
- RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
- Quantum path parallelism: a circuit-based approach to text searching
- Quantum complexity for vector domination problem
- Double-ended palindromic trees in linear time
- A general quantum circuit for string matching: unleashing quantum path parallelism
- Approximation algorithms for LCS and LIS with truly improved running times
This page was built for publication: Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2701384)
