第15回　日曜数学会　のレポート

こんにちは。Kumaです。
第15回の日曜数学会議に参加してきました！
ので、レポートを書きます。

私、かなりいろいろな分野をかじっているので、知識総動員で全部レビューしていきたいと思います。
この努力だけ誰か褒めて。

ちなみにニコ生のタイムシフトが残っています。
twitter.com
第１５回日曜数学会 - 2019/06/29 14:00開始 - ニコニコ生放送

キグロ「スマブラの物理」

超有名ゲーム　大乱闘スマッシュブラザーズ　の世界の物理法則を推定するという試み。
考えたことなかったですね～

スマブラの世界では軌道が放物線ではなく、どうも空気抵抗が実装されているらしい。
その空気抵抗係数を、いくつかの仮定のもとで計算していくと・・・？

「自分の解きたい問題を解くためにサイエンスを使う」というのは私自身もよくやるので、
共感するところが多かったです。終了後に実際に私も解いてみました。
意外と線形微分方程式解く程度は錆びついてなかったですね。良かった。
スマブラ物理研究部、あってもいいかも。

ちばまさみ「春のパン祭り2019」

春のパン祭りガチ勢による攻略速報。シールの枚数をどの形で集めると無駄がないのか、
コストパフォーマンスや裏技まで戦略的に分析されています。
これも「自分の解きたい問題を解くためにサイエンスを使う」　ですね！
雑談で、これは最適化問題なのでアニーリングでも解けますね　なんて話をしました。

ヤマザキ春のパンまつり問題は量子加速される・・・？

tsujimotter「ラマヌジャンやっぱりやばいじゃん」

ラマヌジャンとかいうインドの英雄はやっぱりやばかった。
タクシー数を無数に知ってしまうことができるという、恐るべき・・・
そしてスライドの背景になってしまったK2凸.
K3のほうが数字的に強いから仕方ないね。

BSD予想(確かゼータ関数のオイラー積表示の一般化と楕円曲線の特徴量の話）というワードが出てきて、
そういえば未解決問題の本で聞いたなぁと。
楕円曲線は、方程式みるとなかなか簡単そう（次数が低いという意味で）で難しい・・・のですが
演算が考えられたり豊富な構造を持っていますね。体系的に勉強したい対象の１つ。
通信分野では準同型暗号で耳にします。

Kuma「光の偏波とリー代数」

本ブログの内容のサマリーでした。SU(2)~SO(3) は神が作ったと思う。

まこぴ～「p次以下等式群」

「鑑賞しましょう」
ある数のペアに対しては、1乗和, 2乗和, 3乗和...が全て等しいという不思議な関係が成立する。
いくつかの定理について、私は発表中にこそこそ証明を議論したりしてました。

吉田雄紀「スーパーマリオメーカーはチューリング完全」

スーパーマリオメーカーを　計算機　としてみなすというとんでもない研究活動。
主にニコニコで始まった文化です。（いわゆるニコニコ学会）
最近はアナログコンピューターが注目されていますが、これは　デジタル上に実装された物理法則を用いたアナログコンピュータ　といえますね。
意味わかりません。

論理演算できれば、そこから加算器や乗算器がどんどん作れるわけです。
よくみると、除算器は乗算器の何倍も複雑な回路（といってもマリオのステージね）になっています。
これは非常に本質的で、実際にFPGAに除算器を入れようとするととんでもないことになります。
直感的には　割り算というのは上の桁から逐次的に商が決定されていくので、商が確定するまでいっぱい待たなければいけない
ということに相当します。まぁ、FPGA屋に聞いただけの知識なんですけどね。

「使い回し」や「カメラも並列で動く」などの新技術で時代が変わっていったそうです。
技術ですねー。

これ、スマブラ計算機も出来るわけですね。
調べてみるとスマブラで時計を実装している人がいました。これは計算というか、カウンタですね。

おおとや「論文投稿したった」

グラフ理論によって、
P≠NP　が否定的に証明できちゃったかも　らしい。
未解決問題なので、解くと１億円貰えますから、正しいと凄いことになりますね。
論文はarxivでレビュー中？だそうです。乞うご期待？

三好潤一「折紙ビリヤードの極限軌道」

折り紙を二等分線で折り続けていくと、極限として周回軌道が得られるという発表。
カオスでいうところのリミットサイクルですかね。
初期値依存性も強いようです。みなさん、折り紙を無限回折りましょう。

岩淵夕希「輪廻数」

ある程度いくと戻ってくる数　の世界を考えた　な発表。
輪廻数　という命名がおしゃんてぃー。
ぶっちーさんはオリジナルなアイデア*1が本当に多く、発想力分けてほしい。

佐々木マン「驚くべきグリッド平面の世界:まとめ」

グリッド（離散格子点）の幾何学の話。毎回スライドを紙で作るという拘りがすごい。
ぶっちーさんがQ&Aで　「マンハッタン距離を距離だと思ったときの幾何学ぽいですね」
とおっしゃっていましたが、私もそうだと思います。
量子跳躍の話、聞きたかったですね～。

完全有罪

penpenpen「"非可換な"統計学」

ランダム行列の固有値分布に関するお話。
行列だから”非可換性”が出てくるわけです。
個人的には、最近お仕事（半分趣味）で調べていることと非常に近かったので
勉強になりました。

乱数を要素に持つ行列を考えたときに、その固有値（これも確率変数になる）の分布はどうなっているだろう？と考えると
実は行列のサイズを無限大に飛ばすとある分布に収束するのです。
これは漸近分布とか呼ばれています。

通信では、通信路で転送可能な情報量の上限（通信路容量）が通信路の雑音度合いと、通信路の行列表示の固有値で決まります。
つまり通信路の行列表示の固有値を知ることが極めて重要です。
通信路は殆どの場合は外乱によって絶えず変動しているので、確率モデルで記述しますので、上記の話とリンクします。
特にユーザー数が多い場合は行列のサイズが増えることになるので、漸近分布になっていきます。
こうなると、通信路の瞬時的な行列を知らなくても統計的な考察だけで平均容量が決定でき、かえって設計もしやすくなります。
このアイデアは　Massive MIMO という技術の基礎をなしており、2020年にサービスイン予定の 5Gモバイル通信　に採用されています。

めるのん「コンピュータ方程式を作ろう」

ディオファントス方程式を計算資源とみて、その間の演算（方程式と方程式を演算して方程式を得る！）をうまく定義することで
”計算”ができるという発表。
こういうのを聞くと、　コンピューターってなんだろう？　計算ってなんだろう？　って考えますよね。
計算できる閉じた構造が定義できれば、なんでもコンピュータになりうる。

まとめ

今回は数学的な話題と、そのビジュアライズや応用が１：１ぐらいだったので
非常に聞きやすかったと思います。
休憩時間も熱い議論が交わされていました。
（私は漸近分布について教えてもらっていました）
大成功の回だったと思います。

みなさんも、一度は日曜数学会に参加してみてください。

なお8月3日には　大阪でも　日曜数学会を開催しますのでチェックしてみてください。
kansai-sunday-math.connpass.com

ではでは。

*1:フラクタル音楽とか。

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

こんにちは。Kumaです。

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

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

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

ということです。

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

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


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

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

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

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

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

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


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

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

図で見るとこんな感じ。*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桁の２進数から n桁の２進数への写像で規定される　ともいえます。

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

ハミング限界 - 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} である。