チュートリアル: Q# でグローバーの探索アルゴリズムを実装する
このチュートリアルでは、検索ベースの問題を解決するために、 Q# にグローバーのアルゴリズムを実装します。 グローバーのアルゴリズムの背後にある理論の詳細については、グローバーのアルゴリズムに関するページを参照してください。
このチュートリアルでは、次の作業を行いました。
- 検索の問題に対するグローバーのアルゴリズムを定義する
- でグローバーのアルゴリズムを実装する Q#
ヒント
量子コンピューティングの取り組みを加速させる場合は、Azure Quantum Web サイトのユニークな機能である Azure Quantum を使用した Codeをご覧ください。 ここでは、組み込みの Q# サンプルまたは独自の Q# プログラムを実行し、プロンプトから新しい Q# コードを生成し、 VS Code for the Web でコードを開いて実行し ワンクリックで Copilot に量子コンピューティングに関する質問を行うことができます。
前提条件
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}}} $ 回に次の操作を適用します。
- oracle $O_f$ フェーズでは、ソリューション項目に対して $-$1 の条件付きフェーズ シフトが適用されます。
- レジスタの各量子ビットに $H$ を適用します。
- $\ket{0}$ を除くすべての計算基準の状態に、$-1$ の条件付きフェーズ シフトを $-O_0$ を適用します。
- レジスタの各量子ビットに $H$ を適用します。
- 確率が非常に高いソリューションである項目のインデックスを取得するには、レジスタを測定します。
- 項目をチェックして、有効なソリューションであるかどうかを確認します。 それ以外の場合は、再度開始します。
グローバーのアルゴリズムのコードを Q#
ここでは、Q# にアルゴリズムを実装する方法について説明します。 グローバーのアルゴリズムを実装する際に考慮すべき点はほとんどありません。 マークされた状態の内容、その状態を反映する方法、およびアルゴリズムを実行するイテレーションの数を定義する必要があります。 グローバーのタスクの関数を実装する Oracle も定義する必要があります。
マークされた状態を定義する
まず、検索で検索しようとしている入力を定義します。 これを行うには、Grover のアルゴリズムからステップ b、c および d を適用する操作を記述。
これらの手順は、 Grover の S 拡散演算子 $-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$ 量子ビットのレジスタを初期化し、レジスタを均一な重ね合わせに準備した後、指定された反復回数に対してグローバーのアルゴリズムを適用します。 検索自体は、マークされた状態と開始状態を繰り返し反映して構成され、 Q# for ループとして書き出すことができます。 最後に、レジスタを測定し、結果を返します。
このコードでは、 PrepareUniform
、 ReflectAboutUniform
、 ReflectAboutAllOnes
の 3 つのヘルパー操作を使用します。
レジスタが全ゼロ状態の場合、 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 を使用して Q# コードを無料でテストできます。必要なのは、Microsoft (MSA) メール アカウントのみです。 Azure Quantum の Copilot の詳細については、「 Explore 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 でプログラムを開くことができます。
インメモリ シミュレーターを使用してプログラムを実行する
- メモリ シミュレーターを選択します。
- 実行するショットの数を選択し、 実行をクリックします。
- 結果はヒストグラムと Results フィールドに表示されます。
- [ Explain code をクリックして、コードを説明するように Copilot に求めるメッセージを表示します。
Quantinuum H シリーズ エミュレーターを使用してプログラムを実行する
また、無料の Quantinuum H シリーズ エミュレーターにプログラムを送信することもできます。 エミュレーターは、20 量子ビットで量子コンピューターをシミュレートします。
- [In-Memory Simulator] (メモリ内シミュレーター) ドロップダウンを選んで、Quantinuum H-Series Emulator を選びます。
- ショットの数を選んで (現在は 20 回に制限されています)、[Run] (実行) を選びます。
関連するコンテンツ
Q# のその他のチュートリアルを確認します。
- 量子エンタングルメント は、量子ビットを操作および測定し、重ね合わせとエンタングルメントの効果を示す Q# プログラムを記述する方法を示します。
- 量子乱数ジェネレーター は、重ね合わせで量子ビットから乱数を生成する Q# プログラムを記述する方法を示しています。
- 量子フーリエ変換 では、特定の量子ビットに直接対処する Q# プログラムを記述する方法について説明します。
- Quantum Katasは、量子コンピューティングとQ#プログラミングの要素を同時に教えることを目的とした、自習型のチュートリアルとプログラミング演習です。