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

[アーティクル]
10/29/2024

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

このチュートリアルでは、次の作業を行いました。

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

ヒント

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

前提条件

Azure Quantum の Copilot でコードサンプルを実行するには:
- Microsoft (MSA) メールアカウント。
Visual Studio Code でコードサンプルを開発して実行するには:
- 最新バージョンの Visual Studio Code または VS Code on the Web を開きます。
- 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}}} $ 回に次の操作を適用します。
1. oracle $O_f$ フェーズでは、ソリューション項目に対して $-$1 の条件付きフェーズシフトが適用されます。
2. レジスタの各量子ビットに $H$ を適用します。
3. $\ket{0}$ を除くすべての計算基準の状態に、$-1$ の条件付きフェーズシフトを $-O_0$ を適用します。
4. レジスタの各量子ビットに $H$ を適用します。
確率が非常に高いソリューションである項目のインデックスを取得するには、レジスタを測定します。
項目をチェックして、有効なソリューションであるかどうかを確認します。それ以外の場合は、再度開始します。

グローバーのアルゴリズムのコードを Q#

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

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

まず、検索で検索しようとしている入力を定義します。これを行うには、グローバーのアルゴリズムからステップ 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# すことができます。最後に、レジスタを測定し、結果を返します。

このコードでは、次の 3 つのヘルパー操作をReflectAboutUniformReflectAboutAllOnes使用します。 PrepareUniform

すべてのゼロの状態のレジスタを指定すると 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 に変換します。次に、すべて 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
Visual Studio Code

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

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

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

import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;

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 量子ビットで量子コンピューターをシミュレートします。

[In-Memory Simulator] (メモリ内シミュレーター) ドロップダウンを選んで、Quantinuum H-Series Emulator を選びます。
ショットの数を選んで (現在は 20 回に制限されています)、[Run] (実行) を選びます。

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

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


import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;


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] をQ#検索し、[Azure Quantum QIR target プロファイルを設定する] を選択して、[無制限] を選択Q#します。
プログラムを実行するには、操作の上Mainにあるコマンドの一覧から [実行] を選択するか、Ctrl キーを押しながら F5 キーを押します。既定では、コンパイラは既定の Main シミュレーターで操作または関数を実行します。
出力がターミナルのデバッグコンソールに表示されます。

Note

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

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

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

次の方法で共有

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

前提条件

問題を定義する

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

グローバーのアルゴリズムのコードを Q#

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

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

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

最後のコードを実行する

プログラムを実行する

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

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

フィードバック

その他のリソース

次の方法で共有

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

前提条件

問題を定義する

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

グローバーのアルゴリズムのコードを Q#

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

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

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

最後のコードを実行する

プログラムを実行する

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

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

関連するコンテンツ

フィードバック

その他のリソース

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

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