| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-07-14 16:05 ハッシュパズルに対するBoyer量子アルゴリズムの計算量逆転現象について ○樋川雅人・楫 勇一（名大）  ISEC2026-48 SITE2026-44 BioX2026-71 HWS2026-44 ICSS2026-63 EMM2026-55 |
|
| 抄録 | （和） | ハッシュパズルは，正解が複数存在するようなハッシュ関数原像計算問題として定義される．Grover量子アルゴリズムをハッシュパズルに単純適用すると計算失敗の確率が無視できない場合が生じるため，その失敗を補償するBoyer量子アルゴリズムが提案されている．古典的アルゴリズムでは，正解数が増えると問題は容易となって計算量は減少するが， Boyer量子アルゴリズムでは，正解数の増加が計算量の増加も招く計算量逆転現象が生じることが実験的に示されている．本研究では，計算量逆転現象が生じる必要十分条件を解析的に明らかにし，正解数が微小となる実用的なパラメータ設定では，計算量逆転現象が発生し得ないことを証明する． |
| （英） | A hash puzzle is defined as a preimage-computation problem with multiple correct answers. The naive application of Grover’s quantum algorithm to hash puzzles can fail with non-negligible probability, and Boyer proposed an alternative algorithm that eliminates this failure. In the classical framework, the increase in the number of correct answers makes the problem easier and reduces the complexity. In Boyer’s quantum algorithm, on the other hand, it has been demonstrated that increasing the number of correct answers can, in some cases, increase the complexity, a phenomenon we call the inversion of complexity. In this study, we analytically derive the necessary and sufficient conditions for this phenomenon to occur and show that the inversion of complexity cannot occur under practical parameter settings where the number of correct answers is very small. | |
| キーワード | （和） | ハッシュパズル / Boyer量子アルゴリズム / 正解数 / 計算量 / 計算量逆転現象 / / / |
| （英） | hash puzzle / Boyer's quantum algorithm / the number of correct answers / complexity / the inversion of complexity / / / | |
| 文献情報 | 信学技報, vol. 126, no. 107, ISEC2026-48, pp. 240-247, 2026年7月. | |
| 資料番号 | ISEC2026-48 | |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2026-48 SITE2026-44 BioX2026-71 HWS2026-44 ICSS2026-63 EMM2026-55 |
|
| 研究会情報 | |
| 研究会 | BioX HWS ISEC SITE ICSS EMM IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2026-07-13 - 2026-07-15 |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2026） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2026-07-BioX-HWS-ISEC-SITE-ICSS-EMM-CSEC-SPT-SEC |
| 本文の言語 | 日本語 |
| タイトル（和） | ハッシュパズルに対するBoyer量子アルゴリズムの計算量逆転現象について |
| サブタイトル（和） | |
| タイトル（英） | Inversion of Complexity in Boyer's Quantum Algorithm for Hash Puzzle |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ハッシュパズル / hash puzzle |
| キーワード(2)（和/英） | Boyer量子アルゴリズム / Boyer's quantum algorithm |
| キーワード(3)（和/英） | 正解数 / the number of correct answers |
| キーワード(4)（和/英） | 計算量 / complexity |
| キーワード(5)（和/英） | 計算量逆転現象 / the inversion of complexity |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 樋川 雅人 / Masato Hikawa / ヒカワ マサト |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 楫 勇一 / Yuichi Kaji / カジ ユウイチ |
| 第2著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-07-14 16:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2026-48, SITE2026-44, BioX2026-71, HWS2026-44, ICSS2026-63, EMM2026-55 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.107(ISEC), no.108(SITE), no.109(BioX), no.110(HWS), no.111(ICSS), no.112(EMM) |
| ページ範囲 | pp.240-247 |
| ページ数 | 8 |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]