チュートリアル:Q# でグローバーの検索アルゴリズムを実装する

このチュートリアルでは、Q# で Grover のアルゴリズムを実装して、検索に基づく問題を解決する方法を学習します。

グローバーのアルゴリズムは、量子コンピューティングにおいて最も有名なアルゴリズムの 1 つです。 解決する問題は、"データベースの検索" と呼ばれることがよくありますが、検索の問題 の観点から考える方が正確です。

検索タスクは、検索項目 $x$ を受け入れる抽象関数 $f(x)$ を使用して数学的に表現できます。 項目 $x$ が検索タスクのソリューションである場合は、$f(x)=1$ となります。 項目 $x$ がソリューションでない場合は、$f(x)=0$ になります。 検索に関する問題は、$f(x_0)=1$ という任意の項目 $x_0$ を検索することで構成されます。

注意

このチュートリアルは、Q# での実装方法を学習するグローバーのアルゴリズムについて理解している方を対象としています。 よりゆっくりとしたペースでのチュートリアルについては、Microsoft Learn モジュールのグローバーの検索を使用してグラフの色分けの問題を解決するをお勧めします。 グローバーのアルゴリズムの背後にある理論の詳細については、グローバーのアルゴリズムの概念記事理論を確認してください。

グローバーのアルゴリズム タスク

クラシック関数 $f(x):\{0,1\}^n \rightarrow\{0,1\}$ と指定します。ここで $n$ は検索スペースのビットサイズです。$f(x_0)=1$ の入力 $x_0$ を検索します。

グローバーのアルゴリズムを実装して問題を解決するには、次のことを行う必要があります:

  1. 問題をグローバーのタスクの形式に変換する: たとえば、グローバーのアルゴリズムを使用して $M$ 整数の要素を検索するとします。 関数 $$f_M(x)=1[r],$$ を作成することによって、整数の因子分解問題をグローバーのタスクに変換できます。ここで $1[r]=1$ if $r=0$ and $1[r]=0$ if $r\neq0$ and $r$ は $M/x$ の剰余です。 これにより、$f_M(x_i)=1$ の整数 $x_i$ が $M$ の要因になり、問題がグローバーのタスクに変換されました。
  2. グローバーのタスクの関数を quantum oracle として実装する: グローバーのアルゴリズムを実装するには、グローバーのタスクの関数 $f(x)$ を quantum oracle として実装する必要があります。
  3. Oracle でグローバーのアルゴリズムを使用してタスクを解決する: quantum oracle がある場合は、グローバーのアルゴリズム実装にプラグインして、問題を解決し、出力を解釈することができます。

グローバーのアルゴリズムの概要

検索タスクに $N=2^n$ の対象項目があるとします。各項目に $0$ から $N-$1 の整数を割り当ててインデックスを作成します。 アルゴリズムの手順:

  1. 状態 $\ket{0}$ で開始される $n$ 個の量子ビットのレジスタから始めます。
  2. レジスタ内の各量子ビットに $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$ という $H$ を適用して、登録を一様の重ね合わせに準備します:
  3. 次の操作をレジスタ $N_{\text{optimal}}$ times に適用します:
    1. oracle $O_f$ フェーズでは、ソリューション項目に対して $-$1 の条件付きフェーズ シフトが適用されます。
    2. レジスタの各量子ビットに $H$ を適用します。
    3. $\ket{0}$ を除くすべての計算基準の状態に、$-1$ の条件付きフェーズ シフトを $-O_0$ を適用します。
    4. レジスタの各量子ビットに $H$ を適用します。
  4. 確率が非常に高いソリューションである項目のインデックスを取得するには、レジスタを測定します。
  5. 有効なソリューションであるかどうかを確認してください。 それ以外の場合は、再度開始します。

グローバーのアルゴリズム用のコードを記述する

ここでは、Q# にアルゴリズムを実装する方法について説明します。

グローバーの拡散演算子

まず、上記のループから手順 bc、および d を適用する操作を記述します。 これらの手順は、グローバーの拡散演算子 $-H^{\otimes n} O_0 H^{\otimes n}$ とも呼ばれます

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {

    within {
        ApplyToEachA(H, inputQubits);
        ApplyToEachA(X, inputQubits);
    } apply {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

}

この操作では、グローバーの拡散演算子で発生する自動活用形操作を実装する、within-apply ステートメントを使用します。

注意

Q# の活用の詳細については、Q# 言語ガイドの活用に関する記事を参照してください。

コードと操作を理解するには、操作 ReflectAboutUniform がグローバーの拡散演算子を適用することをペンと紙で確認することをお勧めします。 このことを確認するために、操作 Controlled Z(Most(inputQubits),Tail(inputQubits)) は、すべての量子ビットが $\ket{1}$ 状態である場合にのみ、id とは異なる効果を持つことに注意してください。

使用されている各操作と関数を確認するには、API のドキュメントを参照してください:

この操作は、一様の重ね合わせ状態に関するベクター空間内の反射として幾何学的に解釈される可能性があるため、ReflectAboutUniform と呼ばれます。

イテレーション数

グローバーの検索には、有効な出力を測定する確率が最も高いイテレーションの最適数があります。 問題に割り当て可能な変数が $N=2^n$ 個あり、そのうちの $M$ 個が問題の解である場合、最適なイテレーション数は次のようになります:

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

その回数を超えてイテレーションを続けると、その確率は減少し始め、イテレーション $2 N_{\text{optimal}}$ で成功の確率はほぼゼロになります。 その後、確率は再び大きくなり、$3 N_{\text{optimal}}$ などとなります。

実際のアプリケーションでは、通常、問題を解くまでは、問題にいくつの解があるかわかりません。 この問題に対処する効率的な方法は、2 の累乗 (すなわち、$1、2、4、8、16、...、2^n$) の累乗を徐々に増加させることで、$M$ のソリューション数を "推測" することです。 これらの推測の 1 つは、$\sqrt{\frac{N}{M}}$ の平均イテレーション回数で、アルゴリズムによってソリューションが十分に検出されます。

グローバーの操作の完了

これで、グローバーの検索アルゴリズムの Q# 操作を記述する準備ができました。 次の 3 つの入力があります:

  • すべての Zero 状態で初期化する必要がある量子ビット配列 register : Qubit[]。 このレジスタにより、一時的ソリューションが検索の問題にエンコードされます。 操作の後、測定されます。
  • グローバーのタスクの oracle フェーズを表す操作 phaseOracle : (Qubit[]) => Unit is Adj。 この操作では、汎用量子ビット レジスタに対して、Unitary 変換を適用します。
  • アルゴリズムのイテレーション処理を表す整数 iterations : Int
operation RunGroversSearch(register : Qubit[], phaseOracle : (Qubit[]) => Unit is Adj, iterations : Int) : Unit {
    // Prepare register into uniform superposition.
    ApplyToEach(H, register);
    // Start Grover's loop.
    for _ in 1 .. iterations {
        // Apply phase oracle for the task.
        phaseOracle(register);
        // Apply Grover's diffusion operator.
        ReflectAboutUniform(register);
    }
}

このコードは汎用的なものであり、検索の問題を解決するために使用できます。 探索コードへのパラメーターとして、解決したい問題インスタンスの知識に依存する唯一の操作である量子オラクルを渡します。

oracle の実装

グローバーのアルゴリズムが高速となる主要な特徴の 1 つは、個々の入力だけでなく、入力の重ね合わせに対しても計算を実行できる量子コンピューターです。 量子操作のみを使用して、検索問題のインスタンスを記述する関数 $f (x) $ を計算する必要があります。 これにより、重ね合わせの入力に対して計算を行うことができます。

残念ながら、従来の関数を量子操作に変換する自動的な方法はありません。 これは、コンピューター サイエンスの 元に戻すコンピューティング と呼ばれる研究のオープンなフィールドです。

ただし、関数 $f (x) $ を quantum oracle に変換する際に役立つガイドラインがいくつかあります:

  1. 古典的関数を、簡単に実装できる小さな構成要素に分割します。 たとえば、関数 $f(x)$ を一連の算術演算またはブール型のロジックゲートに分解することができます。
  2. 中間操作を実装するには、Q# ライブラリの上位レベルの構成要素を使用します。 たとえば、関数を単純な算術演算の組み合わせに分解した場合、数値ライブラリを使用して中間操作を実装できます。

次の等価テーブルは、Q# でブール関数を実装するときに役立つ場合があります。

従来のロジック ゲート Q#操作
$NOT$ X
$XOR$ CNOT
$AND$ 補助量子ビットを持つ CCNOT

例: 数値が除数であるかどうかを確認する量子操作

重要

このチュートリアルでは、グローバーのアルゴリズムの検索アルゴリズムを教訓的な例として使用して数値を計算し、単純な数学問題をグローバーのタスクに変換する方法を示します。 ただし、グローバーのアルゴリズムは、整数の因子分解問題を解決する効率的なアルゴリズムではありません。 従来のアルゴリズムよりも速く、整数の因子分解問題を解決する量子アルゴリズムを調べるには、ショアのアルゴリズム のサンプル を確認してください。

例として、関数 $f_M(x)=1[r]$ を使用して、Q# の量子操作としてファクタリング問題を表現する方法を見てみましょう。

従来は、$M/x$ の残りの部分を計算し、0 に等しいかどうかを確認します。 その場合は、プログラムが 1 を出力します。そうでない場合は、プログラムが 0 を出力します。 次を行う必要があります:

  • 除算の剰余を計算します。
  • 剰余が 0 の場合は、1 であるために制御された操作を出力ビットに適用します。

そのため、量子操作を使用して 2 つの数値の除算を計算する必要があります。 幸いにも、除算を実装する回線をゼロから作成する必要はありません。代わりに、数値ライブラリから DivideI 操作を使用できます。

DivideI の説明を見ると、3 つの量子ビット レジスタが必要であることがわかります。$n$ ビット被除数 xs、$n$ ビット除数 ys、および状態 Zero で初期化する必要がある $n $ ビット result です。 操作は Adj + Ctl であるため、この操作を活用して、within-apply ステートメント内で使用できます。 また、説明では、入力レジスタの被除数 xs が剰余に置き換えられていることが示されます。 これは、操作の結果ではなく、剰余部分のみに関心があるため、完璧です。

その後、次の処理を実行する量子操作を作成できます:

  1. 次の 3 つの入力を受け取ります:
    • 被除数、number : Int。 これは $M$ in $f_M(x)$ です。
    • 除数をエンコードする量子ビット配列、divisorRegister : Qubit[]。 これは、重ね合わせ状態にある可能性のある $f_M(x)$ の $x$ です。
    • $f_M(x)$ の出力が $1$ の場合に反転するターゲット量子ビット target : Qubit
  2. 元に戻す量子操作だけを使用して $M/x$ を計算し、剰余がゼロの場合にのみ target の状態を反転させます。
  3. target を反転する以外のすべての操作を元に戻します。これにより、使用された補助量子ビットがゼロ状態に戻り、測定などの取り消し不可能な操作を導入する必要がなくなります。 この手順は、プロセス中に結び付きと重ね合わせを維持するために重要です。

この量子操作を実装するコードは次のとおりです:

operation MarkDivisor (
    dividend : Int,
    divisorRegister : Qubit[],
    target : Qubit
) : Unit is Adj + Ctl {
    // Calculate the bit-size of the dividend.
    let size = BitSizeI(dividend);
    // Allocate two new qubit registers for the dividend and the result.
    use dividendQubits = Qubit[size];
    use resultQubits = Qubit[size];
    // Create new LittleEndian instances from the registers to use DivideI
    let xs = LittleEndian(dividendQubits);
    let ys = LittleEndian(divisorRegister);
    let result = LittleEndian(resultQubits);

    // Start a within-apply statement to perform the operation.
    within {
        // Encode the dividend in the register.
        ApplyXorInPlace(dividend, xs);
        // Apply the division operation.
        DivideI(xs, ys, result);
        // Flip all the qubits from the remainder.
        ApplyToEachA(X, xs!);
    } apply {
        // Apply a controlled NOT over the flipped remainder.
        Controlled X(xs!, target);
        // The target flips if and only if the remainder is 0.
    }
}

注意

ステップ 3 を実現するために、within-apply のステートメントを利用します。 または、target の制御された反転後に、各操作の随伴行列を within ブロック内に明示的に記述することもできます。 within-apply ステートメントは、コードを短く、読みやすくするためのものです。 Q# の主な目的の1つは、量子プログラムを簡単に記述して読み取れるようにすることです。

操作をフェーズ oracle に変換する

この操作 MarkDivisor は、有効な項目を、もつれさせる補助量子ビット (target) でマークするため、marking oracle として知られています。 ただし、グローバーのアルゴリズムには、ソリューション項目に対して $-1$ の条件付きフェーズ シフトを適用する、phase oracle が必要です。 しかし、この操作は無駄で記述されていません。 では、oracle の 1 つの型から Q# の別の型に簡単に切り替えることができます。

次の操作を実行すると、phase oracle として marking oracle を適用できます:

operation ApplyMarkingOracleAsPhaseOracle(
    markingOracle : (Qubit[], Qubit) => Unit is Adj,
    register : Qubit[]
) : Unit is Adj {
    use target = Qubit();
    within {
        X(target);
        H(target);
    } apply {
        markingOracle(register, target);
    }
}

この有名な変換は phase kickback と呼ばれ、多くの量子コンピューティング アルゴリズムで広く使用されています。 この手法の詳細については、この Microsoft Learn モジュールを参照してください。

これで、グローバーの検索アルゴリズムの特定のインスタンスを実装するためのすべての要素が用意され、ファクタリングの問題を解決できます。

以下のプログラムを使用して、21 の要素を見つけてみましょう。 コードを簡単にするために、有効な項目の数 $M$ が判明していると仮定します。 この場合は、3 と 7 の 2 つの要素があり、それ自体 1 と 21 であるため、$M=4$ になります。

namespace GroversTutorial {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Preparation;

    @EntryPoint()
    operation FactorizeWithGrovers(number : Int) : Unit {

        // Define the oracle that for the factoring problem.
        let markingOracle = MarkDivisor(number, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
        // Bit-size of the number to factorize.
        let size = BitSizeI(number);
        // Estimate of the number of solutions.
        let nSolutions = 4;
        // The number of iterations can be computed using the formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

        // Initialize the register to run the algorithm
        use (register, output) = (Qubit[size], Qubit());
        mutable isCorrect = false;
        mutable answer = 0;
        // Use a Repeat-Until-Succeed loop to iterate until the solution is valid.
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
            // Check that if the result is a solution with the oracle.
            markingOracle(register, output);
            if MResetZ(output) == One and answer != 1 and answer != number {
                set isCorrect = true;
            }
            ResetAll(register);
        } until isCorrect;

        // Print out the answer.
        Message($"The number {answer} is a factor of {number}.");

    }

    operation MarkDivisor (
        dividend : Int,
        divisorRegister : Qubit[],
        target : Qubit
    ) : Unit is Adj+Ctl {
        let size = BitSizeI(dividend);
        use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
        let xs = LittleEndian(dividendQubits);
        let ys = LittleEndian(divisorRegister);
        let result = LittleEndian(resultQubits);
        within{
            ApplyXorInPlace(dividend, xs);
            DivideI(xs, ys, result);
            ApplyToEachA(X, xs!);
        }
        apply{
            Controlled X(xs!, target);
        }
    }

    operation PrepareUniformSuperpositionOverDigits(digitReg : Qubit[]) : Unit is Adj + Ctl {
        PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
    }

    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : (Qubit[], Qubit) => Unit is Adj,
        register : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            X(target);
            H(target);
        } apply {
            markingOracle(register, target);
        }
    }

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            phaseOracle(register);
            ReflectAboutUniform(register);
        }
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }
}

重要

数値ライブラリ (または標準ライブラリ以外のライブラリ) からの操作を使用できるようにするには、対応するパッケージがプロジェクトに追加されていることを確認する必要があります。 VS Code でこの操作を簡単に行うには、プロジェクト内からターミナルを開き、次のコマンドを実行します: dotnet add package Microsoft.Quantum.Numerics

Visual Studio または Visual Studio Code での実行

上記のプログラムは、プロジェクトの構成とコマンドライン オプションに応じて、シミュレーターまたはリソース推定機能で @EntryPoint() 属性でマークされた操作または関数を実行します。

Visual Studio では、Ctrl キーを押しながら F5 キーを押すだけでスクリプトを実行します。

VS Code では、ターミナルで次のように入力して、Program.qs の初回のビルドを行います。

dotnet build

以降の実行では、再度ビルドする必要はありません。 これを実行するには、次のコマンドを入力して、Enter キーを押します。

dotnet run --no-build --number 21

Enter キーを押すと、ターミナルに次のメッセージが表示されます:

The number 7 is a factor of 21.

追加: Python で統計を確認してください

アルゴリズムが正しく動作しているかどうかを確認するには、どうすればよいでしょうか? たとえば、上記のコードでグローバーの検索をランダムな数値ジェネレーターに置き換えた場合、$N$ 回まで試行した後に、要素も検出されます。

プログラムが動作しているかどうかを確認するための小さな Python スクリプトを作成してみましょう。

ヒント

Python での Q# アプリケーションの実行について支援が必要な場合は、Q# プログラムを実行する方法についてのガイドと Python のインストール ガイドを参照してください。

最初に、メイン操作を変更して repeat-until-success ループを除き、代わりに、グローバーの検索を実行した後に最初の測定結果を出力します:

@EntryPoint()
operation FactorizeWithGrovers2(number : Int) : Int {

    let markingOracle = MarkDivisor(number, _, _);
    let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
    let size = BitSizeI(number);
    let nSolutions = 4;
    let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

    use register = Qubit[size] {
        RunGroversSearch(register, phaseOracle, nIterations);
        let res = MultiM(register);
        return ResultArrayAsInt(res);
        // Check whether the result is correct.
    }

}

出力の種類を Unit から Int に変更したことに注意してください。 これは Python プログラムに役立ちます。

Python プログラムは非常に単純です。 操作 FactorizeWithGrovers2 を何回か呼び出すだけで、結果がヒストグラムにプロットされます。

コードは次のとおりです:

import qsharp
qsharp.packages.add("Microsoft.Quantum.Numerics")
qsharp.reload()
from GroversTutorial import FactorizeWithGrovers2
import matplotlib.pyplot as plt
import numpy as np

def main():

    # Instantiate variables
    frequency =  {}
    N_Experiments = 1000
    results = []
    number = 21

    # Run N_Experiments times the Q# operation.
    for i in range(N_Experiments):
        print(f'Experiment: {i} of {N_Experiments}')
        results.append(FactorizeWithGrovers2.simulate(number = number))

    # Store the results in a dictionary
    for i in results:
        if i in frequency:c
            frequency[i]=frequency[i]+1
        else:
            frequency[i]=1

    # Sort and print the results
    frequency = dict(reversed(sorted(frequency.items(), key=lambda item: item[1])))
    print('Output,  Frequency' )
    for k, v in frequency.items():
        print(f'{k:<8} {v}')

    # Plot an histogram with the results
    plt.bar(frequency.keys(), frequency.values())
    plt.xlabel("Output")
    plt.ylabel("Frequency of the outputs")
    plt.title("Outputs for Grover's factoring. N=21, 1000 iterations")
    plt.xticks(np.arange(1, 33, 2.0))
    plt.show()

if __name__ == "__main__":
    main()

注意

Python プログラムの行 from GroversTutorial import FactorizeWithGrovers2 は、前に記述した Q# コードをインポートします。 Python モジュール名 (GroversTutorial) は、インポートする操作の名前空間と同じである必要があることに注意してください (この場合は FactorizeWithGrovers2)。

プログラムによって次のヒストグラムが生成されます:

グローバーのアルゴリズムが数回実行された結果を含むヒストグラム

ヒストグラムでわかるように、このアルゴリズムはソリューションを検索の問題 (1、3、7、21) に出力し、非ソリューションよりもはるかに高い確率で出力します。 グローバーのアルゴリズムは、検索の問題に対する解決策であるインデックスに対して意図的にバイアスされる量子ランダム ジェネレーターと考えることができます。

次のステップ

これで、グローバーのアルゴリズムを実装する方法がわかりました。次は、数学的な問題を検索タスクに変換し、Q# とグローバーのアルゴリズムを使用して解決します。