Near-Optimal Quantum Algorithms for String Problems - Summary and Insights

Slide Note

Near-Optimal Quantum Algorithms for String Problems by Ce Jin and Shyan Akmal presents groundbreaking research on string problem solutions using quantum algorithms. The study delves into various key topics such as Combinatorial Pattern Matching, Basic String Problems, Quantum Black-box Model, and more. It discusses the quantum query complexity and time efficiency in comparison with classical algorithms. Notable findings include advancements in Exact Pattern Matching, Longest Common Substring, and Lexicographically Minimal String Rotation. The research highlights the development of near-optimal quantum algorithms for a range of string-related challenges, promising significant advancements in quantum computing applications in this domain.

lark Follow

Uploaded on Jul 17, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Near-Optimal Quantum Algorithms for String Problems Ce Jin (MIT) Joint work with Shyan Akmal (MIT) QIP 2022 arXiv 2110.09696 (appeared in SODA 2022)

Combinatorial Pattern Matching GCTTACAGATTCAGTCTTACAGATGGT This Work Quantum Query Algorithms

Basic String Problems Exact Pattern Matching Longest Common Substring Lexicographically Minimal String Rotation ? = nan? = banana KMP 70 Weiner 73 ? = banana? = ananas ? = bananaMinRot(?) = abanan Booth 80, Shiloach 81 Well-known linear time classical algorithms Quantum speed-up?

Quantum Black-box Model Input string ? 1..? ? alphabet = {0,1,2, ,poly(?)} |? |? |? |? ?[?] Quantum Oracle (? ? ,? ) For a quantum query algorithm (with 2/3 success probability): Query complexity ?= number of quantum queries to the oracle (? ? holds trivially) Time complexity? also counts the number of elementary gates (Goal: time-efficient implementation with ? ? polylog(?) )

Basic String Problems Exact Pattern Matching Longest Common Substring Lexicographically Minimal String Rotation ? = nan? = banana KMP 70 Weiner 73 ? = banana? = ananas ? = bananaMinRot(?) = abanan Booth 80, Shiloach 81 Well-known linear time classical algorithms Quantum speed-up? Ramesh-Vinay 03: Exact Pattern Matching in ? quantum time* * ?, , hide polylog(n) factors.

Our results: Near-optimal quantum algorithms for many string problems! This talk

This talk: Longest Common Substring (LCS) Input: two strings ? 1..? ,? 1..? Output: maximum ? such that ? ?..? + ? = ?[?..? + ?) for some ?,? (? = baabcd? = bcaabc output = 4) not to be confused with Longest Common Subsequence (may not be contiguous) Le Gall & Seddighin (2020, ITCS 22) : ? ?5/6quantum query & time complexity ?2/3quantum query lower bound* This work: ? ??/?quantum query & time complexity * [LG-S] gave tight ?(?2/3) algorithm for a special case of LCS

An Easier Problem: (Bipartite) Element Distinctness Input: Two integer lists ?1, ,??, ?1, ,?? Output: Return YES iff ?? ?? for all ?,? (i.e, decide if ??? ?,? is zero or ?) Quantum query LB: ?2/3(Aaronson & Shi 02) Quantum walk algorithm: ?(?2/3) (Ambainis 04) - Time-efficient implementation with Quantum Random-Access Quantum Memory

Another easier problem: Longest Common Longest Common Prefix Prefix Input: ?= bananas ? = banquet Output: LCP = 3 Lexicographical order: ? ? Binary Search for prefix length ?: Grover Search detects ? [1..?]: ? ? ? ? in ? ? ? total quantum time ? quantum time.

LCS Warm up algorithm (Le Gall & Seddighin) After binary search: Decision problem LCS ?,? ?? i.e., find ?,? such that ? ?..? + ? = ?[?..? + ?) ? 1 ? ? ? 1 ? ? ? + ? ? + ? Reduces to (Bipartite) Element Distinctness each lexicographical comparison costs ? ?(?2/3 ?) time via Ambainis algorithm (comparison-based version) ? For large ?, nearby substrings heavily overlap with each other Try to avoid considering all ?(?) possible starting positions

Anchoring for LCS [SV13, CCIKPRRW18, ACPR19, ACPR20, BGKK20, CGP20, CKPR21, ] ( Decision problem: LCS ?,? ?? ) Construct anchor sets ??,?? [?]such that: If LCS ?,? ?, then exists an anchored length-? common substring. ? b a n a b a n a n a h h = anchor n a b a n a b a b a b a ?

Anchoring for LCS [SV13, CCIKPRRW18, ACPR19, ACPR20, BGKK20, CGP20, CKPR21, ] ( Decision problem: LCS ?,? ?? ) Construct anchor sets ??,?? [?]such that: If LCS ?,? ?, then exists an anchored length-? common substring. ? b a n a b a n a n a h h = anchor n a b a n a b a b a b a ?

Anchoring for LCS [SV13, CCIKPRRW18, ACPR19, ACPR20, BGKK20, CGP20, CKPR21, ] Hope: for larger ?, size ??+ |??| is smaller ( Decision problem: LCS ?,? ?? ) Construct anchor sets ??,?? [?]such that: If LCS ?,? ?, then exists an anchored length-? common substring. Task: Find ? ??,? ??(a witness pair ) that determine a length-? anchored common substring. LCP ? ? ,?(?) + LCP(?(?),?(?)) ?. ? ? + ? ? ? ?(?) ?(?) ? ? = ? + ? b a n a b a n a n a h h = anchor n a b a n a b a b a b a ? ? ? = ? +

Algorithm outline ( Decision problem: LCS ?,? ?? ) ? = ?(?/?3/4) ? = ? 1. Design anchor sets ??,?? Small size ? = ??+ |??| ? Easy to compute: Strongly explicitly -?-time computable Given 1 ? ?, output the ?-th anchor in ? quantum time. 2. Find a witness pair ? ??,? ?? Compare: warm-up LCS algorithm: ? 1. Design anchor sets ??,?? Small size ? = ??+ |??| ? Easy to compute ? ? ?2/3 quantum time ? ? + ? ?2/3 quantum time Overall ? ?2/3 quantum time

Ingredient 1: Difference Cover [Mae85, BK03] (also used by Le Gall Seddighin) If LCS ?,? ?, then exists anchored length-? common substring ? ? ? ? Pro: ?(1)-time-computable (input-oblivious) Con: Size ? = ?(?/ ?) too large

Ingredient 2: String Synchronizing Sets [Kempa-Kociumaka STOC 19] Input-dependent (in a sophisticated way) Pro: small size ? = ?(?/?) Con: Computation time ? = ?(?) too slow

Size & computation time trade-off Difference Cover ? ?/ ? ? = ?(1) String Sync Set ? ?/? ? ? Our anchor set ? ?/?3/4 ? ? baaaaaaaaaaaac A technicality: String Sync Set fails in highly-periodic regions. Instead, find their boundaries (up to ? distance) in ? search + Grover search), and add them into the anchor set. ? quantum time (binary

Algorithm outline (Decision problem: LCS ?,? ??) ? = ?(?/?3/4) ? = ? 1. Design anchor sets Small size ? = ??+ |??| ? Easy to compute: Strongly explicitly -?-time computable Given 1 ? ?, output the ?-th anchor in ? quantum time. 2. Find a witness pair ? ??,? ?? ? ? ? + ? ?2/3 quantum time We use quantum walk search on Johnson graph [Ambainis 04, Magniez-Nayak-Roland-Santha 11]

Finding a witness pair using quantum walks (Anchor set ? = ?? ??: size ? = ?) Quantum walk on Johnson graph ?(?,?) State: ?-subset ? ? Search for an ?-subset ? ? that contains a witness pair Associate every ?-subset ? with a data structure data ? Want to efficiently implement - Setup step: - Update step: - Checking step: check if ? contains a witness pair, given ????(?) initialize the data structure update data(?) when ? ? ? {?}

Finding a witness pair using quantum walks ? ? + ? ? ? (Anchor set ? = ?? ??: size ? = ?, ?-time computable) (Witness pair ? ??,? ??:LCP ? ? ,?(?) + LCP(?(?),?(?)) ?. ) ?(?) ?(?) For ?-subset ? ?, data ? includes Lexicographical order of length-? substrings associated with all anchors in ? LCPs of lexicographically adjacent pairs ( together determine LCP of every pair) Update step: In ? time, compute the anchor ? ? to be inserted. Binary search on the lexicographical order, where each comparison takes ? time. Query & Time complexity ? ?(using suitable data structures to maintain the order) Setup step: ? insertions back band bona bond LCP=2 ? LCP=1 LCP=3

Finding a witness pair using quantum walks ? ? + ? ? ? (Anchor set ? = ?? ??: size ? = ?, ?-time computable) (Witness pair ? ??,? ??:LCP ? ? ,?(?) + LCP(?(?),?(?)) ?. ) ?(?) ?(?) For ?-subset ? ?, data ? includes Lexicographical order of length-? substrings associated with all anchors in ? LCPs of lexicographically adjacent pairs ( together determine LCP of every pair) Update step: In ? time, compute the anchor ? ? to be inserted. Binary search on the lexicographical order, where each comparison takes ? time. Setup step: ? insertions Checking step does ?contain a witness pair? Query complexity = 0. Time complexity? Update step: In ? time, compute the anchor ? ? to be inserted. Binary search on the lexicographical order, where each comparison costs ? ? . ?

Finding a witness pair using quantum walks Time-efficient checking step by maintaining more information with suitable data structures Hash tables Skip Lists supporting (1D) range minimum queries 2D orthogonal range search We can achieve checking time complexity ?( ??) Total time = S +? ? ? + ? ?? ? + ? ? + ? ?2/3 ? (C + ? U) [Ambainis 04, Magniez-Nayak-Roland-Santha 11]

A technical issue for time-efficient implementation We need quantum-walk-friendly data structures for dynamic 2D orthogonal range search History Independence Worst-case ?? 1 time per operation And the 2D points have non-integer coordinates The coordinates are length-d substrings (compared in lexico order) No known data structures satisfy all requirements Fix: sampling and estimating the rankings -> integer coordinates By Balls-and-bins, only a tiny fraction in the Johnson graph will fail

Algorithm outline (Decision problem: LCS ?,? ??) ? = ?(?/?3/4) ? = ? 1. Design anchor sets Small size ? = ??+ |??| ? Easy to compute: Strongly explicitly -?-time computable Given 1 ? ?, output the ?-th anchor in ? quantum time. 2. Find a witness pair ? ??,? ?? ? ? ? + ? ?2/3 quantum time Overall ? ?2/3 quantum time