# 2020年度 計算論 質問掲示板

## 使い方

マークダウンという記法を使って、複数人でリアルタイムに編集できるページです。ログインしなくても編集できます。

$\LaTeX$記法を使って数式を書き込むこともできます。

<!-- ブラケット記法のマクロ -->
$$
\newcommand{\bra}[1]{\left\langle #1 \right|}
\newcommand{\ket}[1]{\left|#1 \right\rangle}
\newcommand{\braket}[2]{\left\langle #1 \middle|#2 \right\rangle}
$$

$$
H \ket{0} \otimes \cdots \otimes H \ket{0} \\
= \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \otimes \cdots \otimes \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \\
= \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} \ket{x}
$$

めんどくさかったら数式はちゃんとしたものでなくてもいいです。誰かが直してくれます。

他に何ができるかは、こちらの [機能紹介](https://hackmd.io/s/features-jp) というページを参考にしてください。

## 質問例: 2019年の過去問の問8はどう答えればいいですか？

## 質問例: 今年はどういう問題が出ると思いますか？

## 質問: 第7回スライドの29ページ目の分母間違ってる気がするんですがみなさんいかがですか？

- 確かにミスっぽそう。正しくは $\frac{\ket{00}+\ket{11}}{\sqrt{2}}$ ですかね（うら）
- というかここ $\frac{1}{\sqrt{2}}(\ket{0}+\ket{1}) \otimes \ket{0}$ と $\frac{\ket{00}+\ket{11}}{2}$ がイコールになってるのがおかしくないですか？　実際は図のように$H$の後のCNOTがあるからこうなっているので矢印に置き換えたほうが良い気がします（うら）
- ↑賛成です

## 質問: 第10回スライドの29,30ページ目，$U_{1}$ が $a_{00}\ket{00}$にも作用してしまいそうな問題，解決してますか...?

- 図の $n=3$ のときはちゃんと1, 2ビット目が制御ビットになって作用しているので、ミス（というか記述不足？）ですかね…？（うら）
- こういうとき式だとどう書くんでしょうね？（うら）
- ↑ (latexうまく書けないのですみません$$\ket{0}\bra{0} \otimes I+\ket{1}\bra{1} \otimes R(-\theta)$$とかではないでしょうか
- ↑なるほど、よさそうです！（うら）

## 質問: 第12回スライドの9ページ目の最後の数式 $p_{0}=\frac{1}{2}-\frac{1}{2}|\braket{\psi_{a}}{\psi_{b}}|^{2}$ ってなんでマイナスが出てくるんでしょうか．手元の計算ではプラスになっちゃいます．($p_{1}$の方がマイナスかな？と思ったのですがどうでしょうか？)

- ミスっぽいですね。[Wikipedia](https://en.wikipedia.org/wiki/Swap_test) でもプラスになっています（うら）
- ↑すみません、この$p_0$の計算過程を教えていただけないでしょうか
- $$\ket{\psi}=\frac{1}{2}\ket{0}\otimes(\ket{\psi_{a}}\ket{\psi_{b}}+\ket{\psi_{b}}\ket{\psi_{a}})+\frac{1}{2}\ket{1}\otimes(\ket{\psi_{a}}\ket{\psi_{b}}-\ket{\psi_{b}}\ket{\psi_{a}})$$を観測して0が得られる確率は，\begin{eqnarray}p_{0}&=&|\braket{0}{\psi}|^{2} \\ &=&\bra{\psi}(\ket{0}\bra{0}\otimes I)\ket{\psi} \\&=&\frac{1}{4}(\bra{\psi_{a}}\bra{\psi_{b}}+\bra{\psi_{b}}\bra{\psi_{a}})(\ket{\psi_{a}}\ket{\psi_{b}}+\ket{\psi_{b}}\ket{\psi_{a}}) \\&=&\frac{1}{4}(\braket{\psi_{a}}{\psi_{a}}\braket{\psi_{b}}{\psi_{b}}+\braket{\psi_{a}}{\psi_{b}}\braket{\psi_{b}}{\psi_{a}}+\braket{\psi_{b}}{\psi_{a}}\braket{\psi_{a}}{\psi_{b}}+\braket{\psi_{b}}{\psi_{b}}\braket{\psi_{b}}{\psi_{b}}) \\&=&\frac{1}{2}+\frac{1}{2}|\braket{\psi_{a}}{\psi_{b}}|^{2} \end{eqnarray}と計算できるかなと思いました．

## 質問: 第3,4回のスライドで、先生がよく言語A = \{<B,w>|Bは入力する文字列wを受理するTM B\}みたいな表現をすると思うのですが、この<>は何を表しているのでしょうか？そしてなぜTMを言語に落とし込むことができるのでしょうか？

- $\langle O \rangle$ はオブジェクト $O$ を符号化（文字列化）したものを表します（第3回スライド18ページ、『計算論の基礎』第2巻184ページ）。上の例であれば、言語とは文字列の集合のことなので、$B$と$w$のペアを符号化する必要があってこの書き方になります。
TMをどのように文字列にできるかは、雰囲気で言えばC言語をコンパイルして0と1のバイナリ列にするのと似ていると思います。具体的にやるのは大変ですが、TMの形式的な定義は$(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$なので、これを頑張ってどうにかすると0と1の文字列に変換することができます。論理学で言えば、ゲーデル数とかも近い概念かと思います。（うら）
- ↓参考に、「形式言語理論」という授業で使われていたテキストの抜粋です（うら）

## 質問: 第06回・量子情報理論の基礎2の65ページ目の部分トレースの計算がよくわかりません...(2行目から3行目のtr2()を展開するところ)

- \begin{align}\mathrm{tr}_2[\ket{vw}\bra{v'w'}] &= \mathrm{tr}_2[(\ket{v}\otimes\ket{w})(\ket{v'}\otimes\ket{w'})^\dagger] \\ &= \mathrm{tr}_2[(\ket{v}\otimes\ket{w})(\bra{v'}\otimes\bra{w'})] \\ &= \mathrm{tr}_2[(\ket{v}\bra{v'})\otimes(\ket{w}\bra{w'})] \\ &= \ket{v}\bra{v'}\mathrm{tr}[\ket{w}\bra{w'}] \\ &= \ket{v}\bra{v'}\braket{w'}{w}\end{align} とかやってそうな気がしました（2行目→3行目のソースがスライドから見つけ出せないんですがあってますよね…？）（うら）
- 第6回スライドp62より,\begin{align}&\bra{\psi}\mathrm{tr}_2[\ket{vw}\bra{v'w'}]\ket{\phi} \\ &\overset{\mathrm{def}}{=} \sum_k \bra{\psi\otimes e_k} [\ket{vw}\bra{v'w'}]\ket{\phi\otimes e_k} \\
&= \sum_k \bra{\psi\otimes e_k} \ket{v\otimes w}\bra{v'\otimes w'}\ket{\phi\otimes e_k} \\
&= \sum_k \braket{\psi}{v}\braket{w'}{e_k}\braket{e_k}{w}\braket{v'}{\phi} \\
&= \braket{\psi}{v}\bra{w'}\left(\sum_k\ket{e_k}\bra{e_k}\right)\ket{w}\braket{v'}{\phi} \\
&= \bra{\psi}\left(\braket{w'}{w}\ket{v}\bra{v'}\right)\ket{\phi}\end{align}よって, $$\mathrm{tr}_2[\ket{vw}\bra{v'w'}] = \braket{w'}{w}\ket{v}\bra{v'}$$という感じで導くのもアリかなと思いました(第三者)

## 質問: 過去問2019問7の-ρ'lnρ'=...の式の最後変形で、<φ_k|U†=<Uφ_k|としてるのって正しいですか？最後の式変形を行わずにトレースをとってU†を先頭に持ってくるのかなと思いました。

- そう言われると自信無くなってきましたが、確か第5回スライド12ページの「ケットベクトルが $A\ket{\phi}$ で与えられる時，そのブラベクトルは $\bra{\phi}A^\dagger$ である．」というのを参考にしました。実際エルミート転置の性質から $(AB)^\dagger=B^\dagger A^\dagger$ なのでいいんじゃないかな…？と思います。
トレースを取って中身の順番を入れ替える証明も良いと思います。余裕があったら書き足しておきます…。（うら）
- 「ケットベクトルが $A\ket{\phi}$ で与えられる時，そのブラベクトルは $\bra{\phi}A^\dagger$ である．」それはそうでしたごめんなさいありがとうございます。（質問者）
- それに加えてなんですが、$\ln{\rho'}=U(\ln{\rho})U^\dagger$ の説明がちょっと足りなかった気がしてきました。これも余裕があったら書き足しておきます…。（うら）