Microsoft Q# Coding Contest - Winter 2019 - その4
今回はC1からです。
$$ \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}} $$
- C1. Alternating bits oracle
- C2. "Is the bit string periodic?" oracle
- C3. "Is the number of ones divisible by 3?" oracle
C1. Alternating bits oracle
問題
次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。
- $\vec{x}の隣接するビットに00か11が含まれていないなら f(\vec{x}) = 1$
なお、adjoint autoでadjointが生成できなければならない。
解答
C問題シリーズは量子オラクルを実装するものです。 量子オラクルというのは、このあたりに詳しいです。 要するに、 $$O(\ket{x}\otimes\ket{y}) = \ket{x}\otimes\ket{y\oplus f(x)}$$ なる$O$を実装せよというものです。
問題の解き方ですが、隣接するビットに00か11が含まれていないものというのは、 0101010...か101010...のような、1と0が交互に現われるものの2通りしかありません。 なので、Nビットのそういうパターン2種類について、それぞれのビット列に対してControlled XすればOKです。
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
let n = Length(x);
let pat = 0x55555555;
(ControlledOnInt(pat % (1<<<n), X))(x, y);
(ControlledOnInt((pat>>>1) % (1<<<n), X))(x, y);
}
adjoint auto;
}
C2. "Is the bit string periodic?" oracle
問題
次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。
- $\vec{x}がperiodicなら、f(\vec{x}) = 1$
あるビット列がperiodicであるとは、ある$P (1 \le P \le N-1)$があって、 全ての$i\in[0,N-P-1]$に対して$x_i=x_{i+P}$であるようなものである。 $P$は$N$を割り切らなくても良い。例えば"01010"は$P=2$でperiodicである。
解答
いいんですかねこんなので。 通ってしまったものは仕方が無い。
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
let tbl =
[[1,2]
,[1,3,4,6]
,[1,3,7,8,12,14]
,[1,3,5,7,11,15,16,20,24,26,28,30]
,[1,3,5,7,11,13,15,19,23,31,32,40,44,48,50,52,56,58,60,62]
,[1,3,5,7,9,11,13,15,19,21,23,27,29,31,35,39,43,47,55,63,64,72,80,84,88,92,96,98,100,104,106,108,112,114,116,118,120,122,124,126]];
X(y);
let n = Length(x);
for (i in 0..Length(tbl[n-2])-1) {
(ControlledOnInt(tbl[n-2][i], X))(x, y);
}
}
adjoint auto;
}
C3. "Is the number of ones divisible by 3?" oracle
問題
次のようなN($1\le N \le 9$) Qubitの量子オラクルを実装せよ。
- $\vec{x}$中の立っているビットの数が3で割り切れるなら$f(\vec{x})=1$、それ以外なら$f(\vec{x})=0$
解答
C2と同様にテーブルでやってみたところ、サイズが大きくて時間がかかりTLEになりました。 なのでまともに解きます。
立っているビットの数を数えるには、加算器を実装します。 加算結果は最大で9になるので、4ビット必要です。 なので、4ビット＋1ビットの加算器を実装することになります。
実装するものを、[a0, a1, a2, a3] + b = [c0, c1, c2, c3] とすれば、
c3 = a3 ^ (b & a0 & a1 & a2) c2 = a2 ^ (b & a0 & a1) c1 = a1 ^ (b & a0) c0 = a0 ^ b
となります（桁上がりするにはそれより前の桁が全部1になっていないといけないので）。 これをもとに、xのうち立っているビットを数える操作をQ#で書くと、
// qs: 数えた結果 // x: 入力 operation Count(qs: Qubit[], x: Qubit[]): Unit { body(...) { let n = Length(x); let a0 = qs[0]; let a1 = qs[1]; let a2 = qs[2]; let a3 = qs[3]; for (i in 0..n-1) { let b = x[i]; (ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3); (ControlledOnBitString([true, true, true], X))([b, a0, a1]2); CCNOT(b, a0, a1); CNOT(b, a0); } } // 全体をAdjacentにしないといけないのでこれもAdjacentにしないといけない adjoint auto; }
このようになります。カウントができれば、あとはこれが3の倍数かどうかチェックする関数を書きます。入力のレンジが0～9なので、べた書きすればよいでしょう。
// qsは使わないけど形合わせ（後述） operation Check(qs: Qubit[], y: Qubit): Unit { body(...) { (ControlledOnInt(0, X))(qs, y); (ControlledOnInt(3, X))(qs, y); (ControlledOnInt(6, X))(qs, y); (ControlledOnInt(9, X))(qs, y); } adjoint auto; }
これを組み合せれば、
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
using (qs = Qubit[4]) {
Count(qs, x);
Check(qs, y);
}
}
adjoint auto;
}
となりますが、usingブロックの終了時点で確保したQubitはゼロ状態に戻しておかなければならないので、Countの逆操作を行う必要がります。これを手で書くのは面倒ですが、Q#には逆操作をadjoint autoで自動で作る機能がありますし、しかも今回の問題はそれを要求されているので、それを使えばよさそうです。
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
using (qs = Qubit[4]) {
Count(qs, x);
Check(x, y);
Adjoint Count(qs, x);
}
}
adjoint auto;
}
ところで、こういう何らかの操作Aを行って、別の操作Bを行って、それからAで行った操作を元に戻す、という一連の操作はよく出てくるみたいなので、それを行うためのWithAという関数が用意されています。これを使えば、全体のコードを次のように書けます（WithAを使うためにCountとCheckの引数をそろえています）。
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
using (qs = Qubit[4]) {
WithA(Count, Check, (qs, x, y));
}
}
adjoint auto;
}
operation Count(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
body(...) {
let n = Length(x);
let a0 = qs[0];
let a1 = qs[1];
let a2 = qs[2];
let a3 = qs[3];
for (i in 0..n-1) {
let b = x[i];
(ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3);
(ControlledOnBitString([true, true, true], X))([b, a0, a1]2);
CCNOT(b, a0, a1);
CNOT(b, a0);
}
}
adjoint auto;
}
operation Check(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
body(...) {
(ControlledOnInt(0, X))(qs, y);
(ControlledOnInt(3, X))(qs, y);
(ControlledOnInt(6, X))(qs, y);
(ControlledOnInt(9, X))(qs, y);
}
adjoint auto;
}
今回は割と簡単でした。
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++コミュニティーの中心でC++をDISる
View more presentations from tanakh
C++プログラマ、所謂闇の軍団の集う中でこのような発表をするのは、まさに飛んで火に入る夏の虫というやつで、戦々恐々としていたのですが、思惑とは逆に、全然DISれていないと私がDISられるというような結果となりました。
Haskellerの目線から、C++の気に入らない点を、主に型の話をメインに展開していったのですが、おおよそのC++erにとってはあまり賛否両論とは言えなかったようですね。なんでしょうか。動的型付け言語ユーザに静的型付けのメリットをとくとくととくような感じで。
もっと私自身の主観的な立場から、個人的に気に入らない点をあげあつらえば、いい感じに炎上してくれたのかなあと思います。const否定論やら、スマポ否定論やら、いろいろアイデアはありましたが、ちょっと日和ってしまったのと、全部話すには時間が足りないという感じでした。
C++は関数型言語だと言われて久しい（？）ですが、私はパターンマッチとカリー化が関数型言語では重要と考えていますので、そこがやはり不満なのです。そこのところがもう少し掘り下げて喋れればよかったなあと、すこし残念ではありました。それはまたいつぞやの機会にブログにでも書きましょうか、あるいは、私の昨日あたりのtwitterを見ていただければ少しは想いが伝わるかもしれません。
