https://codeforces.com/contest/1116/problem/D6
$N$桁の量子状態に対して、Hessenberg行列（ここではupper Hessenberg行列）で表されるユニタリ演算を定義せよ。
例として、$N=2$のとき $$\left( \begin{array}{rr} X & X & X & X \\ X & X & X & X \\ . & X & X & X \\ . & . & X & X \end{array} \right)$$ の形で表される演算であり、'.'は絶対値の二乗が$10^{-5}$以下の複素数、'$X$'は絶対値の二乗が$10^{-5}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。
対角行列$A$に対して、$A_{i,j}, A_{j,i}$をゼロでない成分に置き換えた行列（単位行列にゼロ成分をもたない$2\times2$行列を埋め込んだような形）を$T_{i,j}$と書くことにすると、Hessenberg行列の重要な性質として $$T_{0,1}T_{1,2}\cdots T_{N-2,N-1}$$ は$2^N\times2^N$Hessenberg行列になるというものがあります。$N=2$を例にとると $$\left( \begin{array}{rr} X & X & . & . \\ X & X & . & . \\ . & . & X & . \\ . & . & . & X \end{array} \right) \left( \begin{array}{rr} X & . & . & . \\ . & X & X & . \\ . & X & X & . \\ . & . & . & X \end{array} \right) \left( \begin{array}{rr} X & . & . & . \\ . & X & . & . \\ . & . & X & X \\ . & . & X & X \end{array} \right) = \left( \begin{array}{rr} X & X & X & X \\ X & X & X & X \\ . & X & X & X \\ . & . & X & X \end{array} \right)$$ となります。
ここで、これまでの問題と同じように、ゼロ成分をもたない$2\times2$行列としてアダマール・ゲートを利用することにすると、$N=2$で $$T_{0,1}=\left( \begin{array}{rr} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & . & . \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & . & . \\ . & . & 1 & . \\ . & . & . & 1 \end{array} \right)$$ のようになります。
このとき$T_{i,i+1}$は、入力$\ket{i},\ket{i+1}$に対して出力 \begin{align*} T_{i,i+1}\ket{i}&=\frac{1}{\sqrt{2}}\left( \ket{i}+\ket{i+1} \right)\\ T_{i,i+1}\ket{i+1}&=\frac{1}{\sqrt{2}}\left( \ket{i}-\ket{i+1} \right) \end{align*} を返し、それ以外の基底に対しては何もしない演算であって、これを実装するためには、与えられた入力に対して \begin{align*} U\ket{i}&=\ket{01\dots1}\\ U\ket{i+1}&=\ket{11\dots1} \end{align*} となるような演算$U$を作用させたあと、$[1,N)$桁目が$\ket{1\dots1}$である場合のみ0桁目のqubitに対してアダマール・ゲートを作用させ、最後に$U^\dagger$によってもとに戻せばよいです。
このようにして作った行列を上述の順番で掛け合わせることによって、求める行列を得ることができます。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation U (a : Int, b : Int, qs : Qubit[]) : Unit { //b=a+1
body(...){
let N=Length(qs);
let bitsA=BoolArrFromPositiveInt(a,N);
let bitsB=BoolArrFromPositiveInt(b,N);
//b=a+1なので、0桁目は必ず0と1
if(bitsA[0]){ //bitsA[0]が1なら、qsの0桁目を反転
X(qs[0]);
}
for(i in 1..N-1){ //|a⟩, |b⟩だったものの[1,N)桁目がすべて|1⟩になるように
if(bitsA[i]==bitsB[i]){
if(not bitsA[i]){
X(qs[i]);
}
}
else{
if(not bitsA[i]){
(ControlledOnInt(0,X))([qs[0]],qs[i]);
}
else{
CNOT(qs[0],qs[i]);
}
}
}
}
adjoint auto;
}
operation Solve (qs : Qubit[]) : Unit {
let N=Length(qs);
for(i in 2^N-2..-1..0){ //T_{i,i+1}を順に掛ける
U(i,i+1,qs);
Controlled H(qs[1..N-1],qs[0]);
Adjoint U(i,i+1,qs);
}
}
}