銀の光と碧い空

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

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をレジスターとして表現できる 2N を法とする数値を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すると 1 2 ( | ( 3 + 1 ) mod 2 2 + | ( 1 + 1 ) mod 2 2 ) = 1 2 ( | 0 + | 2 ) = 1 2 ( | 00 + | 01 ) となるとあります。つまり、|3>と|1>を表す状態の重ね合わせなので、それぞれIncrementした|0>と|2>を同じ確率で重ね合わせた状態にする必要があります。

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

docs.microsoft.com

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

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

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

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

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

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

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

  1. qarray[0]を制御ビットとして、Solve操作を残りのqarray[1 ...]に適用する。(配列の長さが1より多いときのみ。)
  2. そのあと、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になった場合、残りの数値をデクリメントします(つまり、最下位から2番目のビットを反転させ、それが1であるかどうかをチェックし、同じ手順を再帰的に適用します)。

で、これをQ#で書くと

  1. X操作をqarray[0]に適用する。
  2. 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]);
    }
}

Microsoft Q# Coding Contest – Summer 2020の復習(1) ユニタリーの識別

1か月以上前ですが、Microsoft Q# Coding Contest がSummer 2020として今年も行われました。復習をまとめておきたいと思います。まずは、warmupのA問題、ユニタリーの識別です。公式の解説記事はこちらです。

codeforces.com

A1からA5の問題は与えられたユニタリーゲートが与えられたあるゲートと同じであるかどうかを判定する問題です。これらの問題はユニタリーの識別としてはQuantum Katasにも追加されたので、今から解く場合はこちらを使うのが手っ取り早いでしょう。

QuantumKatas/DistinguishUnitaries at master · microsoft/QuantumKatas · GitHub

A1

最初の問題A1はIゲートもしくはXゲートのどちらかが unitary として与えられるので、次の操作を実装してIゲートなら0をXゲートなら1を返すようにするものです。

operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    return -1;
}

今回の問題の共通の考え方として解説に説明されていますが、量子プログラムでは「測定」が情報を得る唯一の方法です。その測定とは量子ビット(Qubit)の状態を計測した結果です。ゲートは量子ビットの状態を変える操作ですので、既知の状態の量子ビットを与えられたゲートで変化させてその測定結果で判定する必要があります。すなわち、どのような状態の量子ビットを与えて、ゲートで操作した後、測定した結果でどちらか判定する必要があります。 一般に量子ビットの測定は確率的であるため、任意の2つの状態を測定で区別することはできません。しかし、直交する2つの状態であれば区別することができます。したがって、IゲートとXゲートを適用すると直交する状態になるような量子ビットの状態を見つける必要があります。

Iゲートは|0>と|1>の状態をそのままにし、Xゲートはそれぞれ反転させることを考えれば、|0>の量子ビットを用意しゲートを操作した後測定して、|0>ならIゲート、|1>ならXゲートと考えることができます。したがって答えは次のようになります。

operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using (q = Qubit()) {
        unitary(q);
        let res = M(q);
        Reset(q);
        return res == Zero ? 0 | 1;
    }       
}

usingを抜けるときにQubitは初期化しておかないといけないので、Reset操作をしてから測定結果を比較して値を返しています。この計測してResetする操作をまとめておこなうMResetZという操作がMicrosoft.Quantum.Measurement名前空間にあるので次のように書くことができます。

open Microsoft.Quantum.Measurement;

operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using (q = Qubit()) {
        unitary(q);
        return MResetZ(q) == Zero ? 0 | 1;
    }       
}

A2

今度は与えられたunitaryゲートがIゲートなら0をPauliZゲートなら1を返す問題です。PauliZゲートは|0>はそのままに、|1>は位相をひっくり返して-|1>にするためこの2つの状態では区別できません。しかし、|+>と|->の2つの直交する状態を考えると、PauliZは|+>を|->に変化させるので区別することができます。H|0>=|+>、H|+>=|0> とH|->=|1> を利用すると次のように書けます。

operation DistinguishIfromZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using(q = Qubit()) {
        H(q);
        unitary(q);
        H(q);
        let res = M(q);
        Reset(q);
        return res == Zero ? 0 | 1;
    }
}

また、|+>と|->はPauliXに沿った測定で計測できることと、MResetX という操作があるので次のように短く書けます。

operation DistinguishIfromZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using(q = Qubit()) {
        H(q);
        unitary(q);
        return MResetX(q) == Zero ? 0 | 1;
    }
}

A3

今度はZゲートなら0をSゲートなら1を返す関数です。ヒントは問題文の条件がexactly onceからat most twiceに変わっていることです。いままでは1回しかunitary操作ができなかったところを、今回は2回できます。Zゲートを2回適用するとIゲートになり、Sゲートを2回適用するとZゲートになります。つまりA2と同じ問題になります。

ration DistinguishZfromS (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using (q = Qubit()) {
        H(q);
        unitary(q);
        unitary(q);
        return MResetX(q) == Zero ? 0 | 1;
    }
}

A4

なぜか本来の問題の順番と、解説およびQuantumKatasではA4とA5の順番が逆になっています。おそらく単一Qubutに対するunitary操作の識別を最初に並べて、最後に2つのQubitの操作にしたのでしょう。本来の問題通り、I⊗XとCNOTの識別をA4として解きます。

I⊗Xは2番目のQubitのみにXゲートを適用させる操作で、CNOTは1番目のゲートを制御Qubitとして2番目のQubitにNOT操作(つまりXゲート)を適用する操作です。|0>と|1>の直交状態のQubit2つからなる4つの状態において、それぞれの操作でどのように変化するか考えてみましょう。

State I⊗X CNOT
|00> |01> |00>
|01> |00> |01>
|10> |11> |11>
|11> |10> |10>

2つのQubitはentangle状態にはなっていないので、|00>という状態のQubitに対してunitary操作をしたあとの2番目のQubitの状態が|0>か|1>か計測すれば識別できることになります。したがって答えは次のようになります。

operation DistinguishIXfromCNOT (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
    using (qs = Qubit[2]) {
        unitary(qs);
        return MResetZ(qs[1]) == One ? 0 | 1;
    }
}

A5

今度はZゲートなら0を-Zゲートなら1を返す関数です。Zゲートと-Zゲートはグローバル位相しか違わないので直交する2つの状態で識別できなさそうな気がしてきます。そこでここまで問題文に与えられているのに使っていない条件に着目します。unitary操作がControlledという条件です。ひとつ前の問題でCNOTという操作を出しているのもこの条件に気付いてほしかったのではと、解説を読んで気付きました。制御Qubitが必要なので、2つQubitを用意し、1番目のQubitを制御Qubitとし、2番目のQubitにControlled ZもしくはControlled -Z を適用した場合の状態変化を考えます。

State Controlled Z Controlled -Z
|00> |00> |00>
|01> |01> |01>
|10> |10> -|10>
|11> -|11> |11>

1番目のQubitが|0>であればどちらの操作でも状態は変化しません。1番目のQubitが|1>のときだけ-1の位相のずれが発生します。そこで|00>と|10>が均等に混じった状態、つまり (|0> + |1>) ⊗ |0>に着目します。この状態にControlled Zを適用しても状態は変化しません。Controlled -Zを適用すると、|1> ⊗ |0> が位相-1だけずれ、 (|0> - |1>) ⊗ |0>の状態になります。1番目のQubitが (|0> + |1>) と (|0> - |1>) の状態を識別すればよいので、A2と同じ問題であることがわかります。というわけで答えは次のようになります。Q#のControlled functorはQubitの配列に対して適用できるので、単一Qubitを要素数1の配列として渡します。

peration DistinguishZfromMinusZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using (qs = Qubit[2]) {
        H(qs[0]);
        Controlled unitary(qs[0..0], qs[1]);
        return MResetX(qs[0]) == Zero ? 0 | 1;
    }
}

以上でwarmupラウンドのA問題のまとめになります。

Microsoft MVPを再受賞しました

Microsoft MVPを再受賞しました。最近は新規受賞者は毎月審査して発表、継続受賞者は1年に一度7月1日に発表となっています。

たしかここ2年ほどAzureカテゴリでの受賞だったのですが、今年はAzureとDeveloper Technologiesの2つのカテゴリで受賞となりました。

f:id:tanaka733:20200702165848p:plain

今回で8度目の受賞らしいのですが、最初の受賞からしばらくはC#(とそこから名前が変わった.NETなど)カテゴリでの受賞でした。2年ほど前からAzureカテゴリでの活動も増えたのでAzureカテゴリのみの受賞になったのですが、今年は両方のカテゴリで受賞することができました。正直、片方ずつだと活動量たりないかも?と思っていたので非常に驚いています。

今年も昨年に引き続き、Azure、C#、Q#あたりの分野で活動していく予定です。特にQ#はオンライン化が進む中であまり活動できていないので、さっそくなにかやろうと考えています。

活動もますますオンライン化が進む1年になりそうですが、引き続きよろしくお願いします。