https://codeforces.com/contest/1116/problem/D3
$N$桁の量子状態に対して、対角行列と反対角行列をあわせたパターンで表されるユニタリ演算を定義せよ。
例として、$N=3$のとき $$\left( \begin{array}{rr} X & . & . & . & . & . & . & X \\ . & X & . & . & . & . & X & . \\ . & . & X & . & . & X & . & . \\ . & . & . & X & X & . & . & . \\ . & . & . & X & X & . & . & . \\ . & . & X & . & . & X & . & . \\ . & X & . & . & . & . & X & . \\ X & . & . & . & . & . & . & X \end{array} \right)$$ の形で表される演算であり、'.'は絶対値の二乗が$10^{-5}$以下の複素数、'$X$'は絶対値の二乗が$10^{-5}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。
演算の行列表現をよく見ると、入力された状態$\ket{x_0x_1\dots x_{N-1}}$と、すべてのqubitを反転させた状態$\ket{\overline{x_0x_1\dots x_{N-1}}}$の重ね合わせ $$\frac{1}{\sqrt{2}}\left(\ket{\overline{x_0x_1\dots x_{N-1}} \pm \ket{x_0x_1\dots x_{N-1}}}\right)$$ を出力する演算は定義を満たすことがわかります。
ここで、$\ket{x_0}=\ket{0}$であれば、0桁目にアダマール・ゲートを作用させて $$\frac{1}{\sqrt{2}}\left( \ket{0}\otimes\ket{x_1\dots x_{N-1}} + \ket{1}\otimes\ket{x_1\dots x_{N-1}}\right)$$ としたあと0桁目を制御ビット、残りの桁をターゲットビットとしてCNOTゲートを作用させれば $$\frac{1}{\sqrt{2}}\left( \ket{0}\otimes\ket{x_1\dots x_{N-1}} + \ket{1}\otimes\ket{\overline{x_1\dots x_{N-1}}}\right)$$ となり、定義を満たします。
$\ket{x_0}=\ket{1}$の場合は、最初に0桁目を制御ビット、残りの桁をターゲットビットとしてCNOTゲートを作用させておく（0桁目が$\ket{0}$の場合は何も起こらないので、この操作は常に行って問題ありません）ことで $$\ket{1}\otimes\ket{\overline{x_1\dots x_{N-1}}}$$ となり、あとは同様の演算によって $$\frac{1}{\sqrt{2}}\left( \ket{0}\otimes\ket{\overline{x_1\dots x_{N-1}}} - \ket{1}\otimes\ket{x_1\dots x_{N-1}}\right)$$ となり、こちらも定義を満たします。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Unit {
let N=Length(qs);
for(i in 1..N-1){
CNOT(qs[0],qs[i]);
}
H(qs[0]);
for(i in 1..N-1){
CNOT(qs[0],qs[i]);
}
}
}