Microsoft Q# Coding Contest – Summer 2020の復習(2) 可逆計算

前回のA1~A5 ユニタリーの識別に引き続き、今回はB1,B2の可逆計算（Reversible computing）のおさらいです。

可逆計算をWikipediaで見てみると次のように書いています。

可逆計算（かぎゃくけいさん、英: Reversible computing）とは、可逆な、すなわち計算過程において常に直前と直後の状態が一意に定まる計算。可逆計算は、計算過程において情報が消失しないため非破壊的計算（Non-destructive computing）としても知られている。

ja.wikipedia.org

量子コンピューターにおいては古典的な計算を可逆的に表現することで、算術などの古典的な計算を量子コンピューター上で実行できるようになる、と解説に書いています。今回はIncrementとDecrementを表現することが課題になっています。

B1

N個のQubitをレジスターとして表現できる 2^N を法とする数値をIncrementするユニタリー操作を実装します。さて、スケルトンコードを見ると LittleEndianというタイプが引数として与えられています。

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

    operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
        // your code here
    }
}

定義を見るとわかるように、これはQubitの配列です。

docs.microsoft.com

newtype LittleEndian = Qubit[];

符号なし整数をリトルエンディアンでフォーマットしたもの、つまり最下位ビットが配列一番目の要素として表現されています。このようにある符号なし整数を表現したregister をIncrementする操作を実装します。問題文には例として、 $\frac{1}{\sqrt{2}}(|11\rangle + |10\rangle) = \frac{1}{\sqrt{2}}(|3\rangle + |1\rangle)$ をIncrementすると $\frac{1}{\sqrt{2}} (| (3 + 1) \mod 2^{2} ⟩ + | (1 + 1) \mod 2^{2} ⟩) = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 2 ⟩) = \frac{1}{\sqrt{2}} (| 00 ⟩ + | 01 ⟩)$ となるとあります。つまり、|3>と|1>を表す状態の重ね合わせなので、それぞれIncrementした|0>と|2>を同じ確率で重ね合わせた状態にする必要があります。

また、Q#ではそのものずばりのIncrementByInteger という操作もありますが、測定をふくむこのような操作をおこなわず、Xゲートとそのcontrolled操作のみで実装せよと条件があります。

docs.microsoft.com

どのように実装するか、ですが、まず古典的な数を2進法でIncrementするときの手順を考えます。

最下位のビットを反転させる。
最下位のビットが0になった場合、残りの数値をインクリメントします（つまり、最下位から2番目のビットを反転させ、それが0であるかどうかをチェックし、同じ手順を再帰的に適用します）。

この操作を逆順に考えると次のようになります。

最下位のビットが1であれば、残りのビットをインクリメントします。この手順は再帰的に行われます。
その後、最下位のビットを反転させます。

これを量子プログラミングで実装するとこうなります。さきほど逆順で考えたのは、制御量子ビットとして使う最下位の量子ビットが1になるときに条件付き操作をおこないたいからです。

最下位の量子ビットを制御量子ビットとして、残りのビットに対してインクリメント操作を行います。（再帰処理）
最下位のビットにXゲートを適用します。

だんだん実装イメージができてきました。Q#で実装する場合、registerを表現するQubitの配列をqarrayとすると、

qarray[0]を制御ビットとして、Solve操作を残りのqarray[1 ...]に適用する。（配列の長さが1より多いときのみ。）
そのあと、X操作をqarray[0]に適用する。

となります。これでコードが書けます。Q#では newtype LittleEndian = Qubit[]; のように定義したタイプからQubit[]をアンラップして取り出す処理を!で記述します。

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

    operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
        let qarray = register!;
        if (Length(qarray) > 1) {
            (Controlled Solve)([qarray[0]], LittleEndian(qarray[1 ...]));
        }
        X(qarray[0]);
    }
}

B2

同じように考えると、古典的な数を2進法でデクリメントする操作がこう書けます。

最下位のビットを反転させる。
最下位のビットが1になった場合、残りの数値をデクリメントします（つまり、最下位から2番目のビットを反転させ、それが1であるかどうかをチェックし、同じ手順を再帰的に適用します）。

で、これをQ#で書くと

X操作をqarray[0]に適用する。
qarray[0]を制御ビットとして、Solve操作を残りのqarray[1 ...]に適用する。（配列の長さが1より多いときのみ。）

となります。したがって実装するとこのようになります。

operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
    let qarray = register!;
    X(qarray[0]);
    if (Length(qarray) > 1) {
        (Controlled Solve)([qarray[0]], LittleEndian(qarray[1 ...]));
    }
}

これでよいのですが、この実装よくみると先ほどのインクリメントの操作の逆順です。またビットの操作の手順を考えてもインクリメントの逆順の操作となります。Q#ではある操作を逆順に行う操作もユニタリーである場合、操作がAdjointであるといい、Adjoint functorでその逆順操作を実行できます。したがって、B2のSolveはB1のSolveの実装を例えばIncrementという名前で定義し、そのAdjoint functorを呼び出すことで実装できます。

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

    operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
        Adjoint Increment(register);
    }

    operation Increment (register : LittleEndian) : Unit is Adj+Ctl {
        let qarray = register!;
        if (Length(qarray) > 1) {
            (Controlled Increment)([qarray[0]], LittleEndian(qarray[1 ...]));
        }
        X(qarray[0]);
    }
}

銀の光と碧い空

クラウドなインフラとC#なアプリ開発の狭間にいるエンジニアの日々

Microsoft Q# Coding Contest – Summer 2020の復習(2) 可逆計算

B1

B2