https://codeforces.com/contest/1002/problem/C1
1桁のqubitが与えられる。このqubitは$\ket{0}$または$\ket{+}$であることが保証されており、それぞれが与えられる確率は$\frac12$ずつである。これに対して、どちらが与えられたかを80%以上の確率で正しく識別せよ。
できるだけ高確率で$\ket{0}$と$\ket{+}$を識別したいと考えたときに、はじめに工夫無しでどの程度の精度が出せるか見てみます。
与えられたqubitに対してPauli Z演算子を対角とする測定を行って、固有値$1$を得たとき$\ket{0}$、固有値$-1$を得たとき$\ket{+}$であると判定するプログラムを書いたとします。この方法であれば、$\ket{0}$が与えられたときに必ず正解できます（$\ket{0}$に対してPauli Z演算子を対角とする測定を行って固有値$-1$を得ることはないため）が、$\ket{+}$が与えられた場合に50%の確率でしか正解できません、それぞれが与えられる確率は等しいので、この方法では全体として75%の確率でしか正解できないことになります。これでは正答率が低いので、状態を回転させてより高い精度で正解する方法を考えます。
基底状態$\ket{0}, \ket{1}$が直交している二次元平面を考えます(デカルト座標でのxy平面のように)。この平面上で、$\ket{0}$からの回転角を$\theta$と書くことにすると、$\ket{0}$は$\theta=0$、$\ket{1}$は$\theta=\frac{\pi}{2}$の状態であると考えることができて、状態$\ket{+}=\frac{1}{\sqrt{2}}\left( \ket{0}+\ket{1} \right)$は$\theta=\frac{\pi}{4}$となります。
ここで、状態$\ket{0}$を$\left( \begin{array}{rr} 1\\0 \end{array} \right)$、状態$\ket{1}$を$\left( \begin{array}{rr} 0\\1 \end{array} \right)$と表すことにすれば（スピノル表示）、状態$\ket{+}$は$\frac{1}{\sqrt{2}}\left( \begin{array}{rr} 1\\1 \end{array} \right)$と表せて、この平面上で状態を$\theta$回転させる操作は、回転行列$\left( \begin{array}{rr} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{array} \right)$で表せるようになります。
与えられた状態を平面上で$\frac{\pi}{8}$回転させると、状態$\ket{0}(\theta=0)$は$\theta=\frac{\pi}{8}$に、状態$\ket{+}(\theta=\frac{\pi}{4})$は$\frac{3\pi}{8}$に遷移します。これらの状態についてPauli Z演算子を対角とする測定を行ったとき、状態$\ket{0}, \ket{1}$が測定される確率を以下に計算します。
状態$\ket{0}$を平面上で$\frac{\pi}{8}$回転させた状態は $$\left( \begin{array}{rr} \cos{\frac{\pi}{8}} & -\sin{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}} & \cos{\frac{\pi}{8}} \end{array} \right) \left( \begin{array}{rr} 1\\0 \end{array} \right)=\left( \begin{array}{rr} \cos{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}} \end{array} \right)$$ すなわち状態$\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1}$となり、これに対してPauli Z演算子を対角とする測定を行うと、固有値$1$が測定される確率は$\cos^2{\frac{\pi}{8}}\simeq 0.854$、固有値$-1$が測定される確率は$\sin^2{\frac{\pi}{8}}\simeq 0.146$となります。
同様に、状態$\ket{+}$を平面上で$\frac{\pi}{8}$回転させた状態は $$\frac{1}{\sqrt{2}}\left( \begin{array}{rr} \cos{\frac{\pi}{8}} & -\sin{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}} & \cos{\frac{\pi}{8}} \end{array} \right) \left( \begin{array}{rr} 1\\1 \end{array} \right)=\frac{1}{\sqrt{2}}\left( \begin{array}{rr} \cos{\frac{\pi}{8}}-\sin{\frac{\pi}{8}} \\ \sin{\frac{\pi}{8}}+\cos{\frac{\pi}{8}} \end{array} \right)$$ すなわち状態$\frac{ \cos{\frac{\pi}{8}}-\sin{\frac{\pi}{8}}}{\sqrt2}\ket{0}+\frac{ \cos{\frac{\pi}{8}}+\sin{\frac{\pi}{8}}}{\sqrt2}\ket{1}$となり、これに対してPauli Z演算子を対角とする測定を行うと、固有値$1$が測定される確率は$\left( \frac{ \cos{\frac{\pi}{8}}-\sin{\frac{\pi}{8}}}{\sqrt2} \right)^2\simeq 0.146$、固有値$-1$が測定される確率は$\left( \frac{ \cos{\frac{\pi}{8}}+\sin{\frac{\pi}{8}}}{\sqrt2} \right)^2\simeq 0.854$となります。
以上のことから、与えられた状態を$\ket{0}$と$\ket{1}$が直交している平面上で$\frac{\pi}{8}$回転させたあとにPauli Z演算子を対角とする測定を行い、固有値$1$が測定されれば状態$\ket{0}$、固有値$-1$が測定されれば状態$\ket{+}$であると判定すれば、約85%の確率で正解できることがわかります。
これで、この問題が解けました。
なお、Q#において回転を表すゲートはブロッホ球上の回転を表しており、先程まで考えていた平面上における$\frac{\pi}{8}$の回転はブロッホ球上ではY軸まわりの$\frac{\pi}{4}$の回転に対応していることに注意が必要です（ブロッホ球では$\ket{0}$と$\ket{1}$が両方z軸上に存在するため、基底が直交することはブロッホ球でのベクトルの直交を意味しない）。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (q : Qubit) : Int
{
body
{
Ry(3.1415/4.0,q);
if(M(q)==Zero){
return 0;
}
return 1;
}
}
}