ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング


インデックスリンク

インデックスツリー

  • RootNode

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. アルゴリズム(AL)
  3. 1999
  4. 92(1999-AL-070)

Groverの量子探索アルゴリズムの応用

https://ipsj.ixsq.nii.ac.jp/records/32119
https://ipsj.ixsq.nii.ac.jp/records/32119
56969989-ed06-4aca-a3b8-1be701381725
名前 / ファイル ライセンス アクション
IPSJ-AL99070005.pdf IPSJ-AL99070005.pdf (716.2 kB)
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
著者名 徳永, 裕己 小林, 弘忠 今井, 浩

× 徳永, 裕己 小林, 弘忠 今井, 浩

徳永, 裕己
小林, 弘忠
今井, 浩

Search repository
著者名(英) Yuki, Tokunaga Hirotada, Kobayashi Hiroshi, Imai

× Yuki, Tokunaga Hirotada, Kobayashi Hiroshi, Imai

en Yuki, Tokunaga
Hirotada, Kobayashi
Hiroshi, Imai

Search repository
論文抄録
内容記述タイプ 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
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-22 16:19:05.389095
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3