| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2012-04-27 10:35 Reconstructing Strings from Substrings with Quantum Queries Richard Cleve (Univ. of Waterloo), Kazuo Iwama (Kyoto Univ.), Francois Le Gall (Univ. of Tokyo), Harumichi Nishimura (Nagoya Univ.), Seiichiro Tani (NTT), Junichi Teruyama (Kyoto Univ.), Shigeru Yamashita (Ritsumeikan Univ.)  COMP2012-2 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | 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 $\frac{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 $\Omega(\frac{N}{\log^2{N}})$ 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. |
|
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | quantum computing / string algorithms / query complexity / lower bounds / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 112, no. 21, COMP2012-2, pp. 7-14, April 2012. | |
| Paper # | COMP2012-2 | |
| Date of Issue | 2012-04-20 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2012-2 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2012-04-27 - 2012-04-27 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Osaka Prefecture University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2012-04-COMP |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reconstructing Strings from Substrings with Quantum Queries |
| Sub Title (in English) | |
| Keyword(1) | quantum computing |
| Keyword(2) | string algorithms |
| Keyword(3) | query complexity |
| Keyword(4) | lower bounds |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Richard Cleve |
| 1st Author's Affiliation | University of Waterloo (Univ. of Waterloo) |
| 2nd Author's Name | Kazuo Iwama |
| 2nd Author's Affiliation | Kyoto University (Kyoto Univ.) |
| 3rd Author's Name | Francois Le Gall |
| 3rd Author's Affiliation | The University of Tokyo (Univ. of Tokyo) |
| 4th Author's Name | Harumichi Nishimura |
| 4th Author's Affiliation | Nagoya University (Nagoya Univ.) |
| 5th Author's Name | Seiichiro Tani |
| 5th Author's Affiliation | NTT Communication Science Laboratories (NTT) |
| 6th Author's Name | Junichi Teruyama |
| 6th Author's Affiliation | Kyoto University (Kyoto Univ.) |
| 7th Author's Name | Shigeru Yamashita |
| 7th Author's Affiliation | Ritsumeikan University (Ritsumeikan Univ.) |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-6 |
| Date Time | 2012-04-27 10:35:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2012-2 |
| Volume (vol) | vol.112 |
| Number (no) | no.21 |
| Page | pp.7-14 |
| #Pages | 8 |
| Date of Issue | 2012-04-20 (COMP) |
[Return to Top Page]