差分

このページの2つのバージョン間の差分を表示します。

この比較画面にリンクする

shor [2020/04/13 10:23] (現在)
行 1: 行 1:
 +# ショアのアルゴリズム 手計算ノート
 +<!--<style>
 +td, th{
 +  border-bottom: 1px solid;
 +}-->
 +</style>
 +## Phase 0
 +N=15
 +a=2
 +(スライドの回路そのまま)
  
 +## Phase 1
 +### 初期状態
 +|  x |   p |
 +| ---:| ---:|
 +|   0 | 1.0 |
 +
 +### Hadamarの後
 +|   x |          p |
 +| ---:| ----------:|
 +|   0 | 1/sqrt(32) |
 +|   1 | 1/sqrt(32) |
 +|   2 | 1/sqrt(32) |
 +|   3 | 1/sqrt(32) |
 +|   4 | 1/sqrt(32) |
 +|   5 | 1/sqrt(32) |
 +|   6 | 1/sqrt(32) |
 +|   7 | 1/sqrt(32) |
 +|   8 | 1/sqrt(32) |
 +|   9 | 1/sqrt(32) |
 +|  10 | 1/sqrt(32) |
 +|  11 | 1/sqrt(32) |
 +|  12 | 1/sqrt(32) |
 +|  13 | 1/sqrt(32) |
 +|  14 | 1/sqrt(32) |
 +|  15 | 1/sqrt(32) |
 +|  16 | 1/sqrt(32) |
 +|  17 | 1/sqrt(32) |
 +|  18 | 1/sqrt(32) |
 +|  19 | 1/sqrt(32) |
 +|  20 | 1/sqrt(32) |
 +|  21 | 1/sqrt(32) |
 +|  22 | 1/sqrt(32) |
 +|  23 | 1/sqrt(32) |
 +|  24 | 1/sqrt(32) |
 +|  25 | 1/sqrt(32) |
 +|  26 | 1/sqrt(32) |
 +|  27 | 1/sqrt(32) |
 +|  28 | 1/sqrt(32) |
 +|  29 | 1/sqrt(32) |
 +|  30 | 1/sqrt(32) |
 +|  31 | 1/sqrt(32) |
 +
 +## Phase 2
 +
 +### CCN
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   0 | 1/sqrt(32) |
 +|   1 |   0 | 1/sqrt(32) |
 +|   2 |   0 | 1/sqrt(32) |
 +|   3 |   8 | 1/sqrt(32) |
 +|   4 |   0 | 1/sqrt(32) |
 +|   5 |   0 | 1/sqrt(32) |
 +|   6 |   0 | 1/sqrt(32) |
 +|   7 |   8 | 1/sqrt(32) |
 +|   8 |   0 | 1/sqrt(32) |
 +|   9 |   0 | 1/sqrt(32) |
 +|  10 |   0 | 1/sqrt(32) |
 +|  11 |   8 | 1/sqrt(32) |
 +|  12 |   0 | 1/sqrt(32) |
 +|  13 |   0 | 1/sqrt(32) |
 +|  14 |   0 | 1/sqrt(32) |
 +|  15 |   8 | 1/sqrt(32) |
 +|  16 |   0 | 1/sqrt(32) |
 +|  17 |   0 | 1/sqrt(32) |
 +|  18 |   0 | 1/sqrt(32) |
 +|  19 |   8 | 1/sqrt(32) |
 +|  20 |   0 | 1/sqrt(32) |
 +|  21 |   0 | 1/sqrt(32) |
 +|  22 |   0 | 1/sqrt(32) |
 +|  23 |   8 | 1/sqrt(32) |
 +|  24 |   0 | 1/sqrt(32) |
 +|  25 |   0 | 1/sqrt(32) |
 +|  26 |   0 | 1/sqrt(32) |
 +|  27 |   8 | 1/sqrt(32) |
 +|  28 |   0 | 1/sqrt(32) |
 +|  29 |   0 | 1/sqrt(32) |
 +|  30 |   0 | 1/sqrt(32) |
 +|  31 |   8 | 1/sqrt(32) |
 +
 +### X
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   0 | 1/sqrt(32) |
 +|   1 |   0 | 1/sqrt(32) |
 +|   2 |   8 | 1/sqrt(32) |
 +|   3 |   0 | 1/sqrt(32) |
 +|   4 |   0 | 1/sqrt(32) |
 +|   5 |   0 | 1/sqrt(32) |
 +|   6 |   8 | 1/sqrt(32) |
 +|   7 |   0 | 1/sqrt(32) |
 +|   8 |   0 | 1/sqrt(32) |
 +|   9 |   0 | 1/sqrt(32) |
 +|  10 |   8 | 1/sqrt(32) |
 +|  11 |   0 | 1/sqrt(32) |
 +|  12 |   0 | 1/sqrt(32) |
 +|  13 |   0 | 1/sqrt(32) |
 +|  14 |   8 | 1/sqrt(32) |
 +|  15 |   0 | 1/sqrt(32) |
 +|  16 |   0 | 1/sqrt(32) |
 +|  17 |   0 | 1/sqrt(32) |
 +|  18 |   8 | 1/sqrt(32) |
 +|  19 |   0 | 1/sqrt(32) |
 +|  20 |   0 | 1/sqrt(32) |
 +|  21 |   0 | 1/sqrt(32) |
 +|  22 |   8 | 1/sqrt(32) |
 +|  23 |   0 | 1/sqrt(32) |
 +|  24 |   0 | 1/sqrt(32) |
 +|  25 |   0 | 1/sqrt(32) |
 +|  26 |   8 | 1/sqrt(32) |
 +|  27 |   0 | 1/sqrt(32) |
 +|  28 |   0 | 1/sqrt(32) |
 +|  29 |   0 | 1/sqrt(32) |
 +|  30 |   8 | 1/sqrt(32) |
 +|  31 |   0 | 1/sqrt(32) |
 +
 +### CCN
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   0 | 1/sqrt(32) |
 +|   1 |   0 | 1/sqrt(32) |
 +|   2 |   8 | 1/sqrt(32) |
 +|   3 |   4 | 1/sqrt(32) |
 +|   4 |   0 | 1/sqrt(32) |
 +|   5 |   0 | 1/sqrt(32) |
 +|   6 |   8 | 1/sqrt(32) |
 +|   7 |   4 | 1/sqrt(32) |
 +|   8 |   0 | 1/sqrt(32) |
 +|   9 |   0 | 1/sqrt(32) |
 +|  10 |   8 | 1/sqrt(32) |
 +|  11 |   4 | 1/sqrt(32) |
 +|  12 |   0 | 1/sqrt(32) |
 +|  13 |   0 | 1/sqrt(32) |
 +|  14 |   8 | 1/sqrt(32) |
 +|  15 |   4 | 1/sqrt(32) |
 +|  16 |   0 | 1/sqrt(32) |
 +|  17 |   0 | 1/sqrt(32) |
 +|  18 |   8 | 1/sqrt(32) |
 +|  19 |   4 | 1/sqrt(32) |
 +|  20 |   0 | 1/sqrt(32) |
 +|  21 |   0 | 1/sqrt(32) |
 +|  22 |   8 | 1/sqrt(32) |
 +|  23 |   4 | 1/sqrt(32) |
 +|  24 |   0 | 1/sqrt(32) |
 +|  25 |   0 | 1/sqrt(32) |
 +|  26 |   8 | 1/sqrt(32) |
 +|  27 |   4 | 1/sqrt(32) |
 +|  28 |   0 | 1/sqrt(32) |
 +|  29 |   0 | 1/sqrt(32) |
 +|  30 |   8 | 1/sqrt(32) |
 +|  31 |   4 | 1/sqrt(32) |
 +
 +### X * 2
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   4 | 1/sqrt(32) |
 +|   1 |   8 | 1/sqrt(32) |
 +|   2 |   0 | 1/sqrt(32) |
 +|   3 |   0 | 1/sqrt(32) |
 +|   4 |   4 | 1/sqrt(32) |
 +|   5 |   8 | 1/sqrt(32) |
 +|   6 |   0 | 1/sqrt(32) |
 +|   7 |   0 | 1/sqrt(32) |
 +|   8 |   4 | 1/sqrt(32) |
 +|   9 |   8 | 1/sqrt(32) |
 +|  10 |   0 | 1/sqrt(32) |
 +|  11 |   0 | 1/sqrt(32) |
 +|  12 |   4 | 1/sqrt(32) |
 +|  13 |   8 | 1/sqrt(32) |
 +|  14 |   0 | 1/sqrt(32) |
 +|  15 |   0 | 1/sqrt(32) |
 +|  16 |   4 | 1/sqrt(32) |
 +|  17 |   8 | 1/sqrt(32) |
 +|  18 |   0 | 1/sqrt(32) |
 +|  19 |   0 | 1/sqrt(32) |
 +|  20 |   4 | 1/sqrt(32) |
 +|  21 |   8 | 1/sqrt(32) |
 +|  22 |   0 | 1/sqrt(32) |
 +|  23 |   0 | 1/sqrt(32) |
 +|  24 |   4 | 1/sqrt(32) |
 +|  25 |   8 | 1/sqrt(32) |
 +|  26 |   0 | 1/sqrt(32) |
 +|  27 |   0 | 1/sqrt(32) |
 +|  28 |   4 | 1/sqrt(32) |
 +|  29 |   8 | 1/sqrt(32) |
 +|  30 |   0 | 1/sqrt(32) |
 +|  31 |   0 | 1/sqrt(32) |
 +
 +### CCN
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   4 | 1/sqrt(32) |
 +|   1 |   8 | 1/sqrt(32) |
 +|   2 |   0 | 1/sqrt(32) |
 +|   3 |   2 | 1/sqrt(32) |
 +|   4 |   4 | 1/sqrt(32) |
 +|   5 |   8 | 1/sqrt(32) |
 +|   6 |   0 | 1/sqrt(32) |
 +|   7 |   2 | 1/sqrt(32) |
 +|   8 |   4 | 1/sqrt(32) |
 +|   9 |   8 | 1/sqrt(32) |
 +|  10 |   0 | 1/sqrt(32) |
 +|  11 |   2 | 1/sqrt(32) |
 +|  12 |   4 | 1/sqrt(32) |
 +|  13 |   8 | 1/sqrt(32) |
 +|  14 |   0 | 1/sqrt(32) |
 +|  15 |   2 | 1/sqrt(32) |
 +|  16 |   4 | 1/sqrt(32) |
 +|  17 |   8 | 1/sqrt(32) |
 +|  18 |   0 | 1/sqrt(32) |
 +|  19 |   2 | 1/sqrt(32) |
 +|  20 |   4 | 1/sqrt(32) |
 +|  21 |   8 | 1/sqrt(32) |
 +|  22 |   0 | 1/sqrt(32) |
 +|  23 |   2 | 1/sqrt(32) |
 +|  24 |   4 | 1/sqrt(32) |
 +|  25 |   8 | 1/sqrt(32) |
 +|  26 |   0 | 1/sqrt(32) |
 +|  27 |   2 | 1/sqrt(32) |
 +|  28 |   4 | 1/sqrt(32) |
 +|  29 |   8 | 1/sqrt(32) |
 +|  30 |   0 | 1/sqrt(32) |
 +|  31 |   0 | 1/sqrt(32) |
 +
 +### X
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   8 | 1/sqrt(32) |
 +|   1 |   4 | 1/sqrt(32) |
 +|   2 |   2 | 1/sqrt(32) |
 +|   3 |   0 | 1/sqrt(32) |
 +|   4 |   8 | 1/sqrt(32) |
 +|   5 |   4 | 1/sqrt(32) |
 +|   6 |   2 | 1/sqrt(32) |
 +|   7 |   0 | 1/sqrt(32) |
 +|   8 |   8 | 1/sqrt(32) |
 +|   9 |   4 | 1/sqrt(32) |
 +|  10 |   2 | 1/sqrt(32) |
 +|  11 |   0 | 1/sqrt(32) |
 +|  12 |   8 | 1/sqrt(32) |
 +|  13 |   4 | 1/sqrt(32) |
 +|  14 |   2 | 1/sqrt(32) |
 +|  15 |   0 | 1/sqrt(32) |
 +|  16 |   8 | 1/sqrt(32) |
 +|  17 |   4 | 1/sqrt(32) |
 +|  18 |   2 | 1/sqrt(32) |
 +|  19 |   0 | 1/sqrt(32) |
 +|  20 |   8 | 1/sqrt(32) |
 +|  21 |   4 | 1/sqrt(32) |
 +|  22 |   2 | 1/sqrt(32) |
 +|  23 |   0 | 1/sqrt(32) |
 +|  24 |   8 | 1/sqrt(32) |
 +|  25 |   4 | 1/sqrt(32) |
 +|  26 |   2 | 1/sqrt(32) |
 +|  27 |   0 | 1/sqrt(32) |
 +|  28 |   8 | 1/sqrt(32) |
 +|  29 |   4 | 1/sqrt(32) |
 +|  30 |   2 | 1/sqrt(32) |
 +|  31 |   0 | 1/sqrt(32) |
 +
 +### CCN
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   8 | 1/sqrt(32) |
 +|   1 |   4 | 1/sqrt(32) |
 +|   2 |   2 | 1/sqrt(32) |
 +|   3 |   1 | 1/sqrt(32) |
 +|   4 |   8 | 1/sqrt(32) |
 +|   5 |   4 | 1/sqrt(32) |
 +|   6 |   2 | 1/sqrt(32) |
 +|   7 |   1 | 1/sqrt(32) |
 +|   8 |   8 | 1/sqrt(32) |
 +|   9 |   4 | 1/sqrt(32) |
 +|  10 |   2 | 1/sqrt(32) |
 +|  11 |   1 | 1/sqrt(32) |
 +|  12 |   8 | 1/sqrt(32) |
 +|  13 |   4 | 1/sqrt(32) |
 +|  14 |   2 | 1/sqrt(32) |
 +|  15 |   1 | 1/sqrt(32) |
 +|  16 |   8 | 1/sqrt(32) |
 +|  17 |   4 | 1/sqrt(32) |
 +|  18 |   2 | 1/sqrt(32) |
 +|  19 |   1 | 1/sqrt(32) |
 +|  20 |   8 | 1/sqrt(32) |
 +|  21 |   4 | 1/sqrt(32) |
 +|  22 |   2 | 1/sqrt(32) |
 +|  23 |   1 | 1/sqrt(32) |
 +|  24 |   8 | 1/sqrt(32) |
 +|  25 |   4 | 1/sqrt(32) |
 +|  26 |   2 | 1/sqrt(32) |
 +|  27 |   1 | 1/sqrt(32) |
 +|  28 |   8 | 1/sqrt(32) |
 +|  29 |   4 | 1/sqrt(32) |
 +|  30 |   2 | 1/sqrt(32) |
 +|  31 |   1 | 1/sqrt(32) |
 +
 +### X * 2
 +|   x |   y |          p |
 +| ---:| ---:| ----------:|
 +|   0 |   1 | 1/sqrt(32) |
 +|   1 |   2 | 1/sqrt(32) |
 +|   2 |   4 | 1/sqrt(32) |
 +|   3 |   8 | 1/sqrt(32) |
 +|   4 |   1 | 1/sqrt(32) |
 +|   5 |   2 | 1/sqrt(32) |
 +|   6 |   4 | 1/sqrt(32) |
 +|   7 |   8 | 1/sqrt(32) |
 +|   8 |   1 | 1/sqrt(32) |
 +|   9 |   2 | 1/sqrt(32) |
 +|  10 |   4 | 1/sqrt(32) |
 +|  11 |   8 | 1/sqrt(32) |
 +|  12 |   1 | 1/sqrt(32) |
 +|  13 |   2 | 1/sqrt(32) |
 +|  14 |   4 | 1/sqrt(32) |
 +|  15 |   8 | 1/sqrt(32) |
 +|  16 |   1 | 1/sqrt(32) |
 +|  17 |   2 | 1/sqrt(32) |
 +|  18 |   4 | 1/sqrt(32) |
 +|  19 |   8 | 1/sqrt(32) |
 +|  20 |   1 | 1/sqrt(32) |
 +|  21 |   2 | 1/sqrt(32) |
 +|  22 |   4 | 1/sqrt(32) |
 +|  23 |   8 | 1/sqrt(32) |
 +|  24 |   1 | 1/sqrt(32) |
 +|  25 |   2 | 1/sqrt(32) |
 +|  26 |   4 | 1/sqrt(32) |
 +|  27 |   8 | 1/sqrt(32) |
 +|  28 |   1 | 1/sqrt(32) |
 +|  29 |   2 | 1/sqrt(32) |
 +|  30 |   4 | 1/sqrt(32) |
 +|  31 |   8 | 1/sqrt(32) |
 +
 +## Phase 2
 +### 観測
 +#### 確率
 +1: (1/sqrt(32))^2 * 8 = 1/4
 +2: (1/sqrt(32))^2 * 8 = 1/4
 +4: (1/sqrt(32))^2 * 8 = 1/4
 +8: (1/sqrt(32))^2 * 8 = 1/4
 +
 +#### コイントス
 +1枚め: 表
 +2枚め: 裏
 +
 +選ばれたのは4でした
 +
 +#### 収束
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(8) |
 +|   6 | 1/sqrt(8) |
 +|  10 | 1/sqrt(8) |
 +|  14 | 1/sqrt(8) |
 +|  18 | 1/sqrt(8) |
 +|  22 | 1/sqrt(8) |
 +|  26 | 1/sqrt(8) |
 +|  30 | 1/sqrt(8) |
 +
 +## Phase 3(QFT)
 +### H
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(4) |
 +|   6 | 1/sqrt(4) |
 +|  10 | 1/sqrt(4) |
 +|  14 | 1/sqrt(4) |
 +
 +### R(2)
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(4) |
 +|   6 | 1/sqrt(4) |
 +|  10 | 1/sqrt(4) |
 +|  14 | 1/sqrt(4) |
 +
 +### H
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(2) |
 +|   6 | 1/sqrt(2) |
 +
 +### R(3)
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(2) |
 +|   6 | 1/sqrt(2) |
 +
 +### R(2)
 +|   x |         p |
 +| ---:| ---------:|
 +|   2 | 1/sqrt(2) |
 +|   6 | 1/sqrt(2) |
 +
 +### H
 +|   x |   p |
 +| ---:| ---:|
 +|   2 |   1 |
 +
 +### R(4)
 +|   x |   p |
 +| ---:| ---:|
 +|   2 |   1 |
 +
 +### R(3)
 +|   x |   p |
 +| ---:| ---:|
 +|   2 |   1 |
 +
 +### R(2)
 +|   x |   p |
 +| ---:| ---:|
 +|   2 |   1 |
 +
 +### H
 +|   x |          p |
 +| ---:| ----------:|
 +|   0 |  1/sqrt(2) |
 +|   2 | -1/sqrt(2) |
 +
 +### R(5)
 +|   x |          p |
 +| ---:| ----------:|
 +|   0 |  1/sqrt(2) |
 +|   2 | -1/sqrt(2) |
 +
 +### R(4)
 +|   x |          p |
 +| ---:| ----------:|
 +|   0 |  1/sqrt(2) |
 +|   2 | -1/sqrt(2) |
 +
 +### R(3)
 +|   x |          p |
 +| ---:| ----------:|
 +|   0 |  1/sqrt(2) |
 +|   2 | -1/sqrt(2) |
 +
 +### R(2)
 +|   x |            p |
 +| ---:| ------------:|
 +|   0 |    1/sqrt(2) |
 +|   2 | -1/sqrt(2) i |
 +
 +### H
 +|   x |      p |
 +| ---:| ------:|
 +|   0 |    1/2 |
 +|   1 |    1/2 |
 +|   2 | -1/2 i |
 +|   3 | -1/2 i |
 +
 +### Revert
 +|   x |      p |
 +| ---:| ------:|
 +|   0 |    1/2 |
 +|   8 | -1/2 i |
 +|  16 |    1/2 |
 +|  24 | -1/2 i |
 +
 +
 +## Phase 4
 +### Try 1
 +#### 観測
 +##### 各々の確率
 +|   x |   p |
 +| ---:| ---:|
 +|   0 | 1/4 |
 +|   8 | 1/4 |
 +|  16 | 1/4 |
 +|  24 | 1/4 |
 +
 +##### コイントス
 +1枚め: 裏
 +2枚め: 裏
 +
 +選ばれたのは0でした
 +
 +##### 収束
 +|   x |   p |
 +| ---:| ---:|
 +|   0 |   1 |
 +
 +→分数とみなして分母を推測できないので失敗
 +
 +### Try 2
 +私は神だ ふふふ,何度でもやり直せるのだよ
 +#### 観測
 +##### コイントス
 +裏,表
 +選ばれたのは8でした
 +##### 収束
 +|   x |   p |
 +| ---:| ---:|
 +|   8 |   1 |
 +
 +試行回数32より
 +$\frac{8}{32}$
 +
 +分母は$\frac{32}{8}=4$と推測できる
 +
 +(スライドへ戻る)
 +
 +<script>$('table').addClass('table')</script>
最終更新: 2020/04/13 10:23