Reconstructing strings from substrings with quantum queries

DOI10.1007/978-3-642-31155-0_34zbMATH Open1357.68307arXiv1204.4691OpenAlexW3105563233MaRDI QIDQ2904573FDOQ2904573

Authors: Richard Cleve, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, S. Yamasita, Kazuo Iwama 

Publication date: 14 August 2012

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

Abstract: This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string $S$ by making queries of the following form: "Is $s$ a substring of $S$?", where $s$ is a query string over the given alphabet. The number of queries required to identify the string $S$ is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string $S$ with at most $3/4N+o(N)$ queries, where $N$ is the length of $S$. This contrasts sharply with the classical query complexity $N$. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in $S$, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of $Omega(fracNlo{g}^{2}N)$, which means we cannot achieve a query complexity of $O(N^{1-epsilon})$ for any constant $epsilon$. The other one claims that if we cannot use queries of length roughly between $logN$ and $3logN$, then we cannot achieve a query complexity of any sublinear function in $N$.

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
• Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
• An optimal quantum algorithm for the oracle identification problem

zbMATH Keywords

lower boundsquery complexityquantum computingstring algorithms

Mathematics Subject Classification ID

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

Cited In (14)

• Quantum algorithm for learning secret strings and its experimental demonstration
• Quantum algorithm for lexicographically minimal string rotation
• Recovering strings in oracles: quantum and classic
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A promiseBQP-complete string rewriting problem
• Near-optimal quantum algorithms for string problems
• Quantum algorithms for learning hidden strings with applications to matroid problems
• Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• Parsing a Sequence of Qubits
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time

This page was built for publication: Reconstructing strings from substrings with quantum queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904573)