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

[アーティクル]
01/13/2024

注意

Microsoft Quantum Development Kit (クラシック QDK) は、2024 年 6 月 30 日以降はサポートされなくなります。既存の QDK 開発者の場合は、量子ソリューションの開発を続けるために、新しい Azure Quantum Development Kit (モダン QDK) に移行することをお勧めします。詳細については、「コードを Q# モダン QDK に移行する」を参照してください。

このチュートリアルでは、でグローバーのアルゴリズム Q# を実装して、検索ベースの問題を解決します。グローバーのアルゴリズムの背後にある理論の詳細については、グローバーのアルゴリズムに関するページを参照してください。

このチュートリアルでは、次のことについて説明します。

検索の問題に対するグローバーのアルゴリズムを定義します。
でグローバーのアルゴリズムを Q#実装します。

ヒント

量子コンピューティングの取り組みを加速する場合は、Azure Quantum Web サイトのユニークな機能である Azure Quantum を使用してコードをチェックします。ここでは、組み込みのサンプルまたは独自Q#のQ#プログラムを実行し、プロンプトから新しいQ#コードを生成し、ワンクリックで VS Code for the Web でコードを開いて実行し、Copilot に量子コンピューティングについて質問することができます。

前提条件

Azure Quantum の Copilot でコードサンプルを実行するには:
- Microsoft (MSA) メールアカウント。
Visual Studio Code でコードサンプルを開発して実行するには、
- 最新バージョンの Visual Studio Code または Web 上で VS Code を開きます。
- Azure Quantum Development Kit 拡張機能の最新バージョン。インストールの詳細については、「 VS Code へのモダン QDK のインストール」を参照してください。

問題の定義

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

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

したがって、検索の問題を次のように作成できます。従来の関数 $f(x):\{0,1\}^n \rightarrow\{0,1\}$ です。ここで、$n$ は検索空間のビットサイズであり、$f(x_0)=1$ の入力$x_0$ を見つけます。

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

問題を グローバーのタスクの形式に変換します。たとえば、グローバーのアルゴリズムを使用して $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$ の因数になり、問題をグローバーのタスクに変換しました。
グローバーのタスクの関数を量子オラクルとして実装します。グローバーのアルゴリズムを実装するには、グローバーのタスクの関数 $f(x)$ を量子オラクルとして実装する必要があります。
オラクルでグローバーのアルゴリズムを使用して、タスクを解決します。量子オラクルがある場合は、グローバーのアルゴリズム実装にプラグインして、問題を解決し、出力を解釈することができます。

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

探索問題に $N=2^n$ 個の対象項目があり、各項目に $0$ から $N-1$ までの整数を割り当てることで、それらにインデックスを付けるとします。アルゴリズムの手順:

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

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

ここでは、Q# にアルゴリズムを実装する方法について説明します。グローバーのアルゴリズムを実装する際に考慮すべき点はほとんどありません。マークされた状態の内容、その状態を反映する方法、アルゴリズムを実行するイテレーションの数を定義する必要があります。また、グローバーのタスクの関数を実装するオラクルを定義する必要もあります。

マークされた状態を定義する

まず、検索で検索しようとしている入力を定義します。これを行うには、グローバーのアルゴリズムからステップ b、c、d を適用する操作を記述します。

これらの手順は、グロー バーの拡散演算子 $-H^{\otimes n} O_0 H^{\otimes n}$ とも呼ばれます。

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

操作は ReflectAboutMarked 、0 と 1 を交互に指定した基準状態を反映します。これを行うために、グローバーの拡散演算子を入力量子ビットに適用します。この操作では、補助量子ビットを使用します。これは、 outputQubit$X$ ゲートと $H$ ゲートを適用することで、状態 $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ で初期化されます。次に、この操作によって、レジスタ内の他のすべての量子ビットに$X$ ゲートが適用され、量子ビットの状態が反転されます。最後に、制御された$X$ ゲートを補助量子ビットと入力量子ビットに適用します。この操作は、すべての入力量子ビットが状態 $\ket{1}$ (マークされた状態) の場合にのみ、補助量子ビットを反転します。

最適なイテレーションの数を定義する

グローバーの検索には、有効な出力を測定する確率が最も高いイテレーションの最適数があります。問題に割り当て可能な変数が $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# の関数は、レジスタ内の特定の数の量子ビットに対する最適な反復回数を計算します。

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

関数は CalculateOptimalIterations 、上記の数式を使用して反復回数を計算し、最も近い整数に丸めます。

グローバーの操作を定義する

Q#グローバーの検索アルゴリズムの操作には、次の 3 つの入力があります。

量子ビットレジスタ内の量子ビット nQubits : Intの数。このレジスタにより、一時的ソリューションが検索の問題にエンコードされます。操作後、測定されます。
最適なイテレーションの数 ( iterations : Int)。
グローバーのタスクのフェーズオラクルを表す操作 phaseOracle : Qubit[] => Unit) : Result[]。この操作では、汎用量子ビットレジスタに対して、Unitary 変換を適用します。

operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

この操作は GroverSearch 、状態 $\ket{0}$ の$n$ 量子ビットのレジスタを初期化し、レジスタを均一な重ね合わせに準備し、指定された反復回数に対してグローバーのアルゴリズムを適用します。検索自体は、マークされた状態と開始状態を繰り返し反映して構成されます。これは for ループとして書き出 Q# すことができます。最後に、レジスタを測定し、結果を返します。

コードでは、、ReflectAboutUniform、およびの 3 つのヘルパー操作PrepareUniformを使用しますReflectAboutAllOnes。

レジスタが全ゼロ状態の場合、 PrepareUniform 演算はすべての基準状態に対して均一な重ね合わせを準備します。

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

''ReflectAboutAllOnes' 操作は、オールインワンの状態を反映します。

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

この操作 ReflectAboutUniform は、均一な重ね合わせ状態を反映します。まず、均一な重ね合わせを全ゼロに変換します。次に、すべて 0 の状態を all-one に変換します。最後に、すべての状態が反映されます。この操作は、一様の重ね合わせ状態に関するベクター空間内の反射として幾何学的に解釈される可能性があるため、ReflectAboutUniform と呼ばれます。

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

最後のコードを実行する

これで、グローバーの検索アルゴリズムの特定のインスタンスを実装するためのすべての要素が用意され、ファクタリングの問題を解決できます。完了するには、 Main 量子ビット数と反復回数を指定して問題を設定します。

operation Main() : Result[] {
let nQubits = 5;
let iterations = CalculateOptimalIterations(nQubits);
Message($"Number of iterations: {iterations}");

// Use Grover's algorithm to find a particular marked state.
let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
return results;
}

コードは、Azure Quantum の Copilot で無料でテスト Q# できます。必要なのは Microsoft (MSA) のメールアカウントです。 Azure Quantum の Copilot の詳細については、「Azure Quantum の探索」を参照してください。

ブラウザーで Azure Quantum で Copilot を開きます。

次のコードをコピーしてコードエディターに貼り付けます。

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
    }

    operation GroverSearch(
        nQubits : Int,
        iterations : Int,
        phaseOracle : Qubit[] => Unit) : Result[] {

        use qubits = Qubit[nQubits];

        PrepareUniform(qubits);

        for _ in 1..iterations {
            phaseOracle(qubits);
            ReflectAboutUniform(qubits);
        }

        // Measure and return the answer.
        return MResetEachZ(qubits);
    }

    function CalculateOptimalIterations(nQubits : Int) : Int {
        if nQubits > 63 {
            fail "This sample supports at most 63 qubits.";
        }
        let nItems = 1 <<< nQubits; // 2^nQubits
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
        let iterations = Round(0.25 * PI() / angle - 0.5);
        return iterations;
    }

    operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
        Message("Reflecting about marked state...");
        use outputQubit = Qubit();
        within {
            // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
            // toggling it results in a (-1) phase.
            X(outputQubit);
            H(outputQubit);
            // Flip the outputQubit for marked states.
            // Here, we get the state with alternating 0s and 1s by using the X
            // operation on every other qubit.
            for q in inputQubits[...2...] {
                X(q);
            }
        } apply {
            Controlled X(inputQubits, outputQubit);
        }
    }

    operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
        for q in inputQubits {
            H(q);
        }
    }

    operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            // Transform the uniform superposition to all-zero.
            Adjoint PrepareUniform(inputQubits);
            // Transform the all-zero state to all-ones
            for q in inputQubits {
                X(q);
            }
        } apply {
            // Now that we've transformed the uniform superposition to the
            // all-ones state, reflect about the all-ones state, then let the
            // within/apply block transform us back.
            ReflectAboutAllOnes(inputQubits);
        }
    }
}

ヒント

Azure Quantum の Copilot から、コードエディターの右上隅にある [VS Code ロゴ] ボタンをクリックして、VS Code for the Web でプログラムを開くことができます。

メモリ内シミュレーターを使用してプログラムを実行する

[ メモリ内シミュレーター] を選択します。
実行するショットの数を選択し、[ 実行] をクリックします。
結果はヒストグラムと [結果 ] フィールドに表示されます。
[ コードの説明 ] をクリックして、コードを説明するように Copilot に求めるメッセージを表示します。

Quantinuum H シリーズエミュレーターを使用してプログラムを実行する

無料の Quantinuum H シリーズエミュレーターにプログラムを送信することもできます。エミュレーターは、20 量子ビットの量子コンピューターをシミュレートします。

[ メモリ内シミュレーター ] ドロップダウンを選択し、[ Quantinuum H シリーズエミュレーター] を選択します。
ショットの数 (現在は 20 個に制限) を選択し、[実行] を選択します。

Visual Studio Code を開き、[ ファイル > ] [新しいテキストファイル ] の順に選択して、新しいファイルを作成します。
このファイルを GroversAlgorithm.qs として保存します。このファイルには、プログラムのコードが Q# 含まれます。

ファイルに次のコードを GroversAlgorithm.qs コピーします。

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
    }

    operation GroverSearch(
        nQubits : Int,
        iterations : Int,
        phaseOracle : Qubit[] => Unit) : Result[] {

        use qubits = Qubit[nQubits];

        PrepareUniform(qubits);

        for _ in 1..iterations {
            phaseOracle(qubits);
            ReflectAboutUniform(qubits);
        }

        // Measure and return the answer.
        return MResetEachZ(qubits);
    }

    function CalculateOptimalIterations(nQubits : Int) : Int {
        if nQubits > 63 {
            fail "This sample supports at most 63 qubits.";
        }
        let nItems = 1 <<< nQubits; // 2^nQubits
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
        let iterations = Round(0.25 * PI() / angle - 0.5);
        return iterations;
    }

    operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
        Message("Reflecting about marked state...");
        use outputQubit = Qubit();
        within {
            // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
            // toggling it results in a (-1) phase.
            X(outputQubit);
            H(outputQubit);
            // Flip the outputQubit for marked states.
            // Here, we get the state with alternating 0s and 1s by using the X
            // operation on every other qubit.
            for q in inputQubits[...2...] {
                X(q);
            }
        } apply {
            Controlled X(inputQubits, outputQubit);
        }
    }

    operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
        for q in inputQubits {
            H(q);
        }
    }

    operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            // Transform the uniform superposition to all-zero.
            Adjoint PrepareUniform(inputQubits);
            // Transform the all-zero state to all-ones
            for q in inputQubits {
                X(q);
            }
        } apply {
            // Now that we've transformed the uniform superposition to the
            // all-ones state, reflect about the all-ones state, then let the
            // within/apply block transform us back.
            ReflectAboutAllOnes(inputQubits);
        }
    }
}

プログラムを実行する前に、プロファイルを [無制限]target に設定する必要があります。 [表示 ] -> [コマンドパレット] を選択し、[QIR] を検索し、[: Azure Quantum QIR target プロファイルを設定する] を選択Q#し、[: unrestricted] を選択Q#します。
プログラムを実行するには、右上の再生アイコンドロップダウンから [ファイルの実行Q#] を選択するか、Ctrl + F5 キーを押します。プログラムは、既定のシミュレーターで属性で @EntryPoint() マークされた操作または関数を実行します。
出力がデバッグコンソールに表示されます。

注意

プロファイルが target[無制限] に設定されていない場合は、プログラムの実行時にエラーが発生します。

次のステップ

Q# のその他のチュートリアルを確認します。

量子エンタングルメントは、量子ビットを操作および測定するプログラムを記述 Q# する方法を示し、重ね合わせとエンタングルメントの影響を示します。
量子乱数ジェネレーターは、重ね合わせで量子ビットから乱数を生成するプログラムを記述 Q# する方法を示します。
Quantum Fourier Transform では、特定の量子ビットに直接対処するプログラムを Q# 記述する方法について説明します。
Quantum Katas は、量子コンピューティングとプログラミングの要素を同時に教えることを目的とした、マイペースのチュートリアルとQ#プログラミング演習です。

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

前提条件

問題の定義

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

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

マークされた状態を定義する

最適なイテレーションの数を定義する

グローバーの操作を定義する

最後のコードを実行する

プログラムの実行

メモリ内シミュレーターを使用してプログラムを実行する

Quantinuum H シリーズエミュレーターを使用してプログラムを実行する

次のステップ

フィードバック

フィードバック

その他のリソース

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

前提条件

問題の定義

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

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

マークされた状態を定義する

最適なイテレーションの数を定義する

グローバーの操作を定義する

最後のコードを実行する

プログラムの実行

メモリ内シミュレーターを使用してプログラムを実行する

Quantinuum H シリーズ エミュレーターを使用してプログラムを実行する

次のステップ

フィードバック

フィードバック

その他のリソース

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

Quantinuum H シリーズエミュレーターを使用してプログラムを実行する