How to realize Universal Quantum Computation by using of magic state.
このエントリは量子計算理論（森前智行）のP41 の上からふたつ目の演習問題の答えになっています。
Clifford group and Universal quantum computation
クリフォード群
クリフォード群Cとは、
任意の一般化パウリ行列$g \in G_n$に対して、その共役演算$UgU^\dagger$をかけてもそれが一般化パウリ行列になっているものの集合
$$ C = \{ U | \forall g \in G_n ,UgU^\dagger \in G_n \} $$
のこと
これは群の構造を持っています、中心化群（？、 一般化パウリ行列が群なので）
そして、このクリフォード群を調べてみると結局、3つの生成元でかけることがわかります。（QCQI excrsize 10.40）
その3つの生成元とは、
$$ C = \{ H, R_{\pi/2}, CZ \}$$
です。
ここで$H$はアダマールゲート、 $R_{\theta} = \ket{0}\bra{0} + e^{i\theta}\ket{1}\bra{1}$、$CZ$はコントロールZゲート、です。
Universal quantum computation
ユニバーサルな計算はクリフォードだけではできません。できないことは明らかです。
それどころか、クリフォードだけでの計算は古典コンピュータによりシミュレーション可能です。これをGottesman-Knillの定理と呼びます。
ユニバーサルな量子計算をするには、クリフォードでないユニタリ演算子が必要になります。なんでもいいですが、例えば、
$$ R_{\pi/4}, R_{-\pi/4}$$
などがあればよいです。このどっちでもいいし、これ以外でも良いです。
Universal QC by Clifford group and Magic state
クリフォードでないユニタリ演算子がなくとも、次のMagic state$\ket{M}$が好きなだけ用意できるなら、ユニバーサルな量子計算が可能になります。
$$ \ket{M} = \cos\frac{\pi}{8}\ket{0} +\sin\frac{\pi}{8}\ket{1}$$
以下、その証明（のようなものです）
状態$\ket{\psi} = \alpha \ket{0} + \beta\ket{1}$ に$R_{\pi/4}, R_{-\pi/4}$を作用させた状態を作り出すことができれば証明できたことになります。
つまり、
$$\ket{\psi} = \alpha \ket{0} + \beta\ket{1}$$
から出発して、
$$\alpha \ket{0} +e^{-i\pi/4}\beta\ket{1},\alpha \ket{0} +e^{i\pi/4}\beta\ket{1}$$
ができればゴールです。
$$\ket{\Psi_0} = \ket{\psi} \otimes \ket{A_{\theta}}$$
という形を考えます。
ここで、$\ket{A_{\theta}} =\ket{0} + e^{i\theta}\ket{1}$です。
$\ket{\Psi_{0}}$を$Z \otimes Z$で測定します。
すると、確率1/2で、
測定結果 ＋１
$$\ket{\Psi^+_1} = \alpha \ket{00} +\beta e^{i\theta} \ket{11}$$
測定結果 -１
$$\ket{\Psi^-_1} = \alpha e^{i\theta}\ket{01} + \beta \ket{10}$$
がでます。
これにCX gate を適用すると
$$\ket{\Psi^+_2} = (\alpha \ket{0} +\beta e^{i\theta} \ket{1}) \otimes \ket{0}$$
$$\ket{\Psi^-_2} = (\alpha e^{i\theta}\ket{0} + \beta \ket{1}) \otimes \ket{1}$$
ふたつ目のキュービットを無視します。
グローバルな位相を無視するために、$\ket{0}$の位相を揃えると、
はじめのキュービットは
$$\ket{\Psi_3} = \alpha \ket{0} +\beta e^{\pm i\theta} \ket{1} $$
となります。
$\theta = \pi / 4$とすれば、ゴールの形になっています。
つまり、$\ket{A_{\pi /4}}$があれば、に$R_{\pi/4}, R_{-\pi/4}$の作用を実現できたことになります。
つぎに、magic stateから$\ket{A_{\pi /4}}$をつくる方法を説明します。
それは簡単で、
$$H R_{\pi / 2} \ket{M} = e^{i\pi/8} \ket{A_{\pi / 4}}$$
なので、つくれます。
以上で証明ができたことになります。
