https://codeforces.com/contest/1115/problem/U2
$N$桁の量子状態に対して、chessboard patternで表されるユニタリ演算を定義せよ。
例として、$N=3$のとき $$\left( \begin{array}{rr} X & X & . & . & X & X & . & . \\ X & X & . & . & X & X & . & . \\ . & . & X & X & . & . & X & X \\ . & . & X & X & . & . & X & X \\ X & X & . & . & X & X & . & . \\ X & X & . & . & X & X & . & . \\ . & . & X & X & . & . & X & X \\ . & . & X & X & . & . & X & X \end{array} \right)$$ の形で表される演算であり、'.'は絶対値の二乗が$10^{-5}$以下の複素数、'$X$'は絶対値の二乗が$10^{-5}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。
はじめに、$N=2$の場合に構築します。
単一のqubitに対して $$U=\left( \begin{array}{rr} X & X \\ X & X \end{array} \right)$$ の形で表されるユニタリ演算が存在するとき、0番目のqubitに$U$を、1番目のqubitに$I$を作用させる演算は、線形写像の直積となるので $$I_1 \otimes U_0= \left( \begin{array}{rr} U & O \\ O & U \end{array} \right) = \left( \begin{array}{rr} X & X & . & . \\ X & X & . & . \\ . & . & X & X \\ . & . & X & X \end{array} \right)$$ のような形になります。
$N=2$の場合が構成できれば、より大きい$N$についても容易に構成できます。$N=2$の場合に加えて、2番目のqubitに$U$を作用させると $$U_2 \otimes I_1 \otimes U_0= \left( \begin{array}{rr} X(I_1 \otimes U_0) & X(I_1 \otimes U_0) \\ X(I_1 \otimes U_0) & X(I_1 \otimes U_0) \end{array} \right) = \left( \begin{array}{rr} X & X & . & . & X & X & . & . \\ X & X & . & . & X & X & . & . \\ . & . & X & X & . & . & X & X \\ . & . & X & X & . & . & X & X \\ X & X & . & . & X & X & . & . \\ X & X & . & . & X & X & . & . \\ . & . & X & X & . & . & X & X \\ . & . & X & X & . & . & X & X \end{array} \right)$$ となり、$N>=3$の場合についても同様に $U_{N-1} \otimes \dots \otimes U_2 \otimes I_1 \otimes U_0$とすればよいことがわかります。
今回、$X$は十分に大きい(N乗しても絶対値の二乗が$10^{-5}$以下にならない)と仮定して、$X^2=X$として計算を行いました。
実装においては、演算$U$としてアダマール・ゲート $H=\frac{1}{\sqrt{2}}\left( \begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array} \right)$ を利用して $$H_{N-1} \otimes \dots \otimes H_2 \otimes I_1 \otimes H_0$$ のようにするとよいです。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Unit {
H(qs[0]);
for(i in 2..Length(qs)-1){
H(qs[i]);
}
}
}