https://codeforces.com/contest/1357/problem/A5
1 qubitに対する演算$unitary$と浮動小数点数$\theta$が与えられ、ここで$unitary$は$R_z(\theta)$または$R_y(\theta)$である。$unitary$を何度でも呼び出してよいので、それが$R_z(\theta)$ならば0、 $R_y(\theta)$ならば1を返せ。
$R_z(\theta)$と$R_y(\theta)$は、行列表示でそれぞれ $$R_z(\theta) = \left( \begin{array}{c} e^{-i\frac{\theta}2} & 0 \\ 0 & e^{i\frac{\theta}2} \end{array} \right)$$ $$R_y(\theta) = \left( \begin{array}{rr} \cos{\frac{\theta}2} & -\sin{\frac{\theta}2} \\ \sin{\frac{\theta}2} & \cos{\frac{\theta}2} \end{array} \right)$$ と表せる演算であり、これらをスピノル $\left( \begin{array}{c} 1 \\ 0 \end{array} \right)$ に作用させると $$ \left( \begin{array}{c} e^{-i\frac{\theta}2} & 0 \\ 0 & e^{i\frac{\theta}2} \end{array} \right) \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} e^{-i\frac{\theta}2} \\ 0 \end{array} \right) $$ $$ \left( \begin{array}{rr} \cos{\frac{\theta}2} & -\sin{\frac{\theta}2} \\ \sin{\frac{\theta}2} & \cos{\frac{\theta}2} \end{array} \right) \left( \begin{array}{c} 1 \\ 0 \end{array} \right) = \left( \begin{array}{c} \cos{\frac{\theta}2} \\ \sin{\frac{\theta}2} \end{array} \right) $$ となることから、これらの状態に対してPauli Zを対角とする演算を行うと、$R_z(\theta)\ket{0}$では必ず$\ket{0}$が得られるのに対して、$R_y(\theta)\ket{0}$では確率$\sin^2{\frac{\theta}2}$で$\ket{1}$が得られることがわかります。
よって、状態$\ket{0}$に与えられた演算を作用させて測定することを十分な回数繰り返し、一度でも$\ket{1}$が得られたかどうかで演算を識別できます。
しかし、この問題では実行時間制限が1 secしかなく、$\ket{1}$が測定される確率が最も小さくなる$\theta = 0.01\pi$の場合に充分な回数操作を行うことはできません。ですが、演算を連続で何度も作用させることで$\theta$の値を大きくすれば$\ket{1}$が測定される確率を大きくすることができ、数回程度の測定で充分高精度な判定を行うことができます。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Math;
open Microsoft.Quantum.Measurement;
open Microsoft.Quantum.Intrinsic;
operation Solve (theta : Double, unitary : (Qubit => Unit is Adj+Ctl)) : Int
{
using (q = Qubit())
{
//U^N|0>を何度も測定して、1度でも|1>が出たらRy
for (i in 0..10)
{
//thetaがπを超える直前まで操作する
mutable angle = 0.0;
repeat
{
unitary(q);
set angle = angle + theta;
}
until(angle + theta >= PI());
if (MResetZ(q) == One)
{
return 1;
}
}
}
return 0;
}
}