Reconstructing Strings from Substrings with Quantum Queries

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

13 pages

Scientific paper

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(\frac{N}{\log^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 $\log N$ and $3 \log N$, then we cannot achieve a query complexity of any sublinear function in $N$.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Reconstructing Strings from Substrings with Quantum Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstructing Strings from Substrings with Quantum Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstructing Strings from Substrings with Quantum Queries will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-6150

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.