◇◇Microsoft Q# Coding Contest - Winter 2019 D4 - TIE fighter◇◇

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

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

• 中央が$2\times2$の部分行列
• 右上と左下がサイズ$2^{N-1}-1$の対角行列
• 左上と右下がサイズ$2^{N-1}-1$の反対角行列

例として、$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}$よりも大きい複素数を表す。また、基底状態の順番にはリトル・エンディアンを採用する。

$N=3$を例として、右上の部分行列 $$\left( \begin{array}{rr} . & X & . & . \\ . & . & X & . \\ . & . & . & X \\ X & . & . & . \\ \end{array} \right)$$ は、入力$\ket{i}$に対して$\ket{i-1}$を返すデクリメント演算になっていることがわかります。この部分行列を$D$とし、$R=X^{\otimes N-1}$（反対角行列）とすると、作るべき演算は $$\left( \begin{array}{rr} DR & D \\ RDR & RD \end{array} \right)$$ の形に表すことができます（行列に$R$を右から掛けると左右が、左から掛けると上下が反転するため）。

この形の行列を構成する手順のうちのひとつは $$ \left( \begin{array}{rr} I & O \\ O & R \end{array} \right) \left( \begin{array}{rr} I & I \\ I & -I \end{array} \right) \left( \begin{array}{rr} D & O \\ O & D \end{array} \right) \left( \begin{array}{rr} O & I \\ I & O \end{array} \right) \left( \begin{array}{rr} I & O \\ O & R \end{array} \right) \left( \begin{array}{rr} O & I \\ I & O \end{array} \right) = \left( \begin{array}{rr} DR & D \\ DRD & -RD \end{array} \right) $$ であり、 $\left( \begin{array}{rr} O & I \\ I & O \end{array} \right)$ は$N-1$桁目に$X$ゲートを作用させる演算、 $\left( \begin{array}{rr} I & I \\ I & -I \end{array} \right)$ は$N-1$桁目に$H$ゲートを作用させる演算です。

デクリメント演算$D$は、0桁目を反転させたあと、$N$桁の入力の$i\;(1\leq i\leq N-1)$桁目をターゲットビットとして、$[0,i)$桁目のqubitすべてを制御ビットとしたControlled Xゲートを順に作用させることで構成できます。

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

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

    operation Reverse (qs : Qubit[]) : Unit{
        body(...){
            let N=Length(qs);
            for(q in qs){
                X(q);
            }
        }
        controlled auto;
    }

    operation Decrement (qs : Qubit[]) : Unit{
        let N=Length(qs);
        X(qs[0]);
        for(i in 1..N-1){
            Controlled X(qs[0..i-1],qs[i]);
        }
    }

    operation Solve (qs : Qubit[]) : Unit {
        let N=Length(qs);
        X(qs[N-1]);
        Controlled Reverse([qs[N-1]],qs[0..N-2]);
        X(qs[N-1]);
        Decrement(qs[0..N-2]);
        H(qs[N-1]);
        Controlled Reverse([qs[N-1]],qs[0..N-2]);
    }
}
                
            

戻る