ショアのアルゴリズム 手計算ノート

Phase 0

N=15
a=2
(スライドの回路そのまま)

Phase 1

初期状態

Hadamarの後

Phase 2

CCN

X

CCN

X * 2

CCN

X

CCN

X * 2

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でした

収束

Phase 3(QFT)

H

R(2)

H

R(3)

R(2)

H

R(4)

R(3)

R(2)

H

R(5)

R(4)

R(3)

R(2)

H

Revert

Phase 4

Try 1

観測

各々の確率

コイントス

1枚め: 裏
2枚め: 裏

選ばれたのは0でした

収束

→分数とみなして分母を推測できないので失敗

Try 2

私は神だ ふふふ,何度でもやり直せるのだよ

観測

コイントス

裏,表
選ばれたのは8でした

収束

試行回数32より
$\frac{8}{32}$

分母は$\frac{32}{8}=4$と推測できる

(スライドへ戻る)