Q# Coding Contestを題材にQuantum Oracleについてがんばって理解してみる

以前話題に出した Q# Coding ContestでQuantum Oracleについての問題があったのですが、Quantum Oracleとはなんなのか？というのを出てきた問題を題材に自分なりにまとめてみました。まず、Quantum Oracleについてはcoding contestのブログにて記事が出ています。

codeforces.com

このブログの記事の概要としては、古典的関数 を扱うことにあるようですが、要はn-bitのバイナリを受け取ってm-bitのバイナリを返すという意味で、古典関数をバイナリの入出力で表現したと考えればよさそうです。 で、これをQ#の中で考えるには、Qubitの操作として定義したいものの、nとmが異なる場合はそもそもそのまま扱えないし、たとえ同じだとしても随伴操作が作れなくてユニタリ変換にならないのでQubitの操作として定義することができないといっています。そこで、n Qubitからなる状態 x とm Qubitからなる状態 y を重ね合わせたものに対する操作 O を考えると、これはユニタリ変換になってて（というよりそうしていて）、次のように古典関数 f を定義できてうれしいといっています。

つまり、出力 |y> も入力 |x> とあわせて入力として扱い、出力 |y> と古典関数f の排他的論理和をとったものと入力 |x> とのテンソル積が欲しいものになる、ということのようです。これだけだと、自分はわかったようなわからんような感じだったので、とりあえずCoding Contestの問題を見てみます。

codeforces.com

入力 |x> に対し、kが指定されたときに、k番目の要素を返す古典関数fに対するQuantum Oracleに関する問題です。ここでは、入力がn Qubitの|x>、出力が1 Qubitなので、Q#のOperationの第一引数がn個のQubit配列、第二引数が単一のQubitでこれが出力となります。 解答としては、|x>に古典関数fを施したものは結局k番目の要素を返すのでx[k]にほかならず、これとyでCNOTをとったものが答えになっています。

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

    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
    {
        body
        {
            CNOT(x[k], y);
        }
    }
}

次の問題は、入力|x> を全部足した値を2を法とした場合の剰余をもとめる問題です。

codeforces.com

全部足した値の2を法とした剰余というのが、結局XORであり、入力 |x> の各要素を順番に*1 出力 |y> とCNOTをとればよいことになります。ここは一応、前の問題がヒントになっています。

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

    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
    {
        body
        {
            for (i in 0..Length(x)-1) 
            {
                CNOT(x[i], y);
            }
        }
    }
}

ここからは本戦の問題です。この問題は直前の問題と並べるとよく似ていることに気づきます。

codeforces.com

違いは、bit配列 b が追加されていて、bと |x> との内積の和の2を法とした場合の剰余になっています。bと |x> との内積に対して、2を法とするということで、結局bit配列であるbの要素が1のときだけ入力|x>のXORをとっていればよいことになり、答えは次のようになっています。

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

    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
    {
        body
        {
            for (i in 0..Length(x)-1) 
            {
                if (b[i] == 1) 
                {
                    CNOT(x[i], y);
                }
            }
        }
    }
}

次がQuantum Oracleに関する最後の問題です。今度は b * x + (1 - b) * (1 - x) という形の内積になっています。

codeforces.com

内積の前半 b*x については直前の問題と同じなので、bit配列bの要素の値が1のときはCNOTをとればいいことになります。後半については (1-b) というのは結局bの否定なのでbが0のときに計算する必要があり(1-x) というのはx の否定になります。そのため、bが0のときは入力|x>の要素の否定=PauliX操作の結果をCNOTすればいいことになります。注意しないといけないのが、Quantum Oracleとなる操作はユニタリ操作でないといけないので、入力|x>の状態を変えてはいけません。そのためPauliX操作を行ったものは同じ操作をしてもとに戻しておく必要があります。

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

    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
    {
        body
        {
            for (i in 0..Length(x)-1) 
            {
                if (b[i] == 1) 
                {
                    CNOT(x[i], y);
                }
                else 
                {
                    // do a 0-controlled NOT
                    X(x[i]);
                    CNOT(x[i], y);
                    X(x[i]);
                }
            }
        }
    }
}

Coding Contestの問題と答えがあるので、照らし合わせてなんとかという感じでまとめました。もうちょっと具体的な問題とアルゴリズムに対するQuantum Oracleがあればよりわかるようになるかもしれません...

*1:順番自体はどうでもよく、とにかく全要素を１回ずつ適用すればよい