2021-02-05

1週間でできるTOEFL iBT対策と受験記

はじめに

ITPがコロナであるかわからず、院試のためにTOEFL ibtを受けなきゃな〜と思ってる人も多いと思うのでTOEFL ibt試験の受験記を残しておきます。

準備編

今回のTOEFLは東大のgo global gatewayでやっているTOEFL iBTかIELTSが無料で受けられるやつを使って受けたので費用負担は0！2月n日までに受けないといけないらしいので1/30のやつに申し込みました。home editionは部屋を片付けるのがめんどいのでやめて口コミの良い御茶ノ水ソラシティを会場に選択。確かこれが12月くらいなはず。1月に入りそろそろ対策しなきゃかな〜などと思っているうちに怒涛の期末試験が開幕。その対策に時間をとられ、TOEFLは単語帳を電車で眺めるくらいに止まっていました。受験一週間前にようやく数学3以外の試験が終わったので気合を入れて対策をしようと思い立ちます。TOEFLには4つのセクションがあるので僕が限られた時間の中で行ったそれぞれの対策を見ていきます。

リーディング

とりあえず過去問を2問くらいとく。あんまり細かいところは聞かれないし東大生なら普通に解けます。単語の意味を問うやつが難しいけど今更無理だと悟り終了。

リスニング

これもとりあえず過去問を2問。これもあんまり細かいのは問われない。メモをとるかも微妙で正直取らなかった方がよかったかもなと今になって思っています。これも今更無理だと悟り終了。

ライティング

問題は2問（independentとintegrated）出てintegratedはリーディング＋リスニングもおまけでついてきます。ネットに転がっているテンプレートを頭に入れておくと最低限の点は取れます。integratedは形式がほぼ決まっているので過去問過学習が有効そう。ライティングしかりスピーキングしかりうまく嘘をつく能力が求められるので厳しい。

スピーキング

絶望のセクション。全四問で最初の1問だけ自分で内容を考える必要があり、残りはリスニングで聞き取ったことを話します。後半三問は形式が定まってるので過去問過学習推奨。テンプレートを暗記すると完全無言を回避できます（できた）。1問目は実質お祈りです。

当日編

試験開始まで

できるだけ早めについた方が他の人のスピーキングにリスニングが邪魔されないのでいいみたいなことを見ていましたが普通に無理だったので定刻に到着。昼休憩のための飲食物と耳栓とパスポートだけもって会場入り。パスポートのコピーしか持ってきてないため受験できないですよと言われている人を横目に番号札兼誓約書みたいなのを取って待合室に。荷物をパスポート以外ロッカーにしまい、呼ばれるのを待ちます。結構待たされたので、その間に誓約書にサインします。呼ばれていくと、ポケットの中が空であることを示すように言われ、パスポートで本人確認。最初誓約書のサインをローマ字で書いてたら漢字で書いてくれと言われました。試験部屋に誘導されると、TOEFLはきた人順にテストを受けるので周りはもう試験中です。静かに席に着くと、監督の人が試験を開始するためのパスワードをうってくれ試験スタート。

テスト（準備）

まず、機器チェックが行われます。ヘッドセットの音量調整をしたあと、マイクの音量調整のために何か話す必要があります。大体の人は"I live in Tokyo"を連呼しているので僕もそれに倣い"I live in Tokyo"を連呼します。この儀式は新しく人が入室するたびに行われるので注意が必要です。耳栓や置いてある耳当てみたいなやつで防御しましょう。ちなみにこの儀式はもう一度行うことになります。儀式（機器チェック）が終わりいよいよリーディングセクションスタートです。

リーディングセクション

約60分3問の試験がスタート。最初に英文がドンと出てきますが問題文で英文のどこに関する問題かが明示されるので問題をときながら読み進める戦略で行きました。特に波乱なく終了。

リスニングセクション

リスニングが始まる前（ここでは制限時間は減らない）にトイレに行っておこうと思い監督を呼ぶも、トイレは時間が進んでいる時にしかいけないよと言われしょうがないので我慢することに。リスニング試験がスタート。中頃からスピーキングに入るやつが出てくるも音量デカくすればリスニングの邪魔にはならない。ただし、設問に答える時に気が散るので結構キツかったです。普通に聞き取れない部分も多いので勘を信じて解く。これも特に波乱なく終了。

休憩

ここで10分間の休憩が入ります。ロッカーから飲食物だけは持ち出せて食べることができる。お茶とお菓子を摂取して糖分を補給。ゆっくりしてたら席に戻った時には残り15秒くらいでビビった。ちゃんと休憩がいつまでか確認してから休憩しよう！でも残り時間が0になっても即座に始まるわけではないっぽかった。

スピーキングセクション

また機器チェック、つまり"I live in Tokyo"の儀式再びです。最大の関門だと考えていたスピーキング。一問目は準備時間15秒で自分の意見と理由をまとめなければならない。もちろんそんな器用な真似はできず、意見だけ決めて解答時間へ。とりあえず意見を話す。・・・・・（無言タイム）。はい、爆死。練習の時も厳しいなぁと思っていたので当然本番でうまくいくはずもない。45秒の解答時間のうち半分くらい「あ〜」って言ってたように思う。気を取り直して2~4問目。そもそも聞き取れねえよ！みたいなのが多すぎて詰んでしまった。さらに悪いことに、2問目では解答時間中リーディングの文章を見れないことを知らずになにもメモしてなかったのでリーディングの内容も曖昧になってしまいました。なんとか聞き取れた部分を連呼して時間を稼ぎ終了。ここらへんでtoefl2回目いつにしようかなと考え始めました。

ライティングセクション

スピーキングで力が抜けたのがよかったのか、意外と筆が進む。とはいえ規定字数を少し超えるくらいしか書けないのは実力ですね。TOEFLは字数たくさん書くのが大事らしい（知らんけど）。スペルミスというかタイプミスが大量にあったのでそれを修正。他のミスまで手が回りませんでした。independentはアイデア出しに時間がかかりタイプミスすら修正できず終了。

帰宅まで

終わったという安堵感とダメだろうなぁという気持ちを感じつつ画面上の指示に従っていくと、リーディングとリスニングの点数が表示されて、「こんな感じだけど採点していい？」みたいなことを聞かれる。その二つのセクションの出来が意外とよかったのでちょっと精神が回復した。採点してくれるよう頼んで試験終了。神保町に足を伸ばしたあと帰宅。

終わりに

僕のような純ジャパはテンプレートでライティングとスピーキングを最低限取ってリーディングとリスニングで稼ぐのが賢いと思った（小並）。英語力は1週間では上がらないので小手先のテクニックを身につけよう！

2020-12-20

幾何学的にCramer-Raoの定理を理解する（メモ）

Cramer-Raoの定理

準備

標本空間$\Omega = \qty{\omega_0, \dots, \omega_n}$について、その上の確率測度全体のなす多様体$S = S_{n}$を考え、$M$をその部分空間とする。

パラメタ$\xi$によって指定される$M$上の点$p\xi$における$S$の接空間$T{p\xi}S$を考える。$X\in T{p\xi}S$について、$X\log p\xi$ を$e$-表現、$Xp_\xi$を$m$-表現と呼ぶ。ここで、$X$は線形性とライプニッツ則を満たす作用素、つまり微分作用素であり、パラメタによる微分作用素$\pdv{}{\xi_i}$の線形結合で表現できることに注意する。

ここで、微分作用素のなす空間$V = T{p\xi}S$（$n$次元）と、その$e$-表現である$X\log p\xi$のなす空間、つまり$\qty{\pdv{\log p\xi}{\xi_i}}i$が張る線形空間$V_e$ （$n$次元）を同一視することを考える。$\pdv{\log p\xi}{\xi_i}$たちは、確率変数であることに注意。

実は$V_e$は$\Omega$上の確率変数であって、その期待値が$0$となるもの全体の集合と一致する（確率変数全体の次元は$|\Omega| =n+1$なのでそこに制約が一つついて$n$次元となる）。これの良いところは、確率変数に対し内積をいつものように $$ \lang X, Y \rang = \sum{\omega\in \Omega} X(\omega)Y(\omega) = E[XY] $$ で定めると、基底を$\qty{\pdv{\log p\xi}{\xi_i}}i$にとれば、計量が$g{ij} = E[\part{\xi_i}\log p\xi\part{\xi_j}\log p\xi]$

となり$T{p\xi}S$と$V_e$の対応で内積が保存されるところである。

Cramer-Raoの定理

$\xi$の推定値を$\hat \xi$としよう。これは$\Omega$上の確率変数である。$\hat \xi$が不変推定量であるとすると、$E[\hat \xi -\xi] = 0$がなりたつ（バイアスがないということ）。よって$\hat \xi_i -\xi_i \in V_e$である。 $T{p\xi}M$はもちろん$T{p\xi}S$の部分空間であり、$L_i\part_i \log p\xi$たちはその基底である。双対基底はもちろん$Lⁱ = g^{ij}L_j$となる。実は以下が成り立つ。 $$ \lang \hat \xi_i -\xi_i, L_j\rang = \delta_jⁱ $$ これは $$ \begin{align} \partial_iE[\hat\xi_j] &= \partial_i\sum p{\xi}(\omega)\hat\xi_j(\omega)\ &=\sum \partial_i p_{\xi}(\omega)\hat\xi_j(\omega)\ &=\delta_i^j \end{align} $$ などから従う。

結果の式は陪直交の条件に似ている。よって直感的には$\hat \xi_i -\xi_i$を$T{p\xi}^{(e)}M$に射影すれば$L_i$と一致しそうである。実際、 $$ \lang \hat \xi_i -\xi_i, L^j\rang = \lang Lⁱ, L^j\rang $$ が任意の$i, j$に対して成り立つのでその予想は正しい。任意の$\qty{a_i}i$について、$\sum a_i(\hat \xi_i -\xi_i)$を考えても同じく、これを$T{p_\xi}^{(e)}M$に射影すれば$\sum a_i Lⁱ$になる。射影によってノルムは小さくなるので、行列不等式を得る。

参考

藤原彰夫, 情報幾何学の基礎, 牧野書店(2015)

2020-12-15

量子情報の基礎＋量子統計推測の基礎の基礎

この記事は物工/計数 Advent Calendar 2020の16日目のものです。これまでの記事は以下のリンクからご覧ください。物工/計数 Advent Calendar 2020

はじめに
基本的な状態、測定、時間発展
- まとめ
一般的な状態
- まとめ
一般的な測定
- まとめ
量子統計推測
参考文献

はじめに

初めましての人は初めまして。計数工学科B3のまさよしです。16日目の記事は流行りの？量子情報理論についてです。まだまだ勉強中であまり高度なことはわからないので、量子情報の基礎の基礎をお送りします。もともと量子競技プログラミングについて書こうと思っていましたが、やめてしまいました。その名残が例題として残っています。初学者なので間違いも多いと思いますのでご指摘お願いします。

量子情報理論では、状態、測定、時間発展という三つが大きな柱となります。そこで、記事の流れとしてはまず通常の量子力学の授業で導入されるような形でそれらを導入し、そのあとで一般的な形を与えます。最後に応用として量子統計推測の基本を話します。前提知識は教養の線形代数と量子論の基礎です*1。

今回は量子アルゴリズムには触れません。Shorのアルゴリズムについては昔かいたショアのアルゴリズムって何？量子コンピュータだと多項式時間で素因数分解できるってホント？調べてみた！を読んでもらえると嬉しいです。

基本的な状態、測定、時間発展

通常の量子力学の授業（応物2Aの量子力学第一*2など）に則って、状態と物理量を導入します。

前提（量子状態と物理量）量子系にはHirbert空間$\mathcal H$が対応し、量子状態はその単位ベクトル、物理量はエルミート演算子に対応する。

スピン系を例にとって考えてみましょう。

例（スピン系）一つのスピン系にはヒルベルト空間 $\mathcal{H} = \mathbb C$ が付随します。$\mathcal H$ の正規直交基底を $\ket 0, \ket 1$ と書くことにします。これらは当然状態を表します。また、$\ket + = \frac{1}{\sqrt{2}}(\ket 0 + \ket 1), \ket - = \frac{1}{\sqrt{2}}(\ket 0 - \ket 1)$ と定めると、これらも単位ベクトルとなっているので、状態を表します。これらの記号は後の例でも出てくるので心に留めておいてください。

物理量が与えられればその測定値が気になります。そこで測定を以下のように導入します。

前提（測定）物理量$A$の測定値は$A$の固有値であり、量子状態$\bra{\varphi}$に対して測定値が$a$になる確率は、その固有ベクトルに対する射影演算子$P_a$を用いて $$ P(A = a|\ket{\varphi}) = \bra{\varphi}P_a\ket{\varphi} $$ で与えられる。

射影演算子は$\sum_a P_a = I$を満たすので、きちんと規格化されていることがわかると思います。また半正定値なので、確率の非負性も満たします。これらの条件はあとで一般的な測定を導入するときにも重要になります。

測定を定義したところで、状態と測定について補足をしておきます。操作論的観点から言えば、どんな測定でも区別できない2つの状態や、どんな状態に対しても同じ確率分布にしたがって値を返す２つの測定を区別することに意味はありません。そこで、そうした状態や測定は同一視することを約束しておきましょう。

さて、次は時間発展です。シュレディンガー方程式を導入します。

定義（シュレディンガー方程式） $H$をハミルトニアンとして、 $$ i\hbar \frac{d}{dt}\ket{\psi(t)} = H\ket{\psi(t)} $$

量子系の時間発展は基本的にこのシュレディンガー方程式に従うことになります。この微分方程式を形式的に解くと、

$$ \begin{align} \ket{\psi(t)} &= U(t)\ket{\psi(0)}\\ &=\exp(-iH t)\ket{\psi(0)} \end{align} $$

となります。$U(t) = \exp(-iHt)$はユニタリになっています。簡単のために時間のことは忘れて時間発展を始状態から終状態への写像だと思うと、$U(t)$だけを考えればいいことがわかります。さらに以下のような大胆な仮定を置きます。

仮定任意のユニタリ演算子による時間発展が可能である。

やはりスピン系の例を用いて考えてみましょう

例（スピン系）線形演算子$H$を以下のように定義します。 $$ \begin{align} H\ket 0 = \ket + \\ H\ket 1 = \ket - \end{align} $$ これはユニタリ変換になっています。よって実現可能です。（行列表示をすると、 $$ H = \frac{1}{\sqrt 2} \begin{eqnarray} \left( \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right) \end{eqnarray} $$ となります。）

以上が基本的な量子力学の復習でした。

まとめ

状態はヒルベルト空間上の単位ベクトルによって表現される
測定は射影演算子によって表現される
時間発展はユニタリ演算子によって表現される

実は上に上げてあるのはあくまで十分条件でしかありません。実は補助的な系を考えることにより、さらに一般的な測定や時間発展が可能です。それに関して次節から説明していきます。

一般的な状態

前節で状態はヒルベルト空間上の単位ベクトルで表されると述べました。しかしそれだけで十分でしょうか？量子情報理論では多くの確率を扱います。そこで、上で述べた意味での状態を確率的に用意したような状態を考えます。このような状態を混合状態と呼びます。これと区別するために、以前に述べた意味での状態を純粋状態と呼ぶこともあります。

例（混合状態）スピン系で考えます。$\ket 0, \ket 1$といった単位ベクトルは純粋状態です。一方、コインを投げて表が出れば$\ket 0$を、裏が出れば$\ket 1$を与えるような状態、つまり、$\ket 0, \ket 1$を確率$\frac{1}{2}$で混合した状態は混合状態です。これは$\frac{1}{2}\ket 0+\frac{1}{2}\ket 1$でもないし$\ket +$でもないことに注意してください。

では、混合状態と純粋状態を統一的に表す記法はないものでしょうか？ここで密度行列を導入します。

定義（密度行列）純粋状態$\ket\psi$について密度行列 $\rho_\psi$を

$$ \rho_{\psi} = \ket \psi \bra \psi $$ と定める。さらに、$\ket{\psi_i}$を確率$p_i$で混合した混合状態について、密度行列$\rho$を

$$ \rho = \sum p_i \rho_{\psi_i} $$ と定める。

実はこの記法を使うと、上で述べた操作論的な視点で同一視される状態が同じ表現を得ることになり、嬉しいです（詳細は省略します）。また、実は密度演算子は$\mathrm{Tr} \rho = 1, \rho\geq 0$によって特徴付けられることもわかります（これも詳細は省略します）。

まとめ

一般的な状態は密度演算子で表される。

一般的な測定

流れとしては、まず測定として最低限成り立たなくてはならない条件を提示します。次にそれがただの必要条件ではなく十分条件であることを示します。

測定が備えるべき必要条件とはなんでしょうか？混合状態$\rho_{mix} = q\rho1+(1-q)\rho2$に対して測定を行ったとしましょう。この時以下のようなアフィン性が成り立つと必要があります。

$$ \begin{align} P(a|\rho_{mix})&=qP(a|\rho_1)+(1-q)P(a|\rho_2) \end{align} $$

さて、最初の方で述べた射影測定を思い出してみましょう。射影測定は$\sum P_a = I$を満たす射影演算子の組によって表され、純粋状態$\ket \psi$に対して測定値$a$が観測される確率は

$$ \begin{align} P(A = a|\ket \psi)&=\bra \psi P_a \ket \psi\\ &=\mathrm{Tr}P_a\ket \psi \bra \psi\\ &=\mathrm{Tr}P_a\rho_\psi \end{align} $$

と密度行列と射影演算子の積のトレースとして表されることがわかります。一般の測定についても、測定が密度行列から実数値へのアフィン写像で特徴付けられるということから、適当な行列と密度行列の積のトレースを取るという表現が可能であることがわかります。そこでそのような行列の組を${E_m}$とおきます。確率の非負性と規格化条件から

$$ \begin{align} E_m & \geq 0\\ \sum E_m &= I \end{align} $$

を満たさなくてはいけないことも簡単にわかります。これは射影行列の組${P_a}$の拡張になっていることがわかると思います。今、任意の測定が上のような表現を持つことがわかりました。逆に、上の条件（半正定値性、規格化条件）を満たす線形演算子の組み（これをPOVMと呼びます）に対応する測定は実現可能なのでしょうか？答えはYesです。補助系（ancilla）を用いることで、任意のPOVMで表される測定（これをPOVM測定と呼びます）が実現可能であることを示します。以下の証明は参考文献1によります。

証明

${E_m}$:POVM
$\ket \psi$:測定したい系の初期状態
$\ket \phi$:補助系の初期状態（固定）

純粋状態について示せば十分です。

POVM${E_m}$に対して、$m\in {1, 2, \dots, n}$を仮定します。また補助系として、n次元以上のヒルベルト空間$\mathcal H_a$を考え、その基底を$\ket{\phi_i}$とします。今測定したい系$\mathcal H$の初期状態が$\ket \psi$、補助系の初期状態が$\ket \phi$（固定）であるとします。

今、以下のような写像を考えます。

$$ \begin{align} U:\ket \psi\otimes\ket \phi \mapsto \sum_{i = 1}^n \ket{\sqrt{E_i}\psi}\otimes\ket{\phi_i} \end{align} $$ 今、この写像は補助系の状態が$\ket \phi$でないところでは定義されていないことに気をつけてください。この写像は（補助系の状態が$\ket \phi$である物について）内積を保存することが簡単な計算で示せるのでユニタリ変換になっています。（補助系の状態が$\ket \phi$でないところは測定には関係しないので、$H\otimes H_a$から、$H\otimes H_a$への写像として、$U$がユニタリであるように適当に定めてあると思ってください。） $U$を作用させた後に、補助系に対して、基底$\ket{\phi_i}$に対する射影測定を行うと、測定値$i$をえる確率は

$$ \begin{align} P(i|\ket \phi) &= \bra{\sqrt{E_i}\psi}\ket{\sqrt{E_i}\psi}\\ &= \bra{\psi}E_i\ket{\psi}\\ &= \mathrm{Tr}E_i\rho_\psi \end{align} $$ となるので、ちゃんとPOVM測定になっていることが示されました。

ここまで一般的な測定がPOVM測定であることを見てきましが、何が嬉しいのかあんまりわからない人も多いのではないでしょうか？（僕はそうでした）。そこで、例題を用いて考えてみましょう。

問題（exc Not A, not B or not C？） $$ \begin{align} \ket A = \frac{1}{\sqrt 2} (\ket 0 + \ket 1)\\ \ket B = \frac{1}{\sqrt 2} (\ket 0 + \omega \ket 1)\\ \ket C = \frac{1}{\sqrt 2} (\ket 0 + \omega ^2 \ket 1) \end{align} $$

とする（ $\omega ^3 = -1$）。

状態 $A, B, C$ がランダムに与えられるので、どの状態でないかを答えよ。（Microsoft Q# Coding Contest - Winter 2019 B2）

これはcodeforces上で行われた量子競技プログラミングの問題からとってきました。量子競プロに関しては今回は触れませんが結構面白いので色々調べてみてください。

さて、これら三状態は直交していないので完全に区別することはできません。そこで、どの状態でないかを答えるわけですが、通常の射影測定では、直交した軸への射影しかできないので、それもできません。ここでPOVM測定の出番となるわけです。各状態を密度行列で表すと、以下の通りです。

$$ \begin{align} \rho_A &=\frac{1}{2}\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right)\\ \rho_B &=\frac{1}{2}\left( \begin{array}{cc} 1 & \bar\omega \\ \omega & 1 \end{array} \right)\\ \rho_C &=\frac{1}{2}\left( \begin{array}{cc} 1 & \bar\omega ^2 \\ \omega ^2 & 1 \end{array} \right)\\ \end{align} $$

POVMを${E_A, E_B, E_C}$とすると、$P(A|\rho_A) = 0$などとなるために、$\mathrm{Tr}{E_X\rho_X} = 0$（直交条件）である必要があります。天下り的ですが、

$$ \begin{align} E_A =\frac{1}{3}\left( \begin{array}{cc} 1 & -1 \\ -1 & 1 \end{array} \right)\\ E_B =\frac{1}{3}\left( \begin{array}{cc} 1 & -\bar\omega \\ -\omega & 1 \end{array} \right)\\ E_C = \frac{1}{3}\left( \begin{array}{cc} 1 & -\bar\omega ^2 \\ -\omega ^2 & 1 \end{array} \right) \end{align} $$

はPOVMで、直交性の条件を満たします。このPOVMから以前述べた手順でユニタリ変換を構成し、qiskit（Pythonの量子計算ライブラリ）で実装した結果を以下に示します。

f:id:masayoshi361:20201214183816p:plain — 量子回路図（量子回路やqiskitを知らない人は補助系と共にユニタリ変換を施したあと測定していることをみてもらえれば十分だと思います。）

結果（入力がAの場合）出力は00:A, 01:B, 10:Cという対応になっています。

f:id:masayoshi361:20201214183944p:plain — 量子回路図（量子回路やqiskitを知らない人は補助系と共にユニタリ変換を施したあと測定していることをみてもらえれば十分だと思います。）

結果（入力がAの場合）出力は00:A, 01:B, 10:Cという対応になっています。

上の画像は入力がAの場合ですが、観測結果はBまたはCとなっており、正しい結果が返っているのがわかりますね。とは言えこれはユニタリ変換をそのまま使っているので、実際には基本的なゲートに直してやる必要があります。$8\times 8$行列を考えるのは大変なのでコンテストのeditorialでは補助ビットを1つだけ使って測定を構成する方法が示されています。ここでは証明でのユニタリ変換の構成の仕方に揃えるため、あえて実際的には大変な方法を用いました。

まとめ

一般的な測定はPOVMで表される。

量子統計推測

少し応用として量子統計推測を考えてみます。最も簡単な設定として以下のような問題を考えます。

量子系$\mathcal H$の状態が$\rho$または$\sigma$ であるかを判別するのに最適な測定は何か？

状態の識別には結果は二種類で十分なので、$0\leq T\leq I$なる$T$を用いたPOVM$\{T, I-T\}$を考えることになります（今回は$T$に対応する測定結果が出た時、$\rho$だと判定し、$I-T$に対応する結果が出た時、$\sigma$だと判定することにします）。さて、もちろん様々は測定法があるわけですが、どのような評価基準を設ければいいでしょうか？

もし本当の状態が$\rho$であるとしましょう。この時、誤って$\sigma$と判定してしまう確率は$\mathrm{Tr}\rho(I-T)$です。逆に本当の状態が$\sigma$である時謝って$\rho$だと判定してしまう確率は$\mathrm{Tr}\sigma T$となります。ここではこれらを適当な実数$c>0$ で重みづけた$\mathrm{Tr}\rho(I-T)+c\mathrm{Tr}\sigma T$を最小化することを目標にします。この重みは事前確率だと考えてもいいでしょう。

$$ \mathrm{Tr}\rho(I-T)+c\mathrm{Tr}\sigma T = 1+\mathrm{Tr}(c\sigma-\rho)T $$

より、$\mathrm{Tr}(c\sigma-\rho)T$を最小化すればいいです。

$c\sigma-\rho$が$\sum\lambda_i\ket{u_i}\bra{u_i}$と対角化されるとすると、$0\leq T\leq I$より、

$$ \begin{align} \mathrm{Tr}(c\sigma-\rho)T &= \sum\lambda_i\bra{u_i}T\ket{u_i}\\ 0 &\leq \bra{u_i}T\ket{u_i}\leq 1\\ \therefore\mathrm{Tr}(c\sigma-\rho)T &\geq \sum_{\lambda_i<0}\lambda_i \end{align} $$

等号は$T^* = \sum_{\lambda_i<0}\ket{u_i}\bra{u_i}$のとき成立します。

以上から、

$$ \begin{align} \mathrm{min}{T}\mathrm{Tr}\rho(I-T)+c\mathrm{Tr}\sigma T = 1+\sum{\lambda_i<0}\lambda_i\\ \end{align} $$

（上の式がうまく表示できてなかったらごめんなさい。全部はてなブログのせいです。）

さて、例題です。

問題（Distinguish zero state and plus state with minimum error）

状態$\ket 0$または$\ket +$がそれぞれ$1/2$の確率で与えられるので$80\%$以上の正解率を達成せよ。（Microsoft Q# Coding Contest - Summer 2018 C1)

与えられる状態の密度行列はそれぞれ、

$$ \begin{align} \rho_0 &=\left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right)\\ \rho_+ &=\frac{1}{2}\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right) \end{align} $$

です。POVM${T, I-T}$に対して、判定に失敗する確率は一般論のところで述べたように

$$ \frac{1}{2}\left(\mathrm{Tr}\rho(I-T)+c\mathrm{Tr}\sigma T\right) $$

となります（等確率なので$c = 1$のケースに相当します）。

$$ \rho_0-\rho_+ =\frac{1}{2}\left( \begin{array}{cc} 1 & -1 \\ -1 & -1 \end{array} \right) $$

ですから、その固有値は$\lambda_1 = 1/\sqrt 2, \lambda_2 = -1/\sqrt 2$です。よって、最小の誤り確率は$\frac{1}{2}-\frac{1}{2\sqrt 2}$であることが一般論からわかります。逆に最大の正答率は$\frac{1}{2}+\frac{1}{2\sqrt 2}$です。

測定方法も一般論に従って計算しても良いのですが、今回はeditorialに従って、直感的なやり方をとることにしましょう。editorialの図を見ると一発でわかると思いますが、以下で定義する$R_y$ゲートによって入力を$\pi/8$回転させた後で$\ket 0, \ket 1$に対応する射影測定を行います。

$$ R_z(\theta) = \left( \begin{array}{cc} \cos(\theta/2) & -\sin(\theta/2) \\ \sin(\theta/2) & \cos(\theta/2) \end{array} \right) $$

この時、正しく判定できる確率は

$$ \begin{align} P_{correct} &= \frac{1}{2}(\cos ^2(\pi/8)+(\cos (\pi/8)+\sin (\pi/8)) ^2)\\ &=\frac{1}{2}+\frac{1}{2\sqrt 2} \end{align} $$

と最大値を達成しています。

以下が解答となるコードです。Q#で書かれています。Q#に関してはぶるーまんさんのQ#のススメ（ISer Advent Calendar 2020）を参照すると良いでしょう。

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
        open Microsoft.Quantum.Extensions.Math;
  
    operation Solve (q : Qubit) : Int
    {
        body
        {
            // Ry(theta)を適用
            Ry(PI() / 4.0, q); 
            // 測定
            if(M(q) == Zero){
                return 0;
            }else{
                return 1;
            }
        }
    }
}

上の測定は直感的には最適そうですが、一般論を用いることでその最適性が証明できました。

参考文献

石坂智・小川朋宏・河内亮周・木村元・林正人:量子情報科学入門, 共立出版(2012) 量子アルゴリズムや量子テレポーテーションなど様々な話題が載っています。一番おすすめです。余談ですが、著者の一人である小川先生は計数工学科の卒業生らしいです。
林正人:量子情報理論入門, サイエンス社(2004) みんな大好きSGCライブラリです。上の文献よりも進んだ話（量子情報幾何とか）が色々載っています。

*1:こういう言説が正しかった試しはありません。つまりそういうことです。

*2:量子力学第二（3S）よりも成績を出すのが遅いことは応物七不思議の一つに数えられます。

2020-03-30

バブルソートと転倒数

基本

バブルソートの交換回数=転倒数転倒数はBITを使って簡単に求められます（BITは区間和をO(logN)で求められるデータ構造です）。以下そのアルゴリズムを述べます。与えられた数列xの要素を左から順番に見ていくことにして、要素a, b(a<b)が転倒している（つまりソート前の順列ではb aの順に現れるという事です）としたとき、この転倒は要素aを考えているときに加えることにします。つまり要素aを見ているときaより左側にあり、かつaよりも大きいような要素の数を足していくことにします。左から要素を見ていくのと同時に、見終わった要素をBITに追加していくことによって以上の操作を高速に行えます。具体的にはBIT.add(a, 1)をaを見終わった後に行い、BIT.sum([i, n))を答えに加えていきます。ただしiはaのインデックスです。逆にs = [0, 1, 2, 3・・・, n]を左から見ていくという考え方もあります。つまりbitにaのインデックスを追加していくということです。ただxとsを入れ替えただけだとも言えますが...

応用

転倒数はdpと相性がいいです。どうしてかというと上で述べたようにある要素aに関する転倒数を考えているとき、aより大きい、かつaより左にある要素の数がもとめられればいいわけですが、これはaより左の並び方に関係なくaの位置と値のみに依存するからです。これを使うのが以下の問題です。 E - Sorted and Sorted

その他

任意の数列a, bの間の転倒数は片方を0, 1, 2, 3・・・に直すのがいい。同じ要素が複数ある場合はその要素間での交換が起きないようにするのが交換回数を最小にする。 E - Papple Sort

おまけ

C - 転倒距離

2020-03-23

PythonとC++でAtCoder黄色になった話

はじめに

先日のABC159で無事黄色になることができたので、いわゆる色変記事を書こうと思います。

黄色になりました！！！！！！！！！！ pic.twitter.com/9BO5Zo0LqN
— まさよし＠今日も１日１AC (@masayoshi361) March 22, 2020

やったこと

AtCoderを始めるまで

atcoderのアカウント自体は１年生の6月くらいに作っていたのですが特に問題を解くでもなく時間が過ぎて行きました。ところが1年生の2月にとあるきっかけがあり、競技プログラミングやってみようかなぁと思い始めることになりました。一応Pythonを独学でやっていたのと、授業でも扱ったことがあったので言語は自然にPythonを選んでいました。とはいえライブラリとか細かい部分は全然知らなかったので手探りという感じでしたね。また高校数学は一通り学んでいたので初めの方はかなりスムーズだった気がします。また計算量の概念も授業でちょっと扱っていたので基本は理解していたつもりでした。

灰色＆茶色編

これをやりました。

qiita.com

あと蟻本も買いました。これ系の本は一冊手元にあるといいと思います。

形から入る人間なので蟻本を買った
— まさよし＠今日も１日１AC (@masayoshi361) February 28, 2019

緑編

蟻本とけんちょんさんの記事を参考に問題を埋めて基礎的な知識を得て行きました。 qiita.com

水色編

旧abcのdらへんを埋めていました

この辺からは問題を解きながら知らない知識を得ていく感じになります。また、蟻本に乗っているような名前のついたアルゴリズム以外に「典型的な考え方」（操作を逆順に考えるとか）も吸収するのが大事だと思います。

青色編

atcoder problems の青difficultyと黄difficultyを埋めていました。この辺から新ABCのF問題がいい感じに解けるようになりレートも好調に伸びて行きましたが、青後半になると最後の一押しが足りない状態が続き、青上位をゆらゆら揺れていました。そこで黄色になるには青diffくらい全部埋めなきゃ駄目だろうと考え、取りあえず全部埋めました。ここからも時間がかかるのですが、春休み＋コロナで持て余した暇を利用して精進していたら何とか黄色にたどり着くことができました。

現状

現在の精進具合はこんな感じです。一応青diffは全て、黄diffは半分くらい埋めました（が、パフォ推定の仕組みが変わったため今は青diffもちょっと残っています...）いわゆる虚無埋めをしていないので問題数は少し少ないかもしれません。

最近はcodeforcesもちょっとやっています（生活リズムが正しいのであんまり出れていませんが）。

まとめ

とにかく問題を解こう！！

C++とPythonの使い分け

去年までは完全にPythonオンリーだったのですが、少し定数倍をサボるとTLEするなど辛かったのでC++を勉強し始めました。やっぱりC++は早いです（当たり前）。とはいえPythonが光らない場面がないわけではなく、多倍長を扱いたい時であったり、そうでなくとも制限時間に余裕があれば簡潔に書けるpythonは強いと思います。またnumpyやscipyが使えるのも大きな利点です（僕は全然使いこなせてませんが...）。今はまだPythonの経験値の方がはるかに高いので、これは間に合うだろうという問題はPythonを使って、ちょっと怪しいなぁというものだけはC++を使っていますが、これからはC++オンリーになるかもしれません。

結局どっちがいいのか？

青までならpythonでも全然大丈夫だと思いますが、黄色以上だと少し計算量の悪い解法（logが付いてしまうなど）でもC++なら通せたりと少し不利に働くことも多いと思います（もちろんpythonで橙に行ったmaspyさんのような人もいるので無理という話ではありません）。あとは情報の問題もあります。いろんな人の解説記事や蟻本は大体C++で書かれているので、そうしたものを参考にするのにもC++はできた方が良いと思います。なので「自分は競プロを無茶苦茶頑張るぜ」っていう人はC++を勉強すればいいんじゃないでしょうか。もちろん今できる言語があるなら僕みたいに取りあえずそれでやってみて辛くなったらC++を勉強してみるのでもいいと思います。

ライブラリ

今ライブラリ（コピペできるようにしているコード）として持っているアルゴリズム、データ構造は以下の通りです。

グラフ系
- 最短距離3種（dijkstra, warshall–foyd, bellman-ford）
- 最小全域木（prim法）
- 最大流
- 最小費用流
- LCA
- 強連結成分分解
データ構造
- segment tree（遅延も）
- BIT
- UnionFind
文字列アルゴリズム
- rolling hash
- suffix array
数学
- combination
- 行列累乗
- 約数列挙、素因数分解

高速フーリエ変換はscipyにあるので持っていません。

知識とか典型

メモ程度に今ある知識を書いておきますが、ライブラリとは異なり当然抜けも多いと思います。また、個人的メモの側面が強いので独自の呼び方とかが混じってるかもしれません。

探索
- 二分探索
- 貪欲
- 半分全列挙
- 決め打ち
dp
- ナップザックdp
- bitdp
- 桁dp
- 木dp
- 全方位木dp
- dp高速化（累積和、セグ木、bitset）
グラフ
- bfs, dfs
- 最短経路
  - グラフを改造する
- 木
  - 直径
  - lca
  - オイラーツアー
- 二部グラフ
高速化
- 累積和
- imos法
その他
- 包除原理
- 平均をあらかじめ引いておく
- 転倒数
- grundy数
- 差だけ持つ
高校数学の整数、場合の数、確率とかの基本

2020-03-20

二乗の木DP

部分木のサイズに比例する大きさのdpテーブルをマージしていくタイプのDPの計算量はO(n²)

void dfs(int v, int p){
    sz[v] = 1;
    dp[v] = {INF, s[v]};
    for(auto &nv:g[v]){
        if(nv == p) continue;
        dfs(nv, v);
        vl merged(sz[v]+sz[nv]+1, INF);
        rep(i, sz[v]+1){
            rep(j, sz[nv]+1){
                chmin(merged[i+j], dp[v][i]+dp[nv][j]);
            }
        }
        sz[v] += sz[nv];
        dp[v] = merged;      
    }
    dp[v]

参考: 木と計算量前編〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

2020-03-19

もうバグらせない桁dp

こんな感じで書けばいいと思うよ

//n = 桁数
//k = 状態数(余りか最後の桁が多い)
vector<mat<ll>> dp(n+1, mat<ll>(k, vl(2)));
dp[0][0][1] = 1;//0桁の時
rep(i, n)rep(j, k){
    rep(d, 10){
        dp[i+1][f(j ,d)][0] += dp[i][j][0];//前の状態がdp[i][j][0]でi+1桁目をdにする遷移
    }
    rep(d, m[i+1]){
        dp[i+1][f(j, d)][0]+=dp[i][j][1];//前の状態がdp[i][j][1]でi+1桁目をdにする遷移
    }
    dp[i+1][f(j, m[i])][1] += dp[i][j][1];
}

0でpaddingするとまずい問題は以下のようにするのがいいかも

mx = list(map(int, list(str(mid))))
mx = list(map(int, list(str(mid))))
n = len(mx)
dp = [[[0]*2 for i in range(s)] for j in range(n+1)]
//1桁目は手動で
for i in range(1, mx[0]):
    dp[1][i][0] = 1
dp[1][mx[0]][1] = 1

for i in range(1, n):
    for j in range(10):
        for d in range(10):
            if abs(j-d)<=1:
                dp[i+1][d][0]+=dp[i][j][0]
        for d in range(mx[i]):
            if abs(j-d)<=1:
                dp[i+1][d][0]+=dp[i][j][1]
        d = mx[i]
        if abs(j-d)<=1:
            dp[i+1][d][1]+=dp[i][j][1]
    //i+1桁目が最高位になる場合をたす
    for d in range(1, 10):
        dp[i+1][d][0]+=1