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

今回からは本選の解説をまとめていきます。

今回は予選のA問題と同じくユニタリー操作を識別する問題A1~A7です。予選問題の解説まとめ記事はこちら。

tech.tanaka733.net

A1

A1は2量子ビットの最初のビットで制御して2番目のビットに適用するCNOT_12と2番目のビットを制御に用いて最初のビットに適用するCNOT_21を識別する問題です。

両者は|00>以外の|01>,|10>,|11>のいずれの状態でも、適用すると異なる状態になります。ここでは |10>が|01>と|10>になることを使って識別しました。

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

    operation SolveA1 (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
        mutable res = 0;
        using (qs = Qubit[2]) {
            within { X(qs[0]);}
            apply { unitary(qs);}
            return MResetZ(qs[1]) == Zero ? 1 | 0;
        }
    }
}

ここで使ったwithin~apply~構文は次のコードと同じです。今回のコードでは必ずしも必要ないのですが、解説に使ってあったので使ってみました。

X(qs[0]);
unitary(qs);
Adjoint X(qs[0]);

Operations and functions in Q# - Microsoft Quantum | Microsoft Docs

A2

次はI⊗I、CNOT_12、CNOT_21、SWAPゲートを識別します。2量子ビットなので1度のユニタリー操作でそれぞれ異なる4つの状態になるような状態があればよいのですが、おそらく存在せず、問題にも2回までユニタリー操作を適用してよいとあるので、2回にわけてしぼることを考えます。そこで初期状態ごとにどんな状態に変わるかをまとめてみましょう。

	II	CNOT12	CNOT21	SWAP
\|00>	\|00>	\|00>	\|00>	\|00>
\|10>	\|10>	\|11>	\|10>	\|01>
\|01>	\|01>	\|01>	\|11>	\|10>
\|11>	\|11>	\|10>	\|01>	\|11>

|00>はだめですが、それ以外の状態を使えば以下の3通りの解決ができそうです。

|10>でCNOT12とSWAPを識別。|01>か|11>でIIとCNOT21を識別。
|01>でCNOT21とSWAPのみ識別。|01>か|11>でIIとCNOT12を識別。
|11>でCNOT12とCNOT21を識別。|01>か|10>でIIとSWAPを識別。

解説では3番目の方法を使っていたので、1番目の方法で解いた答えがこうなります。

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

    operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
        using (qs = Qubit[2]) {
            X(qs[0]);
            unitary(qs);
            let ind = MeasureInteger(LittleEndian(qs));
            let res = ind == 2 ? 3 |
                        ind == 3 ? 1 | 0;
            if (res != 0) {
                return res;
            }
        }
        using (qs = Qubit[2]) {
            X(qs[1]);
            unitary(qs);
            let ind = MeasureInteger(LittleEndian(qs));
            return ind == 2 ? 0 | 2; 
        }
    }
}

using節の中にreturnを書く場合、その分が最後でなければいけないので、最初のusing節はいったん答えを変数に格納し、returnできるときだけ返すif文を入れています。3番目の方法だとここがスマートに書けます。

A3

HゲートとXゲートを識別する問題で、与えられたユニタリー操作は2回まで適用できます。

Problem - A3 - Codeforces

ここでは HXH = Z と XXX = X という関係を使います。Z|0> = |0>でX|0>=|1>なので HXH|0>=|0>、XXX|0>=|1>となります。

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

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

A4

RzとR1の識別です。回転角θは引数として与えられたユニタリー操作の引数として、ユニタリー操作の適用時に指定できます。

Problem - A4 - Codeforces

RzとR1の関係は次のように表せます。

$Rz(\theta) = \begin{bmatrix} e^{-i\theta/2} & 0 \ 0 & e^{i\theta/2} \end{bmatrix} \ R1(\theta) = \begin{bmatrix} 1 & 0 \ 0 & e^{i\theta} \end{bmatrix} = e^{i\theta/2} Rz(\theta)$

つまり、 $e^{i θ / 2}$ だけグローバル位相がずれます。グローバル位相のずれを識別する問題としては、warmupのA5がありました。

tech.tanaka733.net

グローバル位相が-1だけずれればA5と同じ方法で解けるので、θ=2πを指定して同じようにします。

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

    operation Solve (unitary : ((Double, Qubit) => Unit is Adj+Ctl)) : Int {
        using (qs = Qubit[2]) {
            within {
                H(qs[0]);
            } apply {
                Controlled unitary(qs[0..0], (2.0 * PI(), qs[1]));
            }
            return MResetZ(qs[0]) == Zero ? 1 | 0;
        }
    }
}

A5

今度はRyとRzの識別です。回転角についてはA4とは違ってある数値が引数として指定されます。

Problem - A5 - Codeforces

それぞれのゲートの定義はこうなっています。

$Rz(\theta) = \begin{bmatrix} e^{-i\theta/2} & 0 \ 0 & e^{i\theta/2} \end{bmatrix} \ Ry(\theta) = \begin{bmatrix} \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \ \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{bmatrix}$

Rzが対角行列なのに対し、Ryはそうではないため、いままでやってきたような直交する2つの状態を見つけることが難しいように思えます。ここで問題文のas many times as you need (within the time limit).に着目します。今回だけユニタリー操作を何度でも適用してよいとあります。そこで、Ry|0>を測定した結果が|1>になる確率があることを利用して、多数回ユニタリー操作を|0>に適用し、その測定結果が一度でも1であればRyとする、そうでなければRzとする、という処理を行います。試行回数を少なくするには、全体の回転角がπになるまで測定すればよく、解答例として vilim_l氏の回答がリンクされています。

Submission #84346001 - Codeforces

ここまででてきたMResetZを使うとこう書けます。

namespace Solution {
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Diagnostics;
    
    operation Solve (theta : Double, unitary : (Qubit => Unit is Adj+Ctl)) : Int {
        using (q = Qubit()) {
            let k = Floor(PI() / theta);
            mutable res = 0;
            for (rep in 0..10) {
                for (i in 1..k) {
                    unitary(q);
                }
                if (MResetZ(q) == One) {
                    set res = 1;
                }
            }
            return res;
        }
    }
}

A6

今度は、ユニタリー操作は1回しか適用できない条件で、I,X,Y,Zゲートの4種類を識別する問題です。

Problem - A6 - Codeforces

1回しか適用できないので4つ識別できないと思いそうですが、 $\frac{1}{\sqrt{2}} (| 00 ⟩ + | 11 ⟩)$ とその符号違いで表せるBell状態を使い、複数回測定することで識別が可能になります。

4つのBell状態のどの状態かを識別する問題はMicrosoft Q# Coding Contest - Summer 2018 - WarmupのEで出ました。

Problem - E - Codeforces

このとき、Bell状態のままPauliX軸とPauliY軸での測定を行って識別する方法もありましたが、公式解説では、CNOTとH操作を適用することで B0が|00>にB1が|01>になることを利用した回答を説明しています。

https://assets.codeforces.com/rounds/997-998/warmup-editorial.pdf

（文法は当時のまま）

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[]) : Int
    {
        body
        {
            CNOT(qs[0], qs[1]);
            H(qs[0]);
            return ResultAsInt([M(qs[0]); M(qs[1])]);
        }
    }
}

つまり、次のような操作を行うと、適用したユニタリー操作によって|00>や|01>といった状態になることが期待されます。

|00>を用意し、HとCNOT操作でBell状態を作る
与えられたユニタリー操作を適用する
CNOTとH操作をした後、2つの量子ビットを測定する

試してみましょう。

namespace Quantum.Lab {

    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;

    
    @EntryPoint()
    operation HelloQ () : Unit {
        Dump(I);
        Dump(X);
        Dump(Y);
        Dump(Z);
    }

    operation Dump(unitary : (Qubit => Unit is Adj+Ctl)) : Unit {
        using (qs = Qubit[2]) {
            within {
                H(qs[0]);
                CNOT(qs[0], qs[1]);
            }
            apply {
                unitary(qs[0]);
            }
            let ind = MeasureInteger(LittleEndian(qs));
            Message($"{unitary}={ind}");
        }
    }
}

次のような結果が得られます。

I=0
X=2
Y=3
Z=1

この結果を使うと回答は次のようになります。

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

    operation Solve(unitary : (Qubit => Unit is Adj+Ctl)) : Int {
        using (qs = Qubit[2]) {
            within {
                H(qs[0]);
                CNOT(qs[0], qs[1]);
            }
            apply {
                unitary(qs[0]);
            }
            let ind = MeasureInteger(LittleEndian(qs));
            let returnValues = [0, 3, 1, 2];
            return returnValues[ind];
        }
    }
}

A7

A7はY、-XZ、-Y、XZの四つのユニタリー操作を識別する問題です。XZというのは最初にZ操作をした次にX操作をする操作を意味しています。そして、-Y、-XZはそれぞれグローバル位相がπだけずれた操作です。

Problem - A7 - Codeforces

さて、解説の回答では位相推定を使っていますが、ここでは位相推定を使わずに解いてみましょう。3回操作ができるということに着目して、2回操作したときにどうなるかを考えます。行列式で計算すれば、±YはIに、±XZは-Iに等しいことがわかります。これは、warmupのA5、本選のA4で使った方法で解けます。ついでに、XZがiYだということもわかります。

operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
    using (qs = Qubit[2]){
        H(qs[0]);
        Controlled (BoundCA([unitary, unitary]))(qs[0..0], qs[1]);
        let res1 = MResetX(qs[0]);   //Zeroなら±Y Oneなら±iY
        ResetAll(qs);
        
    }
}

res1の値で分岐できるので、Yと-Y、XZと-XZを1回の操作で識別することを考えます。今までと同じような方法として、Controlled ±Yによる状態の変化を計算してみます。

	Controlled Y	Controlled -Y
\|00>	\|00>	\|00>
\|10>	i\|11>	-i\|11>
\|01>	\|01>	\|01>
\|11>	-i\|10>	i\|10>

|10>の状態が|11>になってしまうのでいままでの方法が使えない気がしますが、|11>の状態に再度Yゲートを適用すれば|10>に戻るのでこれを使ってみましょう。

$Y (\pm Y) (| 0 ⟩ + | 1 ⟩) \otimes | 0 ⟩ = Y (| 00 ⟩ \pm ı | 11 ⟩) = | 00 ⟩ \pm | 10 ⟩ = (| 0 ⟩ \pm | 1 ⟩) \otimes | 0 ⟩$

これで、今までの位相-1のずれを識別するパターンに持ち込めました。

XZと-XZも同じように計算できますが、問題を見ると-XZのときに1、XZのときに3と返す値が小さいほうを測定値Zeroとして求められるようにユニタリー操作のあとにXZを適用します。

$X Z (\mp X Z) (| 0 ⟩ + | 1 ⟩) \otimes | 0 ⟩ = X Z (| 00 ⟩ \pm | 11 ⟩) = | 00 ⟩ \pm | 10 ⟩ = (| 0 ⟩ \pm | 1 ⟩) \otimes | 0 ⟩$

以上を踏まえて答えはこうなります。

namespace Solution {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Characterization;
    open Microsoft.Quantum.Oracles;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Intrinsic;


    operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
        using (qs = Qubit[2]){
            H(qs[0]);
            Controlled (BoundCA([unitary, unitary]))(qs[0..0], qs[1]);
            let res1 = MResetX(qs[0]);   //Zeroなら±Y Oneなら±iY
            ResetAll(qs);
            H(qs[0]);
            if (res1 == Zero) {
                Controlled (BoundCA([unitary, Y]))(qs[0..0], qs[1]);
            } else {
                Controlled (BoundCA([unitary, Z, X]))(qs[0..0], qs[1]);
            }
            let res2 = MResetX(qs[0]);
            ResetAll(qs);
            return ResultArrayAsInt([res1, res2]);
        }
    }
}

一連の操作（ここでは、与えられたユニタリー操作を2回だったり、ユニタリー操作のあとにYゲートなど）をControlled functorで実行したい場合、operationの定義を作ってもよいですが、BoundCA関数を使うと、配列で与えた操作をまとめて一つの操作にしてくれます。

docs.microsoft.com

また、回答では使いませんでしたが、-の操作はZX*ZXと書けるので、-Yなどの操作は次の関数定義と合わせてこのように書けます。

BoundCA([Y, MinusOne])(q);

operation MinusOne (q : Qubit) : Unit is Adj+Ctl {
    within { X(q); }
    apply { Z(q); }
    Z(q);
}

銀の光と碧い空

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

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

A1

A2

A3

A4

A5

A6

A7