書記が物理やるだけ#325 Shorのアルゴリズム
準備が整ったので，今回はShorのアルゴリズムを扱っていく。
問題
説明
位数については，以前に数学で扱った：
Shorのアルゴリズムは，1994 年にアメリカの数学者Peter Shorによって開発され，これにより因数分解問題や離散対数問題をより高速に解くことができるようになる。アルゴリズムの基本となるのは位相推定問題で，問題レジスタの入力を|1>にする。
解答
位数計算を量子回路で実現する方法を示していく。まず，以下の位相推定問題に帰着できることを示す。
入力を|1>に変えれば良いのは，以下の性質によるものである。
これによりs/rを求めることができ，容易な計算で位数rを求めることができる。
Shorのアルゴリズムによる因数分解問題の解き方を以下に示す。特に位数を計算する場面で，古典コンピュータよりも高速で解くことができる。
例として15の素因数分解をShorのアルゴリズムで解いてみる。
本記事のもくじはこちら：
