Cover Image

Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems

CC BY

Saved in:
Bibliographic Details
Main Authors: François Le, Gall, Saeed, Seddighin
Format: Book
Language:English
Published: Springer 2023
Subjects:
LCS
LPS
Online Access:https://link.springer.com/article/10.1007/s00453-022-01066-z
https://dlib.phenikaa-uni.edu.vn/handle/PNK/8335
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-8335
record_format dspace
spelling oai:localhost:PNK-83352023-04-26T06:50:27Z Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems François Le, Gall Saeed, Seddighin LCS LPS CC BY Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact O~(n−−√) time algorithm for LPS, we prove that LCS needs at least time Ω~(n2/3) even for 0/1 strings. 2023-04-26T06:50:27Z 2023-04-26T06:50:27Z 2022 Book https://link.springer.com/article/10.1007/s00453-022-01066-z https://dlib.phenikaa-uni.edu.vn/handle/PNK/8335 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic LCS
LPS
spellingShingle LCS
LPS
François Le, Gall
Saeed, Seddighin
Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
description CC BY
format Book
author François Le, Gall
Saeed, Seddighin
author_facet François Le, Gall
Saeed, Seddighin
author_sort François Le, Gall
title Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
title_short Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
title_full Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
title_fullStr Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
title_full_unstemmed Quantum Meets Fine-Grained Complexity Sublinear Time Quantum Algorithms for String Problems
title_sort quantum meets fine-grained complexity sublinear time quantum algorithms for string problems
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s00453-022-01066-z
https://dlib.phenikaa-uni.edu.vn/handle/PNK/8335
_version_ 1764358629323964416
score 8.881002

Similar Items