Reconstructing strings from substrings with quantum queries

DOI10.1007/978-3-642-31155-0_34MaRDI QIDQ2904573zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cited in

(14)

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

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)