| 講演名 | 2008-10-10 ある決定木のクラスに対する量子質問複雑さの下界について 福原 秀明, 瀧本 英二, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文では,ソフトランクと呼ばれる決定木の平衡度を計る指標を導入し,あるクラスGに属する任意の決定木Tに対し,TのソフトランクがTの表す関数の量子質問複雑さの下界であることを示す.このことはGに属する決定木の表す関数の決定的質問複雑きと量子質問複雑さの間に二乗のギャップしかないことを意味する.クラスGは,各変数の出現回数が高々1回の決定木をすべて含み,さらに,パリティ関数を表現する決定木を含む. |
| 抄録(英) | We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. |
| キーワード(和) | 量子質問複雑さ / 決定木 / 量子敵対者法 |
| キーワード(英) | quantum query complexity / decision trees / adversary method |
| 資料番号 | COMP2008-40 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2008/10/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ある決定木のクラスに対する量子質問複雑さの下界について |
| サブタイトル（和） | |
| タイトル（英） | Lower bounds on quantum query complexity for decision trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子質問複雑さ / quantum query complexity |
| キーワード(2)（和/英） | 決定木 / decision trees |
| キーワード(3)（和/英） | 量子敵対者法 / adversary method |
| 第 1 著者 氏名（和/英） | 福原 秀明 / Hideaki FUKUHARA |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 瀧本 英二 / Eiji TAKIMOTO |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 2008-10-10 |
| 資料番号 | COMP2008-40 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 237 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |