|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Reconstructing Strings from Substrings with Quantum Queries | | Richard Cleve
; Kazuo Iwama
; François Le Gall
; Harumichi Nishimura
; Seiichiro Tani
; Junichi Teruyama
; Shigeru Yamashita
; | | Date: |
20 Apr 2012 | | 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(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$. | | Source: | arXiv, 1204.4691 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER