Microsoft Q# Coding Contest - Winter 2019 - その3
前回の続きでB1からになります。
$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$
B1. Distinguish three-qubit states
問題
次の2つのうちのいずれかの3 Qubitの状態が与えられるので、 そのどちらが与えられたのかを答えよ。 操作後のQubitの状態は問わない。
- $\ket{\psi_0} = \frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{2}\ket{001})$
- $\ket{\psi_0} = \frac{1}{\sqrt{3}}(\ket{100}+\omega^{2}\ket{010}+\omega\ket{001})$
- where $\omega = e^{\frac{2i\pi}{3}}$
解答
B問題は、Qubitの状態を見分ける問題になります。 量子コンピューターにおいては、量子ビットを頑張っていじっても、直接的にはその波動関数が見えるわけではないので、何とかして測定して人間が見えるようにしてやらなければ計算した意味も全く無いという話になってしまいます。なので、状態を見分けるというのは非常に重要なタスクです。一般的にはこれは必ずしも100%の確率で状態を見分ける必要はなくて、例えばBQPという計算クラスなら、誤り確率1/3以下であればよいということになっています(何回もやれば、確率に対して指数的に正解率が上げられるので、1/3ではなくて1/2未満ならなんでも大丈夫みたいです)。しかし今回のタスクは、100%の精度でこの識別を行えというものです。
非常に難しかったです。実際に正答率もだいぶ低かったように見えます。
見分けるべき状態が直交しているなら割と簡単に識別できるのですが、
今回の $\ket{\psi_0}$ と $\ket{\psi_1}$ は直交していない(?)
($\braket{\psi_0}{\psi_1}=\frac{1}{3}(1+\omega^{3}+\omega^{3})=1)$)ので、
すんなりとは見分けられてくれません。
計算間違っていて $\braket{\psi_0}{\psi_1}=\frac{1}{3}(1+\omega^{-1}+\omega^{1})=0$ なので直交していますね…。
直交しているので見分けられます。
どこから手を付けたものか悩ましいですが、 識別ではなく作るのであればそれなりに簡単です。 3状態のW state $\frac{1}{\sqrt{3}}(\ket{001}+\ket{010}+\ket{100})$ に Phase shiftゲート(R1) をかければ良さそうです。1Qubit目の所に$\omega$を、2Qubit目の所に$\omega^{2}$をかければ良いので、$R1(\frac{2\pi}{3}, qs[1])$, $R1(\frac{4\pi}{3}, qs[2])$を順に適用すれば良さそうです。
ということは、その逆をすればW stateに戻るということになります。$R1(\frac{-2\pi}{3}, qs[1])$, $R1(\frac{-4\pi}{3}, qs[2])$を順に適用すれば良いです。
operation Solve (qs : Qubit[]) : Int { R1(-PI()*2.0/3.0, qs[1]); R1(-PI()*4.0/3.0, qs[2]); ... }
これを適用した時点で、$\ket{\psi_0}$、$\ket{\psi_1}$はそれぞれ
$$\frac{1}{\sqrt{3}}(\ket{100}+\ket{010}+\ket{001})$$
$$\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{001})$$
になります。ここからさらに $\ket{\psi_0}$の方をゼロ状態$\ket{000}$に戻す操作を考えます。 ゼロ状態からW stateを作る操作は、前回のA1の測定を使わない方の解をちょっといじって、
operation W3 (qs : Qubit[]) : Unit { Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]); (ControlledOnInt(0, H))([qs[0]], qs[1]); // 1/sqrt(3)*(|000>+|010>+|100>) (ControlledOnInt(0, X))(qs[0..1], qs[2]); // |000> -> |001> // 1/sqrt(3)*(|001>+|010>+|100>) }
このような操作になるので、W stateを元に戻すには、これの逆操作を行えば良いということになります。 量子ゲートはすべてユニタリー行列であり、ユニタリー行列は随伴行列が逆行列になる行列なので、自明な逆操作が存在します。なので、一つずつ逆操作を逆に適用していけば良いのですが、そういうのはそれこそ自明に存在しているので、Q#にはその逆操作を自動で作ってくれる機能があります。
operation W3(qs: Qubit[]) : Unit { body(...) { Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]); // (1) (ControlledOnInt(0, H))([qs[0]], qs[1]); // (2) (ControlledOnInt(0, X))(qs[0..1], qs[2]); // (3) } adjoint auto; }
全体をbody(...){}
で囲んで、最後にadjoint auto;
と書けば、随伴バージョンを自動で作ってくれます。Adjoint F(q)
などと書けば、随伴バージョンを呼び出すことができます。これを用いると、
operation Solve (qs : Qubit[]) : Int { R1(-PI()*2.0/3.0, qs[1]); R1(-PI()*4.0/3.0, qs[2]); Adjoint W3(qs); ... }
これで$\ket{\psi_0}=\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{2}\ket{001})\Longrightarrow\ket{000}$ の変換ができました。
このとき、$\ket{\psi_1}$の方がどう変換されているのか計算してみると、
$$\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{001})$$
$$\Longrightarrow\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{000})\tag{Adjoint (3)}$$
$$\Longrightarrow\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{0}\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\ket{0}+\omega^{-1}\ket{0}\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0})\tag{Adjoint (2)}$$
$$=\frac{1}{\sqrt{6} } ( (\omega+\omega^{-1} )\ket{000}-(\omega-\omega^{-1})\ket{010}+\sqrt{2}\ket{100})$$
$$ \Longrightarrow\frac{1}{\sqrt{6} } ( (\omega+\omega^{-1} )(\cos( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{0}+\sin( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) ) \ket{1} )\ket{00}\\ +\sqrt{2}(\sin( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{0}-\cos( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{1})\ket{00}+...) \tag{Adjoint(1)} $$
めんどうなので$\ket{000}$の係数のみ計算
$$=\frac{1}{\sqrt{6} }( (\omega+\omega^{-1} )\sqrt{\frac{2}{3}}\ket{000}+\sqrt{2}(\sqrt{1-{\frac{2}{3}} } ) )\ket{000}+...)$$
$$=\frac{1}{\sqrt{6}}(-1\ket{000}+1\ket{000}+...)$$
$$=\frac{1}{\sqrt{6}}(0\ket{000}+...)$$
なぜか$\ket{000}$の係数が0になりました(なんでこんな都合良く0になるんでしょう?)。ともかく、これで入力が$\ket{\psi_0}$のときは100%の確率で$\ket{000}$になって、入力が$\ket{\psi_1}$のときは100%の確率で$\ket{000}$以外になる操作が書けました。
よって、これらを組み合わせて、解答が得られます。
operation Solve (qs : Qubit[]) : Int { R1(-PI()*2.0/3.0, qs[1]); R1(-2.0*PI()*2.0/3.0, qs[2]); Adjoint W3(qs); if (M(qs[0]) == Zero && M(qs[1]) == Zero) { return 0; } else { return 1; } } operation W3(qs: Qubit[]) : Unit { body(...) { Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]); (ControlledOnInt(0, H))([qs[0]], qs[1]); (ControlledOnInt(0, X))(qs[0..1], qs[2]); } adjoint auto; }
B2. Not A, not B or not C?
問題
以下のA,B,Cいずれかの状態が入力として与えられる。
- $\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})$
- where $\omega = e^{\frac{2i\pi}{3}}$
これらは直交ではないので確実に識別することはできない。なのでその代わりに、どの状態ではない、言うことを示せ。すなわち、
- $\ket{A}$ であれば、1か2
- $\ket{B}$ であれば、0か2
- $\ket{C}$ であれば、0か1
を、それぞれ返せ。
言い換えると、$\ket{A}$ でないのならば0を、$\ket{B}$ でないのならば1を、$\ket{C}$ でないのならば2を、それぞれ返すというのと同値である。
プログラムは1000回実行され$\ket{A}$, $\ket{B}$, $\ket{C}$は等確率で選ばれる。操作後のQubitの状態は問わない。
解答
これが最難問のようです。 いろいろ論文をサーベイしてみたところ、確かにこの3状態ならば、100%の確率で3つのうちどれかの状態ではないということが言えるみたいですが、実際に量子ゲートの形で実装できるように書いてくれているものが見つけられませんでした。
制限時間内に正解できなかったので、他の人の解答を見たところ、
operation Solve (q0: Qubit) : Int { mutable m = 0; H(q0); S(q0); using(q1 = Qubit()){ Controlled Ry([q0],(2.0*ArcCos(1.0/Sqrt(3.0)), q1)); H(q0); set m = ResultAsInt(MultiM([q0, q1])); Reset(q1); } if (m == 1) { return 1; } elif (m == 0) { return 2; } else { return 0; } }
思ったよりシンプルにできるみたいです。ちなみに、MultiM
はQubitをまとめて測定する関数で、ResultAsInt
は計測結果を2進数でIntにデコードする関数です。
なんでこれで答えが得られるのか、実際に計算してみると、$\ket{A}$は、
$$\ket{A}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{10})$$ $$\Longrightarrow\ket{0}\tag{H(q0)}$$ $$\Longrightarrow\ket{0}\tag{S(q0)}$$ $$\Longrightarrow\ket{00}\tag{Qubit増やす}$$ $$\Longrightarrow\ket{00}\tag{Controlled Ry}$$ $$=\frac{1}{\sqrt{2}}(\ket{00}+\ket{10})\tag{H(q0)}$$
$\ket{B}$は、
$$\ket{B}=\frac{1}{\sqrt{2}}(\ket{0}+\omega\ket{1})$$
$$\Longrightarrow\frac{1}{\sqrt{2} }(\frac{1}{\sqrt{2} }(\ket{0}+\ket{1} )+\omega\frac{1}{\sqrt{2} }(\ket{0}-\ket{1} ) )\tag{H(q0)}$$
$$=\frac{1}{2}( (1+\omega)\ket{0}+(1-\omega)\ket{1} )$$
$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{0}+i(1-\omega)\ket{1} )\tag{S(q0)}$$
$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{10} )\tag{Qubit増やす}$$
$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{1}(\cos(\cos^{-1}(\frac{1}{\sqrt{3} } ) )\ket{0}-\sin(\cos^{-1}(\frac{1}{\sqrt{3} } )\ket{1} ) ) ) \tag{Controlled Ry} $$
$$=\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{1}(\frac{1}{\sqrt{3}}\ket{0}-\sqrt{\frac{2}{3}}\ket{1}))$$
$$\Longrightarrow\frac{1}{2}( (1+\omega)\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0}+i(1-\omega)\frac{1}{\sqrt{2}}(\ket{0}-\ket{1}) (\frac{1}{\sqrt{3}}\ket{0}-\sqrt{\frac{2}{3}}\ket{1}))\tag{H(q0)}$$
面倒なので$\ket{10}$の係数だけ抜き出し
$$(1+\omega)\frac{1}{\sqrt{2}}+i(1-\omega)\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$
$$=(1+\cos(2\pi/3)+i\sin(2\pi/3))\frac{1}{\sqrt{2}}+i(1-\cos(2\pi/3)-i\sin(2\pi/3))\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$
$$=(1-\frac{1}{2}+i\frac{\sqrt{3}}{2})\frac{1}{\sqrt{2}}+i(1+\frac{1}{2}-i\frac{\sqrt{3}}{2})\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$
$$=\frac{1}{2\sqrt{2}}+i\frac{\sqrt{3}}{2\sqrt{2}}+i(\frac{\sqrt{3}}{2\sqrt{2}}-i\frac{1}{2\sqrt{2}})$$
$$=0$$
なぜか$\ket{10}$の係数が0になります。$\ket{C}$の計算は面倒なので省略しますが、こちらは同様に$\ket{00}$の係数が0になります。
なので、たしかにこれを計測した結果が
- $00$なら$\ket{C}$ではない
- $10$なら$\ket{B}$ではない
- $01$か$11$なら$\ket{A}$ではない
ということがわかるので、確かに問題が解けています。しかしこれは…どうやって導くのでしょう???(´・_・`)???
自力で解けないと悔しいので、なんとか自力で解いてみます。
1 Qubitしかなければ測定結果は2通りしか得られず、$\ket{A}$, $\ket{B}$, $\ket{C}$は直交ではないので、おそらく少なくとも1 Qubitの追加Qubitが必要になるはず(そうじゃなかったら少なくとも1つは確実に識別できてしまう)です。そこで、次のような量子回路が作れたならば、問題が解けたと言うことになります。
$$if \ket{\psi}=\ket{A} \Rightarrow a=0, b=0, \neq0, d\neq0$$ $$if \ket{\psi}=\ket{B} \Rightarrow a\neq0, b\neq0, c=0, d\neq0$$ $$if \ket{\psi}=\ket{C} \Rightarrow a\neq0, b\neq0, \neq0, d=0$$
ブッロホ球上でのベクトルの回転を考えると、Rx
とRy
の合成があれば任意の回転が表現できるはずで、あとはコントロールするビットと符合の組み合わせが計4通り、トータルで8個のゲートを繋いだもので任意の記述可能なユニタリー行列は表現されるはずです(具体的な8個は後のコードを参照)。
パラメーターをdouble 8個にまで落とせたら、もう解けそうですね。そうです、焼きなましです。焼きなましに持ち込んでやればこっちのもんです。解けない問題はありません。
基本的には上の条件にマッチするときに0になって、そこから外れれば外れるほど大きくなるスコアを設定して焼き鈍せば良いですが、今回は誤差0に限りなく近い解が必要なので、温度に応じてパラメーターの変動率を下げていくのが良いでしょう。
そうして得られたのが次のコードです(先頭にH(q0)
が挟まっているのはこれがないと上手く収束しなかったからなんですが、本当は無しでも行けるはず…?)。
operation Solve (q0: Qubit) : Int { mutable m = 0; using (q1 = Qubit()) { H(q0); (ControlledOnInt(0, Ry))([q0], (4.712388980385413, q1)); (ControlledOnInt(0, Rx))([q0], (3.1415926535894254, q1)); (ControlledOnInt(1, Ry))([q0], (0.4528278334939593, q1)); (ControlledOnInt(1, Rx))([q0], (2.437018063152431, q1)); (ControlledOnInt(0, Ry))([q1], (2.2598858459337396, q0)); (ControlledOnInt(0, Rx))([q1], (1.7816609588202006, q0)); (ControlledOnInt(1, Ry))([q1], (4.712388980374012, q0)); (ControlledOnInt(1, Rx))([q1], (5.243709997732253, q0)); set m = ResultAsInt(MultiM([q0, q1])); Reset(q1); } if (m == 0 || m == 1) { return 0; } elif (m == 2) { return 1; } else { return 2; } }
というわけで、脳筋焼きなまし殴りでも解けたので、これで人の閃きに頼らなくても、古典コンピューターを使いこなす人間であれば量子コンピューターが扱えるはずなので、安心して眠れます。メタ的な話になりますが、こういうのを量子コンピューターで解いて欲しいものですね。量子コンピューターとあろうものを、人間が閃かないと使えないというのは釈然としませんもの。
B1. 別解
B1もやっぱり考えて解いてはいけない気がしてきたので、焼き鈍しでごり押してみます。
入力は3Qubitですが、3Qubitのユニタリー変換を探索するのは大変そうなので2Qubitに縮めます。これは$\ket{001}$を$\ket{110}$に変換して、3Qubit目を$\ket{0}$にしてしまえば良いでしょう。もう一つB2と違うところは、2状態の識別なので$\ket{\psi_0}\Rightarrow\alpha\ket{00}+\beta\ket{01}$、$\ket{\psi_1}\Rightarrow\gamma\ket{10}+\delta\ket{11}$と、それぞれ状態が確定できるように分離できるものを探します。
見つかったコードを貼り付けて、前処理を入れて、完成です。
operation Solve (qs : Qubit[]) : Int { // 前処理 // |001> => |110> CNOT(qs[2], qs[0]); CNOT(qs[2], qs[1]); CCNOT(qs[0], qs[1], qs[2]); let q0 = qs[0]; let q1 = qs[1]; // 焼きなましで求めた2qubitのユニタリー変換 H(q0); (ControlledOnInt(0, Ry))([q0], (0.000000000018460788453467103, q1)); (ControlledOnInt(0, Rx))([q0], (5.064392436516295, q1)); (ControlledOnInt(1, Ry))([q0], (2.324596181147987, q1)); (ControlledOnInt(1, Rx))([q0], (4.7123889803884005, q1)); (ControlledOnInt(0, Ry))([q1], (3.416645503599746, q0)); (ControlledOnInt(0, Rx))([q1], (2.2141724456737695, q0)); (ControlledOnInt(1, Ry))([q1], (3.7803967560193463, q0)); (ControlledOnInt(1, Rx))([q1], (0.7682002923185038, q0)); let r0 = M(qs[0]); if (r0 == Zero) { return 1; } else { return 0; } }
Microsoft Q# Coding Contest - Winter 2019 - その2
前回与太話だけで終わってしまったので、今回はちゃんと解説していきます。
$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$
A1. Generate state |00⟩ + |01⟩ + |10⟩
Aのカテゴリーは、指定されたQubitの状態を生成せよという問題になります。 これはその1問目です。
問題のタイトルで説明が完了している感じがしますが、 タイトルの通り、入力として2 Qubitの状態 $\ket{00}$ が与えられるので、 出力として $\frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10})$ を生成せよという問題です。
いわゆる3状態のW stateに似たものを作ればいいのですが、 前回のA4の問題が $2^{k}$ 状態のW stateを作れというもので、 これが2のべき乗の場合は割と簡単にできるのですが、3状態というのは案外作りづらくなっています。 前回のAのラストの問題よりも難しいのが今回の最初の問題に投入されたことで、 今回の難易度の向上が見て取れます。
ところで僕は個人的に前回の問題を$2^{k}$ 状態を作れというところを$k$ 状態を作れという風に読み間違いをしていて、 なぜかすでに問題が解けていたので、そこから答えを持ってきました。
やり方としてはいくつかあると思いますが、まず簡単な方法から。 この問題では測定が制限されていない(ほかの問題には測定が行えないものもある)ので、 測定を行うとシンプルに解くことができます。
まず、3状態の重ね合わせ作らなければならないので、入力の2つのQubitそれぞれにHadamardゲート(H)を使います。 そうすればとりあえず4状態の重ね合わせが得られます。
$$H(\ket{0}) H(\ket{0}) = \frac{1}{2}(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$
operation Solve (qs : Qubit[]) : Unit { H(qs[0]); H(qs[1]); }
ここからなんとか右端の $\ket{11}$ を消すことを考えます。
qs[0]
とqs[1]
の状態を確定させずに$\ket{11}$の状態を判別するために、もう1 Qubit導入して、
そのQubitと$\ket{11}$の状態をToffoli(CCNOT)ゲートを用いてentangleさせます。
operation Solve (qs : Qubit[]) : Unit { H(qs[0]); H(qs[1]); using (r = Qubit()) { CCNOT(qs[0], qs[1], r); Reset(r); // Qubit解放前に |0> にしておく必要があるのでこれがいる } }
r
はqs=${\ket{11}}$の時のみ$\ket{1}$になるので、CCNOT後の状態は $$ \frac{1}{2}(\ket{000}+\ket{010}+\ket{100}+\ket{111}) $$
になります。
ここでr
を測定します。0が得られれば、qs
の状態は、$ \ket{00}$, $\ket{01}$, $\ket{10} $ の等確率な重ね合わせになるので、
これはまさに求めたい結果になります。
1が得られてしまった場合、qs=$\ket{11}$で確定してしまうので、これは望まぬ状態です。
望まないので、もう一度やり直します。
1回の試行あたり$\frac{3}{4}$の確率で正解が得られるので、これを繰り返せば、TLEまでには十分な確率で答えが得られるはず、ということになります。 全体のコードは次の通り。
operation Solve (qs : Qubit[]) : Unit { repeat { ResetAll(qs); H(qs[0]); H(qs[1]); mutable ok = false; using (r = Qubit()) { CCNOT(qs[0], qs[1], r); set ok = M(r) == Zero; Reset(r); } } until(ok) fixup{} }
これが測定を用いた解法になりますが、測定を用いてしますとadjointにできなくなったりあんまり嬉しくないみたいなので、 測定を用いない解法も示しておきます。測定に頼らないので、余計なQubitを使わず、必ず1回で望みの状態が作れます。
まず状態 $\ket{0}$ から、$\sqrt{\frac{2}{3}}\ket{0}+\sqrt{\frac{1}{3}}\ket{1}$ を作り出します。 このためには、ブロッホ球でいうところのY軸方向に回転させればよさそうです。 $\ket{0}$をY軸方向にΘ回転させると$\cos{\frac{\theta}{2}} \ket{0}-\sin{\frac{\theta}{2}}\ket{1}$になるので、$ \theta = \cos^{-1}({\sqrt{\frac{2}{3}}}) * 2$ とすれば そうなりそうです。
そこから、$\ket{0}$の部分を均等に分割すれば、等確率な3状態が作れそうです。
Controlled Hゲートを使えばよいですが、$\ket{1}$ ではなく、$\ket{0}$でコントロールしたいので、
(ControlledOnInt(0, H))([qs[0]], qs[1])
とします。
この時点で $ \frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10}) $ の状態が出来上がるので、これで完成です。
operation Solve (qs : Qubit[]) : Unit { Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]); (ControlledOnInt(0, H))([qs[0]], qs[1]); }
コードとしてはこちらの方が短いですね。
A2. Generate equal superposition of four basis states
N Qubitのゼロ状態 $\ket{0...0}$ と、basis stateを表す4つの古典ビットのベクトルが与えられるので、
$$ \ket{S} = \frac{1}{2}(\ket{\psi_0}+\ket{\psi_1}+\ket{\psi_2}+\ket{\psi_3}) $$
という状態を作れ、という問題。こちらの方がA1よりも簡単な気がしますね。
とりあえず4つの状態を重ね合わせを作らないといけないので、なにはなくともHadamardゲートを2回使います。 使うのですが、そのまま使うと面倒なので、Hadamardゲートを使う用の余分なQubitを2つ作ることにします。
operation Solve (qs : Qubit[], bits : Bool[][]) : Unit { using (rs = Qubit[2]) { H(rs[0]); H(rs[1]); ... } }
これで状態は $$ \frac{1}{2}(\ket{0...000} + \ket{0...001} + \ket{0...010} + \ket{0...011}) $$ になるので、後ろ2 Qubitでコントロールすれば前のQubitは好きなようにいじれるようになります。
operation Solve (qs : Qubit[], bits : Bool[][]) : Unit { using (rs = Qubit[2]) { H(rs[0]); H(rs[1]); for (i in 0..n-1) { for (j in 0..3) { if (bits[j][i]) { (ControlledOnInt(j, X))(rs, qs[i]); } } } ... } }
末尾の2 Qubit(= rs
) がj
の時にbits[j][i]
が立っているなら、qs[i]
にX
をかけるというコードになります。
これで状態は $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 01} + \ket{\psi_2 10} + \ket{\psi_3 11}) $$ になるのですが、 うしろに余計なものがくっついてしまっているので、すべて $\ket{00}$にしてやる必要があります。 測定などを行ってしまうとエンタングルしている部分が台無しになってしまうので、 コントロールゲートで何とかします。
といっても、$\psi_i$はすべて異なることが保証されているので、今度は$\ket{\psi_i}$の部分でコントロールして後ろの部分を消してやればよいです。
operation Solve (qs : Qubit[], bits : Bool[][]) : Unit { using (rs = Qubit[2]) { H(rs[0]); H(rs[1]); for (i in 0..n-1) { for (j in 0..3) { if (bits[j][i]) { (ControlledOnInt(j, X))(rs, qs[i]); } } } (ControlledOnBitString(bits[1], X))(qs, rs[0]); (ControlledOnBitString(bits[2], X))(qs, rs[1]); (ControlledOnBitString(bits[3], X))(qs, rs[0]); (ControlledOnBitString(bits[3], X))(qs, rs[1]); } }
ControlledOnBitString
というおあつらえ向きな関数があるので、これを使えばすっきり書けます。
これで状態が $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 00} + \ket{\psi_2 00} + \ket{\psi_3 00}) $$
になって、余分に確保したQubitはすべて$\ket{00}$になったので、解放されて、消えて、求める状態が残ります。
Microsoft Q# Coding Contest - Winter 2019
去年の夏に第一回が行われた、マイクロソフトによるQ#のプログラミングコンテストが再びやってきました。 個人的に凄く楽しかったので、次回があると良いなあと勝手に期待していたのですが、案外早くやってきてくれて嬉しいです。
2018夏とタイトルに着いていたので、いずれ別の季節にやってくれるのではと思っていたので、 今年の夏頃にも是非とも期待しておりますマイクロソフトさん。
さて、ご存じの方も多いかと思いますが、Q#というのはマイクロソフトが開発している、量子コンピューター向けのプログラミング言語です。 量子コンピューターとは何かと言いますと、バズワードです。バズワードってなんやねんって仰る方がいるかもしれませんが、 バズワードになってしまったことは仕方がありません。わたしもよもや量子コンピューターがこんな扱いになるなんて、 2010年代も広範になるまで全く思いもよらないことだったんですから。
それはともかく、昨今の量子アニーリングマシンに端を発する、量子コンピューターとはなんぞや問題がどんどん拡大を続けている風潮に反して、 マイクロソフトが社内で開発しているという噂の量子コンピューターは、古式ゆかしい、量子チューリングマシンの定義に基づく、 量子ゲートを組み合わせた量子回路によって実現されるも、いわゆる「狭義」の量子コンピュータと呼べるもののようで、 どういう計算ができるのだとか、どういう計算が古典コンピューターと比較して真に高速に行えるのかという、 そういう研究もおそらく量子コンピューターの中ではもっともしっかりやられている分野であろうと思います。
計算複雑性理論によると、BQP の定義の逆からして、 これを多項式時間で解からしむるデバイスがまさに量子コンピューターであると言えるし、 しかるモチベによって、BQP研究はそれこそもう死ぬほど行われているはずなので、 これがある程度のサイズ以上で実現したら、世の中的にはいくつかの、 有用であるにかかわらず時間的な都合で解けなかった問題が解けるようになるはずなので、 世の中の様相が少なからず変わるという可能性が高いでしょう。
最たるものが素因数分解で、これが効率よく解けないと言うことが、 現代の良く用いられている公開鍵暗号の破られにくさの根拠に用いられているので、 これが破られると、全世界の暗号が全部破られてしまい、そういうものを失った人類は再び戦争の世の中へと 歩みを進めていくことになるのであった……。
などと言うことにもならなさそうで、私個人的には多項式時間っていうのはそんな楽観的なものだと思っていなくて、 有名な素因数分解の量子アルゴリズムであるShorのアルゴリズムでは、桁数の3乗回のゲート数やら測定やらが必要だそうで、 そういうのを例えば、桁数数千の素因数分解に適用しようと思うと、結局の所計算量のオーダーとしては数十億に及びますし、 これが現実的な時間でできるかはまた別問題じゃないかとも思っています。
ましてや桁数を倍にするのは簡単だけど、桁数を倍にされたら、量子計算で素因数分解する手間はあっという間に8倍にされてしまいます。 きっと多項式時間が現実的に解けるという風潮の背景には、かつてのシリコン半導体が、ムーアの法則に従っている、乃ち、 コンピューターの持ちうる計算性能が、時間に対して指数的なのびを示すという事実が元となっている可能性がありますし、 だとすれば多項式時間アルゴリズムは何時かの未来には漸近的に定数時間で解けてしまうというのも乱暴とも言えないのでしょうけれども、 残念ながらシリコン半導体には物理限界が近そうですし、また、量子コンピューターはそもそも本質的に指数的に性能が伸びていくものなのかも よく分かりません(少なくとも僕には)。
だからすぐにどうなるという話でもないと思いますし、まあそもそもだからなんやねんという話で、もっと別の、 どこかの誰かがとても解きたかった問題にはキッチリマッチすることもある可能性もあるので、 やっぱりそういう計算を行うツールが一つ増えることは、我々プログラマーにとっては全く無視できるものではありませんよね。
前置きが長くなり過ぎました。 Microsoft Q#コーディングコンテストについて少し説明しましょう。
このコンテストは、MicrosoftのQ#というプログラミング言語を用いて、与えられたタスクの条件を満たすコードを書いて提出して、制限時間以内に正解を返すプログラムを書けばOKというものです、なるべく沢山のタスクについて、速く正確に作った者が勝者になります。プロコンに慣れ親しんでいる方にとっては、Q#という所だけが独特で、それ以外は普通のプロコンと余り変わらないと考えて良いと思います。そういう風に考えて大丈夫なので、プロコン好きな人、次のQ#コンテストがあったら、いっしょに、でましょ?(,,´・_・`,,)
今コンテストは、量子コンピュータのプログラミング自体が大変難しい上に、従来のプログラミングとはやり方も目的も何もかも異なってきますので、その全く異なる環境への柔軟性を見せられるかと言うところが一つのポイントだと思っています。オッサンのカチカチ頭ではきびしくて、お子様のプルプル脳みそだとジュワーッと新概念がみるみる浸透していって、なんなら小学生とかが優勝してもおかしくないコンテストだと思います。
問題のカテゴリーは大きく4つに分けられており、まず1つ目がAグループ、「特定のQubitの状態を作れ」というものです。初期状態のQubitをぐりぐり動かして複数のQubitをコネコネもつれさせて、お望みの形を作り上げるという、いうなれば粘土工作(?)のようなタスクですね。いろいろ試しているのが楽しい問題です。ですが、そういう職人的な楽しみをすててシステマティックに解く画一的な方法を考えるのも一つのテーマな気はします。
次のBグループは、Aとは逆な感じで、与えられたQubitの状態がどういう状態なのかを判別する系のタスクになります。問題としては、2つの状態のうちのどちらであるか、とか、100%分からないなら、20%の確率で絶対に正解を出せとか、結構バリエーションに富んでいます。与えられたQubitをもちもちねばねばうごかし、これなら見破りやすいぞという形に持っていって、そこで測定して、スパーン!と正解を言い当てる、とてもかっこいいタスクです。でもここが一番難しいんですよね。いわば量子の世界から現実の世界へデータを持ってくるフェーズですし、そういうときに情報はどんどん失われる。でも量子の世界で閉じこもったままで何も計測しないなら、量子計算自体何の意味もないんですよね。猫が死んでるのかも生きているのか、勇気を振り絞って、Qubitを叩き潰すタイプの問題です。
つぎのCグループは、オラクルがテーマです。オラクルと一言で言ってもいろいろありますしなんだろうと思われるかもしれませんが、ここでのオラクルは量子オラクルです。量子オラクルというのは、なんか関数渡すから、その結果をこの別のQubitにもつれさせた形で記録してくれ、というあんまり直感的ではない自明的な一連のプロトコルになります。要するに、Qubit上の関数を書けという話だと思うのですが、Qubitは破壊できないし、コピーもできない(No cloning theoremとか)ので、結局出力を何か他のビットにもつれさせるしかないんでしょうね。問題のカテゴリーの中では、これが一番適当に書けば良いだけだから簡単だと思いました。
最後のDグループは、なんかユニタリー行列の条件が与えられるので、それを満たすユニタリー行列を、 使える量子ゲートを組み合わせて組み立てて下さいと言うものです。 量子ゲートによるプログラミングでは、ユニタリー行列を作ることがまさにプログラミングなんですが、 このタスクでは、大体こことここを非ゼロにしてという大雑把な仕様が与えられるので、 それを満たす行列の組み立て方をひたすら頑張って考えるわけです。 何時の時代もプログラマーというのはそういういい加減な仕様を満たすコードをなんとかして考えなきゃ行けないもので、 ツライのですねと言う哀愁漂う問題(?)で、 しかし、まさにこういうユニタリー行列による量子プログラムの記述から、それを既知のゲートの組み合わせで表現する方法を見つけるというのは、 いまさらそういうことをやる必要があるのか!と思うぐらいには、非常にプリミティブで重要な量子プログラミングにおいては、 重要な進捗が求められる分野だと思います。 この辺解きながらサーベイしていて、あんまりパッとした超すごいやり方が2020年になろうという今でも なかなかないんだなあと思いながら解いていました。
と、そんなことを書いているうちに長くなりすぎて、参加記を書く余白がなくなったので、本編は明日以降書いていきたいと思います。
JavaScript UM Emulator
JavaScript上のPCエミュレータ http://bellard.org/jslinux/ に触発されて、
こんなものを作りました。
詳しくはこちら → http://www.boundvariable.org/
JavaScript意外と速くてびっくりなのです。
本家よりは全然すごくないですけど、
本家よりは遊べるんじゃないかと思います。
みんなで楽しくHacking!
Boost.勉強会 #4 で発表してきました
Boost.勉強会 #4で発表してきました。ICFP Programming Contest 2010 での Discriminating Hacker's 言語の件から、 C++をDISるというテーマで話す機会を頂いたので、せっかくなので、発表させていただくことにしました。
C++プログラマ、所謂闇の軍団の集う中でこのような発表をするのは、まさに飛んで火に入る夏の虫というやつで、戦々恐々としていたのですが、思惑とは逆に、全然DISれていないと私がDISられるというような結果となりました。
Haskellerの目線から、C++の気に入らない点を、主に型の話をメインに展開していったのですが、おおよそのC++erにとってはあまり賛否両論とは言えなかったようですね。なんでしょうか。動的型付け言語ユーザに静的型付けのメリットをとくとくととくような感じで。
もっと私自身の主観的な立場から、個人的に気に入らない点をあげあつらえば、いい感じに炎上してくれたのかなあと思います。const否定論やら、スマポ否定論やら、いろいろアイデアはありましたが、ちょっと日和ってしまったのと、全部話すには時間が足りないという感じでした。
C++は関数型言語だと言われて久しい(?)ですが、私はパターンマッチとカリー化が関数型言語では重要と考えていますので、そこがやはり不満なのです。そこのところがもう少し掘り下げて喋れればよかったなあと、すこし残念ではありました。それはまたいつぞやの機会にブログにでも書きましょうか、あるいは、私の昨日あたりのtwitterを見ていただければ少しは想いが伝わるかもしれません。
Haskellのエラー処理とMonadCatchIOの落とし穴
(この記事はHaskell Advent Calendar jp 2010のために書かれました)
Haskellではエラー処理に例外が用いられます(MaybeモナドやErrorモナドも用いられますが、ここでは例外に焦点をあてます)。
例外インターフェースの話
Haskellにも、例外を扱うためにtry, catch, finallyなどが用意されています。他の多くの言語ではこれらは構文として用意されますが、HaskellではIOモナドを引数にとる関数になっています。
try :: Exception e => IO a -> IO (Either e a) catch :: Exception e => IO a -> (e -> IO a) -> IO a finally :: IO a -> IO b -> IO a
tryはIOアクションを引数にとり、それを実行した結果が正常に値を返したか、はたまた例外かを返します。catchは例外が起こった場合の処理を記述できます。finallyは例外が起こっても起こらなくても第2引数のアクションを実行します。
これら(ともっと他にある例外処理用関数)を組み合わせてHaskellではエラー処理を行います。ひときわ良くあるケースとして、リソースの獲得、リソースの使用、リソースの解放の一連のパターンがあります。たとえば、ファイルをオープンして、ファイルにアクセスして、用事が済んだらファイルをクローズする処理を考えてみます。
main = do h <- openFile "hoge" ReadMode ... ファイルにアクセス hClose h
ファイルのオープンとクローズが別々になっているので、クローズを忘れるということがあるかもしれません。これを抽象化してみます。
main = do withFile "hoge" ReadMode $ \h -> ... ファイルにアクセス withFile filename mode m = do h <- openFile filename mode m h hClose h
これでwithFileを用いている限りは、ファイルのcloseし忘れということに煩わされる心配はなくなりました。ところが、この実装は不完全です。ファイルにアクセスする部分のコードが例外を発生させた場合、withFileの最後の行、hCloseが実行されずに終わってしまいます。そのため、正しく例外を処理するコードが必要になります。
withFile filename mode m = do h <- openFile filename mode m h `finally` hClose h
これで正しいコードができました。この様なリソースの確保、リソースの解法を例外安全に行う処理というのは至る所で必要になってくるので、bracketという便利な関数が用意されています。
bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c
第一引数がリソース獲得関数で、第2引数がリソース解法関数で、第3引数がリソースを使用する関数です。リソース解法関数は、例外が起こった場合も正しく実行されます。これを用いると、withFileは次のようにかけます。
withFile filename mode m =
bracket (openFile filename mode)
hClose
m
MonadCatchIO
このようにしてHaskellでエラー処理を記述することができますが、一つ大きな問題点があります。それは、これらの関数がすべてIOモナドを用いたインターフェースになっていることです。Haskellで例外が発生するのはIOモナドだけではありません。一つはpureなコードから発生する場合ともう一つはIOをリフトしたモナドから発生する場合です。pureなコードから発生する場合は、evaluate :: a -> IO a という関数を介することにより、IOモナド経由で例外を処理することができます。後者はたとえば変換子版のモナドを用いている場合に頻発します。近年の多くのモナディックなライブラリでは変換子版が用意されていることが多く、liftIOを用いてどこでもIOができるようになっています。liftIOによってIOをリフトできるモナドはMonadIOクラスとして抽象化されています。
MonadIOに対して例外処理を追加し、例外処理を一般化したものがMonadCatchIOクラスです。Hackage上の、MonadCatchIO-mtlや、MonadCatch-transformersのいずれかで利用できます。これを用いると、IOモナドをリフトできるIOモナド以外のモナド(たとえば StateT Int IO など)に対してtry, catch, bracketなどができるようになります。
foo :: MonadCatchIO m => m () foo = bracket (putStrLn "begin") (\_ -> putStrLn "end") (\_ -> ... 凝った処理 ... )
エラーモナドに対するインスタンス
ところがこれには大きな罠が潜んでいます。MonadCatchIO-transformersのドキュメントにWarningとして記載されていますが、ここでそれを解説しておきたいと思います。
(MonadCatchIO m, Error e) => MonadCatchIO (ErrorT e m)
問題となっているMonadCatchIOのインスタンスはこれです。どうしてこれがいけないのかというと、このモナドには2つのエラー通知方法があります。一つはMonadCatchIOで扱える例外、もう一つはエラーモナドです。一方のエラー処理の方法では、当然ながら他方のエラーは検出できません。つまり、エラー処理が分散してしまうことになります。これはこれでうれしいことではないのですが、さらに良くないことに、このことは奇妙な、望ましくない現象を引き起こします。
例えば、次のようなコードを考えます。
import Data.Typeable import Control.Exception as E import Control.Monad.CatchIO as MCIO import Control.Monad.Trans data MyException = MyException deriving (Show, Typeable) instance Exception MyException iofail :: IO () iofail = do E.throwIO MyException foo :: MonadCatchIO m => m () -> m () foo m = MCIO.bracket (liftIO $ putStrLn "abc") (\_ -> liftIO $ putStrLn "def") (\_ -> m) main :: IO () main = do foo iofail
MyExceptionはユーザ定義の例外を定義しています。iofailで例外をIOモナドとして発生させています。fooにiofailを渡しているので、bracketの中で例外が発生しますが、終了処理のputStrLn "def"は実行されるはずです。実行結果は次のようになります。
abc def mcio.hs: MyException
この場合、MonadCatchIOは単なるIOとしてインスタンス化されます。正しく動いているように見えます。次に、ErrorT String IO としてfooを実行してみます。
errfail :: MonadCatchIO m => m () errfail = do MCIO.throw MyException foo :: MonadCatchIO m => m () -> m () foo m = MCIO.bracket (liftIO $ putStrLn "abc") (\_ -> liftIO $ putStrLn "def") (\_ -> m) main :: IO () main = do r <- runErrorT $ foo errfail print (r :: Either String ())
abc def mcio.hs: MyException
これも正しく動いているように見えます。
これらはいずれも例外を投げていました。次に、もう一つのモナドの標準的なエラーであるfailを試してみます。
iofail :: IO () iofail = do fail "hoge" foo :: MonadCatchIO m => m () -> m () foo m = MCIO.bracket (liftIO $ putStrLn "abc") (\_ -> liftIO $ putStrLn "def") (\_ -> m) main :: IO () main = do foo iofail
まずはIOモナドです。
abc def mcio.hs: user error (hoge)
これは正しく動作します。次に、ErrorT String IO で試してみます。
errfail :: MonadCatchIO m => m () errfail = do fail "hoge" foo :: MonadCatchIO m => m () -> m () foo m = MCIO.bracket (liftIO $ putStrLn "abc") (\_ -> liftIO $ putStrLn "def") (\_ -> m) main :: IO () main = do r <- runErrorT $ foo errfail print (r :: Either String ())
さて、実行結果です。
abc Left "hoge"
おや、さっきとは変わりました。failによるエラーがErrorモナドによるエラーの扱いになっているようですね。結果としてLeft "hoge"が返って来ています。そこはそれで良いのですが、問題なのは、defが出力されていないということです。これはどういうことなのでしょうか?
これはErrorTモナドのbindのセマンティクスおよびfailのセマンティクスに問題があります。ErrorTモナドでは、エラーが起こるとbindにおける右辺値、すなわち後続の計算がすべてショートカットされるようになっています。そして、failはErrorTモナドにおけるエラー値を返します。ゆえに、ErrorTにおいては、failが呼ばれた時点で残りの計算はすべてスキップされてしまいます。当然それにはリフトされているIOも含まれます。折角MonadCatchIOを用いて記述した例外処理も含まれます。確実にリソース解放処理を行わせるためにbracketを使っているのにこれでは大問題です。
どうすべきか
MonadCatchIOの例外処理が正しく動作するかどうかは、インスタンスにするモナドのセマンティクスに全面的に依存します。たとえば標準モナド変換子ライブラリですと、ErrorTとContTがこの問題を抱えているようで、ドキュメントにその旨が記載されています。モナドのセマンティクスに依存するので、もちろんそれ以外のモナドでもありうるかもしれません。例えば、Snap web frameworkにおけるSnapモナドでも同様の問題がありました(Snapモナドでは例外発生時でもbracketをすり抜けてしまっていました)。
どうすればいいんでしょうか。これに対する決定的な解決を私は知りません。自分がMonadCatchIOのインスタンスを作成する場合、もし可能なら、計算がショートカットしないようにすれば解決です。しかし、それは一般的には可能ではないでしょう。
この様な問題を抱えたMonadCatchIOのモナドを扱うにおいては、もっとも妥当な対策として、liftIOする前にすべての例外を捕まえてしまうようにするのがいいかと思われます(何のためのMonadCatchIOなのかという話になりますが…)。
少なくとも、この様な現象が発生し得るということを知っておくだけでもデバッグの役に立つかもしれません。私は最初この現象に遭遇した時に、必死にprintを挿んでコードを追っていましたが、突然コードパスが途切れて一体どうなっているのかとかなり悩んでしまいました。