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

電子情報通信学会総合大会講演論文集

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

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

Published Feb 28, 2011• 0 citations
OpenAlex

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

Reconstructing Strings from Substrings with Quantum Queries

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

arXiv:1204.4691•Lecture notes in computer science•Jan 1, 2012•13 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•3 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.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•10 citations

Quantum Algorithm for the Multiple String Matching Problem

Kamil Ravilevich Khadiev, Danil Serov

arXiv:2411.14850•Lecture notes in computer science•Jan 1, 2025•3 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.