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ゲートを適用すると直交する状態になるような量子ビットの状態を見つける必要があります。

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回できます。Ｚゲートを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問題のまとめになります。

銀の光と碧い空

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

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

A1

A2

A3

A4

A5