因数分解に対する量子アルゴリズムのシミュレーション

渥美 賢嗣  西野 哲朗  

誌名
電子情報通信学会論文誌 A   Vol.J81-A   No.12   pp.1670-1677
発行日: 1998/12/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 特集論文 (量子情報理論とその応用論文小特集)
専門分野: 量子アルゴリズム・量子ネットワーク
キーワード: 
量子Turing機械,  量子アルゴリズム,  Shorのアルゴリズム,  因数分解,  シミュレーション,  

本文: PDF(508.6KB)>>
論文を購入




あらまし: 
1994年にShorは,自然数Nの因数分解を行うために,任意のxmodNのオーダを多項式時間内に求める量子アルゴリズムを示した[3].しかし,現在多数の量子ビットをもつ量子コンピュータは存在しないため,そのアルゴリズムが実際にどのような計算結果を出力するかを知る方法がない.このような状況においては,既存の計算機を用いて,Shorの量子アルゴリズムをシミュレーションし,その振舞いや性質を考察することの意義は大きい.本研究では,Shorの因数分解に対する量子アルゴリズムを,パーソナルコンピュータ上でシミュレーションすることにより,Shorのアルゴリズムの振舞いや種々の性質を明らかにする.