Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
summary
Presents quantum algorithms for longest palindromic substring and longest common substring with concrete bounds: LPS solved in sqrt(n) time (with matching lower bound), LCS achieved in n^{5/6} time via binary search on length d, subsampling, amplitude amplification and pattern matching, plus a reduction to element distinctness giving an Ω(n^{2/3}) lower bound; proves a surprising quantum separation (LPS vs LCS) and gives randomized algorithms that succeed with high probability.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:54Quantum Complexity
- 2:16Complexity
- 2:44Conjectures
- 3:55Famous Problems
- 5:12Project Overview
- 5:49Problems
- 7:18Algorithm
- 8:44Binary Session
- 10:02Lower D
- 12:12Second Algorithm
- 14:11Thought Experiment
- 14:40The Problem
- 16:04Additional Work
- 16:41Open Question
related talks
29mLower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
48mQuantum Linear Algebra Using Subspace States
44mNLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
28mPost-Quantum Manifesto
01h 07mIntroduction to qLDPC Codes
22mQuantum space, ground space traversal, and how to embed multi-prover...
20mThe Quantum Supremacy Tsirelson Inequality