◇◇Microsoft Q# Coding Contest – Summer 2020 - Warmup B2 - Decrement◇◇

https://codeforces.com/contest/1356/problem/B2

$N$ qubitの量子状態がLittleEndianで与えられるので、状態を${\rm mod}\;2^N$でデクリメントする演算を定義せよ。例として \begin{align*} U\left( \frac1{\sqrt2} \left( \ket{00} + \ket{01} \right) \right) &= U\left( \frac1{\sqrt2} \left( \ket{0} + \ket{2} \right) \right) \\ &= \frac1{\sqrt2} \left( \ket{3} + \ket{1} \right) \\ &= \frac1{\sqrt2} \left( \ket{11} + \ket{10} \right) \end{align*} ただし、$X$ゲートとそのControlled派生以外の演算を用いてはならない。

デクリメントは、インクリメントと同様の手順で行うことができます。

1. $X$ゲートを用いて最下位qubitを反転させる。
2. 反転によって最下位qubitが$\ket{1}$になった場合は繰り下がりが起こっているので、最下位qubitを除いた部分に対して再帰的にデクリメントを行う。この操作は、最下位qubitを制御bitとしたControlled演算として定義できる。

また、前問で定義したインクリメント演算をAdjointで実行することでもこの問題を解くことができます。

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

                
namespace Solution {
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Intrinsic;

    operation Solve (register : LittleEndian) : Unit is Adj+Ctl
    {
        //LittleEndianをQubit[]に変換する
        let qs = register!;

        //最下位bitをデクリメントする
        X(qs[0]);

        //最下位bitが1になったら繰り上がり
        if (Length(qs) > 1)
        {
            (Controlled Solve)(qs[0..0], LittleEndian(qs[1...]));
        }
    }
}
                
            

Incrementの逆演算を行うバージョン

                
namespace Solution {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Intrinsic;

    operation Increment (register : LittleEndian) : Unit is Adj+Ctl
    {
        //LittleEndianをQubit[]に変換する
        let qs = register!;

        //最下位bitをインクリメントする
        X(qs[0]);

        //最下位bitが0になったら繰り下がり
        if (Length(qs) > 1)
        {
            (ControlledOnInt(0, Increment))(qs[0..0], LittleEndian(qs[1...]));
        }
    }

    operation Solve (register : LittleEndian) : Unit is Adj+Ctl
    {
        //registerに対して、Incrementの逆演算を適用する
        Adjoint Increment(register);
    }
}
                
            

戻る