15を手計算で素因数分解する

〜量子の気持ちになるですよ〜

杉山 衣吹(にこなのにふわわあ)

スライドはこちらで公開しています

fuwa.dev/pf15

自己紹介

  • 杉山 衣吹
  • @ibuki2003
  • 麻布高校 一年生
  • https://fuwa.dev
AtCoderレートを分けてください…
## めにゅー - 15の素因数は…? - 量子で素因数分解 理論編 - 量子で素因数分解 実践編 - 所感

$15$の素因数は…?

Q. $15$の素因数は何でしょうか?
最小の素数として知られる$2$で割ってみる `$$ \displaystyle 15 \div 2 = 7 \cdots 1 $$`
有名な *†素数†* $57$ で割ってみる `$$ \displaystyle 15 \div 57 = 0 \cdots 15 $$`
素因数分解すればわかりそう…? 自然数$n$の素因数分解は時間計算量`$\displaystyle\mathcal{O}(\sqrt{n})$`かかるらしい.
$$ \displaystyle \sqrt{15} = 3.8729833462074168851792653997823996108329217052915908265875737661134830919369790335192873768586735179163022068609496470131895404391636496156798917461212035110687547910134935812839195312288892925658464170280625091931734126598648184554646285513159402626176726405086463004505778106319728809397819251883003553015300107483544380987190144324607755850231048117170906062841573975815829010133303$$ やばそう…
            _人人人人人人人人人人人人人人_
            > 量子コンピュータ「やあ」 <
             ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^ ̄
                        
量子コンピュータなら *一度に多くの演算を行える* ので素因数分解がすぐに終わるはず!

量子で素因数分解 理論編

量子で素因数分解:Shor's Algorithm
### しくみ 1. 素因数分解したい数$N$,自然数$a$を決める `$$\displaystyle N=15$$` `$$\displaystyle a=2$$`
  1. $x$について$a^x \mod N$を求める
$x$$a^x$
01
12
24
$︙$
3. $a^x \mod N$の結果から1つ選び,その$x$を列挙し,周期$r$を求める *古典コンピュータの場合* 列挙した数に対して全探索をかけなければいけない! →量子コンピュータでは全探索をかけるのが得意(この場合$\mathcal{O}(\log n)$の装置で実装可能)
4. $r$について次が成り立つため因数分解して素因数分解ができる `$$\displaystyle a^r \equiv 1 \pmod{N}$$` `$$\displaystyle \Leftrightarrow a^r - 1 \equiv 0 \pmod{N}$$` `$$\displaystyle a^r - 1 = (a^\frac{r}2 - 1)(a^\frac{r}2 + 1) (n\text{は偶数})$$`
とりあえず正しそう

量子で素因数分解 実践編

手順 - 量子を操作する回路を組む - 量子を回路に突っ込んで計算させる - 得られた結果をもとに素因数分解を行う

量子で素因数分解 実践編/回路を組む

今回用いるのは量子ゲート方式というもの ゲートという素子で量子のスピン状態を操作して計算をする
今回は前章の手順1〜4のうち2,3を量子コンピュータで行います. 2. $x$について$a^x \mod N$を求める 3. $a^x \mod N$の結果から1つ選び,その$x$を列挙し,周期$r$を求める
$x$について$a^x \mod N$を求める 古典コンピュータではxを **ループで回してえいっ!** 量子コンピュータでは重ね合わせ状態を実現させることでxを同時に表現可能に
$x$について$a^x \mod N$を求める 量子ゲートのうち$H$($Hadamar$)ゲートを用いると重ね合わせ状態が実現できる 今回は5bit(32通り)を列挙する 5量子bitで同時に表現できる
xについて列挙する回路 完成 ![回路1](./circuit1.png)
$x$について$a^x \mod N$を求める 先程の入力に対して$a^x \mod N$を出力する回路 今回は$N=15, a=2$ 行列式やをごにょごにょする(今回は省略)
$x$について$a^x \mod N$を求める回路 完成
$a^x \mod N$の結果から1つ選び,その$x$を列挙 量子の重ね合わせ: **世界線の重ね合わせ** 量子ビット:観測をすると確率で結果を返す - 前の回路の量子ビットの関係を観測 - →他の量子ビットともつれ合って可能性が消える - $a^x \mod N$側の量子ビットを観測 - →該当する$x$の可能性だけが残る
$a^x \mod N$の結果から1つ選び,その$x$を列挙する回路 完成
$x$の周期$r$を求める $x$について逆フーリエ変換というのをすると求まるらしい. `data[]`を次のように入力してやる. - 5量子ビットの組が $|00000\rangle$である可能性:`data[0]` - 5量子ビットの組が $|00001\rangle$である可能性:`data[1]` →前の回路の出力の形式と同等
逆フーリエ変換は次の回路で実現できる(らしい)
詳しくはGoogle先生に聞いてください.FFTの式を変換するとわかるようです.
回路全体が完成

量子で素因数分解 実践編/量子回路で計算

問題: 量子コンピュータが実用レベルで触れる状況ではない! ふつうの解法:神になる(量子状態を計算で再現する)手法
. ## $\text{Q#}$ Microsoft製量子コンピュータ用言語/エミュレート環境 死ぬほど書きづらい ![WA!](./cf_wrong.png)
## C++でエミュレート 「量子コンピュータじゃなくてよくない…?」
## 手計算 これをやりました.
## なんでそうしたの?バカなの? #### 建前 - 手元で数値を扱うことで量子計算やショアのアルゴリズムをより深く理解できる
#### 本音 - 他の人とかぶりそうなテーマしか思いつかないので奇をてらってそれなりに簡単にできるインパクト強めのテーマがほしかった
## 手計算のルール - 古典コンピュータを計算機として使用禁止 - 回路のとおりにエミュレートする - 乱数にはコイントスをして厳正な乱数を用いる 計算過程は次のURLにて公開しています:[fuwa.dev/shor](https://fuwa.dev/shor) ![QR](https://api.qrserver.com/v1/create-qr-code/?size=150x150&data=fuwa.dev/shor)
計算結果:周期=$4$ 周期は偶数になったので `$$\displaystyle a^r - 1 = (a^\frac{r}2 - 1)(a^\frac{r}2 + 1)$$` にあてはめて `$$\displaystyle 2^4 - 1 = (2^\frac{4}2 - 1)(2^\frac{4}2 + 1)$$` `$$\displaystyle = (2^2-1)(2^2+1)$$` $(2^2-1)$または$(2^2+1)$が約数候補
`$$\displaystyle 2^2-1 = 3$$` `$$\displaystyle 15 \div 3 = 5 \cdots 0$$` 🎉割り切れた!

所感

#### 今回奇をてらってあえて量子シミュレーションを手計算で行った. このテーマが受けがいいのかわからなくて不安(8/28現在)
#### 「神はサイコロを振らない」 量子を司り操った私 $\fallingdotseq$ *神* 神はコインを投げました
## ありがとうございました