講演名 2001/1/18
量子コンピューティング最小置換回数問題への応用
澤江 隆一, 財部 健一, 坂田 年男, 鄭 実生, 福田 健治, 松田 祐輔,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) メンバー数nの置換の位数rとは、任意のメンバーmに置換πを行うとき、メンバーmが元の位置まで戻るのに必要な最小置換回数のことをいう。位数rはmとπに依存する。最小置換回数問題とは、π^r(y)=yを満たす最小の数rを見つけることである。古典的アルゴリズムではrを発見するステップ数は2nで増加する。一方、量子コンピューティングではnのオーダであることが知られている。従って、量子コンピューティングでは古典計算に比べて顕著な高速性が期待できる。しかし量子コンピューティングでは得られる結果は確率的である。そこで本研究では、メンバーmを観測したときに、メンバーの分布、すなわちメンバーmの選択の恣意性によらない最適な正答率を線形計画法により推定した。
抄録(英) Order-finding problem for a permutation π with the 2^n members is to find the least number r for any member y in the 2^n members by the r iterations of which the member y returns to the original position. The number of oracle queries for classical computation increases exponentially in n of π. The quantum computation overcomes this difficulty by its inherent parallel processing. However, to show the advantage of the quantum computation for the order-finding problem, it is needed to know whether the quantum computation could give the probability to get the correct answer larger than the classicalprobabilistic guess. This is considered by the liner programming theory.
キーワード(和) 量子コンピューティング / 最小置換回数問題 / 線形計画法
キーワード(英) Quantum Computing / Order-finding problem / Linear programming
資料番号 PS2000-65,OFT2000-75,OPE2000-127,LQE2000-108
発行日

研究会情報
研究会 OFT
開催期間 2001/1/18(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Optical Fiber Technology (OFT)
本文の言語 JPN
タイトル(和) 量子コンピューティング最小置換回数問題への応用
サブタイトル(和)
タイトル(英) Quantum order-finding by linear programming theory
サブタイトル(和)
キーワード(1)(和/英) 量子コンピューティング / Quantum Computing
キーワード(2)(和/英) 最小置換回数問題 / Order-finding problem
キーワード(3)(和/英) 線形計画法 / Linear programming
第 1 著者 氏名(和/英) 澤江 隆一 / Ryuichi SAWAE
第 1 著者 所属(和/英) 岡山理科大学・応用数学科
Okayama University of Science, Department of Applied Mathematics
第 2 著者 氏名(和/英) 財部 健一 / Kenichi TAKARABE
第 2 著者 所属(和/英) 岡山理科大学・基礎理学科
Okayama University of Science, Department of Applied Science
第 3 著者 氏名(和/英) 坂田 年男 / Toshio SAKATA
第 3 著者 所属(和/英) 九州芸術工科大学
Kyushu Institute of Design, Department of Industrial Design
第 4 著者 氏名(和/英) 鄭 実生 / Minaru TEI
第 4 著者 所属(和/英) 岡山理科大学・電子工学科
Okayama University of Science, Department of Electronic Engineering
第 5 著者 氏名(和/英) 福田 健治 / Kenji FUKUDA
第 5 著者 所属(和/英) 岡山理科大学・応用数学科
Okayama University of Science, Department of Applied Mathematics
第 6 著者 氏名(和/英) 松田 祐輔 / Yusuke MATUDA
第 6 著者 所属(和/英) 岡山理科大学・応用数学科
Okayama University of Science, Department of Applied Mathematics
発表年月日 2001/1/18
資料番号 PS2000-65,OFT2000-75,OPE2000-127,LQE2000-108
巻番号(vol) vol.100
号番号(no) 588
ページ範囲 pp.-
ページ数 6
発行日