{ "cells": [ { "cell_type": "markdown", "id": "37d2b600", "metadata": {}, "source": [ "---\n", "title: \"解析\"\n", "description: \"量子情報と量子計算に関する無料の IBM 講座\"\n", "---\n", "\n", "\n", "\n", "# 解析\n", "\n", "では、グローバーのアルゴリズムを分析し、その仕組みを理解しよう。\n", "私たちはまず、グローバー演算（ $G$ ）が特定の状態に対してどのように作用するかを計算する、 *記号的*解析とでも言うべきものから始める。そして、この記号的解析を、アルゴリズムがどのように機能するかを視覚化するのに役立つ*幾何学的な*図と結びつける。\n", "\n", "\n", "\n", "## 解決策と非解決策\n", "\n", "まず、2組の文字列を定義することから始めよう。\n", "\n", "$$\n", "\\begin{aligned}\n", " A_0 &= \\bigl\\{ x\\in\\Sigma^n : f(x) = 0\\bigr\\} \\\\\n", " A_1 &= \\bigl\\{ x\\in\\Sigma^n : f(x) = 1\\bigr\\}\n", "\\end{aligned}\n", "$$\n", "\n", "集合 $A_1$ には、探索問題に対するすべての解が含まれ、 $A_0$ には、解ではない文字列が含まれる（都合のいいときには、これを*非解と*呼ぶことができる）。\n", "これらの2つのセットは、 $A_0 \\cap A_1 = \\varnothing$ と $A_0 \\cup A_1 = \\Sigma^n,$ *を満たして*いる。 $\\Sigma^n.$\n", "\n", "次に、解と非解の集合に対する一様な重ね合わせを表す2つの単位ベクトルを定義する。\n", "\n", "$$\n", "\\begin{aligned}\n", " \\vert A_0\\rangle &= \\frac{1}{\\sqrt{\\vert A_0\\vert}} \\sum_{x\\in A_0} \\vert x\\rangle \\\\\n", " \\vert A_1\\rangle &= \\frac{1}{\\sqrt{\\vert A_1\\vert}} \\sum_{x\\in A_1} \\vert x\\rangle\n", "\\end{aligned}\n", "$$\n", "\n", "形式的に言えば、これらの各ベクトルは、対応する集合が空でない場合にのみ定義されるが、以下では、 $A_0$ も $A_1$ も空でない場合に焦点を当てる。\n", "$A_0 = \\varnothing$、 $A_1 = \\varnothing$。\n", "\n", "余談だが、ここで使われている表記法は一般的なものだ。有限で空でない集合 $S,$ があるときはいつでも、 $\\vert S\\rangle$ と書けば、 の要素に一様な量子状態ベクトルを表すことができる。 $S.$\n", "\n", "また、 $\\vert u \\rangle$ を、すべての $n$ -bit文字列にわたる*一様な*量子状態と定義しよう：\n", "\n", "$$\n", "\\vert u\\rangle = \\frac{1}{\\sqrt{N}} \\sum_{x\\in\\Sigma^n} \\vert x\\rangle.\n", "$$\n", "\n", "そうすると\n", "\n", "$$\n", "\\vert u\\rangle\n", "= \\sqrt{\\frac{\\vert A_0 \\vert}{N}} \\vert A_0\\rangle\n", "+ \\sqrt{\\frac{\\vert A_1 \\vert}{N}} \\vert A_1\\rangle.\n", "$$\n", "\n", "また、 $\\vert u\\rangle = H^{\\otimes n} \\vert 0^n \\rangle,$、 $\\vert u\\rangle$ は、グローバーのアルゴリズムのステップ1での初期化後のレジスタ $\\mathsf{Q}$ の状態を表している。\n", "\n", "このことは、ステップ2で $G$ の反復が起こる直前に、 $\\mathsf{Q}$ の状態は $\\vert A_0\\rangle$ と $\\vert A_1\\rangle,$ によってスパンされる2次元ベクトル空間に含まれ、さらにこれらのベクトルの係数は実数であることを意味する。\n", "これからわかるように、 $\\mathsf{Q}$ の状態は、ステップ2の操作 $G$ を何回繰り返しても、常にこれらの特性、つまり $\\vert A_0\\rangle$ と $\\vert A_1\\rangle$ の実線型結合を持つ。\n", "\n", "\n", "\n", "## グローバー作戦に関する所見\n", "\n", "次にグローバーの作戦に注目しよう\n", "\n", "$$\n", "G = H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n} Z_f,\n", "$$\n", "\n", "という興味深い見解から始まった。\n", "\n", "関数 $f$ を、 $f$ とNOT関数の合成、言い換えれば、 の出力ビットを反転させることで得られる関数に置き換えたとしよう。 $f.$ この新しい関数を $g,$ と呼ぶことにし、記号を使っていくつかの方法で表現することができる。\n", "\n", "$$\n", "g(x) = \\neg f(x) = 1 \\oplus f(x) = 1 - f(x) =\n", "\\begin{cases}\n", "1 & f(x) = 0\\\\[1mm]\n", "0 & f(x) = 1\n", "\\end{cases}\n", "$$\n", "\n", "そうすると\n", "\n", "$$\n", "(-1)^{g(x)} = (-1)^{1 \\oplus f(x)} = - (-1)^{f(x)}\n", "$$\n", "\n", "すべての文字列に対して $x\\in\\Sigma^n,$、したがって\n", "\n", "$$\n", "Z_g = - Z_f.\n", "$$\n", "\n", "つまり、もし関数 $f$ を関数 $g,$ で置き換えたとしても、グローバーのアルゴリズムは何も変わらないということだ。なぜなら、この2つのケースでアルゴリズムから得られる状態は、大局的な位相までは必ず等価だからである。\n", "\n", "これは問題ない！\n", "直感的に言えば、アルゴリズムはどの文字列が解でどの文字列が非解であるかを気にしません。正しく動作するために解と非解を*区別*できれば十分です。\n", "\n", "\n", "\n", "## グローバー作戦の行動\n", "\n", "ここで、量子状態ベクトル $\\vert A_0\\rangle$ と $G$ の作用を考えてみよう。 $\\vert A_1\\rangle.$\n", "\n", "まず、 $Z_f$ という操作が、 $\\vert A_0\\rangle$ と $\\vert A_1\\rangle.$\n", "\n", "$$\n", "\\begin{aligned}\n", "Z_f \\vert A_0\\rangle & = \\vert A_0\\rangle \\\\[1mm]\n", "Z_f \\vert A_1\\rangle & = -\\vert A_1\\rangle\n", "\\end{aligned}\n", "$$\n", "\n", "次に、次の操作がある。 $H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n}.$ 演算 $Z_{\\mathrm{OR}}$ は次のように定義される。\n", "\n", "$$\n", "Z_{\\mathrm{OR}} \\vert x\\rangle\n", "= \\begin{cases}\n", "\\vert x\\rangle & x = 0^n \\\\[2mm]\n", "-\\vert x\\rangle & x \\neq 0^n,\n", "\\end{cases}\n", "$$\n", "\n", "$x\\in\\Sigma^n,$、この操作を表す便利な代替方法は次のようなものだ：\n", "\n", "$$\n", "Z_{\\mathrm{OR}} = 2 \\vert 0^n \\rangle \\langle 0^n \\vert - \\mathbb{I}.\n", "$$\n", "\n", "この式が $Z_{\\mathrm{OR}}$ の定義と一致していることを確認する簡単な方法は、標準的な基底状態に対する作用を評価することである。\n", "\n", "したがって、 $H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n}$ ：\n", "\n", "$$\n", "H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n} = 2 H^{\\otimes n} \\vert 0^n \\rangle \\langle 0^n \\vert H^{\\otimes n} - \\mathbb{I} = 2 \\vert u \\rangle \\langle u \\vert - \\mathbb{I},\n", "$$\n", "\n", "$n$ -bitの文字列を一様に重ね合わせる場合に使用したのと同じ表記法、 $\\vert u \\rangle,$。\n", "\n", "これで、 $\\vert A_0\\rangle$ に対する $G$ の作用を計算するのに必要なものが揃った。 $\\vert A_1\\rangle.$ まず、 $G$。 $\\vert A_0\\rangle.$\n", "\n", "$$\n", "\\begin{aligned}\n", " G \\vert A_0 \\rangle\n", " & = \\bigl( 2 \\vert u\\rangle \\langle u \\vert - \\mathbb{I}\\bigr) Z_f \\vert A_0\\rangle \\\\\n", " & = \\bigl( 2 \\vert u\\rangle \\langle u \\vert - \\mathbb{I}\\bigr) \\vert A_0\\rangle \\\\\n", " & = 2 \\sqrt{\\frac{\\vert A_0\\vert}{N}} \\vert u\\rangle -\\vert A_0 \\rangle\\\\\n", " & = 2 \\sqrt{\\frac{\\vert A_0\\vert}{N}} \\biggl(\n", " \\sqrt{\\frac{\\vert A_0\\vert}{N}} \\vert A_0\\rangle + \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\vert A_1\\rangle\\biggr)\n", " -\\vert A_0 \\rangle \\\\\n", " & = \\biggl( \\frac{2\\vert A_0\\vert}{N} - 1\\biggr) \\vert A_0 \\rangle\n", " + \\frac{2 \\sqrt{\\vert A_0\\vert \\cdot \\vert A_1\\vert}}{N} \\vert A_1 \\rangle \\\\\n", " & = \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} \\vert A_0 \\rangle\n", " + \\frac{2 \\sqrt{\\vert A_0\\vert \\cdot \\vert A_1\\vert}}{N} \\vert A_1 \\rangle\n", "\\end{aligned}\n", "$$\n", "\n", "次に、 $G$ の作用を計算してみよう。 $\\vert A_1\\rangle.$\n", "\n", "$$\n", "\\begin{aligned}\n", " G \\vert A_1 \\rangle\n", " & = \\bigl( 2 \\vert u\\rangle \\langle u \\vert - \\mathbb{I} \\bigr) Z_f \\vert A_1\\rangle \\\\\n", " & = - \\bigl( 2 \\vert u\\rangle \\langle u \\vert - \\mathbb{I} \\bigr) \\vert A_1\\rangle \\\\\n", " & = - 2 \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\vert u\\rangle + \\vert A_1 \\rangle \\\\\n", " & = - 2 \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\biggl(\\sqrt{\\frac{\\vert A_0\\vert}{N}} \\vert A_0\\rangle\n", " + \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\vert A_1\\rangle\\biggr) + \\vert A_1 \\rangle \\\\\n", " & = - \\frac{2 \\sqrt{\\vert A_1\\vert \\cdot \\vert A_0\\vert}}{N} \\vert A_0 \\rangle\n", " + \\biggl( 1 - \\frac{2\\vert A_1\\vert}{N} \\biggr) \\vert A_1 \\rangle \\\\\n", " & = - \\frac{2 \\sqrt{\\vert A_1\\vert \\cdot \\vert A_0\\vert}}{N} \\vert A_0 \\rangle\n", " + \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} \\vert A_1 \\rangle\n", "\\end{aligned}\n", "$$\n", "\n", "どちらの場合も、次の方程式を使う\n", "\n", "$$\n", "\\vert u\\rangle\n", "= \\sqrt{\\frac{\\vert A_0 \\vert}{N}} \\vert A_0\\rangle\n", "+ \\sqrt{\\frac{\\vert A_1 \\vert}{N}} \\vert A_1\\rangle\n", "$$\n", "\n", "という表現とともに\n", "\n", "$$\n", "\\langle u \\vert A_0\\rangle = \\sqrt{\\frac{\\vert A_0 \\vert}{N}}\n", "\\qquad\\text{and}\\qquad\n", "\\langle u \\vert A_1\\rangle = \\sqrt{\\frac{\\vert A_1 \\vert}{N}}\n", "$$\n", "\n", "その後に続く。\n", "\n", "要約すると\n", "\n", "$$\n", "\\begin{aligned}\n", " G \\vert A_0 \\rangle\n", " & = \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} \\vert A_0 \\rangle\n", " + \\frac{2 \\sqrt{\\vert A_0\\vert \\cdot \\vert A_1\\vert}}{N} \\vert A_1 \\rangle\\\\[2mm]\n", " G \\vert A_1 \\rangle\n", " & = - \\frac{2 \\sqrt{\\vert A_1\\vert \\cdot \\vert A_0\\vert}}{N} \\vert A_0 \\rangle\n", " + \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} \\vert A_1 \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "すでに述べたように、ステップ2の直前の $\\mathsf{Q}$ の状態は、 $\\vert A_0\\rangle$ と $\\vert A_1\\rangle,$ によってスパンされる2次元空間に含まれており、 $G$ がこの空間内の任意のベクトルを同じ空間内の別のベクトルにマッピングすることを証明したばかりである。\n", "つまり、分析のためには、この部分空間だけに注目すればいいのだ。\n", "\n", "この2次元空間の中で起こっていることをよりよく理解するために、この空間に対する $G$ の作用を行列として表現してみよう、\n", "\n", "$$\n", "M = \\begin{pmatrix}\n", " \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} & -\\frac{2 \\sqrt{\\vert A_1\\vert \\cdot \\vert A_0\\vert}}{N} \\\\[2mm]\n", " \\frac{2 \\sqrt{\\vert A_0\\vert \\cdot \\vert A_1\\vert}}{N} & \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N}\n", "\\end{pmatrix},\n", "$$\n", "\n", "その1行目と2列目はそれぞれ $\\vert A_0\\rangle$ と $\\vert A_1\\rangle,$ に対応している。\n", "このシリーズではこれまで、常に行列の行と列をシステムの古典的な状態と結びつけてきたが、行列は今回のように、異なるベース上の線形写像の作用を記述するためにも使うことができる。\n", "\n", "一見しただけではまったくわからないが、行列 $M$ は、より単純に見える行列を *2乗する*ことで得られるものである。\n", "\n", "$$\n", "\\begin{pmatrix}\n", " \\sqrt{\\frac{\\vert A_0\\vert}{N}} & - \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\\\[2mm]\n", " \\sqrt{\\frac{\\vert A_1\\vert}{N}} & \\sqrt{\\frac{\\vert A_0\\vert}{N}}\n", "\\end{pmatrix}^2\n", "=\n", "\\begin{pmatrix}\n", " \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N} & -\\frac{2 \\sqrt{\\vert A_1\\vert \\cdot \\vert A_0\\vert}}{N} \\\\[2mm]\n", " \\frac{2 \\sqrt{\\vert A_0\\vert \\cdot \\vert A_1\\vert}}{N} & \\frac{\\vert A_0\\vert - \\vert A_1\\vert}{N}\n", "\\end{pmatrix} = M\n", "$$\n", "\n", "マトリックス\n", "\n", "$$\n", "\\begin{pmatrix}\n", " \\sqrt{\\frac{\\vert A_0\\vert}{N}} & - \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\\\[2mm]\n", " \\sqrt{\\frac{\\vert A_1\\vert}{N}} & \\sqrt{\\frac{\\vert A_0\\vert}{N}}\n", "\\end{pmatrix}\n", "$$\n", "\n", "は*回転行列*である\n", "\n", "$$\n", "\\begin{pmatrix}\n", " \\sqrt{\\frac{\\vert A_0\\vert}{N}} & - \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\\\[2mm]\n", " \\sqrt{\\frac{\\vert A_1\\vert}{N}} & \\sqrt{\\frac{\\vert A_0\\vert}{N}}\n", "\\end{pmatrix}\n", "=\n", "\\begin{pmatrix}\n", " \\cos(\\theta) & -\\sin(\\theta) \\\\[2mm]\n", " \\sin(\\theta) & \\cos(\\theta)\n", "\\end{pmatrix}\n", "$$\n", "\n", "の場合\n", "\n", "$$\n", "\\theta = \\sin^{-1}\\biggl(\\sqrt{\\frac{\\vert A_1\\vert}{N}}\\biggr).\n", "$$\n", "\n", "この角度（ $\\theta$ ）は、この後の分析で非常に重要な役割を果たすことになるので、ここで初めてその重要性を強調しておきたい。\n", "\n", "このマトリックスの表現に照らし合わせると、次のようになる\n", "\n", "$$\n", "M = \\begin{pmatrix}\n", " \\cos(\\theta) & -\\sin(\\theta) \\\\[2mm]\n", " \\sin(\\theta) & \\cos(\\theta)\n", "\\end{pmatrix}^2\n", "= \\begin{pmatrix}\n", " \\cos(2\\theta) & -\\sin(2\\theta) \\\\[2mm]\n", " \\sin(2\\theta) & \\cos(2\\theta)\n", "\\end{pmatrix}.\n", "$$\n", "\n", "これは、 $\\theta$ の角度で2回回転することは、 の角度で回転することと等価だからである。 $2\\theta.$ このことを理解するもう一つの方法は、次のような代替表現を使うことである。\n", "\n", "$$\n", "\\theta\n", "= \\cos^{-1}\\biggl(\\sqrt{\\frac{\\vert A_0\\vert}{N}}\\biggr),\n", "$$\n", "\n", "を三角法の*二重角度の*公式と合わせて使う：\n", "\n", "$$\n", "\\begin{aligned}\n", "\\cos(2\\theta) & = \\cos^2(\\theta) - \\sin^2(\\theta)\\\\[1mm]\n", "\\sin(2\\theta) & = 2 \\sin(\\theta)\\cos(\\theta).\n", "\\end{aligned}\n", "$$\n", "\n", "要約すると、ステップ2の開始時のレジスタ $\\mathsf{Q}$ の状態は次のようになる\n", "\n", "$$\n", "\\vert u\\rangle\n", "= \\sqrt{\\frac{\\vert A_0\\vert}{N}} \\vert A_0\\rangle\n", "+ \\sqrt{\\frac{\\vert A_1\\vert}{N}} \\vert A_1\\rangle\n", "= \\cos(\\theta) \\vert A_0\\rangle + \\sin(\\theta) \\vert A_1\\rangle,\n", "$$\n", "\n", "そして、この状態に $G$ を適用する効果は、 $\\vert A_0\\rangle$ と $2\\theta$ でスパンされる空間内で角度 だけ回転させることである。 $\\vert A_1\\rangle.$ したがって、例えば\n", "\n", "$$\n", "\\begin{aligned}\n", "G \\vert u \\rangle &= \\cos(3\\theta) \\vert A_0\\rangle + \\sin(3\\theta) \\vert A_1\\rangle\\\\[1mm]\n", "G^2 \\vert u \\rangle &= \\cos(5\\theta) \\vert A_0\\rangle + \\sin(5\\theta) \\vert A_1\\rangle\\\\[1mm]\n", "G^3 \\vert u \\rangle &= \\cos(7\\theta) \\vert A_0\\rangle + \\sin(7\\theta) \\vert A_1\\rangle\n", "\\end{aligned}\n", "$$\n", "\n", "そして一般的に\n", "\n", "$$\n", "G^t \\vert u \\rangle\n", "= \\cos\\bigl((2t + 1)\\theta\\bigr) \\vert A_0\\rangle\n", "+ \\sin\\bigl((2t + 1)\\theta\\bigr) \\vert A_1\\rangle.\n", "$$\n", "\n", "\n", "\n", "## 幾何学的な絵\n", "\n", "さて、先ほどの分析を幾何学的な絵に繋げてみよう。\n", "$G$ は2つの*反射の*積である、 $Z_f$ そして $H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n}.$ そして、2つの反射を行う正味の効果は*回転を*行うことである。\n", "\n", "始めよう $Z_f.$ すでに述べたように\n", "\n", "$$\n", "\\begin{aligned}\n", "Z_f \\vert A_0\\rangle & = \\vert A_0\\rangle \\\\[1mm]\n", "Z_f \\vert A_1\\rangle & = -\\vert A_1\\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "によってスパンされる2次元ベクトル空間内で、 $\\vert A_0\\rangle$ と $\\vert A_1\\rangle,$ $\\vert A_0\\rangle,$ に平行な線に対する*反射*である。 $L_1.$ この反射が、仮想的な単位ベクトル $\\vert\\psi\\rangle,$ $\\vert A_0\\rangle$ の実線型結合であると仮定する。 $\\vert A_1\\rangle.$\n", "\n", "![ベクトルに対する反射の作用を表した図。](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/reflection1.svg)\n", "\n", "次に、 $H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n},$ という操作がある\n", "\n", "$$\n", "H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n} = 2 \\vert u \\rangle \\langle u \\vert - \\mathbb{I}.\n", "$$\n", "\n", "これも反射であり、今度はベクトルに平行な線 $L_2$。 $\\vert u\\rangle.$ 単位ベクトルに対するこの反射の作用を表した図がこれだ。 $\\vert\\psi\\rangle.$\n", "\n", "![ベクトルに対する2回目の反射の作用を表した図。](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/reflection2.svg)\n", "\n", "これらの2つの反射を合成すると、この図が示すように、反射線間の角度の2倍の回転が得られる。\n", "\n", "![ベクトルに対するグローバー演算の作用を表した図。](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/Grover_rotation.svg)\n", "\n", "このことは、幾何学的な用語で、なぜグローバー・オペレーションの効果が、 $\\vert A_0\\rangle$ と $\\vert A_1\\rangle$ の直線的な組み合わせを、以下の角度だけ回転させることになるのかを説明している。 $2\\theta.$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }