三人寄れば文殊の知恵符号

こんにちは。Kumaです。

先日、とても素晴らしい記事が鯵坂もっちょ氏により公開されました。
www.ajimatics.com

私はこの記事を見た時に、別の側面で捉えました。
それは、

「三人寄れば文殊の知恵は誤り訂正符号である」

ということです。

三人寄れば文殊の知恵、n人寄れば・・・・

鯵坂もっちょ氏のブログ通り、
確率 pで正解出来る人が3人居たとし、多数決で全体の回答を決める時に「三人寄れば文殊の知恵」が成立します。*1
n人寄れば・・・・を考えると、全体の回答が正解となる確率はどんどん1に近づきます。


三人寄れば文殊の知恵 の符号的捉え方

簡単のため、正解を数字の1、誤りを数字の0で表現します。
そして、以下のような問題を考えます。
(図をみるとわかりやすいかと思います)

  1. 正解を知っている人 が1人いるとします。[1]
  2. この人をコピーして3人にします。[111]
  3. 確率1-pで1を0に反転する操作 を3人にそれぞれ行います。例として[101]
  4. 多数決で全体の回答を決めます。[101]の場合は[111]となります。

f:id:phymath1991:20190511020447p:plain
三人寄れば文殊の知恵 の別の捉え方

これは誤り訂正符号とその復号になっています。つまり、

1. 正解を知っている人 が1人いるとします。[1] 
→ 守りたい情報を決めます。この場合は1を守りたい。 (ここで0を選んでもよいわけです)
2. この人をコピーして3人にします。[111] 
→ 守りたい情報を3倍の長さの情報に埋め込みます。(”符号化”)
3. 確率 1-pで1を0に反転する操作 を3人にそれぞれ行います。例として[101]
→ 0/1反転誤りが発生してしまいました。
4. 多数決で全体の回答を決めます。[101]の場合は[111]となります。 
→ 誤りを多数決で元に戻します。("復号")


守りたい情報を、より長い系列に埋め込むことで冗長性を取っているわけです。
冗長性があるので、一部が破壊されても元の系列が推定できる。この仕組を 誤り訂正符号 といいます。*2
この符号を
「3人寄れば文殊の知恵符号」 とでも名付けましょう!!

三人寄れば文殊の知恵符号 を図で見る

図で見るとこんな感じ。*3

f:id:phymath1991:20190511012440p:plain
符号化の過程
f:id:phymath1991:20190511012510p:plain
復号の過程

三人寄れば文殊の知恵符号 の性質

三人寄れば文殊の知恵符号 は、実は符号理論では有名な 反復復号 と呼ばれるものに相当します。

反復符号 - Wikipedia

3人寄れば文殊の知恵符号 は  (3,1) 反復符号であり、n人寄れば文殊の知恵符号は (n,1)反復符号です。
復号方法としては 多数決論理復号法 を採用したことになります。*4

一般の符号において、 (n,k) 符号というのは元の情報量が k bit で、冗長化した後の情報量が n bitであるものを指します。
 k桁の2進数から n桁の2進数への写像で規定される ともいえます。

反復符号は 完全符号 と呼ばれる性質を満たします。

ハミング限界 - Wikipedia
ハミング限界(ハミングげんかい、英: Hamming bound)は、符号(線型符号とは限らない)のパラメータの限界値を指す。球充填の限界を情報理論の観点で言い直したものと言える。ハミング限界に従った符号を「完全符号; perfect code」と呼ぶ。

完全符号というのはとてもカッコイイ名前ですが、完全符号だからといってそれだけで誤り訂正符号としての性能が良いとかってことはないです。
他にもいくつか条件があり、それを複数満たすものが 「良い符号」 と言われます。*5

n人寄れば文殊の知恵符号 の極限とShannonの定理

 n人寄れば文殊の知恵符号 を考えましょう。 nを無限大に飛ばすと、明らかに正答率は1に近づきます。
しかし たかだか1 bitの情報を守るために、 \infty bit の情報を使うというのはどうも効率が悪い気がします。

正答率を1に近づけるには  \infty 人寄れば文殊の知恵符号 にするしかないのでしょうか?
 (n,1)符号ではなく (n, k > 2)符号を考えた場合にも、やはりその効率 \frac{k}{n} は0にする他にないのでしょうか?

段々、難しくなってきたと思います。このあたりがまさに 符号理論の真髄 の一端です。
情報理論の始祖である C.E.Shannon は驚くべき結果を示しています。*6

与えられた誤り率 1-pの通信路に対して、ある数 C(p)が存在する。
符号の効率 \frac{k}{n} C(p)未満でありさえすれば、いくらでも誤り率を小さくする うまい符号 が存在する。

つまり、効率を0にまで落とさなくても、 C(p)未満にしておけば、誤りを完全に無くすような符号/復号が必ず構成出来る ということです。*7
 C(p)は誤りなく転送可能な情報量の上限といえますから、 通信路容量 と呼ばれます。*8
逆に、いかなる符号をもってしても通信路容量を超える誤りなし転送は不可能です。

話は尽きませんが、今回はこのあたりでおしまいです。
興味を持たれた方はぜひ、甘利先生の情報理論などを手にとって見て下さい。(この本は、私の知る限りでは最も分かりやすく気軽に読める符号の本です)
www.amazon.co.jp

*1:正解率が p < 1/2 の時は「船頭多くして船山に登る」となりますが。

*2:身近なところではQRコードなどに使われています。符号のないデジタルシステムは無いと言っていいでしょう

*3:なぜ符号化した系列を立方体の頂点に配置したのかには、意味があります。気になる方は ハミング距離 や 符号空間 で調べてみて下さい。

*4:わざわざ 「多数決論理復号法 を採用した」 と書いたということは、他の復号方法もあるというわけです。 符号理論において、一般的な復号方法は 「最小距離復号(Minimum Distance Decoding)」です。反復符号の場合、両者は同じ結果を与えますが。

*5:QRコードに使われている リードソロモン符号 は良い符号の代表です

*6:かなり雑な書き方をしているのはご容赦下さい

*7:Shannon の証明ではランダム符号というものが使われています。これは復号に指数時間かかるために実用上は役に立ちません。具体的な符号の構成方法についてShannonの定理は何も教えてくれません。それでも、実際にランダム符号に非常によく漸近するような符号はいくつも見つかっています

*8:ちなみにKumaは光の通信路に対して通信路容量を調べたりもしています

(箸休め) 量子計算について学んでみたいこと

こんにちは。Kumaです。

番外編として、量子計算について私が学んでみたい課題について書いてみます。
つまり「XXの理解を目指して、やってます」ということですね。
知りたいことはいっぱいあるのですが、基本素人スタートなので先は長そうです。

量子計算の速さ

  • 量子計算は"なぜ(Why)"速いのか

重ね合わせやエンタングルメントがポイントなことには違いないが、それが「どこに」「どれぐらい」効いているかはアルゴリズム次第

  • 量子計算は"どう(How)"速いのか

速い ってなんだろう。Groverのアルゴリズムは”速い”だろうが、オラクルがないと実行不能という意味で工学者にとっては”速い”とは言い難い

  • 量子計算に出来ないことはなんなのか

量子計算HWの実装

  • HWに求められる要件はなんなのか。

スケーラビリティ、量子誤りの低さ、計算可能時間etc ?

  • 分散型量子計算の可能性。何が必要か。

おそらく一度に大規模な量子ビットのHWを作るのはきついので、マルチコアっぽく複数の小規模な量子ビットのHWを作って並列計算させるほうが良いはず

量子誤り訂正符号

  • 古典符号との設計や仕組みの違い

量子情報と古典情報の違いはかなり効くのでは? 例えばスタビライズされているものしか使えない?とか。
噂ではFEC閾値(ウォーターフォールするFEC前BER)を下げるのが大変らしい。
(他方、古典符号だと 10^{-2}のBERでウォーターフォールを起こさせることは現代では容易)

  • 量子シャノンリミット

何らかの意味で”量子化”された相互情報量がやはり限界なのか。違うのか。

  • 何が”良い”量子符号なのか

古典符号ならば シャノン限界への近さ、符号長、復号の計算量 etc

  • 古典の”良い符号”の量子化も”良い”符号なのか

例えばリードソロモン、ターボ畳み込み符号、LDPC、Polarの量子化は”良い符号”なのか

量子計算理論(森前 著) の演習問題を解く part10

こんにちは。Kumaです。

最近、量子コンピュータについて勉強しています。
今回は有名な以下の本の演習問題について、解答が載っていないので一部書いてみたいとおもいます。
f:id:phymath1991:20181224165540p:plain
量子計算理論 量子コンピュータの原理 | 森北出版株式会社

本書の勉強会が大阪で開催されているそうです。
演習問題の解答も一部公開中です。(私の我流よりも少し見通しの良い解き方になっていますね)
大阪近郊の方はぜひ参加してみてください。
sites.google.com


今回はpp.40- です。

pp.40 クリフォード演算子(2)



 \begin{eqnarray*}
 &(&1) R_{\frac{\pi}{4}} X R^{\dagger}_{\frac{\pi}{4}} = \frac{X+Y}{2} = e^{-i \frac{\pi}{4} } R_{\frac{\pi}{2}} X \\
 &(&2) R_{\frac{\pi}{4}} Y R^{\dagger}_{\frac{\pi}{4}} = \frac{-X+Y}{2} = e^{-i \frac{\pi}{4} } R_{\frac{\pi}{2}} Y \\
 &(&3) R_{\frac{\pi}{4}} Z R^{\dagger}_{\frac{\pi}{4}} = Z
 \end{eqnarray*}
を示せ。
ここに

 \begin{eqnarray*}
 X &=& | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 | \\
 Y &=& i | 1 \rangle \langle 0 | -i  | 0 \rangle \langle 1 | \\
 Z &=& | 0 \rangle \langle 0 | -  | 1 \rangle \langle 1 | \\
 R_{\frac{\pi}{4}} &=&  | 0 \rangle \langle 0 | +  e^{j \frac{\pi}{4}} | 1 \rangle \langle 1 |  \\
 \end{eqnarray*}
である。

  • 解答


 \begin{eqnarray*}
 R_{\frac{\pi}{4}}(  X R^{\dagger}_{\frac{\pi}{4}}  ) &=&  R_{\frac{\pi}{4}}( | 0 \rangle \langle 1 | +  | 1 \rangle \langle 0 | )( | 0 \rangle \langle 0 | +  e^{-i \frac{\pi}{4}} | 1 \rangle \langle 1 | ) \\
&=& R_{\frac{\pi}{4}} (e^{-i \frac{\pi}{4}} | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 |) \\
&=& (| 0 \rangle \langle 0 | +  e^{i \frac{\pi}{4}} | 1 \rangle \langle 1 | ) (e^{-i \frac{\pi}{4}} | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 |) \\
&=& e^{-i \frac{\pi}{4}}| 0 \rangle \langle 1 | + e^{i \frac{\pi}{4}}| 1 \rangle \langle 0 | \\
&=& ( \frac{1}{\sqrt{2}} - i \frac{1}{\sqrt{2}} ) | 0 \rangle \langle 1 | + ( \frac{1}{\sqrt{2}} + i \frac{1}{\sqrt{2}} ) | 1 \rangle \langle 0 | \\ 
&=& \frac{1}{\sqrt{2}}( | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 |  ) + \frac{1}{\sqrt{2}}( i | 1 \rangle \langle 0 | - i | 0 \rangle \langle 1 |  ) \\
&=&  \frac{X+Y}{2} 
 \end{eqnarray*}
となり第一の等式が示された。第二の等式については以下の通り。


 \begin{eqnarray*}
 R_{\frac{\pi}{4}}(  X R^{\dagger}_{\frac{\pi}{4}}  ) &=&  R_{\frac{\pi}{4}}( | 0 \rangle \langle 1 | +  | 1 \rangle \langle 0 | )( | 0 \rangle \langle 0 | +  e^{-i \frac{\pi}{4}} | 1 \rangle \langle 1 | ) \\
&=& R_{\frac{\pi}{4}} (e^{-i \frac{\pi}{4}} | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 |) \\
&=& (| 0 \rangle \langle 0 | +  e^{i \frac{\pi}{4}} | 1 \rangle \langle 1 | ) (e^{-i \frac{\pi}{4}} | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 |) \\
&=& e^{-i \frac{\pi}{4}}| 0 \rangle \langle 1 | + e^{i \frac{\pi}{4}}| 1 \rangle \langle 0 | \\
&=& e^{-i \frac{\pi}{4}}|( | 0 \rangle \langle 1 | + e^{i \frac{\pi}{2}}| 1 \rangle \langle 0 | ) \\
&=& e^{-i \frac{\pi}{4}}( | 0 \rangle \langle 0 | + e^{i \frac{\pi}{2}}| 1 \rangle \langle 1 | )( | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 | ) \\
&=&  e^{-i \frac{\pi}{4} } R_{\frac{\pi}{2}} X
 \end{eqnarray*}
となり示された。*1

他についても同様。

 R_{\frac{\pi}{4}} は共役作用 R_{\frac{\pi}{4}} ( \cdot ) R^{\dagger}_{\frac{\pi}{4}} の下でパウリ行列をパウリ行列に移さないので、
即ちクリフォード演算子ではない。
クリフォード演算子かどうかは、ぱっとみてわかるようなものではなさそうですね。

今回はここまで。

*1:途中の式変形が少し難しい。

量子計算理論(森前 著) の演習問題を解く part9

こんにちは。Kumaです。

最近、量子コンピュータについて勉強しています。
今回は有名な以下の本の演習問題について、解答が載っていないので一部書いてみたいとおもいます。
f:id:phymath1991:20181224165540p:plain
量子計算理論 量子コンピュータの原理 | 森北出版株式会社

本書の勉強会が大阪で開催されているそうです。
演習問題の解答も一部公開中です。(私の我流よりも少し見通しの良い解き方になっていますね)
大阪近郊の方はぜひ参加してみてください。
sites.google.com


今回はpp.39- です。

pp.39.2 クリフォード演算子



 \begin{eqnarray*}
 &(&1) HXH = Z, HYH = -Y, HZH = X \\
 &(&2) R_{\frac{\pi}{2}}XR^{\dagger}_{\frac{\pi}{2}} = Y,  R_{\frac{\pi}{2}}YR^{\dagger}_{\frac{\pi}{2}} = -X, R_{\frac{\pi}{2}}ZR^{\dagger}_{\frac{\pi}{2}} = Z \\
 &(&3) CZ( X \otimes I ) CZ = X \otimes Z, CZ( Y \otimes I ) CZ = Y \otimes Z, CZ( Z \otimes I ) CZ = Z \otimes I
 \end{eqnarray*}
を示せ。
ここに

 \begin{eqnarray*}
H &=& \frac{1}{\sqrt{2}} ( | 0 \rangle \langle 0 | +  | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 | - | 1 \rangle \langle 1 | ) \\
 X &=& | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 | \\
 Y &=& i | 1 \rangle \langle 0 | -i  | 0 \rangle \langle 1 | \\
 Z &=& | 0 \rangle \langle 0 | -  | 1 \rangle \langle 1 | \\
 R_{\frac{\pi}{2}} &=&  | 0 \rangle \langle 0 | +  e^{j \frac{\pi}{2}} | 1 \rangle \langle 1 |  \\
CZ &=&  | 0 \rangle \langle 0 | \otimes I +  | 1 \rangle \langle 1 | \otimes Z 
 \end{eqnarray*}
である。

  • 解答

(1) HXH = Z, HYH = -Y, HZH = X


 \begin{eqnarray*}
 H(XH) &=& H( | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 | )( \frac{1}{\sqrt{2}} ( | 0 \rangle \langle 0 | +  | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 | - | 1 \rangle \langle 1 | )  ) \\
&=& H \frac{1}{\sqrt{2}}(  | 1 \rangle \langle 0 | + | 1 \rangle \langle 1 | + | 0 \rangle \langle 0 | - | 0 \rangle \langle 1 |  ) \\
&=&  \frac{1}{\sqrt{2}} ( | 0 \rangle \langle 0 | +  | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 | - | 1 \rangle \langle 1 | ) \frac{1}{\sqrt{2}}(  | 1 \rangle \langle 0 | + | 1 \rangle \langle 1 | + | 0 \rangle \langle 0 | - | 0 \rangle \langle 1 |  ) \\
&=& \frac{1}{2}(  2| 0 \rangle \langle 0 | - 2| 1 \rangle \langle 1 |) \\
&=& Z    
 \end{eqnarray*}
となり示された。他についても同様である。

(2)  R_{\frac{\pi}{2}}XR^{\dagger}_{\frac{\pi}{2}} = Y,  R_{\frac{\pi}{2}}YR^{\dagger}_{\frac{\pi}{2}} = -X, R_{\frac{\pi}{2}}ZR^{\dagger}_{\frac{\pi}{2}} = Z


 \begin{eqnarray*}
 R(XR) &=& R( ( | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 |)( | 0 \rangle \langle 0 | +  e^{-j \frac{\pi}{2}} | 1 \rangle \langle 1 |  ) )\\
&=& R( | 1 \rangle \langle 0 | +  +  e^{-j \frac{\pi}{2}} | 0 \rangle \langle 1 |  ) \\
&=&  ( | 0 \rangle \langle 0 | +  e^{j \frac{\pi}{2}} | 1 \rangle \langle 1 | )( | 1 \rangle \langle 0 | +  +  e^{-j \frac{\pi}{2}} | 0 \rangle \langle 1 |  ) \\
&=& -i  | 0 \rangle \langle 1 | +  i | 1 \rangle \langle 0 | = Y
 \end{eqnarray*}
となり示された。他についても同様である。

(3)  CZ( X \otimes I ) CZ = X \otimes Z, CZ( Y \otimes I ) CZ = Y \otimes Z, CZ( Z \otimes I ) CZ = Z \otimes I

 \begin{eqnarray*}
CZ(( X \otimes I ) CZ)  &=& CZ ( X \otimes I) ( | 0 \rangle \langle 0 | \otimes I +  | 1 \rangle \langle 1 | \otimes Z ) \\
&=& CZ( X | 0 \rangle \langle 0 | \otimes I + X | 1 \rangle \langle 1 | \otimes Z  ) \\
&=& CZ ( | 1 \rangle \langle 0 | \otimes I + | 0 \rangle \langle 1 | \otimes Z ) \\
&=& (| 0 \rangle \langle 0 | \otimes I +  | 1 \rangle \langle 1 | \otimes Z ) ( | 1 \rangle \langle 0 | \otimes I + | 0 \rangle \langle 1 | \otimes Z ) \\
&=& | 0 \rangle \langle 1 | \otimes Z + | 1 \rangle \langle 0 |  \otimes Z \\
&=& X \otimes Z
 \end{eqnarray*}

となり示された。他についても同様である。

これらの確認によりH, R_{\frac{\pi}{2}}, CZ がクリフォード演算子であることが示された。
(ただし H^{\dagger} = H, CZ^{\dagger} = CZ であることを示さなければならない)

今回はここまで。

量子計算理論(森前 著) の演習問題を解く part8

こんにちは。Kumaです。

最近、量子コンピュータについて勉強しています。
今回は有名な以下の本の演習問題について、解答が載っていないので一部書いてみたいとおもいます。
f:id:phymath1991:20181224165540p:plain
量子計算理論 量子コンピュータの原理 | 森北出版株式会社

本書の勉強会が大阪で開催されているそうです。
演習問題の解答も一部公開中です。(私の我流よりも少し見通しの良い解き方になっていますね)
大阪近郊の方はぜひ参加してみてください。
sites.google.com


今回はpp.39- です。

pp.39 複素係数表示と実係数表示


複素係数表示におけるゲート \Lambda(R_{\frac{\pi}{2}}) は実係数表示においては
 T( I \otimes I \otimes H ) T (I \otimes I \otimes H ) を作用させることによりシミュレートできることを示せ。
ここで、複素係数表示(2量子ビット)は
 | \psi \rangle = \sum c_{z} | z \rangle
であり、実係数表示(2量子ビット+1量子ビット)は、 c_{z} = \alpha_{z} + j \beta_{z} として
 | \tilde{ \psi } \rangle = \sum ( \alpha_{z} | z \rangle \otimes | 0 \rangle + \beta_{z} | z \rangle \otimes | 1 \rangle  )
で定義される。
さらに Tはトフォリゲート(CCXゲート)、 \Lambda(U) はコントロールUゲート、HはHadamrdゲートであり

 \begin{eqnarray*}
 T &=& ( I ^{\otimes 2} - | 11 \rangle \langle 11 | ) \otimes I +  | 11 \rangle \langle 11 | \otimes X \\
 \Lambda(U) &=& | 0 \rangle \langle 0 | \otimes I +  | 1 \rangle \langle 1 | \otimes U \\
H &=& \frac{1}{\sqrt{2}} ( | 0 \rangle \langle 0 | +  | 0 \rangle \langle 1 | + | 1 \rangle \langle 0 | - | 1 \rangle \langle 1 | )
 \end{eqnarray*}
である。

  • 解答

まず Hについて

 \begin{eqnarray*}
 H | 0 \rangle = \frac{1}{\sqrt{2}} ( | 0 \rangle + | 1 \rangle ) \\
 H | 1 \rangle = \frac{1}{\sqrt{2}} ( | 0 \rangle - | 1 \rangle ) \\
 \end{eqnarray*}
により、

 \begin{eqnarray*}
  | + \rangle \equiv \frac{1}{\sqrt{2}} ( | 0 \rangle + | 1 \rangle ) \\
  | - \rangle \equiv \frac{1}{\sqrt{2}} ( | 0 \rangle - | 1 \rangle ) \\
 \end{eqnarray*}
と定義する。


 \begin{eqnarray*}
 | \tilde{ \psi } \rangle &=& \sum ( \alpha_{z} | z \rangle \otimes | 0 \rangle + \beta_{z} | z \rangle \otimes | 1 \rangle  ) \\
 (I \otimes I \otimes H )| \tilde{ \psi } \rangle &=& \sum ( \alpha_{z} | z \rangle \otimes | + \rangle + \beta_{z} | z \rangle \otimes | - \rangle  ) \\
 T(I \otimes I \otimes H )| \tilde{ \psi } \rangle &=& ( \alpha_{11} | 11 \rangle \otimes X | + \rangle  +  \beta_{11} | 11 \rangle \otimes X | - \rangle ) + \sum_{z \neq 11} ( \alpha_{z} | z \rangle \otimes | + \rangle +  \beta_{z} | z \rangle \otimes | - \rangle  ) \\
 \end{eqnarray*}

ここで

 \begin{eqnarray*}
 X | + \rangle &=& | + \rangle \\
 X | - \rangle &=& - | - \rangle \\
 \end{eqnarray*}

よって、

 \begin{eqnarray*}
 T(I \otimes I \otimes H )| \tilde{ \psi } \rangle &=& ( \alpha_{11} | 11 \rangle \otimes  | + \rangle  -  \beta_{11} | 11 \rangle \otimes  | - \rangle ) + \sum_{z \neq 11} ( \alpha_{z} | z \rangle \otimes | + \rangle +  \beta_{z} | z \rangle \otimes | - \rangle  ) \\
 \end{eqnarray*}
となる。

ここで、

 \begin{eqnarray*}
 H | + \rangle &=& | 0 \rangle \\
 H | - \rangle &=& | 1 \rangle \\
 \end{eqnarray*}

よって

 \begin{eqnarray*}
 (I \otimes I \otimes H )T(I \otimes I \otimes H )| \tilde{ \psi } \rangle &=& ( \alpha_{11} | 11 \rangle \otimes  | 0 \rangle  -  \beta_{11} | 11 \rangle \otimes  | 1 \rangle ) + \sum_{z \neq 11} ( \alpha_{z} | z \rangle \otimes | 0 \rangle +  \beta_{z} | z \rangle \otimes | 1 \rangle  ) \\
 \end{eqnarray*}

最後に Tを作用させると、

 \begin{eqnarray*}
 T(I \otimes I \otimes H )T(I \otimes I \otimes H )| \tilde{ \psi } \rangle &=& ( \alpha_{11} | 11 \rangle \otimes  | 1 \rangle  -  \beta_{11} | 11 \rangle \otimes  | 0 \rangle ) + \sum_{z \neq 11} ( \alpha_{z} | z \rangle \otimes | 0 \rangle +  \beta_{z} | z \rangle \otimes | 1 \rangle  ) \\
 \end{eqnarray*}
元の状態 | \tilde{\psi} \rangle と比較すると、 z = 11に相当する量子状態(制御ビットが1かつ標的ビットが1)の項だけが  \alpha_{z} + j \beta_{z} \rightarrow_{( \times j )} - \beta_{z} + j \alpha_{z}  \pi/2回転した状態に移されている。
すなわち複素数表示において  \Lambda (R_{\frac{\pi}{2}}) ゲートを作用させたことに他ならない。
*1

今回はここまで。

*1:回転ゲート Rは、 |1 \rangle のみを回転させるゲートであることに注意しよう。 その制御ゲートversionなので、制御ビットが1のときだけ Rが作用することになる。 結果として | 11 \rangle だけが回転する。

量子計算理論(森前 著) の演習問題を解く part7

こんにちは。Kumaです。

最近、量子コンピュータについて勉強しています。
今回は有名な以下の本の演習問題について、解答が載っていないので一部書いてみたいとおもいます。
f:id:phymath1991:20181224165540p:plain
量子計算理論 量子コンピュータの原理 | 森北出版株式会社

本書の勉強会が大阪で開催されているそうです。
演習問題の解答も一部公開中です。(私の我流よりも少し見通しの良い解き方になっていますね)
大阪近郊の方はぜひ参加してみてください。
sites.google.com


今回はpp.38- です。

pp.38 Hadamardテスト

f:id:phymath1991:20190113185722p:plain:w300
Hadamardテスト

一番上の量子ビットを測定した時に0が得られる確率は

 \begin{eqnarray*}
 \frac{2+ \langle \psi | U | \psi \rangle +  \langle \psi | U^{\dagger} | \psi \rangle }{4}
 \end{eqnarray*}
であることを示せ。
ただし

H = \frac{1}{\sqrt{2}} ( | 0 \rangle \langle 0 | + | 1 \rangle \langle 0 |  + | 0 \rangle \langle 1 |  - | 1 \rangle \langle 1 | )

  • 解答

ゲートを左から順に U_{1}, U_{2}, U_{3}とおく。

 \begin{eqnarray*}
U_{1} &=& H \\
U_{2} &=& | 0 \rangle \langle 0 | \otimes I + | 1 \rangle \langle 1 | \otimes U \\
U_{3} &=& H  \\
 \end{eqnarray*}

初期状態は  | 0 \rangle \otimes | \psi \rangle です。

 \begin{eqnarray*}
 U_{1} ( | 0 \rangle \otimes | \psi \rangle ) &=& \frac{1}{\sqrt{2}}( | 0 \rangle +  | 1 \rangle ) \otimes | \psi \rangle \\
 U_{1}U_{2} ( | 0 \rangle \otimes | \psi \rangle ) &=& ( | 0 \rangle \langle 0 | \otimes I + | 1 \rangle \langle 1 | \otimes U)  \frac{1}{\sqrt{2}}( | 0 \rangle +  | 1 \rangle ) \otimes | \psi \rangle \\
&=&   \frac{1}{\sqrt{2}}( | 0 \rangle \otimes | \psi \rangle +  | 1 \rangle \otimes U | \psi \rangle) \\
 U_{1}U_{2}U_{3} ( | 0 \rangle \otimes | \psi \rangle ) &=&  \frac{1}{2}( | 0 \rangle \otimes | \psi \rangle +  | 1 \rangle \otimes | \psi \rangle  +  | 0 \rangle \otimes U | \psi \rangle -  | 1 \rangle \otimes U | \psi \rangle)
 \end{eqnarray*}
これがゲート通過後の量子状態 | \psi_{out} \rangle である。第一量子ビットが0である確率 p_{0}は、

p_{0} = | ( | 0 \rangle \langle 0 | \otimes I ) | \psi_{out} \rangle |^{2}
である。
*1


 \begin{eqnarray*}
p_{0} &=& | | \psi \rangle + U | \psi \rangle | ^{2} \frac{1}{4} \\
&=& ( \langle \psi | + \langle \psi | U^{\dagger} )( | \psi \rangle + U| \psi \rangle ) \frac{1}{4} \\
&=& ( \langle \psi | \psi \rangle +  \langle \psi | U | \psi \rangle +  \langle \psi | U^{\dagger} | \psi \rangle +  \langle \psi | U^{\dagger} U | \psi \rangle  )  \frac{1}{4} \\
&=&  ( \langle \psi | \psi \rangle +  \langle \psi | U | \psi \rangle +  \langle \psi | U^{\dagger} | \psi \rangle +  \langle \psi  | \psi \rangle  )  \frac{1}{4} \\ 
&=&  (1 +  \langle \psi | U | \psi \rangle +  \langle \psi | U^{\dagger} | \psi \rangle +  1  )  \frac{1}{4} \\
&=&  (2 +  \langle \psi | U | \psi \rangle +  \langle \psi | U^{\dagger} | \psi \rangle)  \frac{1}{4} 
 \end{eqnarray*}
となり、示された。


なお第一量子ビットが1である確率 p_{1}

 \begin{eqnarray*}
p_{1} &=&  | ( | 1 \rangle \langle 1 | \otimes I ) | \psi_{out} \rangle |^{2} \\
&=& | | \psi \rangle - U | \psi \rangle | ^{2} \frac{1}{4} \\
&=& ( \langle \psi | - \langle \psi | U^{\dagger} )( | \psi \rangle - U| \psi \rangle ) \frac{1}{4} \\
&=&  ( \langle \psi | \psi \rangle -  \langle \psi | U | \psi \rangle -  \langle \psi | U^{\dagger} | \psi \rangle +  \langle \psi  | \psi \rangle  )  \frac{1}{4} \\ 
&=&  (2 -  \langle \psi | U | \psi \rangle -  \langle \psi | U^{\dagger} | \psi \rangle)  \frac{1}{4} 
 \end{eqnarray*}
すなわち p_{0} + p_{1} = 1 が確認できる。

今回はここまで。

*1:ちなみに第一量子ビットが1である確率 p_{1}
p_{1} = | ( | 1 \rangle \langle 1 | \otimes I ) | \psi_{out} \rangle |^{2}
であるし、 第一および第二量子ビットが同時に1である確率 p_{11}
p_{11} = | ( | 1 \rangle \langle 1 | \otimes | 1 \rangle \langle 1 | ) | \psi_{out} \rangle |^{2}
である。

量子計算理論(森前 著) の演習問題を解く part6

こんにちは。Kumaです。

最近、量子コンピュータについて勉強しています。
今回は有名な以下の本の演習問題について、解答が載っていないので一部書いてみたいとおもいます。
f:id:phymath1991:20181224165540p:plain
量子計算理論 量子コンピュータの原理 | 森北出版株式会社

本書の勉強会が大阪で開催されているそうです。
演習問題の解答も一部公開中です。(私の我流よりも少し見通しの良い解き方になっていますね)
大阪近郊の方はぜひ参加してみてください。
sites.google.com


今回はpp.37- です。

pp.37.2 CCZゲート


CCZは以下の回路と等価であることを示せ。

f:id:phymath1991:20190113105807p:plain
回路図
ここで R_{\theta}は回転演算である。

R_{\theta} 
=
\begin{pmatrix}
1 & 0 \\
0 & e^{j \theta}
\end{pmatrix}
=
 | 0 \rangle \langle 0 |  + e^{j \theta} | 1 \rangle \langle 1 |
なおCCZとは3bit量子ビット演算であり、2つの制御ビットが共に1であるときに限り標的ビットにZを作用させる。

CCZ = ( I ^{\otimes ^{2}} - | 11 \rangle \langle 11 | ) \otimes I + | 11 \rangle \langle 11 | \otimes Z

  • 解答

回路図のゲート演算を左から順に U_{1}, U_{2}, U_{3}, U_{4}, U_{5} とする。

 \begin{eqnarray*}
U_{1} &=& I \otimes ( | 0 \rangle \langle 0 | \otimes I + | 1 \rangle \langle 1 | \otimes R_{\frac{\pi}{2}} \\
U_{2} &=& ( | 0 \rangle \langle 0 | \otimes I + | 1 \rangle \langle 1 | \otimes X | \otimes I \\
U_{3} &=& I \otimes ( | 0 \rangle \langle 0 | \otimes I + | 1 \rangle \langle 1 | \otimes R^{\dagger}_{\frac{\pi}{2}}  \\
U_{4} &=& U_{2} \\
U_{5} &=& | 0 \rangle \langle 0 | \otimes I \otimes I+ | 1 \rangle \langle 1 | \otimes I \otimes R_{\frac{\pi}{2}} \\
 \end{eqnarray*}
あとは U_{4}U_{5}, U_{3}(U_{4}U_{5}),...と順に計算して U_{1}U_{2}U_{3}U_{4}U_{5}を得ればよい。

式変形の過程で次の性質を使うと便利です。

 \begin{eqnarray*}
  | 0 \rangle \langle 0 | X &=&  | 0 \rangle \langle 0 | (  | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 | ) =  | 0 \rangle \langle 1 | \\
  | 1 \rangle \langle 1 | X &=&  | 1 \rangle \langle 0 | \\
  X | 0 \rangle \langle 1 | &=& ( | 1 \rangle \langle 0 | +  | 0 \rangle \langle 1 | ) | 0 \rangle \langle 1 | =  | 1 \rangle \langle 1 | \\
  X | 1 \rangle \langle 0 | &=&  | 0 \rangle \langle 0 | \\
  R^{\dagger}_{\frac{\pi}{2}} R_{\frac{\pi}{2}} &=& I \\
  R_{\frac{\pi}{2}} R_{\frac{\pi}{2}} &=& Z
 \end{eqnarray*}

今回はここまで。