Reconstructing Strings from Substrings with Quantum Queries

DOI10.1007/978-3-642-31155-0_34zbMath1357.68307arXiv1204.4691OpenAlexW3105563233MaRDI QIDQ2904573

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

Publication date: 14 August 2012

Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.4691

zbMATH Keywords

lower boundsquantum computingstring algorithmsquery complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

Quantum algorithm for lexicographically minimal string rotation ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum algorithms for learning hidden strings with applications to matroid problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC ⋮ Quantum algorithm for learning secret strings and its experimental demonstration

This page was built for publication: Reconstructing Strings from Substrings with Quantum Queries