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;
}
}