量子コンピューティング最小置換回数問題への応用

スポンサーリンク

概要

論文の詳細を見る
メンバー数nの置換の位数rとは、任意のメンバーmに置換πを行うとき、メンバーmが元の位置まで戻るのに必要な最小置換回数のことをいう。位数rはmとπに依存する。最小置換回数問題とは、π^r(y)=yを満たす最小の数rを見つけることである。古典的アルゴリズムではrを発見するステップ数は2nで増加する。一方、量子コンピューティングではnのオーダであることが知られている。従って、量子コンピューティングでは古典計算に比べて顕著な高速性が期待できる。しかし量子コンピューティングでは得られる結果は確率的である。そこで本研究では、メンバーmを観測したときに、メンバーの分布、すなわちメンバーmの選択の恣意性によらない最適な正答率を線形計画法により推定した。
社団法人電子情報通信学会の論文
2001-01-18

著者

関連論文

もっと見る

スポンサーリンク