■ 証明・計算

（１）量子アルゴリズム編

〔２キュービットの任意の状態がどれかの基底に掃き出せることの証明〕

２キュービットの任意の状態Σ_a,b={0,1}C_ab|a>|b>を，基底の一つである|1>|1>に変換するアルゴリズムとその量子回路を考える。ここで，Σ_a,b={0,1}|C_ab|² = 1.

Σ_a,b={0,1}C_ab|a>|b> → |1>|1>

基底を２つのグループ|0>|0>,|0>|1>と|1>|0>,|1>|1>に分けて考える。第一ビットを制御ビット，次を標的ビットとする制御－Ｕ₁₂を用いて，

Σ_a,b={0,1}C_ab|a>|b> →
C₀₀|0>|0> + C₀₁|0>|1> + √(|C₁₀|²+|C₁₁|²)|1>|1>

と|1>|0>基底を掃き出すことができる。

（証明）制御－Ｕ₁₂の変換後は，|1>|0>基底と|1>|1>基底の係数がそれぞれ，
C₁₀|1>|0> → (C₁₀u₁₁ + C₁₁u₁₂)|1>|0>
C₁₁|1>|1> → (C₁₀u₂₁ + C₁₁u₂₂)|1>|1>

と変換され，|1>|0>基底の係数C₁₀u₁₁ + C₁₁u₁₂を零とするようにu₁₁とu₁₂を選ぶことができるからである。ここに，u_nm(n,m=1,2)は制御－Ｕ₁₂の第三，第四行・列成分であり，ユニタリー性により
|u₁₁|² + |u₁₂|² = 1
|u₂₁|² + |u₂₂|² = 1
u₁₁u₂₁^* + u₁₂u₂₂^* = 0
である。従って，
C₁₀u₁₁ + C₁₁u₁₂ = 0
であることから， u₁₁ = - (C₁₁/C₁₀) * u₁₂
= - C₁₁/√(|C₁₀|²+|C₁₁|²)
u₁₂ = C₁₀/√(|C₁₀|²+|C₁₁|²)

基底|1>|1>の係数をＹとすると，
Ｙ = C₁₀u₂₁ + C₁₁u₂₂
u₂₁/ u₂₂ = －u₁₂^*/u₁₁^*= C₁₀^*/C₁₁^*より，
u₂₁ = C₁₀^* * Y /(|C₁₀|²+|C₁₁|²)
u₂₂ = C₁₁^* * Y /(|C₁₀|²+|C₁₁|²)

|u₂₁|² + |u₂₂|² = 1 に代入して，

｜Ｙ｜²/(|C₁₀|²+|C₁₁|²) = 1
故に，｜Ｙ｜ = √(|C₁₀|²+|C₁₁|²)

Ｙ = |Ｙ|e^iφ
= √(|C₁₀|²+|C₁₁|²)e^iφ

となり，位相φは不定であるが全体にかかるので影響はない。

次に，第一ビットにNOTを掛けたものに同様な操作を施すことにより，|0>|0>基底を掃き出すことができ，
√(|C₀₀|²+|C₀₁|²)|0>|1> + √(|C₁₀|²+|C₁₁|²)|1>|1>

に変換できる。最後に，第2ビットを制御ビット，第1ビットを標的ビットとする制御－Ｖ₂₁を施すことにより|0>|1>基底を掃き出すことができる。結論を繰り返すと，

Σ_a,b={0,1}C_ab|a>|b> → |1>|1>

が制御NOTとNOTで作られた制御－U，制御－Vにより達成されるのである。同様にして，
Σ_a,b={0,1}C_ab|a>|b> → |0>|0>

Σ_a,b={0,1}C_ab|a>|b> → |0>|1>

Σ_a,b={0,1}C_ab|a>|b> → |1>|0>

も達成できる。
Q.E.D

〔Ｓ’がＳに等しいことの証明〕

Ｓ’の構成要素である，
Ｇ(Ψ₀)^-1Ｘ₀Ｇ(Ψ₀)
の働きを考える。Ｇ(Ψ₀)の定義により，
Ｇ(Ψ₀)|Ψ₀> = |0>であり，
Ｘ₀|0> = e ^iσ₀|0>
であるから，
Ｘ₀Ｇ(Ψ₀)|Ψ₀> = e ^iσ₀Ｇ(Ψ₀)|Ψ₀>

は明らかである。両辺に左からＧ(Ψ₀)^-1を作用させ，
Ｇ(Ψ₀)^-1Ｘ₀Ｇ(Ψ₀)|Ψ₀> = e ^iσ₀|Ψ₀>

を得る。ｎ≠0の|n>に関しては，
Ｇ(Ψ₀)^-1Ｘ₀Ｇ(Ψ₀)|Ψ_n>
= Ｇ(Ψ₀)^-1(e ^iσ₀|0><0| + |1><1| + |2><2| + |3><3|)Ｇ(Ψ₀)|Ψ_n>
= Ｇ(Ψ₀)^-1(|0><0| + |1><1| + |2><2| + |3><3|)Ｇ(Ψ₀)|Ψ_n>
= Ｇ(Ψ₀)^-1Ｇ(Ψ₀)|Ψ_n>
= |Ψ_n>

ここに，<0|Ｇ(Ψ₀)|Ψ₀> = 1であるから，
<0|Ｇ(Ψ₀)|Ψ_n> = 0 （ｎ≠0）であることを用いた（従って，黄色の|0><0| の部分はダミーである）。

以上より，一般に次のことが成り立つ。

Ｇ(Ψ_n)^-1Ｘ_nＧ(Ψ_n)|Ψ_n> = e ^iσ_n|Ψ_n>
Ｇ(Ψ_m)^-1Ｘ_mＧ(Ψ_m)|Ψ_n> = |Ψ_n> (ｎ≠m)

このことは，Ｓ'を|Ψ_n>に作用させる場合，積Π_m=0³Ｇ(Ψ_m)^-1Ｘ_mＧ(Ψ_m)のうち，n = m のところが位相e ^iσ_nを与え，他は恒等変換として働くことを示している。即ち，

Ｓ’|Ψ_m> = e ^iσ_m|Ψ_m>

であり，固有状態でＳ'を展開すれば，

Ｓ’ = Σ_m=0³e ^iσ_m|Ψ_m><Ψ_m|

と書くことができる。これはＳと同じものである。

Q.E.D.

〔フェルマーの小定理の証明〕

素数ｐを法とする体系Ｚ_pで，０以外の数ａを一つ定める。１，２，３，… ｐ-１の全てにａをかけるとａ，２ａ，３ａ，…（ｐ-１）ａとなるが，これらは全て相異なり，しかも０ではない。従って，これらは１，２，３，… ｐ-１を並べ替えたものであり，全部かければ１，２，３，… ｐ-１の積と同じはずである。即ち，

ａ^p-1(p - 1)! = (p - 1)!    mod    p

しかし，(p - 1)!は素数ｐでは割り切れないから，両辺を(p - 1)!で割って，

ａ^p-1 = １   Mod   ｐ

である。 Q.E.D. （２００２年５月５日；第一版 Copyright 寒泉）