https://codeforces.com/contest/1116/problem/D5
$3$桁の量子状態に対して、以下のようなパターンで表されるユニタリ演算を定義せよ。
例として、$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 \end{array} \right)$$ の形で表される演算であり、'.'は絶対値の二乗が$10^{-5}$以下の複素数、'$X$'は絶対値の二乗が$10^{-5}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。
いきなり完成形を設計することは難しいため、構築しやすい形の行列から行および列を並べ替えることで目的の演算を得ることを目指します。
構築しやすい演算として $$A= \left( \begin{array}{rr} H\otimes H & O\\ O & I\otimes H \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 \end{array} \right)$$ が考えられます。上に示したとおり、簡単なControlled演算のみで構成できます。
これを目的の行列に並べ替える演算の例として $$R_LAR_R= \left( \begin{array}{rr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 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 \end{array} \right) \left( \begin{array}{rr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 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 \end{array} \right)$$ があり $$R_L=CNOT(1,2)$$ $$R_R=CCNOT(0,2,1)CNOT(2,0)CNOT(1,2)$$ です。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Unit {
//R_R
CNOT(qs[1],qs[2]);
CNOT(qs[2],qs[0]);
CCNOT(qs[0],qs[2],qs[1]);
//A
(ControlledOnInt(0,ApplyToEachCA(H,_)))([qs[2]],qs[0..1]);
Controlled H([qs[2]],qs[0]);
//R_L
CNOT(qs[1],qs[2]);
}
}