ショアのアルゴリズム 手計算ノート
Phase 0
N=15
a=2
(スライドの回路そのまま)
Phase 1
初期状態
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
R(3)
R(2)
H
R(4)
R(3)
R(2)
H
R(5)
R(4)
R(3)
R(2)
x | p |
---|
0 | 1/sqrt(2) |
2 | -1/sqrt(2) i |
H
Revert
x | p |
---|
0 | 1/2 |
8 | -1/2 i |
16 | 1/2 |
24 | -1/2 i |
Phase 4
Try 1
観測
各々の確率
コイントス
1枚め: 裏
2枚め: 裏
選ばれたのは0でした
収束
→分数とみなして分母を推測できないので失敗
Try 2
私は神だ ふふふ,何度でもやり直せるのだよ
観測
コイントス
裏,表
選ばれたのは8でした
収束
試行回数32より
328
分母は832=4と推測できる
(スライドへ戻る)