| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | 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. |
|
| キーワード | （和） | / / / / / / / |
| （英） | quantum computing / string algorithms / query complexity / lower bounds / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 21, COMP2012-2, pp. 7-14, 2012年4月. | |
| 資料番号 | COMP2012-2 | |
| 発行日 | 2012-04-20 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-2 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-04-27 - 2012-04-27 |
| 開催地（和） | 大阪府立大学 |
| 開催地（英） | Osaka Prefecture University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-04-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Reconstructing Strings from Substrings with Quantum Queries |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / quantum computing |
| キーワード(2)（和/英） | / string algorithms |
| キーワード(3)（和/英） | / query complexity |
| キーワード(4)（和/英） | / lower bounds |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | リチャード クリーブ / Richard Cleve / リチャード クリーブ |
| 第1著者 所属（和/英） | Waterloo大学 (略称： Waterloo大) University of Waterloo (略称： Univ. of Waterloo) |
| 第2著者 氏名（和/英/ヨミ） | 岩間 一雄 / Kazuo Iwama / イワマ カズオ |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | フランソワ ルガル / Francois Le Gall / フランソワ ルガル |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo) |
| 第4著者 氏名（和/英/ヨミ） | 西村 治道 / Harumichi Nishimura / ニシムラ ハルミチ |
| 第4著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 谷 誠一郎 / Seiichiro Tani / タニ セイイチロウ |
| 第5著者 所属（和/英） | NTT コミュニケーション科学基礎研究所 (略称： NTT) NTT Communication Science Laboratories (略称： NTT) |
| 第6著者 氏名（和/英/ヨミ） | 照山 順一 / Junichi Teruyama / テルヤマ ジュンイチ |
| 第6著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第7著者 氏名（和/英/ヨミ） | 山下 茂 / Shigeru Yamashita / ヤマシタ シゲル |
| 第7著者 所属（和/英） | 立命館大学 (略称： 立命館大) Ritsumeikan University (略称： Ritsumeikan Univ.) |
| 講演者 | 第6著者 |
| 発表日時 | 2012-04-27 10:35:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-2 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.21 |
| ページ範囲 | pp.7-14 |
| ページ数 | 8 |
| 発行日 | 2012-04-20 (COMP) |
[研究会発表申込システムのトップページに戻る]