Quantum Algorithms For String Problems

We design near-optimal quantum query algorithms for two important text processing problems: Longest Common Substring and Lexicographically Minimal String Rotation. Specifically, we show that: - Longest Common Substring can be solved by a quantum algorithm in Õ(n²⸍³) time, improving upon the Õ(n⁵⸍⁶)-time algorithm by Le Gall and Seddighin (2022). Moreover, given a length threshold 1 ≤ d ≤ n, our algorithm decides in n²⸍³⁺⁰⁽¹⁾/d¹⸍⁶ time whether the longest common substring has length at least d, almost matching the Omega(n²⸍³/d¹⸍⁶) quantum query lower bound. - Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n¹⸍²⁺⁰⁽¹⁾ time, improving upon the Õ(n³⸍⁴)-time algorithm by Wang and Ying (2020), and almost matching the Ω(√n) quantum query lower bound. Our algorithm for Lexicographically Minimal String Rotation is obtained by speeding up a divide-and-conquer algorithm using nested Grover search and quantum minimum finding. Combining this divide-and-conquer idea with the deterministic sampling algorithm of Vishkin (1991) and Ramesh and Vinay (2003), we achieve a quantum speed-up of the String Synchronizing Set technique introduced by Kempa and Kociumaka (2019). Our algorithm for Longest Common Substring applies this string synchronizing set in the quantum walk framework.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Jin, Ce

Advisors dc:contributor.advisor

• Williams, Virginia Vassilevska
• Williams, R. Ryan

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/147440

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/147440