$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

◇◇Microsoft Q# Coding Contest – Summer 2020 - Warmup B1 - Increment◇◇

☆問題URL

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

☆問題の概要

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

☆解法

通常、整数のインクリメントは以下の手順で行うことができます。

  1. 最下位bitに1を加算する。
  2. 桁上がりが起こったら、最下位bitを0にして最下位bitを除いた部分に対して再びインクリメント操作を行う。

この問題では、上記と同様の手順で2進数で表される量子状態のインクリメント操作を行うことができます。

  1. $X$ゲートを用いて最下位qubitを反転させる。
  2. 反転によって最下位qubitが$\ket{0}$になった場合は桁上がりが起こっているので、最下位qubitを除いた部分に対して再帰的にインクリメントを行う。この操作は、最下位qubitを制御bitとしたControlled演算として定義できる。
  • インクリメント操作を${\rm mod}\;2^N$で行うことは $$U\ket{2^N - 1} = \ket{0}$$ であることを意味しますが、この操作ではこの条件が満たされます。

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

    ☆ソースコード 

                    
namespace Solution {
    open Microsoft.Quantum.Canon;
    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が0になったら繰り上がり
        if (Length(qs) > 1)
        {
            (ControlledOnInt(0, Solve))(qs[0..0], LittleEndian(qs[1...]));
        }
    }
}

    戻る