WEKO3
-
RootNode
アイテム
Groverの量子探索アルゴリズムの応用
https://ipsj.ixsq.nii.ac.jp/records/32119
https://ipsj.ixsq.nii.ac.jp/records/3211956969989-ed06-4aca-a3b8-1be701381725
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1999 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1999-11-08 | |||||||
タイトル | ||||||||
タイトル | Groverの量子探索アルゴリズムの応用 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Applications or Grover's Quantum Search Algorithm | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東京大学大学院理学系研究科情報科学 | ||||||||
著者所属 | ||||||||
東京大学大学院理学系研究科情報科学 | ||||||||
著者所属 | ||||||||
東京大学大学院理学系研究科情報科学 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, University of Tokyo | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, University of Tokyo | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, University of Tokyo | ||||||||
著者名 |
徳永, 裕己
小林, 弘忠
今井, 浩
× 徳永, 裕己 小林, 弘忠 今井, 浩
|
|||||||
著者名(英) |
Yuki, Tokunaga
Hirotada, Kobayashi
Hiroshi, Imai
× Yuki, Tokunaga Hirotada, Kobayashi Hiroshi, Imai
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | N個の未整列なインデックスからあるインデックスを探すとき,現状のコンピュータでは平均でN/2回の探索をする.しかし,Groverの量子探索アルゴリズムではO(√<N>)回で探すことができる.このアルゴリズムは”振幅の増幅”という手法を用いており,SATなど様々な問題に応用ができる.本研究では,Groverのアルゴリズムの応用として最小値探索,数え上げを取り上げる.我々はDurrとHoyerによる最小値のアルゴリズムを応用して,その近似アルゴリズムを考案した.また,Brassardらによる数え上げアルゴリズムの最適性を示した.さらにこれらの問題に対して徳永,長井,今井の量子計算機シミュレータを用いてシミュレーション実験による平均計算時間や解の分散の検証も行った. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | In order to search an index among unsorted N indices, a present computer searches N/2 times on average. However, Grover's quantum algorithm can search in only O(√<N>) steps. This algorithm is based on the method of "amplitude amplification" and can apply various problem such as SAT. In this paper, minimum search and counting problem are taken up as applications of Grover's algorithm. Approximate minimum search algorithm applying Durr and P. Hoyer's algorithm is described. We show Counting algorithm of Brassard et al.'s is optimal. For above problems, mean time or variance are analyzed and verified using Tokunaga Nagai and Imai's quantum computer simulation program. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1999, 号 92(1999-AL-070), p. 33-40, 発行日 1999-11-08 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |