Part I. Problem Statement and Classical Algorithm解説

Deutsch-Jozsaアルゴリズム(ドイチェジョザアルゴリズム)に関するチュートリアルです。Deutsch-Jozsaアルゴリズムは量子コンピューティングの世界では非常に有名なアルゴリズムで、量子コンピューターの有益性を理解するためには良い題材です。ただ実際の世界においてはあまり有効に活用できるようなロジックではないためここでは量子コンピュータの優位性を理解することにフォーカスします。

Deutsch-JozsaのTutorialは4部に分かれています。
Part 1: 問題の定義と古典アルゴリズムについて
Part 2: 量子オラクルについて
Part 3: 量子アルゴリズムについて
Part 4: 実際にDeutsch-Jozsaを量子アルゴリズムで動かしてみる

「Part 1: 問題の定義と古典アルゴリズムについて」は
Deutsch-Jozsaが解決しようとする問題を理解し、古典コンピューターで解こうとした場合の問題点を理解します。

Deutsch–Jozsa Algorithmついて

Deutsch-Jozsaアルゴリズムとは中身のわからないブラックボックスな関数\(f(x)\)について、
1) すべての入力\(x\)に対して、常に0を返す、あるいは、常に1を返す場合、constant
2) 入力\(x\)に対して50%ずつの確率で0と１をそれぞれ返す場合balanced
と関数の性質を判定するアルゴリズムです。

古典コンピューターの場合、関数の性質を判定するのに最悪の場合、全体の51%の入力に対して総当たり的に入力を与えないと解が求まらないのに対して、量子コンピュータを使うと多項式時間で解が求まることを理解します。

Q#の基本的な文法について

この辺りからQ#の基本的な文法についてある程度知っておかないと、if文やfor/whileループの書き方なに戸惑ってしまいます。
Q#の基本的な文法についてはこちらにまとめています。

Exercise 1: Implement a classical function in Q#

Most Significant Bitが０か1かを判定する関数を作成します。

%kata E1_ClassicalFunction_Test 

function Function_MostSignificantBit (x : Int, N : Int) : Int {
    let msb = x >>> (N-1);
    return msb;
}

古典アルゴリズムについて

古典コンピュータの場合、組み合わせを求めるためにループを回す必要があり計算量が\(2^n\)のオーダーになります。実際にプログラムを書いてみて確かめてみましょう。

Exercise 2: Implement the classical algorithm!

ここでは古典コンピュータの古典的なアルゴリズムを使って関数\(f(x)\)がConstantかBalancedかを判定する処理を作ります。ループを\(2^{(n-1)}\)回まわす処理が必要で、前提条件からループが回りきらせる必要はないですが、Constantと判断するには最低でも全入力の51%\((n^{(n/2 +1)}回)\)は試す必要があります。

%kata E2_ClassicalAlgorithm_Test 

operation IsFunctionConstant_Classical (N : Int, f : (Int -> Int)) : Bool {
    mutable ret = true;
    let ret0 = f(0);
    for (i in 1 .. 1 .. (2^N - 1)) {
        let ret_i = f(i);
        if (ret0 != ret_i){
            set ret = false;
            return ret;
        }
    }
    return ret;
}