| 講演名 | 2014-03-10 バイアス付きオラクルに対する量子アドバイスを用いたアルゴリズム 河内 亮周, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | バイアス付きオラクルは元々量子版Goldreich-Levinの定理の証明における量子帰着のために提案されたが,量子オラクル計算の文脈でもいくつか研究がなされている.本稿では量子アドバイス状態を用いてBeaudrap-Cleve-Watrousのアルゴリズムのバイアス付きオラクル版を提案し,その解析を与える.またその応用としてある特殊な量子一方向性関数に対するハードコア述語の一般的構成およびその量子帰着による安全性を与えるが・この構成の古典一方向性関数に対する安全性はある特殊な古典一方向性置換の存在性仮定の下で古典帰着では不可能であることも証明する. |
| 抄録(英) | The biased oracles, which were originally motivated from cryptographic quantum reductions for the quantum Goldreich-Levin theorem, have been investigated in the contexts of the quantum oracle computation. ' In this note, we propose the biased-oracle version of the Beaudrap-Cleve-Watrous algorithm using the quantum advice state. As an application of the biased-oracle algorithm, we give a general construction of hardcore predicates for some special quantum one-way function, of which security for classical one-way functions cannot be proved by classical cryptographic reductions under the assumption that some special classical one-way permutation exists. |
| キーワード(和) | オラクル計算 / バイアス付きオラクル / 量子帰着 |
| キーワード(英) | oracle computation / biased oracles / quantum reductions |
| 資料番号 | COMP2013-61 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | バイアス付きオラクルに対する量子アドバイスを用いたアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Quantum-Advised Algorithms for Biased Oracles |
| サブタイトル（和） | |
| キーワード(1)（和/英） | オラクル計算 / oracle computation |
| キーワード(2)（和/英） | バイアス付きオラクル / biased oracles |
| キーワード(3)（和/英） | 量子帰着 / quantum reductions |
| 第 1 著者 氏名（和/英） | 河内 亮周 / Akinori KAWACHI |
| 第 1 著者 所属（和/英） | 東京工業大学大学隣情報理工学研究科数理・計算科学専攻 Department of Mathematical and Computing Sciences, Graduate School for Information Science and Engineering, Tokyo Institute of Technology |
| 発表年月日 | 2014-03-10 |
| 資料番号 | COMP2013-61 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 488 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |