量子コンピュータを用いた素因数分解

質問

量子コンピュータを用いた素因数分解の方法を教えてください。
ある数Aの素因数分解を行うときに、Aより小さい数全ての重ね合わせのような状態で割る事でその全ての余りを出し、0となった物を取り出すと聞いたのですが、これだと、余りが0でない時と0の時の違いを全てチェックし、どれが素数かを調べる必要が出てしまいます。

実際に採用されたアルゴリズムや方法ではどのような方法をとっているのでしょうか？
カテゴリーがどれか分かりませんでした。
カテ違いでしたらすいません。

回答No.1

stomachman

> Aより小さい数全ての重ね合わせのような状態で割る事でその全ての余りを出し、0となった物を取り出す

　いや、そういうやりかたじゃありません。「Shor 因数分解」で検索してみてはいかが？
　納得するには、量子の混合状態（状態の重ね合わせ）についての理解の他に、因数分解（や素数判定）の確率的アルゴリズムに関する知識だとか、フーリエ変換に関する知識も必要ですが。