https://codeforces.com/contest/1116/problem/B1
3桁の量子状態が与えられるので、与えられた状態が
のどちらであるか判定し、$\ket{\psi_0}$なら0を、$\ket{\psi_1}$なら1を返せ。ただし、$\omega=e^{\frac{2i\pi}{3}}$(1の3乗根)である。
$U\ket{\psi_0}=\ket{000}$となるユニタリ演算$U$が存在すると仮定すると、 \begin{align*} \braket{000}{U\psi_1}&=\braket{U\psi_0}{U\psi_1}\\ &=\bra{\psi_0}U^{\dagger}U\ket{\psi_1}\\ &=\braket{\psi_0}{\psi_1}\\ &=\left( \bra{100} + \omega^2\bra{010} + \omega\bra{001} \right)\left( \ket{100} + \omega^2\ket{010} + \omega\ket{001} \right)\\ &=\braket{100}{100}+\omega^4\braket{010}{010}+\omega^2\braket{001}{001}\\ &=1+\omega+\omega^2\\ &=0 \end{align*} より、状態$\ket{000}$と状態$U\ket{\psi_1}$の内積が0となるので、$U\ket{\psi_1}$には$\ket{000}$成分が存在しない（係数が0である）ことがわかります。
よって、与えられた状態に演算$U$を作用させたあとすべてのqubitに対してPauli Z演算子を対角とする測定を行い、状態$\ket{000}$が測定されれば$\ket{\psi_0}$、測定されなければ$\ket{\psi_1}$と判断すればよいです。
ここで演算$U$について考えます。演算$U$は、定義より状態$\ket{000}$を$\ket{\psi_0}$に変化させる演算の逆演算(Adjoint)であることがわかります。以下、$\ket{000}$を$\ket{\psi_0}$に変化させる演算$U^{\dagger}$を構成します。
始状態$\ket{000}$に対して、A1と同様に、0番目のqubitをブロッホ球上でY軸まわりに$2\arccos{\frac{\sqrt{2}}{\sqrt{3}}}$だけ回転させると $$\frac{\sqrt{2}}{\sqrt{3}}\ket{000} + \frac{1}{\sqrt{3}}\ket{100}$$ となり、ここで、0番目のqubitが0の場合のみ1番目のqubitにアダマール・ゲートを作用させる演算を行うと $$\frac{1}{\sqrt{3}}\left( \ket{000} + \ket{010} + \ket{100} \right)$$ を得ます。さらに、0番目、1番目のqubitがともに0である場合のみ2番目のqubitにNOTゲートを作用させると、状態 $$\frac{1}{\sqrt{3}}\left( \ket{100} + \ket{010} + \ket{001} \right)$$ を作ることができました。これは3桁のW状態であり、$\ket{\psi_0}, \ket{\psi_1}$とは各項の位相のみが異なる状態です。
重ね合わせの位相を変化させるために、Phase shiftゲートを利用します。Phase shiftゲートは $$R_\phi=\ket{0}\bra{0}+e^{i\phi}\ket{1}\bra{1}$$ で表される演算であって、ブロッホ球上でのZ軸まわりの回転に対応する演算です。3桁のW状態に対して、1番目のqubitに$R_{\frac{2\pi}{3}}$、2番目のqubitに$R_{\frac{4\pi}{3}}$を作用させると、目的の状態 $$\ket{\psi_0}=\frac{1}{3}\left( \ket{100} + \omega\ket{010} + \omega^2\ket{001} \right)$$ となり、以上の一連の操作が演算$U^{\dagger}$となります。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Extensions.Math;
open Microsoft.Quantum.Extensions.Convert;
operation U_Adj (qs : Qubit[]) : Unit { //|000⟩を|ψ_0⟩にする演算
body(...){
Ry(2.0*ArcCos(Sqrt(2.0)/Sqrt(3.0)),qs[0]);
(ControlledOnInt(0,H))([qs[0]],qs[1]);
(ControlledOnInt(0,X))(qs[0..1],qs[2]); //ここまででW状態
R1(2.0*PI()/3.0,qs[1]);
R1(4.0*PI()/3.0,qs[2]);
}
adjoint auto;
controlled auto;
controlled adjoint auto;
}
operation Solve (qs : Qubit[]) : Int {
Adjoint U_Adj(qs); //qsにUを作用させる
return MeasureInteger(LittleEndian(qs))==0?0|1; //|000⟩が測定されれば0, そうでなければ1を返す。
}
}