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

この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つ以上の計算基底状態を見つけたい状態としてマークするオラクル関数と、マークされた状態の振幅を増大させ、結果として残りの状態を抑制する増幅回路が必要である。

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

数学

バイナリ文字列を単一のバイナリ変数にマップする関数 $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® 量子コンピュータを使って実践してみる。

明らかな注意点

グローバーのアルゴリズムを適用するためには、グローバー演算子を構築しなければならない。つまり、解の基準を満たす状態で位相を反転させることができなければならない。もし私たちが解の集合をよく知っていて、それぞれにラベルを付ける量子回路を設計できるのなら、私たちは何を探しているのだろうか？その答えは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）量子ビットを右に置く表記になっているため、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,$ は、この式から求めることができる：

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

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量子ビットゲートを連ねてもノイズにしかならない。これらのパフォーマンスを見てみよう。

Qiskit primitives を使用して実行する

多くの測定を行い、どの状態が最も可能性が高いかを確認したい。このような振幅増幅は、 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)

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: `Qiskit primitives`を使用して実行する

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

# 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：特定のビット列以外の基準

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

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

Output:

['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()

Output:

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

Output:

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

num_marked_states

Output:

plot_distribution(dist)

Output:

ここでグローバーのアルゴリズムは、確かにハミング重み2の状態を、他のどの状態よりも測定される可能性が非常に高く、およそ1桁高い確率で準備した。

重要な概念：

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

古典的な非構造化検索アルゴリズムが、空間の大きさに対して線形にスケールするクエリー数を必要とするのに対し、 $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：量子ハードウェア実行に向けた問題の最適化

Qiskit primitives を使用して実行する

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

理解度チェック

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

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

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

ステップ3: Qiskit primitivesを使用して実行する

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

理解度チェック

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

ステップ 1:

重要な概念：

質問

正誤問題：

MCの質問：

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

ステップ3: `Qiskit primitives`を使用して実行する