「2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した。」という記事を読んで、量子コンピュータとはなんぞやと調べてみた。
よくわからなかったのだが、従来コンピュータは因数分解が苦手で、量子コンピュータは得意らしいとのことである。
「量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが、22以上の数の素因数分解の報告はない(2019年9月時点)。」(量子コンピュータ-Wikipedia)だそうである。
そこで以下の記事を見てもらいたい。
jigendho.hatenablog.com
この記事は”縦読み”マトリックスを210で割ったあまりの値をランクとしてヒストグラムを作成したものである。
この中で13本の強ピークから四つの値を見出している。
この四つの値は210の四つの素因数の中の三つをかけた値に相当する。
よって、210を四つの値それぞれで割った値が素因数となる。
即ち、210を素因数分解したことになる。
このアルゴリズムは以下のようになる。
- 強ピーク値の間隔から素因数の値を見つける。
このアルゴリズムの特徴は、素因数の値を計算するのではなく見つけるところにある。
実際強ピークの度数も全て同じ値ではなく、1000から2000の間に分布しているだけで計算で求まる値という感じではない。
