Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1204.4691 · Lecture notes in computer science

Reconstructing Strings from Substrings with Quantum Queries

Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita

Published Jan 1, 2012• 13 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-31155-0_34

Related papers

Reconstructing Strings from Substrings with Quantum Queries

Cleve Richard, Kazuo Iwama, Le Francois +4 more

IEICE Technical Report; IEICE Tech. Rep.•Apr 20, 2012•0 citations

DS-1-11 Reconstructing Strings from Substrings with Quantum Query

Richard Cleve, Kazuo Iwama, François Le Gal +4 more

電子情報通信学会総合大会講演論文集•Feb 28, 2011•0 citations

Quantum Algorithms for Longest Common Substring with a Gap

Daniel Gibney, Md Helal Hossen

Lecture notes in computer science•Sep 18, 2024•0 citations

Quantum Circuits for Fixed Matching Substring Problems

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

Lecture notes in networks and systems•Jan 1, 2024•2 citations

Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching

Ce Jin, Jakob Nogler

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.

arXiv:2211.15945•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•23 citations

Quantum Algorithms for String Processing

Farid Mansurovich Ablayev, Marat Ablayev, Kamil Ravilevich Khadiev +2 more

arXiv:2012.00372•Lecture notes in computational science and engineering•Oct 21, 2021•19 citations
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.