Reconstructing Strings from Substrings with Quantum Queries

概要

論文の詳細を見る
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/4 N + 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 that any bounded-error quantum algorithm needs Ω(N/log^2N ) queries. For this, we introduce another query model and obtain a lower bound for this model with the adversary method, from which bound we get the desired lower bound in the original query model.
2012-04-20