◇◇Microsoft Q# Coding Contest - Winter 2019 D2 - Pattern of increasing blocks◇◇

https://codeforces.com/contest/1116/problem/D2

$N$桁の量子状態に対して、以下のようなパターンで表されるユニタリ演算を定義せよ。

• 右上と左下はすべて0
• 左上は$N-1$の場合になっている($N=1$の場合には、0でない要素)
• 右下はすべて0でない要素

例として、$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 \end{array} \right)$$ の形で表される演算であり、'.'は絶対値の二乗が$10^{-5}$以下の複素数、'$X$'は絶対値の二乗が$10^{-5}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。

サイズ$2^N$のパターンの中にサイズ$2^{N-1}$のパターンを含んでいるので、再帰を用いて定義することができます。

サイズ$2^N$の場合を$U_N$、同じくゼロでない要素のみから構成されるブロックを$X_N$とすると $$U_N= \left( \begin{array}{rr} U_{N-1} & O \\ O & X_{N-1} \end{array} \right)$$ と表せます。これは、$N-1$番目のqubitが$\ket{0}$の場合には0から$N-2$番目のqubitに$U_{N-1}$を、$N-1$番目のqubitが$\ket{1}$の場合には0から$N-2$番目のqubitに$X_{N-1}$を作用させる演算を表します。

$X_N$に関しては、すべてのqubitにアダマール・ゲート$H$を作用させる演算がこの形を満たします。

これで、この問題が解けました。

                
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation IncreasingBlocks (qs : Qubit[]) : Unit{
        body(...){
            let N=Length(qs);
            if(N==1){
                //N=1の場合、恒等演算になる（なにもしない）
            }
            else{
                (ControlledOnInt(0,IncreasingBlocks))([qs[N-1]],qs[0..N-2]);
                for(i in 0..N-2){
                    Controlled H([qs[N-1]],qs[i]);
                }
            }
        }
        controlled auto;
        adjoint auto;
    }

    operation Solve (qs : Qubit[]) : Unit {
        IncreasingBlocks(qs);
    }
}
                
            

戻る