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

このQiskit in Classroomsモジュールでは、以下のパッケージがインストールされた Python 環境が必要です：

qiskit v2.1.0 または新しい
qiskit-ibm-runtime v0.40.1 または新しい
qiskit-aer v0.17.0 または新しい
qiskit.visualization
numpy
pylatexenc

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

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

# 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が発表したGroverのアルゴリズムは、量子コンピューターがこの問題をはるかに効率的に解く方法を示しており、マークされたアイテムを高確率で見つけるのに必要なステップはわずか $O(\sqrt{N})$ 。これは古典的な方法に比べて 2次関数的なスピードアップであり、大規模なデータセットでは重要である。

このアルゴリズムは次のような文脈で動作する：

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

以下はグローバーのアルゴリズムの非常に基本的な図である。より詳細な図については、本稿を参照されたい。

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

これは構造化されていない検索に最適である。どの量子アルゴリズムも、 $O(\sqrt{N})$ より少ないクエリーで問題を解くことはできない。
これは、他の量子アルゴリズム（例えば、因数分解のためのショールのアルゴリズム）とは異なり、指数関数的ではなく、2次関数的なスピードアップしかもたらさない。
暗号システムに対するブルートフォース攻撃を高速化できる可能性があるなど、実用的な意味合いを持つが、高速化だけでは最新の暗号のほとんどを解読できるほどではない。

基本的なコンピューティングの概念やクエリーモデルに精通した学部生にとって、グローバーのアルゴリズムは、量子コンピューティングが特定の問題において、たとえ "たった "2次関数的な改善であったとしても、いかに古典的なアプローチを上回ることができるかを明確に示している。また、より高度な量子アルゴリズムや量子コンピューティングの幅広い可能性を理解するための入り口としても役立つ。

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

ここでは、グローバー・オラクルの構築方法と、Qiskit回路ライブラリ GroverOperator の機能を活用して、グローバー探索インスタンスを簡単にセットアップする方法について解説します。 IBM QuantumSampler プリミティブを使用すると、Grover回路をシームレスに実行できます。

理論

バイナリ文字列を単一のバイナリ変数にマップする関数 $f$ が存在するとする

f: \Sigma^n \rightarrow \Sigma

$\Sigma^6$

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)$ の引数 $x$ のうち、1に対応する量子状態を見つけるという課題がある。言い換えれば、 $f(x_1)=1$ （または解がない場合はその旨を報告する）ような $\{x_1\}\in \Sigma^n$ をすべて見つける。解でないものを $x_0$ と呼ぶ。もちろん、私たちは量子コンピュータ上で量子状態を用いてこれを行うので、これらの2進文字列を状態として表現することは有用である：

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

量子状態（ディラック）記法を用いると、1つ以上の特別な状態 $\{|x_1\rangle\}$ を、 $N=2^n$ 可能な状態の集合の中から探すことになる。 $n$ は量子ビットの数で、非解は次のように表される。 $\{|x_0\rangle\}.$

関数 $f$ は、オラクルによって提供されるものと考えることができる。ブラックボックスで、状態 $|x\rangle.$ に対する効果を決定するために問い合わせることができる。実際には、関数を知っていることが多いが、実装が非常に複雑な場合がある。つまり、問い合わせや $f$ の適用回数を減らすことが重要になる。別の方法として、ある人が別の人がコントロールするオラクルに問い合わせるというパラダイムを想像することができる。

これは「構造化されていない検索問題」であり、 $f$ 、検索に役立つ特別なものは何もない。出力はソートされておらず、解のクラスタリングなども知られていない。古い紙の電話帳を例えて考えてみよう。この非構造化検索は、特定の番号を探してスキャンするようなもので、アルファベット順に並んだ名前のリストを探すようなものではない。

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

グローバーアルゴリズムにおける回路の概略図

グローバーのアルゴリズムの完全な数学的ウォークスルーは、例えば、ジョン・ワトラスによるコース「 Fundamentals of quantum algorithms 」（ IBM Quantum Learning）で見ることができる。このモジュールの最後には、付録として凝縮された処置が提供されている。しかし今は、グローバーのアルゴリズムを実装する量子回路の全体的な構造をおさらいするにとどめる。

グローバーのアルゴリズムは以下の段階に分けられる：

初期重ね合わせの準備（すべての量子ビットにハダマードゲートを適用する）
位相反転でターゲット状態を「マーク」する
ハダマードゲートと位相反転がすべての量子ビットに適用される「拡散」ステージ。
目標状態を測定する確率を最大にするために、マーキングと拡散の段階を繰り返す可能性
寸法

グローバーのアルゴリズムの基本設定を示す量子回路図。この例では4つの量子ビットを使用している。

多くの場合、マーキングゲート $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 が得られる。したがって、分布が半々であれば、期待値は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$ "-"記号を前に付けることで、対象となる状態（複数可）をマークする。これはすぐに測定確率を変えるわけではないが、その後のステップでターゲット状態がどのように振る舞うかを変える。
もうひとつのハダマード層：前のステップで導入した"-"記号は、いくつかの項間の相対符号を変更する。ハダマードゲートは、ある混合計算状態 $(|0\rangle+|1\rangle)/\sqrt{2}$ を一つの計算状態、 $|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％の確率で目標状態を測定できるとは限らない。むしろ、目標状態を測定する確率を増幅させることになる。また、グローバー・オペレーターは複数回繰り返す必要があるかもしれない。

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

幾何学的な図

上記の2量子ビットの例は、単純なケースにおける代数の働きを示したものですが、グローバーのアルゴリズムを理解するには、もっと直感的な方法があります。それは、2次元平面における一連の幾何学的反射として捉えることです。以下に、この図について説明します。詳細については、ジョン・ワトラウス氏の講座「量子アルゴリズムの基礎」もご参照ください。

思い返して。 ここで必要な重要な数学的事実は、次のような形の演算子が

2|v\rangle\langle v| - I

は、 $|v\rangle.$ で定義される軸に関する任意の状態を反映している。その理由を理解するために、2つのケースを考えてみよう。 $|v\rangle$ に沿った状態は変化しないが、 $|v\rangle$ に垂直な状態は符号が反転する。他のどの状態もこれら2つの要素に分解することができ、演算子はそれぞれに応じて作用する。これはまさに、 $|v\rangle$ に対する反射である。

実は、グローバーのアルゴリズムにおけるオラクル段階と拡散段階の両方が、この幾何学的図式において反射として表現できることがわかった。

鏡としての神託。 この関数は、 $|A_1\rangle$ の状態フラグを反転させ、それ以外の部分は変更しません。それは、 $|A_0\rangle$ 軸に対する反射と同じです。

反射としての拡散。 拡散演算子がどのようにして反射でもあるのかを理解するのは、少し難しい。拡散演算子は

H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}

$Z_{\text{OR}}$ それ自体は全ゼロ状態に対する反射であり、 $|0\rangle^{\otimes n}$ 以外のすべての状態の符号を反転させる。これは、 $2|0\rangle\langle 0| - I$ と表すことができる。周囲のハダマール層は、事実上、基底変換を行い、反射軸を変換する。 $H^{\otimes n}$ は、 $|0\rangle^{\otimes n}$ を一様重ね合わせ $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ に写像することを思い出してください。ハダマール演算はそれ自体の逆演算であるため、式全体は次のようになります

H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I

これは、 $|u\rangle$ に関する反射です。 $|u\rangle$ は $|\psi\rangle$ に非常に近く（どちらも $|A_0\rangle$ にほぼ沿っています）、この2回目の反射により、状態は出発点から $2\theta$ の角度だけずれた位置へと送られます。

$2\theta$ による回転。 これら2つの反射の複合効果は、 $2\theta$ から $|A_1\rangle$ への回転となる。Grover演算子の各反復ごとに、状態はさらに $2\theta.$ だけ回転する

反復の最適回数。 私たちの目標は、状態を $|A_1\rangle$ にできるだけ近づけるように回転させることです。つまり、合計で約 $\pi/2$ ラジアン（4分の1回転）回転させることになります。各反復が $2\theta$ を寄与する場合、最適な反復回数 $t$ は次の条件を満たす

(2t + 1)\theta \approx \frac{\pi}{2}

$N$ の条件を満たす解が1つだけ存在する場合、初期角は $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ となる（ $N$ が十分に大きい場合）。これを代入すると、

t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}

ここで、あの有名な $\sqrt{N}$ による計算速度向上の理由が明らかになります。つまり、目標値に到達するために必要な反復回数は $O(\sqrt{N})$ 回だけで済み、従来の探索法で必要とされる $O(N)$ 回のチェックを行う必要がないのです。

より一般に、 $N$ 個の総状態のうち、 $|A_1|$ 個の解状態が存在する場合、最適な反復回数は

t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}

反復回数を多くしすぎると、 $|A_1\rangle$ を超えて回転し、目標状態が見つかる確率が再び低下し始めることに注意してください。適切な反復回数を決定することは重要ですが、ノイズの多い量子ハードウェアでは、実験的に最適な回数はこの理想的な式とは異なる場合があります。

グローバーのアルゴリズムはなぜ有用なのでしょうか？

ここで疑問に思うかもしれません。「目標状態を示すオラクルを作ったばかりなのに、それを作るためには、そもそもその目標状態を知っていなければならなかったのではないか」と。では、私たちは一体何を探しているのでしょうか？

これは妥当な質問であり、いくつかの良い答えがあります。

クエリモデルは理論的なツールである。 計算のクエリモデルは、もともと実用的なものとして設計されたわけではない。その目的は、問題を「オラクル」と「それ以外」の2つの部分に分けることで、アルゴリズムの計算量を明確に分析できるようにすることです。確認は無料ですが、検索はどれほど大変なのでしょうか？クエリの数は、入力のサイズに応じてどのように変化しますか？実際にこのような仕組みで動作するシステムは存在しないとしても、これらは有用な問いである。
これは、 2人で行うアクティビティと捉えることもできます。一方が目標状態を把握し、オラクルを構築し、もう一方はそのオラクルをブラックボックスとして扱い、内部を覗き見することなく答えを見つけ出すのが役割となります。以下のアクティビティ2では、パートナーと一緒にまさにこの作業を行います。
振幅増幅は、幅広い用途に役立つサブルーチンです。 この最初のデモンストレーションは一見循環論法のように見えるかもしれませんが、その根底にある「 振幅増幅 」と呼ばれるメカニズムは、量子コンピューティングの分野で繰り返し現れます。ここで私たちが実際に構築しているのは、より複雑な量子アルゴリズムの多くにおいてサブルーチンとして登場するツールに対する直感的な理解です。
答えを知らなくてもオラクルを構築できる問題がある。 重要な点は、解決策を見つけるのは非常に難しい一方で、与えられた解決策が正しいかどうかを確認するのは極めて容易な問題という、ある種のカテゴリーが存在するということである。ファクタリングはその一例です。2つの大きな素数の積が与えられた場合、それらの素数が何であるかを特定するのは極めて困難ですが、一度それらを特定できれば、それらを掛け合わせることで簡単に検証することができます。（因数分解に関しては、グローバーのアルゴリズムよりも優れたアルゴリズムが存在します（ショアのアルゴリズムを参照）が、この機能の問題点はこれだけにとどまりません。）数独や制約満足問題、さらには定番の「マインスイーパ」といったゲームも、すべて解くのは難しいが、正解かどうかを確認するのは簡単な問題です。

それがなぜ重要なのでしょうか？つまり、解答そのものは分からなくても、その解答が満たすべきすべての条件や要件を把握し、それらの要件をオラクルとして機能する量子回路に組み込むことができるということです。グローバーのアルゴリズムがそれを求めてくれます。

これらの点を踏まえて、いくつかの例を見ていきましょう。アルゴリズムの論理を追えるよう、解の状態が明確に指定されている例から始めます。次に、2人で行うアクティビティに進み、最後に、答えの知識ではなく問題の制約条件に基づいてオラクルを構築する例を取り上げます。

一般的な輸入とアプローチ

まずは必要なパッケージをいくつかインポートする。

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
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: IBM Quantum プリミティブを使用して実行する
ステップ4：後処理と古典的分析

私たちは通常、これらのステップに従うが、必ずしも明示的にラベルを貼るとは限らない。

アクティビティ1: 単一の与えられた目標状態を見つける

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

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

したがって、 $Z_f$

Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \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")

Output:

多くの量子ビットが制御プロセスに関与している可能性があるが（ここでは3つの量子ビットが関与している）、単一の量子ビットがターゲットとして示されているわけではないことに注意。ゲートはすべての量子ビットに等価に作用する。これは、 CX ゲートのような、1つの制御量子ビットと1つのターゲット量子ビットを持つ他の多くの多重量子ビットゲートとは異なる。

つまり、ビット列表現で定義された1つまたは複数の入力基底状態をマークする。マルチ制御Zゲートの実装にはMCMTゲートが使用される。

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")

Output:

qubit1-3が $|1\rangle$ 、qubit0が初期状態で $|0\rangle$ 、最初のXゲートはqubit0を $|1\rangle$ 、すべてのqubitが $|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")

Output:

前述の図で説明したように、グローバー演算子を複数回適用する必要があるかもしれません。ノイズが存在しない場合に目標状態の振幅を最大化する最適な反復回数 $t$ は、

t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}

ここで、 $|A_1|$ は解の状態の数であり、 $N=2^n$ は状態の総数である。現代のノイズの多い量子コンピュータでは、実験的に最適な反復回数は異なる可能性があるが、ここでは $|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)

Output:

ここで、すべての可能な状態の重ね合わせを作るために、最初のハダマードゲートを含む回路を構成し、グローバー演算子を最適な回数適用してみよう。

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")

Output:

グローバー・サーキットを構築した！

ステップ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

Output:

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),
)

Output:

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

この単純なケースでも、実際にはかなり大きな数字である。すべての量子ゲート（特に2量子ビットゲート）には誤差が生じ、ノイズの影響を受けるため、量子ビットが極めて高性能でなければ、100個以上の2量子ビットゲートを連ねてもノイズにしかならない。これらのパフォーマンスを見てみよう。

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

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

なお、 IBM QuantumSamplerV2 のメソッド 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)

Output:

グローバーのアルゴリズムは、他の選択肢よりも少なくとも一桁高い確率で、望みの状態を返したことがわかる。次のアクティビティでは、クエリーアルゴリズムの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 回実行したとする。一様な確率分布とは、すべての状態が一度でも測定される確率が $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: `IBM Quantum` プリミティブを使用して実行する

これも最初の活動でのプロセスと同じである。

# 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)

Output:

理解度チェック

あなたはパートナーの目標状態を正しく取得しているはずです。そうでなかった場合は、何がいけなかったのかをパートナーと一緒に考えてください。いくつかのアイデアは下記をクリック。

- パートナーの回路を視覚化/描画し、正しくロードされていることを確認する。
- 使用した回路を比較し、期待された結果と得られた結果を比較する。
- ビット列が長すぎたり、グローバーの反復回数が法外に多かったりしないように、使用する回路の深さをチェックする。

まだの人は、パートナーから送られてきたオラクル回路を描く。各ゲートの効果を説明し、目標状態がどうであったに違いないかを論じることができるかどうか。マークされた状態が1つの場合は、複数の場合よりもずっと簡単だろう。

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

グローバー演算子の反復回数を1回減らして実験を繰り返す。それでも正解は出ますか？その理由は何か?

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

グローバーの反復回数を「最適な回数」よりも少なくしたい人がいるのはなぜか？

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

アクティビティ3：グローバーのアルゴリズムを使ってマインスイーパのグリッドを解く

前の節で述べたように、グローバーのアルゴリズムが真に有用となるのは、答えの知識からではなく、問題の制約条件からオラクルを構築できる場合である。「マインスイーパ」はその好例です。番号の付いたマス目は、隣接する地雷の数を示しており、これらの制約条件によって地雷の位置は完全に決定されますが、その配置を見つけるには探索が必要です。

マインスイーパはNP完全であることが証明されている。つまり、解くのは難しいが、正解かどうかを確認するのは簡単である。したがって、これはグローバーのアルゴリズムの自然な適用対象となる。もちろん、ノイズの多い量子コンピュータでは、まだ9× $\times$ 9のグリッド全体を解くことはできません。回路があまりにも深くなってしまうからです。その代わりに、将来の耐障害性マシン上でより大きなボードをどのように扱うかについて、簡単な実例として小さなグリッドを使用します。

いくつか重要な注意点があります。グローバーのアルゴリズムは*、構造を持たない*従来の探索に比べて、計算速度を2倍に高速化するに過ぎない。「マインスイーパ」には、巧妙な古典的アルゴリズムが活用できるような構造が、ほぼ間違いなく存在している。そして、指数関数的に拡大する探索空間においては、 $\sqrt{N}$ による改善効果にも限界がある。しかし、そうした懸念はひとまず脇に置いて、この単純な問題を例に、問題の制約条件が量子オラクルにどのようにエンコードされるかを説明しましょう。

グリッド

こちらが、私たちの「ベビー・マインスイーパー」の盤面です：

3つの空白マスと3つの数字が書かれたマスがある、シンプルなマインスイーパーの盤面です。

各空のセルは、そこに地雷があるかどうかを示す二値変数で表すことができます。これらを $x_0$ 、 $x_1$ 、 $x_2$ と表記する。ここで、 $x_i = 1$ はそのセルに地雷があることを意味し、 $x_i = 0$ は地雷がないことを意味する：

同じマインスイーパのグリッドで、空白のマスには x0、 x1、 x2 という変数がラベルとして付けられています。

頭の中でなら0.5秒ほどで解ける問題ですが、この単純な例題を用いて、量子コンピュータを使えば、はるかに難しい問題にどのように取り組むことができるかを説明しています。

制約をエンコードする

番号が振られた各セルは、隣接する空白のセルに対して条件を課します。これらの条件を、量子回路として表現できるブール式として表す必要があります。

$x_0$ と $x_1$ に隣接する「1」のセルは、この2つのうちちょうど1つに地雷が仕掛けられていることを示しています。これはまさに排他的論理和（XOR）演算、 $\oplus$ であり、入力のうちちょうど1つが真である場合に真を返します：

(x_0 \oplus x_1)

同様に、もう1つの「1」のセル（ $x_1$ および $x_2$ に隣接するセル）からは、以下の結果が得られます：

(x_1 \oplus x_2)

「2」と書かれたマスには、3つの空白マスのうち2つに地雷が埋まっていることが示されています。 XORはパリティ演算であるため、変数の真の数が奇数の場合、 $x_0 \oplus x_1 \oplus x_2$ はtrueを返します。偶数（具体的には2）が真となるようにしたいので、 $\lnot$ を用いて否定します：

\lnot(x_0 \oplus x_1 \oplus x_2)

この式は、パリティに関する記述であるため、 $|1\rangle$ 状態にあるクビットが0個か2個のいずれかであれば、その条件を満たすことになる。しかし、それぞれ少なくとも1つの地雷を配置する必要がある他の2つの条件と組み合わせると、条件を満たす唯一の解は、地雷がちょうど2つ配置されたものとなる。

これら3つの条件はすべて同時に満たされる必要があるため、and記号を用いてこれらを結合します。 $\land$ ：

(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)

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

次に、このブール式を、オラクルとして機能する量子回路にエンコードする必要があります。量子版XORは、CX（CNOT）ゲートを用いて実現できる。データ量子ビットからワークスペース（アンシラ）量子ビットに対して2つのCXゲートを適用することで、事実上それらのXOR演算を行い、その結果をアンシラに保存する。

各節に1つずつ、計3つのワークスペース量子ビットを導入する。各ブール式の結果を対応するワークスペース量子ビットに格納し、その後、マルチ制御Zゲートを使用して3量子ビット状態の位相を反転させ、3つのワークスペース量子ビットすべてを $|1\rangle$ （つまり、すべての節が同時に満たされる）の状態にする。

以下の最初のコードセルでは、オラクルの「演算」部分、つまり各節を評価し、その結果をワークスペースの量子ビットに書き込む部分を構築します。

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

この時点で、各節の結果は、対応するワークスペース量子ビットに格納されます。ここで、ワークスペースの3つの量子ビットすべてが $|1\rangle$ となるような3量子ビットのデータ状態が必要であり、これによりマイナス符号が付与される。これには、多重制御Zゲート（ターゲット側でハダマールゲートに挟まれたMCXゲートとして実装）を使用します。

位相反転を適用した後、ワークスペースの量子ビットを $|0\rangle.$ の状態に戻すために、逆順ですべての句評価ステップを元に戻す（ アンコンピュート ）必要があります。これは、Grover演算子のその後の反復処理において、ワークスペースの量子ビットがクリーンな状態にあるようにするために不可欠です。

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

この回路は私たちの「オラクル」です。これは、マインスイーパの3つの制約すべてを満たすデータ量子ビットの状態の位相を反転させ、ワークスペース量子ビットの状態を元のままに保ちます。 $|0\rangle.$

ここで、このオラクルから完全なグローバー演算子を構築する。 x引数に reflection_qubits 注意してください：ワークスペース量子ビットは探索空間の一部ではないため、データ量子ビットのみを渡します。オラクルが適用されれば、彼らの仕事は完了する。

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

データ量子ビットが3つ、解の状態が1つある場合、Grover反復の最適回数は $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$ となるため、ここでは2回の反復を行う。データ量子ビットにアダマールゲートを適用して初期の重ね合わせ状態を作り出し、グローバー演算子を2回重ね合わせ、データ量子ビットのみを測定する。

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

ステップ2：量子ハードウェア実行に向けた問題の最適化

これまでと同様に、ターゲットバックエンド向けに回路をトランスパイルします。

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)

これで、トランスパイルされた回路の深さを確認できます。マインスイーパ・オラクルはワークスペース量子ビットと複数のCXゲートを使用するため、トランスパイルされた回路は、これまでの演習で扱ったものよりも深くなります。

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),
)

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

# 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()

# 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)

この 101 状態は他のどの状態よりもはるかに高い確率で現れるはずであり、これは地雷が $x_0$ および $x_2$ に配置されていることを示しています。私たちは量子コンピュータを使って、ミニマインスイーパを解いたのです！

もちろん、マインスイーパにおける最良の古典的アルゴリズムは、すべての地雷配置を網羅的に探索する力業的な手法よりも優れています。それらはグリッドの構造を巧みに利用しているからです。グローバーのアルゴリズムが優位性を発揮するのは、最大限に曖昧になるよう設計された極めて困難なボードに限られる。たとえそのような場合でも、その速度向上は二次関数的なものに過ぎないため、指数関数的な増加にいつまでも追いつき続けることはできない。しかし、真に重要なのはその手法そのものです。問題の制約を量子オラクルにエンコードするという手法は、制約充足問題や組み合わせ最適化、その他多くの分野に応用できる強力なパターンなのです。

質問と重要な概念：

重要な概念：

このモジュールでは、グローバーのアルゴリズムの主な特徴を学んだ：

古典的な非構造化検索アルゴリズムが、空間の大きさに対して線形にスケールするクエリー数を必要とするのに対し、 $N,$ Groverのアルゴリズムは、次のようにスケールするクエリー数を必要とする。 $\sqrt{N}.$
グローバーのアルゴリズムでは、一連の操作（一般に「グローバー演算子」と呼ばれる）を、目標状態が測定される可能性が最適になるように選択された回数（ $t,$ ）繰り返す。
Groverのアルゴリズムは、 $t$ より少ない反復回数で実行しても、目標状態を増幅することができる。
グローバーのアルゴリズムは計算のクエリーモデルに適合し、一人が検索を制御し、もう一人がオラクルを制御／構築する場合に最も理にかなっている。また、他の量子計算のサブルーチンとしても有用だろう。
「マインスイーパ」の例で示されたように、オラクルは解に関する知識ではなく、 問題の制約条件から構築することができる。

正誤問題：

T/F グローバーのアルゴリズムは、構造化されていない検索において、一つのマークされた状態を見つけるのに必要なクエリーの数において、古典的なアルゴリズムよりも指数関数的な改善をもたらす。
T/F グローバーのアルゴリズムは、解の状態が測定される確率を反復的に増加させることによって機能する。
T/F グローバー演算子を何度も繰り返すほど、解の状態を測定する確率が高くなる。

MCの質問：

文を完成させるのに最も適した選択肢を選びなさい。最新の量子コンピューターでグローバーのアルゴリズムを成功させる最善の方法は、グローバー演算子を反復することである...

a. 一度だけだ。
b. 常に $t$ 、解の状態の確率振幅を最大にする。
c. 最大で $t$ 、解決策を際立たせるには少ない回数で十分かもしれない。
d. 10回以上だ。

ここでは、ある状態を位相反転でマークするオラクルとして機能する位相問い合わせ回路を示す。この回路によってマークされる状態は次のうちどれか？

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

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

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

ディスカッションの質問：

他にどのような問題をグローバー探索として定式化できるでしょうか？解決策を見つけるのは難しいけれど、その正しさを確認するのは簡単な問題を思い浮かべてみてください。
グローバーのアルゴリズムを現代の量子コンピューターでスケーリングすることに問題はないのか？

このページは役に立ちましたか？

バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。

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

概要

理論

グローバーアルゴリズムにおける回路の概略図

理解度チェック

例

幾何学的な図

グローバーのアルゴリズムはなぜ有用なのでしょうか？

一般的な輸入とアプローチ

アクティビティ1: 単一の与えられた目標状態を見つける

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

ステップ2：量子ハードウェア実行に向けた問題の最適化

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

ステップ4：後処理を行い、結果を希望の古典形式で返す

理解度チェック

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

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

ステップ2：量子ハードウェア実行に向けた問題の最適化

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

ステップ4：後処理を行い、結果を希望の古典形式で返す

理解度チェック

アクティビティ3：グローバーのアルゴリズムを使ってマインスイーパのグリッドを解く

グリッド

制約をエンコードする

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

ステップ2：量子ハードウェア実行に向けた問題の最適化

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

ステップ4：後処理を行い、結果を希望の古典形式で返す

質問と重要な概念：

重要な概念：

正誤問題：

MCの質問：

ディスカッションの質問：

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

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

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