{
"cells": [
{
"cell_type": "markdown",
"id": "7e5d320e",
"metadata": {},
"source": [
"---\n",
"title: \"ドイッチュのアルゴリズム\"\n",
"description: \"量子情報と量子計算に関する無料の IBM 講座\"\n",
"---\n",
"\n",
"\n",
"\n",
"# ドイッチュのアルゴリズム\n",
"\n",
"Deutschのアルゴリズムは、次のような特殊な場合のパリティ問題を解きます。 $n = 1.$ 量子コンピュータの文脈では、この問題は *Deutschの*問題と呼ばれることがあり、このレッスンでもその呼び方に従います。\n",
"\n",
"正確には、入力は1ビットから1ビットへの関数（ $f:\\Sigma \\rightarrow \\Sigma$ ）で表される。\n",
"このような機能は4つある：\n",
"\n",
"$$\n",
"\\rule[-10mm]{0mm}{10mm}\n",
"\\begin{array}{c|c}\n",
" a & f_1(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_2(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_3(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_4(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"$$\n",
"\n",
"これらの関数の最初と最後は*定数で*あり、真ん中の2つは*釣り合いが取れて*いる。つまり、関数の2つの可能な出力値は、入力を範囲指定したときに同じ回数だけ発生する。\n",
"ドイッチュの問題は、入力関数がこの2つのカテゴリーのどちらに属するかを決定することである。\n",
"\n",
"\n",
" 入力：関数 $f:\\{0,1\\}\\rightarrow\\{0,1\\}$ \\ 出力： $f$ が定数なら $0$, $f$ が釣り合いなら $1$\n",
"\n",
"\n",
"ドイチュの問題の入力関数 $f$ を文字列へのランダムアクセスと見なせば、2ビットの文字列を考えていることになる： $f(0)f(1).$\n",
"\n",
"$$\n",
"\\begin{array}{cc}\n",
"\\mathsf{function} & \\mathsf{string}\\\\\n",
"\\hline\n",
"f_1 & 00 \\\\\n",
"f_2 & 01 \\\\\n",
"f_3 & 10 \\\\\n",
"f_4 & 11\n",
"\\end{array}\n",
"$$\n",
"\n",
"このように考えると、ドイッチュの問題は、2つのビットのパリティ（あるいは等価的に排他的論理和）を計算することである。\n",
"\n",
"この問題を正しく解く古典的なクエリーアルゴリズムは、 $f(0)$ と の両方のビットをクエリーしなければならない。 $f(1).$ 例えば、 $f(1) = 1,$ を知ったとしても、 $f(0) = 1$ か $f(0) = 0,$ かによって、答えは $0$ か $1,$ になる。\n",
"2つのビットのうち1つだけを知っても、そのパリティについてはまったく情報が得られないのだ。\n",
"つまり、前節で説明したブール回路は、この問題を解くのに必要なクエリーの数という点で、私たちができる最善のものなのだ。\n",
"\n",
"\n",
"\n",
"## 量子回路記述\n",
"\n",
"Deutschのアルゴリズムは、単一のクエリーを用いてDeutschの問題を解くため、古典的な計算に対する量子の定量的な利点を提供する。\n",
"これはささやかな利点かもしれない。\n",
"科学の進歩は時として、一見地味な起源を持つ。\n",
"\n",
"ドイッチュのアルゴリズムを説明する量子回路を紹介しよう：\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"## 解析\n",
"\n",
"Deutschのアルゴリズムを解析するために、上の回路の動作をトレースし、この図が示唆する時間における量子ビットの状態を特定する：\n",
"\n",
"\n",
"\n",
"初期状態は $\\vert 1\\rangle \\vert 0 \\rangle,$、回路の左辺にある2つのハダマード演算は、この状態を次のように変換する\n",
"\n",
"$$\n",
"\\vert \\pi_1 \\rangle = \\vert - \\rangle \\vert + \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 0\\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 1\\rangle.\n",
"$$\n",
"\n",
"(いつものように、Qiskitの量子ビットの並び順の規則に従っている。上の量子ビットを右に、下の量子ビットを左に置く) この積の状態を部分的に分散して書くのは直感的でないと感じるかもしれないが（量子ビット1の状態を因数分解したままにしておく）、こうすることで後の式がよりコンパクトになる。\n",
"\n",
"次に、 $U_f$。\n",
"$U_f$ ゲートの定義によれば、一番上/右端の量子ビットの古典的状態に対する関数 $f$ の値が一番下/左端の量子ビットにXORされ、 $\\vert \\pi_1\\rangle$ が次の状態に変換される\n",
"\n",
"$$\n",
"\\vert \\pi_2 \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(0) \\rangle - \\vert 1 \\oplus f(0) \\rangle \\bigr) \\vert 0 \\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(1) \\rangle - \\vert 1 \\oplus f(1) \\rangle \\bigr) \\vert 1 \\rangle.\n",
"$$\n",
"\n",
"この式を単純化するには、次の式を使用する\n",
"\n",
"$$\n",
"\\vert 0 \\oplus a\\rangle - \\vert 1 \\oplus a\\rangle = (-1)^a \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"$$\n",
"\n",
"の両方の可能な値に対して機能する。 $a\\in\\Sigma.$ より明確には、2つのケースは以下の通りである。\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert 0 \\oplus 0\\rangle - \\vert 1 \\oplus 0\\rangle\n",
"& = \\vert 0 \\rangle - \\vert 1 \\rangle\n",
"= (-1)^0 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\\\\\n",
"\\vert 0 \\oplus 1\\rangle - \\vert 1 \\oplus 1\\rangle & = \\vert 1 \\rangle - \\vert 0\\rangle\n",
"= (-1)^1 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"したがって、 $\\vert\\pi_2\\rangle$ を次のように表現することもできる：\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = \\frac{1}{2} (-1)^{f(0)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 0 \\rangle\n",
" + \\frac{1}{2} (-1)^{f(1)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 1 \\rangle \\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"面白いことが起きた！\n",
"標準的な基底状態に対する $U_f$ ゲートの動作は、一番上/右端の量子ビットはそのままにしておき、一番下/左端の量子ビットに関数値をXORします。しかし、ここでは、一番上/右端の量子ビットの状態が（一般的に）変化している一方で、一番下/左端の量子ビットの状態は同じままであることがわかります。具体的には、 $U_f$ ゲートが実行される前と後では、 $\\vert - \\rangle$ の状態になっています。\n",
"この現象は*フェイズ・キックバックとして*知られており、これについては後ほど詳しく説明する。\n",
"\n",
"最後の単純化として、 $(-1)^{f(0)}$ の因子を和の外側に引っ張り出すことで、状態 $\\vert\\pi_2\\rangle$ の式が得られる：\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = (-1)^{f(0)} \\vert - \\rangle\n",
" \\biggl( \\frac{\\vert 0\\rangle + (-1)^{f(0) \\oplus f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr) \\\\\n",
" & = \\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert + \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert - \\rangle & \\text{if $f(0) \\oplus f(1) = 1$}.\n",
" \\end{cases}\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"この式では、純粋に代数的な観点から予想される $f(1) - f(0),$ とは対照的に、 $-1$ の指数に $f(0) \\oplus f(1)$ が使われていることに注目してほしい。\n",
"これは、任意の整数 $k$ に対する値 $(-1)^k$ が、 $k$ が偶数か奇数かにのみ依存するからである。\n",
"\n",
"最後のハダマードゲートをトップ量子ビットに適用すると、次のような状態になる\n",
"\n",
"$$\n",
"\\vert \\pi_3 \\rangle =\n",
"\\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 0 \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 1 \\rangle & \\text{if $f(0) \\oplus f(1) = 1$},\n",
"\\end{cases}\n",
"$$\n",
"\n",
"右/一番上の量子ビットが測定されたとき、確率 $1$、正しい結果を導く。\n",
"\n",
"\n",
"\n",
"## 位相キックバックに関する補足説明\n",
"\n",
"次に進む前に、位相のキックバック現象を解明するために、上記の分析を少し違った角度から見てみよう。\n",
"\n",
"まず、以下の式がすべてのビットの選択に対して有効であることに注目してほしい。 $b,c\\in\\Sigma.$\n",
"\n",
"$$\n",
"\\vert b \\oplus c\\rangle = X^c \\vert b \\rangle\n",
"$$\n",
"\n",
"これは、 $c = 0$ と $c = 1$ の2つの可能な値についてチェックすることで検証できる：\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert b \\oplus 0 \\rangle & = \\vert b\\rangle = \\mathbb{I} \\vert b \\rangle = X^0 \\vert b \\rangle\\\\\n",
"\\vert b \\oplus 1 \\rangle & = \\vert \\neg b\\rangle = X \\vert b \\rangle = X^1 \\vert b \\rangle.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"この式を使うと、次のようになる\n",
"\n",
"$$\n",
"U_f \\bigl(\\vert b\\rangle \\vert a \\rangle\\bigr)\n",
"= \\vert b \\oplus f(a) \\rangle \\vert a \\rangle\n",
"= \\bigl(X^{f(a)}\\vert b \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"あらゆるビットの選択に対して $a,b\\in\\Sigma.$ この式は $b=0$ と $b=1,$ について成り立つので、線形性によって次のことがわかる。\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert \\psi \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)}\\vert \\psi \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"すべての量子ビット状態ベクトルについて $\\vert \\psi\\rangle,$、したがって\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert - \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)} \\vert - \\rangle \\bigr) \\vert a \\rangle\n",
"= (-1)^{f(a)} \\vert - \\rangle \\vert a \\rangle.\n",
"$$\n",
"\n",
"この機能を実現する鍵は以下の通りである。 $X\\vert - \\rangle = - \\vert - \\rangle.$ 数学用語で言えば、ベクトル $\\vert - \\rangle$ は、 *固有値を*持つ行列 $X$ の*固有ベクトル*である。 $-1.$\n",
"\n",
"固有ベクトルと固有値については、次回の「 *位相推定と因数分解* 」のレッスンでさらに詳しく説明します。このレッスンでは、位相キックバック現象を他のユニタリー演算に一般化します。\n",
"\n",
"スカラーはテンソル積を通して自由に浮遊することを念頭に置いて、上記の分析において、 $U_f$ という演算が $\\vert \\pi_1\\rangle$ を $\\vert \\pi_2\\rangle$ に変換する方法を推論する別の方法を見つける：\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert \\pi_2 \\rangle\n",
" & = U_f \\bigl( \\vert - \\rangle \\vert + \\rangle \\bigr)\\\\\n",
" & = \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 0\\rangle \\bigr)\n",
" + \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 1\\rangle \\bigr)\\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "d0cff57e",
"metadata": {},
"source": [
"\n",
"\n",
"## Qiskitでの実装\n",
"\n",
"では、DeutschのアルゴリズムをQiskitでどのように実装できるかを見てみよう。 まずはバージョンチェックから始め、この実装だけに必要なインポートを実行する。\n",
"この後に続く他のアルゴリズムの実装については、モジュール性を高めるために、必要なインポートを個別に行うことにする。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "baa9bc2c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.1.1\n"
]
}
],
"source": [
"from qiskit import __version__\n",
"\n",
"print(__version__)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0a706449",
"metadata": {},
"outputs": [],
"source": [
"from qiskit import QuantumCircuit\n",
"from qiskit_aer import AerSimulator"
]
},
{
"cell_type": "markdown",
"id": "0af39df9",
"metadata": {},
"source": [
"まず、先に説明した1ビットから1ビットへの4つの関数 $f_1,$ $f_2,$ $f_3,$ $f_4$ のうちの1つに対するクエリーゲートを実装する量子回路を定義する。 すでに述べたように、クエリゲートの実装はドイチュのアルゴリズムそのものではない； ここでは基本的に、クエリーゲートの回路実装という形で、入力を準備する一つの方法を示しているに過ぎない。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "ba5a708f",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_function(case: int):\n",
" # This function generates a quantum circuit for one of the 4 functions\n",
" # from one bit to one bit\n",
"\n",
" if case not in [1, 2, 3, 4]:\n",
" raise ValueError(\"`case` must be 1, 2, 3, or 4.\")\n",
"\n",
" f = QuantumCircuit(2)\n",
" if case in [2, 3]:\n",
" f.cx(0, 1)\n",
" if case in [3, 4]:\n",
" f.x(1)\n",
" return f"
]
},
{
"cell_type": "markdown",
"id": "46eccf09",
"metadata": {},
"source": [
"`draw` 、各回路がどのように見えるかを見ることができる。 この機能の回路は以下の通りである。 $f_3.$\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "787e3c81",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(deutsch_function(3).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "b6fa5b7b",
"metadata": {},
"source": [
"次に、クエリーゲートを引数として与えられた量子回路実装に置き換えて、ドイチュのアルゴリズムの実際の量子回路を作成する。 まもなく、先に定義した関数 `deutsch_function` で定義された4つの回路のうちの1つを接続する。\n",
"バリアは、クエリーゲートの実装と回路の他の部分との間の視覚的な分離を示すために含まれている。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "379aac92",
"metadata": {},
"outputs": [],
"source": [
"def compile_circuit(function: QuantumCircuit):\n",
" # Compiles a circuit for use in Deutsch's algorithm.\n",
"\n",
" n = function.num_qubits - 1\n",
" qc = QuantumCircuit(n + 1, n)\n",
"\n",
" qc.x(n)\n",
" qc.h(range(n + 1))\n",
"\n",
" qc.barrier()\n",
" qc.compose(function, inplace=True)\n",
" qc.barrier()\n",
"\n",
" qc.h(range(n))\n",
" qc.measure(range(n), range(n))\n",
"\n",
" return qc"
]
},
{
"cell_type": "markdown",
"id": "e5112614",
"metadata": {},
"source": [
"もう一度、 `draw` 。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "27b41067",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(compile_circuit(deutsch_function(3)).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "d24d14eb",
"metadata": {},
"source": [
"最後に、先に定義した回路を1回実行し、適切な結果を出力する関数を作成する：\"コンスタント \"または \"バランス \"である\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "5b31e311",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_algorithm(function: QuantumCircuit):\n",
" # Determine if a one-bit function is constant or balanced.\n",
"\n",
" qc = compile_circuit(function)\n",
"\n",
" result = AerSimulator().run(qc, shots=1, memory=True).result()\n",
" measurements = result.get_memory()\n",
" if measurements[0] == \"0\":\n",
" return \"constant\"\n",
" return \"balanced\""
]
},
{
"cell_type": "markdown",
"id": "3d0868ed",
"metadata": {},
"source": [
"これでDeutschのアルゴリズムを、上で定義した4つの関数のいずれかに対して実行することができる。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "33b8355d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'balanced'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"f = deutsch_function(3)\n",
"display(deutsch_algorithm(f))"
]
},
{
"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
}