https://codeforces.com/contest/1356/problem/A5
1 qubitに対する演算$unitary$が与えられ、ここで$unitary$は$Z$ゲートもしくは$-Z$ゲートである。$unitary$を一度だけ呼び出して、$Z$であれば0を、$-Z$であれば1を返せ。
$Z$ゲートは $$Z = \ket{0}\bra{0} - \ket{1}\bra{1}$$ で表される演算であって、$\ket{1}$の符号を反転させる演算ですが、$-Z$ゲートは $$-Z = -\ket{0}\bra{0} + \ket{1}\bra{1}$$ で表される演算であって、$\ket{0}$の符号を反転させる演算です。
符号の反転を$\ket{+}, \ket{-}$を使って検出することを考えます。0番目のqubitを制御bit、1番目のqubitをターゲットbitとして$Z, -Z$を2qubitの状態に作用させたとき $$[{\rm Controlled}\;Z](\ket{00} + \ket{01} + \ket{10} + \ket{11}) = (\ket{00} + \ket{01} + \ket{10} - \ket{11})$$ $$[{\rm Controlled}\;-Z](\ket{00} + \ket{01} + \ket{10} + \ket{11}) = (\ket{00} + \ket{01} - \ket{10} + \ket{11})$$ となり、Controlled $Z$は$\ket{11}$、Controlled $-Z$は$\ket{10}$の符号だけを反転させることがわかります。
ここで、状態$\ket{+0}$に対してこれらの演算を作用させると \begin{align*} [{\rm Controlled}\;Z]\ket{+0} &= \frac{1}{\sqrt{2}}[{\rm Controlled}\;Z] \left( \ket{00} + \ket{10]} \right) \\ &= \frac{1}{\sqrt{2}}\left( \ket{00} + \ket{10} \right) \\ &= \ket{+0} \end{align*} \begin{align*} [{\rm Controlled}\;-Z]\ket{+0} &= \frac{1}{\sqrt{2}}[{\rm Controlled}\;-Z] \left( \ket{00} + \ket{10]} \right) \\ &= \frac{1}{\sqrt{2}}\left( \ket{00} - \ket{10} \right) \\ &= \ket{-0} \end{align*} となり、0番目のqubitに対してPauli Xを対角とした測定をすることで2つの演算子を判別できます。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
mutable res = 0;
using (qs = Qubit[2])
{
// 与えられたoperationをControlledで|+0>に作用させる
H(qs[0]);
Controlled unitary(qs[0..0], qs[1]);
// 0番目のqubitを測定して、|+>ならZ、|->なら-Z
if (Measure([PauliX], [qs[0]]) == One)
{
set res = 1;
}
ResetAll(qs);
}
return res;
}
}