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

このQiskit教室モジュールの場合、学生は次のパッケージがインストールされた動作するPython環境を持っている必要があります:

• qiskit v2.1.0以降
• qiskit-ibm-runtime v0.40.1以降
• qiskit-aer v0.17.0以降
• qiskit.visualization
• numpy
• pylatexenc

上記のパッケージをセットアップしてインストールするには、Qiskitのインストールガイドを参照してください。 実際の量子コンピュータでジョブを実行するには、学生はIBM Cloudアカウントの設定ガイドの手順に従って、IBM Quantum®でアカウントを設定する必要があります。

このモジュールはテストされ、12秒のQPU時間を使用しました。これは誠実な見積もりです。実際の使用量は異なる場合があります。

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

はじめに

グローバーのアルゴリズムは、構造化されていない検索問題に対処する基礎的な量子アルゴリズムです: $N$個のアイテムのセットと、任意のアイテムが探しているものであるかどうかをチェックする方法が与えられたとき、目的のアイテムをどれだけ速く見つけることができますか？古典的コンピューティングでは、データがソートされておらず、利用できる構造がない場合、最良のアプローチは各アイテムを1つずつチェックすることであり、クエリの複雑さは$O(N)$になります。平均して、ターゲットを見つける前に約半分のアイテムをチェックする必要があります。

1996年にLov Groverによって導入されたグローバーのアルゴリズムは、量子コンピュータがこの問題をはるかに効率的に解決できる方法を示し、マークされたアイテムを高い確率で見つけるために$O(\sqrt{N})$ステップしか必要としません。これは、古典的方法に対する二次的な高速化を表しており、大規模なデータセットにとって重要です。

アルゴリズムは次の文脈で動作します:

• 問題設定: $x$が欲しいアイテムである場合は1を返し、そうでない場合は0を返す関数$f(x)$があります。この関数は、$f(x)$をクエリすることによってのみデータについて学習できるため、しばしばオラクルまたはブラックボックスと呼ばれます。
• 量子の有用性: この問題の古典的アルゴリズムは平均して$N/2$回のクエリを必要としますが、グローバーのアルゴリズムは約$\pi\sqrt{N}/4$回のクエリで解を見つけることができ、大きな$N$に対してははるかに高速です。
• 動作の仕組み（高レベル）:
  • 量子コンピュータはまず、すべての可能なアイテムを一度に表すすべての可能な状態の重ね合わせを作成します。
  • 次に、正しい答えの確率を増幅し、他の確率を減少させる一連の量子演算（グローバー反復）を繰り返し適用します。
  • 十分な反復の後、量子状態を測定すると、高い確率で正しい答えが得られます。

これは、多くのニュアンスをスキップしたグローバーのアルゴリズムの非常に基本的な図です。より詳細な図については、この論文を参照してください。

グローバーのアルゴリズムについて注意すべきいくつかの点:

• 構造化されていない検索に最適です: $O(\sqrt{N})$回未満のクエリで問題を解決できる量子アルゴリズムはありません。
• 指数関数的ではなく二次的な高速化のみを提供します。他の量子アルゴリズム（たとえば、因数分解のためのショアのアルゴリズム）とは異なります。
• 暗号システムに対するブルートフォース攻撃を潜在的に高速化するなど、実用的な意味がありますが、高速化はそれ自体でほとんどの最新の暗号化を破るには十分ではありません。

基本的なコンピューティング概念とクエリモデルに精通している学部生にとって、グローバーのアルゴリズムは、量子コンピューティングが特定の問題に対して古典的アプローチをどのように上回ることができるかの明確な例を提供します。改善が「わずか」二次的である場合でも。また、より高度な量子アルゴリズムと量子コンピューティングのより広い可能性を理解するための入り口としても機能します。

振幅増幅は、汎用目的の量子アルゴリズム、またはサブルーチンであり、少数の古典的アルゴリズムに対して二次的な高速化を得るために使用できます。グローバーのアルゴリズムは、構造化されていない検索問題でこの高速化を最初に実証しました。グローバーの検索問題を定式化するには、1つ以上の計算基底状態を見つけたい状態としてマークするオラクル関数と、マークされた状態の振幅を増加させ、その結果残りの状態を抑制する増幅回路が必要です。

ここでは、グローバーオラクルを構築する方法を示し、Qiskit回路ライブラリのGroverOperatorを使用してグローバーの検索インスタンスを簡単にセットアップします。ランタイムSamplerプリミティブにより、グローバー回路のシームレスな実行が可能になります。

数学

バイナリ文字列を単一のバイナリ変数にマッピングする関数$f$が存在するとします。つまり

$$f: \Sigma^n \rightarrow \Sigma$$

$\Sigma^6$で定義された1つの例は

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

$\Sigma^{2n}$で定義された別の例は

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

$f(x)$が1にマッピングされる引数$x$に対応する量子状態を見つけるタスクがあります。言い換えれば、$f(x_1)=1$となるすべての$\{x_1\}\in \Sigma^n$を見つけます（または解がない場合は、それを報告します）。非解を$x_0$と呼びます。もちろん、量子状態を使用して量子コンピュータでこれを行うので、これらのバイナリ文字列を状態として表現することが有用です:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

量子状態（ディラック）表記法を使用すると、$N=2^n$個の可能な状態のセット内の1つ以上の特別な状態$\{|x_1\rangle\}$を探しています。ここで、$n$は量子ビットの数であり、非解は$\{|x_0\rangle\}$と表されます。

関数$f$は、オラクルによって提供されると考えることができます: クエリして状態$|x\rangle$への効果を決定できるブラックボックス。実際には、関数を知っていることが多いですが、実装が非常に複雑な場合があり、つまり$f$のクエリまたはアプリケーションの数を減らすことが重要である可能性があります。あるいは、ある人が別の人によって制御されているオラクルをクエリしているパラダイムを想像することができます。そのため、オラクル関数を知らず、特定の状態に対するそのアクションのみをクエリから知っています。

これは「構造化されていない検索問題」であり、検索を支援する$f$に関する特別なものは何もないという意味です。出力はソートされておらず、解がクラスターを形成することは知られていません。紙の電話帳を例えとして考えてください。この構造化されていない検索は、特定の__番号__を探してそれをスキャンするようなもので、アルファベット順の名前のリストを調べるようなものではありません。

単一の解が求められる場合、古典的には、これには$N$に対して線形なクエリ数が必要です。明らかに、最初の試行で解を見つけるかもしれませんし、最初の$N-1$回の推測で解を見つけられない場合があり、そのため$N^{th}$入力をクエリして解がまったくあるかどうかを確認する必要があります。関数には利用可能な構造がないため、平均して$N/2$回の推測が必要になります。グローバーのアルゴリズムは、$\sqrt{N}$のようにスケールする$f$のクエリまたは計算の数を必要とします。

グローバーのアルゴリズムの回路のスケッチ

グローバーのアルゴリズムの完全な数学的ウォークスルーは、たとえば、IBM Quantum LearningのJohn Watrousによるコース量子アルゴリズムの基礎にあります。簡潔な扱いは、このモジュールの最後の付録に提供されています。しかし今のところ、グローバーのアルゴリズムを実装する量子回路の全体的な構造のみをレビューします。

グローバーのアルゴリズムは、次の段階に分解できます:

• 初期重ね合わせの準備（すべての量子ビットへのアダマールゲートの適用）
• 位相反転でターゲット状態をマークする
• __すべての__量子ビットにアダマールゲートと位相反転が適用される「拡散」段階
• ターゲット状態を測定する確率を最大化するためのマーキングと拡散段階の反復の可能性
• 測定

多くの場合、マーキングゲート$Z_f$と、$H,$ $Z_{\text{OR}},$ $H$から構成される拡散層は、まとめて「グローバー演算子」と呼ばれます。この図では、グローバー演算子の1回の反復のみが示されています。

アダマールゲート$H$はよく知られており、量子コンピューティング全体で広く使用されています。アダマールゲートは重ね合わせ状態を作成します。具体的には次のように定義されます

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

他の状態に対する演算は線形性を通じて定義されます。 特に、アダマールゲートの層により、すべての量子ビットが$|0\rangle$にある初期状態（$|0\rangle^{\otimes n}$と表される）から、各量子ビットが$|0\rangle$または$|1\rangle$のいずれかで測定される確率を持つ状態に移行できます。これにより、古典的コンピューティングとは異なる方法で、すべての可能な状態の空間を調査できます。

アダマールゲートの重要な系特性は、2回目に作用すると、そのような重ね合わせ状態を元に戻すことができることです:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

これはすぐに重要になります。

理解度チェック

以下の質問を読み、答えについて考えてから、三角形をクリックして解決策を明らかにしてください。

アダマールゲートの定義から始めて、アダマールゲートの2回目の適用が上記の主張どおりにそのような重ね合わせを元に戻すことを実証してください。

答え:

Xを$|+\rangle$状態に適用すると、値+1が得られ、状態$|-\rangle$に適用すると-1が得られます。したがって、50-50の分布がある場合、期待値0が得られます。

$Z_\text{OR}$ゲートはあまり一般的ではなく、次のように定義されます

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

最後に、$Z_f$ゲートは次のように定義されます

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

これの効果は、$Z_f$が$f(x) = 1$であるターゲット状態の符号を反転し、他の状態を影響を受けないままにすることに注意してください。

非常に高い、抽象的なレベルで、回路のステップを次の方法で考えることができます:

• 最初のアダマール層: 量子ビットをすべての可能な状態の重ね合わせに配置します。
• $Z_f$: 前に「-」記号を追加してターゲット状態をマークします。これはすぐに測定確率を変更しませんが、後続のステップでターゲット状態がどのように動作するかを変更します。
• 別のアダマール層: 前のステップで導入された「-」記号は、いくつかの項の間の相対的な符号を変更します。アダマールゲートは、計算状態の1つの混合$(|0\rangle+|1\rangle)/\sqrt{2}$を1つの計算状態$|0\rangle$に変え、$(|0\rangle-|1\rangle)/\sqrt{2}$を$|1\rangle$に変えるため、この相対的な符号の違いが、測定される状態で役割を果たし始めることができます。
• アダマールゲートの最後の層が適用され、次に測定が行われます。

次のセクションでは、これがどのように機能するかをより詳細に見ていきます。

例

グローバーのアルゴリズムがどのように機能するかをよりよく理解するために、小さな2量子ビットの例を調べてみましょう。これは、量子力学とディラック表記法に焦点を当てていない人にとってはオプションと見なされる可能性があります。しかし、量子コンピュータで実質的に作業することを望む人にとっては、これを強くお勧めします。

これは、回路全体のさまざまな位置でラベル付けされた量子状態を持つ回路図です。2つの量子ビットしかないことに注意してください。つまり、どのような状況下でも測定できる可能性のある4つの状態しかありません: $|00\rangle$、$|01\rangle$、$|10\rangle$、$|11\rangle$。

オラクル（$Z_f$、私たちには未知）が状態$|01\rangle$をマークすると仮定しましょう。オラクルを含む各量子ゲートのセットのアクションを調べて、測定時にどのような可能な状態の分布が出てくるかを見ていきます。

最初に、次のようになります

$$|\psi_0\rangle = |00\rangle$$

アダマールゲートの定義を使用すると、次のようになります

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

これで、オラクルはターゲット状態をマークします:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

この状態では、4つの可能な結果すべてが測定される同じ確率を持っていることに注意してください。それらはすべて大きさ$1/2$の重みを持っています。つまり、それぞれが測定される$|1/2|^2=1/4$の確率を持っています。したがって、状態$|01\rangle$は「-」位相を通じてマークされていますが、これはまだこの状態を測定する確率の増加をもたらしていません。次のアダマールゲートの層を適用し続けます。

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

同類項をまとめると、次のようになります

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

これで$Z_{\text{OR}}$が$|00\rangle$以外のすべての状態の符号を反転します:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

そして最後に、アダマールゲートの最後の層を適用します:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

これらの項を結合して、結果が実際に次のようになることを自分自身で確信する価値があります:

$$|\psi_5\rangle =|01\rangle$$

つまり、$|01\rangle$を測定する確率は100%（ノイズとエラーがない場合）であり、他の状態を測定する確率はゼロです。

この2量子ビットの例は特にクリーンなケースでした。グローバーのアルゴリズムは、常にターゲット状態を測定する100%の確率をもたらすとは限りません。むしろ、ターゲット状態を測定する確率を増幅します。また、グローバー演算子を1回以上繰り返す必要がある場合があります。

次のセクションでは、このアルゴリズムを実際のIBM®量子コンピュータを使用して実践に移します。

明らかな注意事項

グローバーのアルゴリズムを適用するには、グローバー演算子を構築する必要がありました。つまり、解決基準を満たす状態の位相を反転できる必要があります。これは疑問を投げかけます: 各解にラベルを付けるために量子回路を設計できるほど解集合をよく知っているなら、何を検索しているのでしょうか？答えは3つに分かれており、チュートリアル全体で再訪します:

(1) これらの種類のクエリアルゴリズムは、しばしば2つの当事者を含みます: 解基準を確立するオラクルを持つ者と、解状態を推測/見つけようとしている者。ある人がオラクルを構築できるという事実は、検索の必要性を否定するものではありません。

(2) 解基準を指定する方が解を見つけるよりも簡単な問題があります。 この最もよく知られた例は、おそらく大きな数の素因数の識別です。グローバーのアルゴリズムは、その特定の問題を解決するのに特に効果的ではありません。素因数分解にはショアのアルゴリズムを使用します。これは、状態の動作の基準を知ることが常に状態を知ることと同じではないことを指摘するための例にすぎません。

(3) グローバーのアルゴリズムは古典的なデータのみを返すわけではありません。 確かに、グローバー演算子の$t$回の反復後に最終状態の測定を行うと、解状態を識別する古典的情報を得る可能性があります。しかし、古典的情報が欲しくない場合はどうでしょうか。別のアルゴリズムでさらに使用するために量子コンピュータで準備された解状態が欲しい場合はどうでしょうか？グローバーのアルゴリズムは実際に、解が重く重み付けされた量子状態を生成します。したがって、より複雑な量子アルゴリズムのサブルーチンとしてグローバーのアルゴリズムを見つけることが期待されるかもしれません。

これらを念頭に置いて、いくつかの例を調べてみましょう。解状態が明確に指定されている例から始めて、アルゴリズムのロジックに従うことができるようにし、グローバーのアルゴリズムの有用性がより明確になる例に移ります。

一般的なインポートとアプローチ

いくつかの必要なパッケージをインポートすることから始めます。

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

このチュートリアルおよび他のチュートリアル全体で、「Qiskitパターン」として知られる量子コンピューティングのフレームワークを使用します。これは、ワークフローを次のステップに分解します:

• ステップ1: 古典的入力を量子問題にマッピングする
• ステップ2: 量子実行のために問題を最適化する
• ステップ3: Qiskit Runtimeプリミティブを使用して実行する
• ステップ4: 後処理と古典的分析

一般的にこれらのステップに従いますが、常に明示的にラベル付けするとは限りません。

アクティビティ1: 単一の指定されたターゲット状態を見つける

ステップ1: 古典的入力を量子問題にマッピングする

位相クエリゲートは、解状態に全体的な位相(-1)を配置し、非解状態を影響を受けないままにする必要があります。これを言う別の方法は、グローバーのアルゴリズムには、1つ以上のマークされた計算基底状態を指定するオラクルが必要であり、「マークされた」とは位相-1を持つ状態を意味します。これは、制御Zゲート、または$N$量子ビット上のその複数制御の一般化を使用して行われます。これがどのように機能するかを確認するために、ビット文字列{110}の特定の例を考えてみましょう。状態$|\psi\rangle = |q_2,q_1,q_0\rangle$に作用し、$|\psi\rangle = |011\rangle$の場合に位相を適用する回路が欲しいです（Qiskitの表記法のため、バイナリ文字列の順序を反転しました。これは、最下位（多くの場合0）量子ビットを右側に配置します）。

したがって、次を達成する回路$Z_f$が必要です

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

複数制御複数ターゲットゲート（MCMTGate）を使用して、すべての量子ビットによって制御されるZゲートを適用できます（すべての量子ビットが$|1\rangle$状態にある場合に位相を反転します）。もちろん、目的の状態の量子ビットの一部は$|0\rangle$である可能性があります。したがって、それらの量子ビットに対して、最初にXゲートを適用し、次に複数制御Zゲートを実行し、次に別のXゲートを適用して変更を元に戻す必要があります。MCMTGateは次のようになります:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

多くの量子ビットが制御プロセスに関与している可能性がある（ここでは3つの量子ビットが関与しています）が、単一の量子ビットがターゲットとして示されていないことに注意してください。これは、全体の状態が全体的な「-」符号（位相反転）を取得するためです。ゲートはすべての量子ビットに同等に影響を与えます。これは、単一の制御量子ビットと単一のターゲット量子ビットを持つCXゲートのような、他の多くの複数量子ビットゲートとは異なります。

次のコードでは、上記で説明したことを実行する位相クエリゲート（またはオラクル）を定義します: ビット文字列表現を通じて定義された1つ以上の入力基底状態をマークします。MCMTゲートは、複数制御Zゲートを実装するために使用されます。

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

今、ターゲットとなる特定の「マークされた」状態を選択し、定義した関数を適用します。どのような種類の回路を作成したかを見てみましょう。

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

量子ビット1-3が$|1\rangle$状態にあり、量子ビット0が最初に$|0\rangle$状態にある場合、最初のXゲートは量子ビット0を$|1\rangle$に反転し、すべての量子ビットが$|1\rangle$になります。これは、MCMTゲートが全体的な符号変化または位相反転を適用することを意味し、望ましいことです。他のケースでは、量子ビット1-3が$|0\rangle$状態にあるか、量子ビット0が$|0\rangle$状態に反転され、位相反転は適用されません。この回路は実際に目的の状態$|0111\rangle$、またはビット文字列{1110}をマークすることがわかります。

完全なグローバー演算子は、位相クエリゲート（オラクル）、アダマール層、$Z_\text{OR}$演算子で構成されています。組み込みのgrover_operatorを使用して、上記で定義したオラクルからこれを構築できます。

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

上で論じたように、グローバー演算子を複数回適用する必要がある場合があります。ノイズがない場合にターゲット状態の振幅を最大化するための最適な反復回数$t$は、この式から得られます:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

ここで、$A_1$は解またはターゲット状態の数です。現代のノイズの多い量子コンピュータでは、実験的に最適な反復回数は異なる可能性がありますが、ここでは$A_1=1$を使用して、この理論的な最適数を計算して使用します。

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

すべての可能な状態の重ね合わせを作成するための初期アダマールゲートを含む回路を構築し、グローバー演算子を最適回数適用しましょう。

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

グローバー回路を構築しました！

ステップ2: 量子ハードウェア実行のために問題を最適化する

抽象的な量子回路を定義しましたが、実際に使用したい量子コンピュータにネイティブなゲートの観点からそれを書き直す必要があります。また、量子コンピュータのどの量子ビットを使用するかを指定する必要があります。これらの理由などから、回路をトランスパイルする必要があります。まず、使用したい量子コンピュータを指定しましょう。

最初の使用時に認証情報を保存するための以下のコードがあります。環境に保存した後、ノートブックを共有するときに認証情報が誤って共有されないように、この情報をノートブックから削除してください。詳細については、IBM Cloudアカウントの設定および信頼されていない環境でサービスを初期化するを参照してください。

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

次に、プリセットパスマネージャーを使用して、選択したバックエンドに対して量子回路を最適化します。

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

この時点で、トランスパイルされた量子回路の深さがかなり大きいことに注目する価値があります。

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

これらは、この単純なケースでもかなり大きな数字です。すべての量子ゲート（特に2量子ビットゲート）はエラーを経験し、ノイズの影響を受けるため、量子ビットが非常に高性能でない場合、100を超える2量子ビットゲートの連続はノイズしかもたらしません。これらがどのように実行されるか見てみましょう。

Qiskitプリミティブを使用して実行する

多くの測定を行い、どの状態が最も可能性が高いかを確認したいと思います。このような振幅増幅は、Sampler Qiskit Runtimeプリミティブでの実行に適したサンプリング問題です。

Qiskit Runtime SamplerV2のrun()メソッドは、プリミティブ統合ブロック（PUB）の反復可能を取ることに注意してください。Samplerの場合、各PUBは(circuit, parameter_values)の形式の反復可能です。ただし、最低限、量子回路のリストを取ります。

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

この経験を最大限に活用するには、IBM Quantumから利用可能な実際の量子コンピュータで実験を実行することを強くお勧めします。ただし、QPU時間を使い果たした場合は、以下の行のコメントを外してシミュレータを使用してこのアクティビティを完了できます。

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

ステップ4: 後処理と結果を目的の古典的形式で返す

これで、サンプリングの結果をヒストグラムにプロットできます。

plot_distribution(dist)

グローバーのアルゴリズムが、他のオプションよりも少なくとも1桁高い確率で、最も高い確率で目的の状態を返したことがわかります。次のアクティビティでは、クエリアルゴリズムの2者間ワークフローとより一致する方法でアルゴリズムを使用します。

理解度チェック

以下の質問を読み、答えについて考えてから、三角形をクリックして解決策を明らかにしてください。

$2^4=16$個の可能な状態のセットで単一の解を検索しました。グローバー演算子の最適な反復回数を$t=3$と決定しました。この最適数は、(a)いくつかの解のいずれか、または(b)より多くの可能な状態の空間での単一の解を検索した場合、増加または減少しますか？

答え:

解の数が全体の解の空間と比較して小さい限り、小さな角度の周りでサイン関数を展開し、次を使用できることを思い出してください

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) 上記の式から、解状態の数を増やすと反復回数が減少することがわかります。分数$\frac{|\mathcal{A}_1|}{N}$がまだ小さい場合、$t$がどのように減少するかを説明できます: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}$。

(b) 可能な解の空間($N$)が増加すると、必要な反復回数は増加しますが、$t~\sqrt{N}$のようにしか増加しません。

ターゲットビット文字列のサイズを任意に長く増やすことができ、ターゲット状態の確率振幅が他の状態よりも少なくとも1桁大きいという結果が得られると仮定します。これは、グローバーのアルゴリズムを使用してターゲット状態を確実に見つけることができることを意味しますか？

答え:

いいえ。最初のアクティビティを20量子ビットで繰り返し、量子回路を数回num_shots = 10,000実行すると仮定します。一様確率分布は、すべての状態が1回でも測定される確率が$10,000/2^{20}=0.00954$であることを意味します。ターゲット状態を測定する確率が非解の10倍である場合（各非解の確率が対応してわずかに減少した場合）、ターゲット状態を1回でも測定する確率は約10%しかありません。ターゲット状態を複数回測定する可能性は非常に低く、ランダムに取得された多くの非解状態と区別できなくなります。良いニュースは、エラー抑制と緩和を使用することで、さらに高忠実度の結果を得ることができることです。

アクティビティ2: 正確なクエリアルゴリズムワークフロー

このアクティビティを最初のアクティビティとまったく同じように開始しますが、今度は別のQiskit愛好家とペアを組みます。秘密のビット文字列を選択し、パートナーは（一般的に）異なるビット文字列を選択します。それぞれがオラクルとして機能する量子回路を生成し、それらを交換します。次に、そのオラクルでグローバーのアルゴリズムを使用して、パートナーの秘密のビット文字列を決定します。

ステップ1: 古典的入力を量子問題にマッピングする

上記で定義したgrover_oracle関数を使用して、1つ以上のマークされた状態のオラクル回路を構築します。パートナーにマークした状態の数を伝えて、グローバー演算子を最適回数適用できるようにしてください。**ビット文字列を長くしすぎないでください。3-5ビットであれば、大きな困難なしに動作するはずです。**より長いビット文字列は、エラー緩和などのより高度な技術を必要とする深い回路をもたらします。

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

これで、ターゲット状態の位相を反転する量子回路を作成しました。以下の構文を使用して、この回路をmy_circuit.qpyとして保存できます。

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

このファイルをパートナーに送信します（電子メール、メッセージングサービス、共有リポジトリなどを介して）。パートナーにも回路を送信してもらいます。簡単に見つけられる場所にファイルを保存してください。パートナーの回路を入手したら、それを視覚化できますが、それはクエリモデルを破ります。つまり、オラクルをクエリできる（オラクル回路を使用できる）が、どの状態をターゲットにしているかを判断するためにそれを検査できない状況をモデル化しています。

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

パートナーにエンコードしたターゲット状態の数を尋ね、以下に入力します。

# Update according to your partner's number of target states.
num_marked_states = 1

これは、次の式で最適なグローバー反復回数を決定するために使用されます。

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

ステップ2: 量子ハードウェア実行のために問題を最適化する

これは以前とまったく同じように進みます。

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

ステップ3: Qiskitプリミティブを使用して実行する

これも最初のアクティビティのプロセスと同じです。

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

ステップ4: 後処理と結果を目的の古典的形式で返す

サンプリング結果のヒストグラムを表示します。1つ以上の状態が他の状態よりもはるかに高い測定確率を持っているはずです。これらをパートナーに報告し、ターゲット状態を正しく決定したかどうかを確認します。デフォルトでは、表示されるヒストグラムは最初のアクティビティの同じ回路のものです。パートナーの回路から異なる結果が得られるはずです。

plot_distribution(dist)

理解度チェック

以下の質問またはプロンプトを読み、答えについて考えるか、パートナーとプロセスについて話し合ってください。ヒントや提案については、三角形をクリックしてください。

パートナーのターゲット状態を正しく取得しているはずです。そうでない場合は、パートナーと協力して何が問題だったのかを特定してください。以下をクリックしていくつかのアイデアを確認してください。

ヒント:

• パートナーの回路を視覚化/描画して、正しく読み込まれたことを確認してください。
• 使用した回路を比較し、期待される結果を得たものと比較してください。
• ビット文字列が長すぎないか、グローバー反復回数が禁止的に高くないかを確認するために、使用した回路の深さを確認してください。

まだ行っていない場合は、パートナーが送信したオラクル回路を描画してください。各ゲートの効果について話し合い、ターゲット状態が何であったかを論じることができるかどうかを確認してください。これは、複数のマークされた状態の場合よりも、単一のマークされた状態の場合の方がはるかに簡単です。

ヒント:

• オラクルの仕事は、ターゲット状態の符号を反転することであることを思い出してください。
• MCMTGateは、制御に関与するすべての量子ビットが$|1\rangle$状態にある場合にのみ、状態の符号を反転することを思い出してください。
• ターゲット状態が特定の量子ビットに既に$|1\rangle$を持っている場合、その量子ビットに対して何もする必要はありません。ターゲットが特定の量子ビットに$|0\rangle$を持っていて、MCMTGateに符号を反転させたい場合は、オラクルでその量子ビットにXゲートを適用する必要があります（そしてMCMTGateの後でXゲートを元に戻します）。

グローバー演算子の反復を1回少なくして実験を繰り返します。まだ正しい答えが得られますか？なぜですか、またはなぜですか？

ガイダンス:

おそらくそうでしょうが、エンコードされた解の数に依存する可能性があります。これは微妙な点を強調しています: グローバー反復の「最適な」数は、マークされた状態を測定する確率をできるだけ高くする数です。しかし、それよりも少ない反復でも、マークされた状態を他の状態よりもかなり可能性が高くすることができます。したがって、最適な数よりも少ない反復で済む可能性があります。これにより、回路の深さが減少し、したがってエラー率が減少します。

誰かがここで識別された「最適な数」よりも少ないグローバー反復を使用したいのはなぜですか？

答え:

グローバー反復の「最適な」数は、ノイズがない場合にマークされた状態を測定する確率をできるだけ高くする数です。しかし、それよりも少ない反復でも、マークされた状態を他の状態よりもかなり可能性が高くすることができます。したがって、最適な数よりも少ない反復で済む可能性があります。これにより、回路の深さが減少し、したがってエラー率が減少します。

アクティビティ3: 特定のビット文字列以外の基準

最後の例として、グローバーのアルゴリズムがサブルーチンの文脈でどのように有用である可能性があるかを示すために、ビット文字列表現で特定の数の1を持つ量子状態が必要であると想像しましょう。これは、保存則が関与する状況で一般的です。たとえば、量子化学の文脈では、電子軌道の占有に量子ビットの1状態をマッピングすることがよくあります。電荷を保存するためには、1の総数も一定に保つ必要があります。このような制約は非常に一般的であるため、特別な名前があります: ハミング重み制約、そして状態の1の数はハミング重みと呼ばれます。

ステップ1:

まず、目的のハミング重みを持つ状態をマークする関数を書きましょう。不特定の量子ビット数num_qubitsとターゲットハミング重みtarget_weightに対して、これを一般的に書きます。

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

ここから、プロセス全体は前の2つのアクティビティのものと同じです。簡潔さのため、Qiskitパターンのステップはここではコードコメントでのみ示されています。

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

ここでは、グローバーのアルゴリズムは実際に、ハミング重み2の状態が他の状態よりも測定される可能性がはるかに高く、約1桁高い可能性があるように準備しました。

重要な概念:

このモジュールでは、グローバーのアルゴリズムのいくつかの主要な機能を学びました:

• 古典的な構造化されていない検索アルゴリズムは、空間のサイズ$N$に対して線形にスケールするクエリ数を必要としますが、グローバーのアルゴリズムは$\sqrt{N}$のようにスケールするクエリ数を必要とします。
• グローバーのアルゴリズムは、一連の演算（一般的に「グローバー演算子」と呼ばれます）を何度も繰り返すことを含み、ターゲット状態を最適に測定される可能性が高くなるように選択された回数$t$繰り返します。
• グローバーのアルゴリズムは、$t$回未満の反復で実行でき、それでもターゲット状態を増幅できます。
• グローバーのアルゴリズムは計算のクエリモデルに適合し、ある人が検索を制御し、別の人がオラクルを制御/構築する場合に最も意味があります。また、他の量子計算のサブルーチンとして有用である可能性もあります。

質問

T/F質問:

1. T/F グローバーのアルゴリズムは、構造化されていない検索で単一のマークされた状態を見つけるために必要なクエリ数で、古典的アルゴリズムに対する指数関数的な改善を提供します。

2. T/F グローバーのアルゴリズムは、解状態が測定される確率を反復的に増加させることによって機能します。

3. T/F グローバー演算子を反復するほど、解状態を測定する確率が高くなります。

MC質問:

1. 文を完成させるための最良のオプションを選択してください。現代の量子コンピュータでグローバーのアルゴリズムを正常に使用するための最良の戦略は、グローバー演算子を反復することです...

• a. 1回のみ。
• b. 常に$t$回、解状態の確率振幅を最大化するために。
• c. $t$回まで、ただし解状態を目立たせるにはそれより少なくても十分かもしれません。
• d. 10回以上。

2. ここに示されている位相クエリ回路は、特定の状態を位相反転でマークするオラクルとして機能します。次のうち、この回路によってマークされる状態はどれですか？

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. 128のセットから3つのマークされた状態を検索したいとします。マークされた状態の振幅を最大化するためのグローバー演算子の最適な反復回数は何ですか？

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

議論の質問:

1. 量子オラクルで使用する他のどのような条件を考えますか？ビット文字列に対して簡単に述べたり課したりできるが、単にマークされたビット文字列を書き出すだけではない条件を考えてください。

2. 現代の量子コンピュータでグローバーのアルゴリズムをスケーリングすることに問題はありますか？