https://codeforces.com/contest/1116/problem/B2
1桁の量子状態が与えられるので、与えられた状態が
のどれであるか判定し、$\ket{A}$なら1または2を、$\ket{B}$なら0または2を、$\ket{C}$なら0または1を返せ。ただし、$\omega=e^{\frac{2i\pi}{3}}$(1の3乗根)である。
問題名にもあるとおり、与えられた状態が$\ket{A},\ket{B},\ket{C}$のうち「どれではない」かを答える問題です。これらの3状態は直交していないので100%判別することはできませんが、確実に$\ket{A}$ではないといえるなら0を、$\ket{B}$ではないといえるなら1を、$\ket{C}$ではないといえるなら2を答えます。
与えられた状態を$\ket{X}$とします。新たなqubitを1つ用意して、与えられた状態にこれを追加して2桁の量子状態$\ket{X0}$とすれば、$4\times4$行列で表される演算子を作用させることができるようになります（以下、状態のベクトル表示では$\ket{00}, \ket{10}, \ket{01}, \ket{00}$の順で基底を表します）。ここで $$U=C\left( \begin{array}{rr} 1 & -1 & ? & ? \\ 1 & -\omega & ? & ? \\ 1 & -\omega^2 & ? & ? \\ 0 & 0 & ? & ? \\ \end{array}\right)$$ という形のユニタリ演算子が存在すると仮定すると、これを$\ket{X0}$に作用させれば $$U\ket{A0}=U\left( \begin{array}{rr} 1\\1\\0\\0 \end{array}\right)=\left( \begin{array}{rr} 0\\1-\omega\\1-\omega^2\\ 0 \end{array}\right)$$ $$U\ket{B0}=U\left( \begin{array}{rr} 1\\\omega\\0\\0 \end{array}\right)=\left( \begin{array}{rr} 1-\omega\\1-\omega^2\\0\\ 0 \end{array}\right)$$ $$U\ket{C0}=U\left( \begin{array}{rr} 1\\\omega^2\\0\\0 \end{array}\right)=\left( \begin{array}{rr} 1-\omega^2\\0\\1-\omega\\ 0 \end{array}\right)$$ となり、測定を行って$\ket{00}$が測定されれば0を、$\ket{01}$が測定されれば1を、$\ket{10}$が測定されれば2を返せばよいことがわかります。入力状態の1桁目は必ず$\ket{0}$であることがわかっているので、$U$の右半分は何でもよいことになります。
$U$として使えるユニタリ演算子を生成する手順のうちのひとつは、以下のようなものです。
$$U=\left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) \left( \begin{array}{rr} \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\sqrt{3}} & 0 & 0 \\ \frac{\sqrt{2}}{\sqrt{3}} & -\frac{1}{\sqrt{3}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & 0 & 0 & i \\ \end{array}\right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{array}\right) $$ これを計算すると $$U=\frac{1}{\sqrt{3}}\left( \begin{array}{rr} 1 & -1 & 1 & 0 \\ 1 & -\omega & \omega^2 & 0 \\ 1 & -\omega^2 & \omega & 0 \\ 0 & 0 & 0 & -\sqrt{3}i \\ \end{array}\right)$$ となり、条件を満たします。
以下、各演算の実装方法について述べます。入力を$\ket{x_0x_1}$と表記します。
まず $$ \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array}\right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} \\ 0 & 0 & 1 & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} \\ \end{array}\right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array}\right) = \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) $$ であって $ \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array}\right) $ は$\ket{x_1}$を制御ビット、$\ket{x_0}$をターゲットビットとしたCNOT演算であり、 $ \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} \\ 0 & 0 & 1 & 0 \\ 0 & \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} \\ \end{array}\right) $ は$\ket{x_0}$を制御ビット、$\ket{x_1}$をターゲットビットとしたアダマール・ゲート（Controlled H演算）です （基底の順番に注意してください）。
次に $$ \left( \begin{array}{rr} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) \left( \begin{array}{rr} \frac{\sqrt{2}}{\sqrt{3}} & -\frac{1}{\sqrt{3}} & 0 & 0 \\ \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\sqrt{3}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) = \left( \begin{array}{rr} \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\sqrt{3}} & 0 & 0 \\ \frac{\sqrt{2}}{\sqrt{3}} & -\frac{1}{\sqrt{3}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) $$ であって $ \left( \begin{array}{rr} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) $ は$\ket{x_1}=\ket{0}$の場合のみ$\ket{x_0}$を反転する演算であり、 $ \left( \begin{array}{rr} \frac{\sqrt{2}}{\sqrt{3}} & -\frac{1}{\sqrt{3}} & 0 & 0 \\ \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\sqrt{3}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\right) $ は、$\ket{x_1}=\ket{0}$の場合のみ$\ket{x_0}$をブロッホ球上でY軸まわりに$2\arccos{\frac{\sqrt{2}}{\sqrt{3}}}$回転させる操作を表します。
その他の演算について、 $ \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & 0 & 0 & i \\ \end{array}\right) $ は、$\pi/4$Phase shiftゲート $ S=\left( \begin{array}{rr} 1 & 0 \\ 0 & i \\ \end{array}\right) $ と恒等演算子との直積$(S\otimes I)$であり、$\ket{x_1}$に対するSゲートに対応します。 $ \left( \begin{array}{rr} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \\ \end{array}\right) $ は、恒等演算子とZゲートの直積$(I\otimes Z)$であり、$\ket{x_0}$に対するZゲートに対応します。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Extensions.Math;
operation Solve (q : Qubit) : Int {
mutable ret=0;
using(a=Qubit()){
//(I⊗Z)
Z(q);
//diag(1,H,1)
CNOT(a,q);
Controlled H([q],a);
CNOT(a,q);
//(S⊗I)
S(a);
//R
(ControlledOnInt(0,Ry))([a],(2.0*ArcCos(Sqrt(2.0/3.0)),q));
(ControlledOnInt(0,X))([a],q);
//diag(1,H,1)
CNOT(a,q);
Controlled H([q],a);
CNOT(a,q);
//測定
let res0=M(q);
let res1=MResetZ(a);
if(res0==Zero && res1==Zero){
set ret=0;
}
elif(res0==Zero && res1==One){
set ret=1;
}
elif(res0==One && res1==Zero){
set ret=2;
}
else{
set ret=3;
}
}
return ret;
}
}