Created
December 9, 2018 06:19
-
-
Save lightondust/f09d330d8ac1f24f107f6061c2dd5e57 to your computer and use it in GitHub Desktop.
play_network/src/quantum_computing/cirq-tuto.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# Cirqで動かしながら学ぶ、量子コンピュータ入門" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "この記事では実際にプログラムで動かしながら量子コンピュータの基本的なことについて説明していきます。目指す対象は\n- 量子力学も量子情報も詳しくないけれど、量子コンピュータが速いと言われているが、それはなぜなのか、そして現在どういう問題があって実現できなくて、またこれからどういう発展ができそうか、などについて自分なりの感覚を持つようになるために必要となる基礎を知りたい人 \n- 理論物理のバックグランドがあって量子力学はよく知っているけれど量子情報を全然知らないので、ざっくりとした感覚を掴みたい人 \n\nの両方です。\n前半は数学も物理も必要としないように努力しました。\n後半は量子力学の基本的な枠組がわかることを仮定しています。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# Cirqについて" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "[Cirq](https://github.com/quantumlib/Cirq)はgoogleから今年の7月に公開した量子コンピュータのフレームワークです。\n[ここ](https://ai.googleblog.com/2018/07/announcing-cirq-open-source-framework.html)によりますとNISQをサポートする、らしい。\n\n量子コンピュータというと素因数分解を古典コンピュータより指数的に早く解くショアのアルゴリズムが有名ですが、最近は量子サポートベクターマシンや量子カーネル法なども提唱されていて夢が広がっております。が、これらのアルゴリズムの多くは一定の精度を得るためにたくさんの量子ゲートが必要で、量子ゲートごとにノイズが重なるため、現在の技術で実用するのが難しいとされています。\n\nそこで、ノイズとうまく付き合ってなんとか近いうちに作れる量子コンピュータで古典コンピュータでは計算できない問題を解いてしまおう、と頑張るのはNISQ(Noisy Intermediate Scale Quantum)です。\n\nNISQで活躍が期待される量子化学計算の[OpenFermion](https://github.com/quantumlib/OpenFermion)をCirq拡張した[OpenFermion-Cirq](https://github.com/quantumlib/OpenFermion-Cirq)も発表されたり、[量子オートエンコーダ](https://github.com/zapatacomputing/cusp_cirq_demo/)のサンプルコードが公開されたり、いろいろワクワクする話が出ています。\n\nと、盛り上がったところで、今回はこれらの高度な話に入らず(すいません)、Cirqを動かしながら量子コンピュータがなぜすごいか、ナニが難しいか、の基礎的な部分について解説していきます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# ライブラリのインストールとインポート" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "[こちら](https://cirq.readthedocs.io/en/latest/install.html)\nに従い、`pip install ほにゃらら`で入るかと思います。注意すべきなのは、Cirqが執筆時点でアルファ版なので、バージョンによってはソースコードが動かないことがあります。こちらで使っているのは0.3.1.35です。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "import cirq\nimport numpy as np\nimport matplotlib.pyplot as plt\n\ncirq.__version__", | |
"execution_count": 46, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "'0.3.1.35'" | |
}, | |
"execution_count": 46, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# hello qubit" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "量子コンピュータは0と1の状態を持った量子ビット(quantum bit, qubit)の集まりで計算します。\nこんな感じで一個作ってみます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "qubit = cirq.GridQubit(0, 0)", | |
"execution_count": 2, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "(0,0)の引数は量子ビットを二次元で並べるためにあるものです(NISQなど実際のデバイスを連想してしまいます)。量子コンピュータで計算をするときは量子ビットに様々な操作を加えて全体として一つの回路を作りますが、その一連の操作をcircuitで定義します。最初なので、とりあえずテキトーになんかやって測定する回路を作ってみます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# Create a circuit\ncircuit = cirq.Circuit.from_ops(\n cirq.RotXGate(half_turns=0.2)(qubit), \n cirq.measure(qubit, key='m') # Measurement.\n)", | |
"execution_count": 3, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "RotXGateはテキトーなナニかで($e^{i\\theta \\hat{X}}$みたいなもの)、とりあえずは気にしません。肝心なのは量子コンピュータとはいえ、最後の結果を得るには測定が必要であり、それが最後の`cirq.measure`で、引数の`key`はなんでもいいみたいです。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "print(\"Circuit:\")\nprint(circuit)", | |
"execution_count": 4, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Circuit:\n(0, 0): ───X^0.2───M('m')───\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "回路ができたので、走らせます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# Simulate the circuit several times.\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.run(circuit, repetitions=200)", | |
"execution_count": 5, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "量子力学の世界ではものごとが確率的に決まっているので、結果を知るには何度も測定します。その回数を`repetitions`で渡します。さあ、結果を見てみましょう。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "print(\"Results:\")\nprint(result)", | |
"execution_count": 6, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Results:\nm=00000000000000010001000000000001000000000000000000000000100000000100000000000000000000000000000001000000000000010001000100010000000000001000000000001000000010000000000000000000000000000100000000000000\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ここでは、一個一個の数字が一回一回の測定結果に対応していおり、測定のたびに結果が異なるのが見て取れると思います。実行結果について集計すると次のようになります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "result.histogram(key='m')", | |
"execution_count": 7, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "Counter({0: 186, 1: 14})" | |
}, | |
"execution_count": 7, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "測定前の量子ビットの状態は、0と1がおおよそ次の比率で入っていることがわかります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "res_count = result.histogram(key='m')\nres_count[0]/res_count[1]", | |
"execution_count": 8, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "13.285714285714286" | |
}, | |
"execution_count": 8, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ちなみに理論値はこんな感じです(わからない人は気にしないでください)。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "np.tan(0.2*0.5*np.pi)**(-2)", | |
"execution_count": 9, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "9.472135954999581" | |
}, | |
"execution_count": 9, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# qubitを動かす:量子ゲート" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "量子ビットを操作する手段が様々ありますが、ここではアダマールゲートと$\\hat{X}$ゲートを使ってみます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "アダマールゲート" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "qubit = cirq.GridQubit(0, 0)\n# Create a circuit\ncircuit = cirq.Circuit.from_ops(\n cirq.H(qubit), \n cirq.measure(qubit, key='m') # Measurement.\n)\n\nprint(\"Circuit:\")\nprint(circuit)", | |
"execution_count": 10, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Circuit:\n(0, 0): ───H───M('m')───\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "実行結果" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# Simulate the circuit several times.\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.run(circuit, repetitions=200)\n\nprint(\"Results:\")\nprint(result)", | |
"execution_count": 11, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Results:\nm=01110101110000101110100000011101000101110100101010011111011100011110100101100000011011000010001001111110000010101100100100101111110000110011010011000000110010010101110000111110100000101100110011011000\n" | |
} | |
] | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "result.histogram(key='m')", | |
"execution_count": 12, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "Counter({0: 105, 1: 95})" | |
}, | |
"execution_count": 12, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "アダマールゲートは次のような式で表現されます(式がわからなくても大丈夫です)。\n$$\\hat{H} \\ |0 \\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle + |1\\rangle)$$\n$$\\hat{H} \\ |1 \\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)$$\n肝心なことは\n- アダマールゲートは0の状態も1の状態も0と1が半分ずつ混ざった状態しすること\n- アダマールゲートを二回作用させると、量子ビットの状態が元に戻る\n二点です。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "次に$\\hat{X}$ゲート" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "qubit = cirq.GridQubit(0, 0)\n# Create a circuit\ncircuit = cirq.Circuit.from_ops(\n cirq.X(qubit), \n cirq.measure(qubit, key='m') # Measurement.\n)\n\nprint(\"Circuit:\")\nprint(circuit)", | |
"execution_count": 13, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Circuit:\n(0, 0): ───X───M('m')───\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "実行結果" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# Simulate the circuit several times.\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.run(circuit, repetitions=200)\n\nprint(\"Results:\")\nprint(result)", | |
"execution_count": 14, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Results:\nm=11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "おおよその比率" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "result.histogram(key='m')", | |
"execution_count": 15, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "Counter({1: 200})" | |
}, | |
"execution_count": 15, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$\\hat{X}$ゲートは0と1の状態を入れ替え、二回作用するともとに戻ります。数式で表現する場合は状態ベクトルの定義によっては書き方が異なることがあります。\n$$\\hat{X} \\ |0 \\rangle = |1\\rangle$$\n$$\\hat{X} \\ |1 \\rangle = |0\\rangle$$\nと書かれる場合もあれば、\n$$\\hat{X} \\ |0 \\rangle = -i \\ |1\\rangle$$\n$$\\hat{X} \\ |1 \\rangle = i \\ |0\\rangle$$\nと書かれる場合もあるようです。シミュレーターではどちらで実装されているかは`simulator.simulate`を使って確認できます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "qubit = cirq.GridQubit(0, 0)\n# Create a circuit\ncircuit = cirq.Circuit.from_ops(\n cirq.X(qubit), \n# cirq.X(qubit) \n)\n\nprint(\"Circuit:\")\nprint(circuit)", | |
"execution_count": 16, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Circuit:\n(0, 0): ───X───\n" | |
} | |
] | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# Simulate the circuit several times.\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.simulate(circuit)\n\nresult.final_state", | |
"execution_count": 17, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "array([6.123234e-17+0.j, 0.000000e+00-1.j], dtype=complex64)" | |
}, | |
"execution_count": 17, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "後者だったようです。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# 多ビット量子状態と量子優越性" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "アダマールゲートを作用させるともともと0か1の状態にある量子ビットが0と1が半分ずつ混ざった状態になることを確認しました。この0と1が混ざる状態を取れることが量子コンピュータの強さの本質です。以下それを具体的に見ていきます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "def get_result_list(result):\n res_hist = result.histogram(key='m')\n res_state = list(res_hist.keys())\n res_state.sort()\n res_list = [[state, res_hist[state]] for state in res_state]\n return np.array(res_list)", | |
"execution_count": 18, | |
"outputs": [] | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "n_qubits = 5\nn_samples = 5000\n\nqubits = [cirq.GridQubit(i, 0) for i in range(n_qubits)]\n\ncircuit = cirq.Circuit()\nsimulator = cirq.google.XmonSimulator()\n\ncircuit.append(cirq.H.on(q) for q in qubits)\n\ncircuit.append(cirq.measure(*qubits , key='m'))\nresult = simulator.run(circuit, repetitions=n_samples)\n\nres_list = get_result_list(result)", | |
"execution_count": 19, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ここで量子ビットを五個用意して、それぞれの量子ビットにアダマールゲートを作用させてから測定してみます。結果は次のようになります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "plt.figure(figsize=(12,9))\nplt.bar(res_list[:,0], res_list[:,1])", | |
"execution_count": 20, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "<BarContainer object of 32 artists>" | |
}, | |
"execution_count": 20, | |
"metadata": {}, | |
"output_type": "execute_result" | |
}, | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAskAAAIMCAYAAAAHEDHqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAGJBJREFUeJzt3X2MZXd93/HPtzZJKxIJU08tC7xdiBwqiFJDVpQqD6KhSXmIYqgiF6slDqFdIoFE1EitQ6VCU0Wy0pBUUVsjIyyMRAw05knCbbEQCkUKBJs4xmAIhi7ClrEdaHhoIlrDt3/MMZl8Netdz7137nr39ZJGc+7vnjP356O7u2+fOfec6u4AAAB/6a9tewIAAHCmEckAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCcv+0JJMmFF17YR48e3fY0AAA4y912221/2t07p1rvjIjko0eP5tZbb932NAAAOMtV1RdPZz2nWwAAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwHDKSK6qS6rqQ1X16ar6VFW9Zhl/YlXdUlWfW75fsIxXVf1OVd1dVXdU1bM2/R8BAADrdDpHkh9K8ivd/fQkz0nyqqp6epKrk3ywuy9N8sHlcZK8IMmly9fxJNeufdYAALBBp4zk7r6vuz+xLH8jyV1JnpTk8iQ3LKvdkOTFy/LlSd7auz6a5AlVdfHaZw4AABvyqM5JrqqjSZ6Z5GNJLuru+5anvpzkomX5SUm+tGeze5YxAAB4TDj/dFesqu9LclOSX+7ur1fVd5/r7q6qfjQvXFXHs3s6Ro4cOfJoNgWAlRy9+v0H3vbENS9a40yAM9VpHUmuqsdlN5Df1t3vWobvf/g0iuX7A8v4vUku2bP5k5exv6K7r+vuY919bGdn56DzBwCAtTudq1tUkjcnuau7f2vPU+9LctWyfFWS9+4Z//nlKhfPSfK1PadlAADAGe90Trf40SQvS/LJqrp9GXttkmuSvLOqXpHki0muWJ67OckLk9yd5M+TvHytMwYAgA07ZSR390eS1Emeft4+63eSV604LwAA2Bp33AMAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgOGUkVxV11fVA1V1556xd1TV7cvXiaq6fRk/WlV/see5N25y8gAAsAnnn8Y6b0nyn5K89eGB7v4nDy9X1RuSfG3P+p/v7svWNUEAADhsp4zk7v5wVR3d77mqqiRXJPnJ9U4LAAC2Z9Vzkn88yf3d/bk9Y0+pqj+qqt+vqh9f8ecDAMChO53TLR7JlUlu3PP4viRHuvsrVfUjSd5TVc/o7q/PDavqeJLjSXLkyJEVpwHAOhy9+v0H3vbENS9a40wAtuvAR5Kr6vwk/zjJOx4e6+5vdfdXluXbknw+yQ/ut313X9fdx7r72M7OzkGnAQAAa7fK6Rb/MMlnuvuehweqaqeqzluWn5rk0iRfWG2KAABwuE7nEnA3JvmDJE+rqnuq6hXLUy/NXz3VIkl+IskdyyXhfi/JL3X3V9c5YQAA2LTTubrFlScZ/4V9xm5KctPq0wIAgO1xxz0AABhEMgAADCIZAAAGkQwAAMOqNxMBHqPcNALYhlX+7kn8/cPhcSQZAAAGkQwAAINIBgCAQSQDAMBwzn9w70z98NKZOi8AgHOBI8kAADCc80eSAeBM4beIcOZwJBkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAZ33IPHEHfjAoDD4UgyAAAMjiQDAKyZ3/w99jmSDAAAgyPJnDX8XzsAsC6OJAMAwCCSAQBgcLoFbJjTQGB1q/w5SvxZAh49R5IBAGBwJBngMc5vKwDWz5FkAAAYRDIAAAwiGQAABpEMAACDD+4BnKZ1fkDOh+2A0+Xvi+1wJBkAAAZHkgEAeNTO9iPcjiQDAMDgSPIane3/RwUAPLZpldPnSDIAAAwiGQAABqdbAMBZyK/VHz37jL0cSQYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAynjOSqur6qHqiqO/eMvb6q7q2q25evF+557ler6u6q+mxV/aNNTRwAADbldI4kvyXJ8/cZ/+3uvmz5ujlJqurpSV6a5BnLNv+lqs5b12QBAOAwnPJmIt394ao6epo/7/Ikb+/ubyX5X1V1d5JnJ/mDA88QtsAF5QHg3LbKOcmvrqo7ltMxLljGnpTkS3vWuWcZAwCAx4yD3pb62iT/Pkkv39+Q5BcfzQ+oquNJjifJkSNHDjgNTscqR0WTzR0ZPVPnBfBo+M0TnJ0OdCS5u+/v7m9393eSvCm7p1Qkyb1JLtmz6pOXsf1+xnXdfay7j+3s7BxkGgAAsBEHiuSqunjPw5ckefjKF+9L8tKq+t6qekqSS5P84WpTBACAw3XK0y2q6sYkz01yYVXdk+R1SZ5bVZdl93SLE0lemSTd/amqemeSTyd5KMmruvvbm5k6AABsxulc3eLKfYbf/Ajr/3qSX19lUgAAsE3uuAcAAINIBgCA4aCXgAP4Lpfzg7Oby9xxLnIkGQAABpEMAACDSAYAgEEkAwDA4IN7wFnNB44AOAhHkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADOdvewIAex29+v0rbX/imhetaSYAnMscSQYAgMGRZAA2wm8FgMcyR5IBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMJy/7QkAABzE0avfv9L2J6550ZpmwtnolEeSq+r6qnqgqu7cM/YfquozVXVHVb27qp6wjB+tqr+oqtuXrzducvIAALAJp3O6xVuSPH+M3ZLkh7r7h5P8SZJf3fPc57v7suXrl9YzTQAAODynjOTu/nCSr46xD3T3Q8vDjyZ58gbmBgAAW7GOD+79YpL/tufxU6rqj6rq96vqx9fw8wEA4FCt9MG9qvo3SR5K8rZl6L4kR7r7K1X1I0neU1XP6O6v77Pt8STHk+TIkSOrTAMAANbqwEeSq+oXkvxMkn/a3Z0k3f2t7v7Ksnxbks8n+cH9tu/u67r7WHcf29nZOeg0AABg7Q4UyVX1/CT/KsnPdvef7xnfqarzluWnJrk0yRfWMVEAADgspzzdoqpuTPLcJBdW1T1JXpfdq1l8b5JbqipJPrpcyeInkvxaVf2/JN9J8kvd/dV9fzAAAJyhThnJ3X3lPsNvPsm6NyW5adVJAQDANrktNQAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAACG87c9AR5bjl79/pW2P3HNi9Y0EwCAzXEkGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMJxWJFfV9VX1QFXduWfsiVV1S1V9bvl+wTJeVfU7VXV3Vd1RVc/a1OQBAGATTvdI8luSPH+MXZ3kg919aZIPLo+T5AVJLl2+jie5dvVpAgDA4TmtSO7uDyf56hi+PMkNy/INSV68Z/ytveujSZ5QVRevY7IAAHAYVjkn+aLuvm9Z/nKSi5blJyX50p717lnGAADgMWEtH9zr7k7Sj2abqjpeVbdW1a0PPvjgOqYBAABrsUok3//waRTL9weW8XuTXLJnvScvY39Fd1/X3ce6+9jOzs4K0wAAgPVaJZLfl+SqZfmqJO/dM/7zy1UunpPka3tOywAAgDPe+aezUlXdmOS5SS6sqnuSvC7JNUneWVWvSPLFJFcsq9+c5IVJ7k7y50levuY5AwDARp1WJHf3lSd56nn7rNtJXrXKpAAAYJvccQ8AAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAIbzD7phVT0tyTv2DD01yb9N8oQk/yLJg8v4a7v75gPPEAAADtmBI7m7P5vksiSpqvOS3Jvk3UlenuS3u/s31zJDAAA4ZOs63eJ5ST7f3V9c088DAICtWVckvzTJjXsev7qq7qiq66vqgjW9BgAAHIqVI7mqvifJzyb5r8vQtUl+ILunYtyX5A0n2e54Vd1aVbc++OCD+60CAABbsY4jyS9I8onuvj9Juvv+7v52d38nyZuSPHu/jbr7uu4+1t3HdnZ21jANAABYj3VE8pXZc6pFVV2857mXJLlzDa8BAACH5sBXt0iSqnp8kp9K8so9w79RVZcl6SQnxnMAAHDGWymSu/v/JPmbY+xlK80IAAC2zB33AABgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgOH/VH1BVJ5J8I8m3kzzU3ceq6olJ3pHkaJITSa7o7v+96msBAMBhWNeR5H/Q3Zd197Hl8dVJPtjdlyb54PIYAAAeEzZ1usXlSW5Ylm9I8uINvQ4AAKzdOiK5k3ygqm6rquPL2EXdfd+y/OUkF63hdQAA4FCsfE5ykh/r7nur6m8luaWqPrP3ye7uquq50RLUx5PkyJEja5gGAACsx8pHkrv73uX7A0neneTZSe6vqouTZPn+wD7bXdfdx7r72M7OzqrTAACAtVkpkqvq8VX1/Q8vJ/npJHcmeV+Sq5bVrkry3lVeBwAADtOqp1tclOTdVfXwz/rd7v7vVfXxJO+sqlck+WKSK1Z8HQAAODQrRXJ3fyHJ391n/CtJnrfKzwYAgG1xxz0AABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADAeO5Kq6pKo+VFWfrqpPVdVrlvHXV9W9VXX78vXC9U0XAAA27/wVtn0oya909yeq6vuT3FZVtyzP/XZ3/+bq0wMAgMN34Eju7vuS3Lcsf6Oq7krypHVNDAAAtmUt5yRX1dEkz0zysWXo1VV1R1VdX1UXrOM1AADgsKwcyVX1fUluSvLL3f31JNcm+YEkl2X3SPMbTrLd8aq6tapuffDBB1edBgAArM1KkVxVj8tuIL+tu9+VJN19f3d/u7u/k+RNSZ6937bdfV13H+vuYzs7O6tMAwAA1mqVq1tUkjcnuau7f2vP+MV7VntJkjsPPj0AADh8q1zd4keTvCzJJ6vq9mXstUmurKrLknSSE0leudIMAQDgkK1ydYuPJKl9nrr54NMBAIDtc8c9AAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYNhbJVfX8qvpsVd1dVVdv6nUAAGDdNhLJVXVekv+c5AVJnp7kyqp6+iZeCwAA1m1TR5KfneTu7v5Cd//fJG9PcvmGXgsAANZqU5H8pCRf2vP4nmUMAADOeNXd6/+hVT+X5Pnd/c+Xxy9L8ve6+9V71jme5Pjy8GlJPrv2iazuwiR/uu1JnMPs/+2y/7fL/t8e+3677P/tOhf2/9/u7p1TrXT+hl783iSX7Hn85GXsu7r7uiTXbej116Kqbu3uY9uex7nK/t8u+3+77P/tse+3y/7fLvv/L23qdIuPJ7m0qp5SVd+T5KVJ3reh1wIAgLXayJHk7n6oql6d5H8kOS/J9d39qU28FgAArNumTrdId9+c5OZN/fxDckafDnIOsP+3y/7fLvt/e+z77bL/t8v+X2zkg3sAAPBY5rbUAAAwiOSTcFvt7aqqE1X1yaq6vapu3fZ8znZVdX1VPVBVd+4Ze2JV3VJVn1u+X7DNOZ6tTrLvX19V9y7v/9ur6oXbnOPZrKouqaoPVdWnq+pTVfWaZdz7f8MeYd97/x+CqvrrVfWHVfXHy/7/d8v4U6rqY0v/vGO5AMM5yekW+1huq/0nSX4quzdC+XiSK7v701ud2Dmkqk4kOdbdZ/u1Gs8IVfUTSb6Z5K3d/UPL2G8k+Wp3X7P8j+IF3f2vtznPs9FJ9v3rk3yzu39zm3M7F1TVxUku7u5PVNX3J7ktyYuT/EK8/zfqEfb9FfH+37iqqiSP7+5vVtXjknwkyWuS/Msk7+rut1fVG5P8cXdfu825bosjyftzW23OKd394SRfHcOXJ7lhWb4hu/94sWYn2fccku6+r7s/sSx/I8ld2b1DrPf/hj3CvucQ9K5vLg8ft3x1kp9M8nvL+Dn93hfJ+3Nb7e3rJB+oqtuWuzNy+C7q7vuW5S8nuWibkzkHvbqq7lhOx/Cr/kNQVUeTPDPJx+L9f6jGvk+8/w9FVZ1XVbcneSDJLUk+n+TPuvuhZZVzun9EMmeqH+vuZyV5QZJXLb+SZkt697ws52YdnmuT/ECSy5Lcl+QN253O2a+qvi/JTUl+ubu/vvc57//N2mffe/8fku7+dndflt07Iz87yd/Z8pTOKCJ5f6e8rTab1d33Lt8fSPLu7P7h5XDdv5wz+PC5gw9seT7njO6+f/nH6ztJ3hTv/41azse8Kcnbuvtdy7D3/yHYb997/x++7v6zJB9K8veTPKGqHr6PxjndPyJ5f26rvUVV9fjlQxypqscn+ekkdz7yVmzA+5JctSxfleS9W5zLOeXhOFu8JN7/G7N8eOnNSe7q7t/a85T3/4adbN97/x+Oqtqpqicsy38juxcruCu7sfxzy2rn9Hvf1S1OYrnkzH/MX95W+9e3PKVzRlU9NbtHj5Pdu0L+rv2/WVV1Y5LnJrkwyf1JXpfkPUnemeRIki8muaK7fcBszU6y75+b3V81d5ITSV655/xY1qiqfizJ/0zyySTfWYZfm91zY73/N+gR9v2V8f7fuKr64ex+MO+87B40fWd3/9ryb/DbkzwxyR8l+Wfd/a3tzXR7RDIAAAxOtwAAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAADD/wfaCkEvpFggSgAAAABJRU5ErkJggg==\n", | |
"text/plain": "<Figure size 864x648 with 1 Axes>" | |
}, | |
"metadata": { | |
"needs_background": "light" | |
}, | |
"output_type": "display_data" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "最初は0の状態にある量子ビットにアダマールゲートを作用させるとおのおのの量子ビットが0と1に混合状態になり、全体としては00000、00001、00011、…、11110、11111のように2の5乗個の状態がすべて同じ重みで重ね合わさった状態になります。これに測定を行うと32個の状態がほぼ同じぐらいの確率で観測されました。\n\nここで注目すべきことは今5回の操作(5つのアダマールゲート)しか行っていないのに、$2^5=32$通りの結果が観測される状態が量子ビットで実現されたことです。\n古典コンピュータは一度に一つの数字しか表せないが、量子ビットでは重ね合わせを利用していろんな状態を一度に扱うことができます。これを量子並列性といいます。\n\nたとえば32個の状態が均等に実現される量子回路に対して、最初の量子ビットにだけもう一度アダマールゲートを作用させると次のようになります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "n_qubits = 5\nn_samples = 5000\n\nqubits = [cirq.GridQubit(i, 0) for i in range(n_qubits)]\n\ncircuit = cirq.Circuit()\nsimulator = cirq.google.XmonSimulator()\n\ncircuit.append(cirq.H.on(q) for q in qubits)\ncircuit.append(cirq.H.on(qubits[-1]))\n\ncircuit.append(cirq.measure(*qubits , key='m'))\nresult = simulator.run(circuit, repetitions=n_samples)\n\nres_list = get_result_list(result)", | |
"execution_count": 21, | |
"outputs": [] | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "plt.figure(figsize=(12,9))\nplt.bar(res_list[:,0], res_list[:,1])", | |
"execution_count": 22, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "<BarContainer object of 16 artists>" | |
}, | |
"execution_count": 22, | |
"metadata": {}, | |
"output_type": "execute_result" | |
}, | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAskAAAIMCAYAAAAHEDHqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAGEBJREFUeJzt3X2MZXd93/HPt7YDCFAN9dRybdOl1C0iUWPQ1iEKqiiIhIc/DBK1jFRwEZWpZCRQoyqGf4CqltwqQIXUujIyxVQEY/FQrOC2cQkS5Q8e1sQYP4SygUX2ytib8GihUtl8+8ccl8k3a8/sztyZWe/rJV3Nub97ztzf6OjIb589957q7gAAAL/01/Z6AgAAsN+IZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGM7c6wkkyTnnnNMHDhzY62kAAPAkd/vtt/95d69ttt6+iOQDBw7k0KFDez0NAACe5Krqe1tZz+UWAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGkQwAAMOZez0BHt+Bqz+3re2PXPuaHZoJAMDpxZlkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgGHTSK6qp1bVV6vqG1V1d1W9dxn/SFV9t6ruWB4XL+NVVR+sqsNVdWdVvWjVfwQAAOykM7ewzs+TvKy7H66qs5J8qar+2/Lav+ruT471X5XkouXxG0muW34CADvswNWf29b2R659zQ7NBJ5cNj2T3OseXp6etTz6CTa5NMlHl+2+nOTsqjpv+1MFAIDdsaVrkqvqjKq6I8lDSW7r7q8sL12zXFLxgap6yjJ2fpL7Nmx+/zIGAACnhC1Fcnc/2t0XJ7kgySVV9WtJ3pnk+Un+YZJnJ/m9E3njqrqyqg5V1aFjx46d4LQBAGB1TujbLbr7R0m+kOSV3f3AcknFz5P85ySXLKsdTXLhhs0uWMbm77q+uw9298G1tbWTmz0AAKzAVr7dYq2qzl6Wn5bkFUn+9LHrjKuqkrw2yV3LJrckedPyLRcvTvLj7n5gJbMHAIAV2Mq3W5yX5MaqOiPrUX1zd/9hVf1xVa0lqSR3JPkXy/q3Jnl1ksNJfpbkzTs/bQAAWJ1NI7m770zywuOMv+xx1u8kV21/agAAsDfccQ8AAAaRDAAAg0gGAIBBJAMAwLCVb7cAdtiBqz+3re2PXPuaHZoJAHA8ziQDAMAgkgEAYBDJAAAwuCYZADbhcwRw+nEmGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGA4c68nAOwvB67+3La2P3Lta3ZoJgCwd5xJBgCAwZlkgNOEfyUA2DpnkgEAYDjtzyRv58yKsyoAAE9OziQDAMAgkgEAYDjtL7cA2Ck+GAd/leOCU5UzyQAAMIhkAAAYRDIAAAwiGQAABh/cAwDYh/b7hx6f7PeacCYZAAAGkQwAAINIBgCAQSQDAMCwaSRX1VOr6qtV9Y2quruq3ruMP7eqvlJVh6vqE1X1K8v4U5bnh5fXD6z2TwAAgJ21lTPJP0/ysu7+9SQXJ3llVb04yb9N8oHu/rtJfpjkLcv6b0nyw2X8A8t6AABwytg0knvdw8vTs5ZHJ3lZkk8u4zcmee2yfOnyPMvrL6+q2rEZAwDAim3pmuSqOqOq7kjyUJLbkvxZkh919yPLKvcnOX9ZPj/JfUmyvP7jJH9jJycNAACrtKVI7u5Hu/viJBckuSTJ87f7xlV1ZVUdqqpDx44d2+6vAwCAHXNC327R3T9K8oUkv5nk7Kp67I59FyQ5uiwfTXJhkiyv//Ukf3Gc33V9dx/s7oNra2snOX0AANh5W/l2i7WqOntZflqSVyS5N+ux/PpltSuSfHZZvmV5nuX1P+7u3slJAwDAKp25+So5L8mNVXVG1qP65u7+w6q6J8lNVfVvkvxJkhuW9W9I8l+q6nCSHyS5fAXzBgCAldk0krv7ziQvPM74d7J+ffIc/z9J/smOzA4AAPbAVs4kAwA86Ry4+nPb2v7Ita/ZoZmwH7ktNQAADCIZAAAGkQwAAINIBgCAQSQDAMAgkgEAYBDJAAAwiGQAABhEMgAADCIZAAAGt6XmScmtRgGA7XAmGQAABpEMAACDyy0A2HMukQL2G2eSAQBgEMkAADCIZAAAGEQyAAAMPrjHSfNBGwDgycqZZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAIYz93oCACfiwNWf29b2R659zQ7NBIAnM2eSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBh00iuqgur6gtVdU9V3V1Vb1/G31NVR6vqjuXx6g3bvLOqDlfVt6rqd1b5BwAAwE47cwvrPJLkd7v761X1zCS3V9Vty2sf6O7f37hyVb0gyeVJfjXJ30ryP6vq73X3ozs5cQAAWJVNzyR39wPd/fVl+adJ7k1y/hNscmmSm7r759393SSHk1yyE5MFAIDdcELXJFfVgSQvTPKVZehtVXVnVX24qp61jJ2f5L4Nm92fJ45qAADYV7YcyVX1jCSfSvKO7v5JkuuSPC/JxUkeSPK+E3njqrqyqg5V1aFjx46dyKYAALBSW4rkqjor64H8se7+dJJ094Pd/Wh3/yLJh/LLSyqOJrlww+YXLGN/SXdf390Hu/vg2tradv4GAADYUVv5dotKckOSe7v7/RvGz9uw2uuS3LUs35Lk8qp6SlU9N8lFSb66c1MGAIDV2sq3W/xWkjcm+WZV3bGMvSvJG6rq4iSd5EiStyZJd99dVTcnuSfr34xxlW+2AADgVLJpJHf3l5LUcV669Qm2uSbJNduYFwAA7Bl33AMAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAAhk0juaourKovVNU9VXV3Vb19GX92Vd1WVd9efj5rGa+q+mBVHa6qO6vqRav+IwAAYCdt5UzyI0l+t7tfkOTFSa6qqhckuTrJ57v7oiSfX54nyauSXLQ8rkxy3Y7PGgAAVmjTSO7uB7r768vyT5Pcm+T8JJcmuXFZ7cYkr12WL03y0V735SRnV9V5Oz5zAABYkRO6JrmqDiR5YZKvJDm3ux9YXvp+knOX5fOT3Ldhs/uXMQAAOCVsOZKr6hlJPpXkHd39k42vdXcn6RN546q6sqoOVdWhY8eOncimAACwUluK5Ko6K+uB/LHu/vQy/OBjl1EsPx9axo8muXDD5hcsY39Jd1/f3Qe7++Da2trJzh8AAHbcVr7dopLckOTe7n7/hpduSXLFsnxFks9uGH/T8i0XL07y4w2XZQAAwL535hbW+a0kb0zyzaq6Yxl7V5Jrk9xcVW9J8r0kly2v3Zrk1UkOJ/lZkjfv6IwBAGDFNo3k7v5Sknqcl19+nPU7yVXbnBcAAOwZd9wDAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAIZNI7mqPlxVD1XVXRvG3lNVR6vqjuXx6g2vvbOqDlfVt6rqd1Y1cQAAWJWtnEn+SJJXHmf8A9198fK4NUmq6gVJLk/yq8s2/7GqztipyQIAwG7YNJK7+4tJfrDF33dpkpu6++fd/d0kh5Ncso35AQDArtvONclvq6o7l8sxnrWMnZ/kvg3r3L+MAQDAKeNkI/m6JM9LcnGSB5K870R/QVVdWVWHqurQsWPHTnIaAACw804qkrv7we5+tLt/keRD+eUlFUeTXLhh1QuWseP9juu7+2B3H1xbWzuZaQAAwEqcVCRX1Xkbnr4uyWPffHFLksur6ilV9dwkFyX56vamCAAAu+vMzVaoqo8neWmSc6rq/iTvTvLSqro4SSc5kuStSdLdd1fVzUnuSfJIkqu6+9HVTB0AAFZj00ju7jccZ/iGJ1j/miTXbGdSAACwl9xxDwAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYNo3kqvpwVT1UVXdtGHt2Vd1WVd9efj5rGa+q+mBVHa6qO6vqRaucPAAArMJWziR/JMkrx9jVST7f3Rcl+fzyPEleleSi5XFlkut2ZpoAALB7No3k7v5ikh+M4UuT3Lgs35jktRvGP9rrvpzk7Ko6b6cmCwAAu+Fkr0k+t7sfWJa/n+TcZfn8JPdtWO/+ZQwAAE4Z2/7gXnd3kj7R7arqyqo6VFWHjh07tt1pAADAjjnZSH7wscsolp8PLeNHk1y4Yb0LlrG/oruv7+6D3X1wbW3tJKcBAAA772Qj+ZYkVyzLVyT57IbxNy3fcvHiJD/ecFkGAACcEs7cbIWq+niSlyY5p6ruT/LuJNcmubmq3pLke0kuW1a/NcmrkxxO8rMkb17BnAEAYKU2jeTufsPjvPTy46zbSa7a7qQAAGAvueMeAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCIZAAAGEQyAAAMIhkAAAaRDAAAg0gGAIBBJAMAwCCSAQBgEMkAADCcuZ2Nq+pIkp8meTTJI919sKqeneQTSQ4kOZLksu7+4famCQAAu2cnziT/4+6+uLsPLs+vTvL57r4oyeeX5wAAcMpYxeUWlya5cVm+MclrV/AeAACwMtuN5E7yR1V1e1VduYyd290PLMvfT3LuNt8DAAB21bauSU7yku4+WlV/M8ltVfWnG1/s7q6qPt6GS1RfmSTPec5ztjkNAADYOds6k9zdR5efDyX5TJJLkjxYVeclyfLzocfZ9vruPtjdB9fW1rYzDQAA2FEnHclV9fSqeuZjy0l+O8ldSW5JcsWy2hVJPrvdSQIAwG7azuUW5yb5TFU99nv+oLv/e1V9LcnNVfWWJN9Lctn2pwkAALvnpCO5u7+T5NePM/4XSV6+nUkBAMBecsc9AAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAABpEMAACDSAYAgEEkAwDAIJIBAGBYWSRX1Sur6ltVdbiqrl7V+wAAwE5bSSRX1RlJ/kOSVyV5QZI3VNULVvFeAACw01Z1JvmSJIe7+zvd/X+T3JTk0hW9FwAA7KhVRfL5Se7b8Pz+ZQwAAPa96u6d/6VVr0/yyu7+58vzNyb5je5+24Z1rkxy5fL07yf51o5PZGeck+TP93oS2A/7iH2xf9gX+4d9sX/YF/vDft4Pf7u71zZb6cwVvfnRJBdueH7BMvb/dff1Sa5f0fvvmKo61N0H93oepzv7Yf+wL/YP+2L/sC/2D/tif3gy7IdVXW7xtSQXVdVzq+pXklye5JYVvRcAAOyolZxJ7u5HquptSf5HkjOSfLi7717FewEAwE5b1eUW6e5bk9y6qt+/i/b9JSGnCfth/7Av9g/7Yv+wL/YP+2J/OOX3w0o+uAcAAKcyt6UGAIBBJD8Ot9XeP6rqSFV9s6ruqKpDez2f00lVfbiqHqqquzaMPbuqbquqby8/n7WXczxdPM6+eE9VHV2OjTuq6tV7OcfTQVVdWFVfqKp7quruqnr7Mu642GVPsC8cF7usqp5aVV+tqm8s++K9y/hzq+orS0t9Yvkyh1OGyy2OY7mt9v9O8oqs3wjla0ne0N337OnETlNVdSTJwe7er9+3+KRVVf8oycNJPtrdv7aM/bskP+jua5f/gXxWd//eXs7zdPA4++I9SR7u7t/fy7mdTqrqvCTndffXq+qZSW5P8tok/yyOi131BPvisjgudlVVVZKnd/fDVXVWki8leXuSf5nk0919U1X9pyTf6O7r9nKuJ8KZ5ONzW21I0t1fTPKDMXxpkhuX5Ruz/h8lVuxx9gW7rLsf6O6vL8s/TXJv1u8o67jYZU+wL9hlve7h5elZy6OTvCzJJ5fxU+64EMnH57ba+0sn+aOqun25UyN769zufmBZ/n6Sc/dyMuRtVXXncjmGf+LfRVV1IMkLk3wljos9NfZF4rjYdVV1RlXdkeShJLcl+bMkP+ruR5ZVTrmWEsmcCl7S3S9K8qokVy3/7Mw+0OvXa7lma+9cl+R5SS5O8kCS9+3tdE4fVfWMJJ9K8o7u/snG1xwXu+s4+8JxsQe6+9Huvjjrd1m+JMnz93hK2yaSj2/T22qze7r76PLzoSSfyfrBx955cLkW8LFrAh/a4/mctrr7weU/TL9I8qE4NnbFcs3lp5J8rLs/vQw7LvbA8faF42JvdfePknwhyW8mObuqHrsnxynXUiL5+NxWe5+oqqcvH8hIVT09yW8nueuJt2LFbklyxbJ8RZLP7uFcTmuPRdnidXFsrNzyAaUbktzb3e/f8JLjYpc93r5wXOy+qlqrqrOX5adl/YsP7s16LL9+We2UOy58u8XjWL4y5t/nl7fVvmaPp3Raqqq/k/Wzx8n6HSL/wL7YPVX18SQvTXJOkgeTvDvJf01yc5LnJPleksu62wfKVuxx9sVLs/5Pyp3kSJK3brgulhWoqpck+V9JvpnkF8vwu7J+LazjYhc9wb54QxwXu6qq/kHWP5h3RtZPwN7c3f96+W/4TUmeneRPkvzT7v753s30xIhkAAAYXG4BAACDSAYAgEEkAwDAIJIBAGAQyQAAMIhkAAAYRDIAAAwiGQAAhv8HHtEZXBySsLsAAAAASUVORK5CYII=\n", | |
"text/plain": "<Figure size 864x648 with 1 Axes>" | |
}, | |
"metadata": { | |
"needs_background": "light" | |
}, | |
"output_type": "display_data" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "奇数の状態が全部消えて、偶数の状態だけが残りました。\nアダマールゲートは二度作用するともとに戻ることを考えれば、この結果は当たり前かもしれませんが、\nしかし見方を変えると、ここで一度の操作で32の数字が記録された媒体から奇数をすべて消したわけです。\n同じことを古典ビットで行おうとすると16回操作が必要になります。\n\n同じことを$n$個の量子ビットの場合で行うと、全体の状態の数は$2^n$になり、古典ビットでは$2^{n-1}$回の操作が必要になることを量子ビットで一回で済ませることになります。ここに量子コンピュータの可能性を感じます。\n\nもちろん、ここで行った操作がごく簡単なものであり、実際には量子ビット上にある大量の状態を意のままに扱うことができなくて、その上、一度にたくさんの状態に対して何らかの操作をしたとしても、最後には観測を通じて結果を得る必要があるため、実際に量子コンピュータを用いてなんらかの現実的な計算を行うにはさまざまな工夫が必要です。また、量子コンピュータがすべての問題に対して強力というわけではありません。次節ではこれらのことを詳しく見ていきますが、最後に$2^n$がいかにスゴイことかを見てみます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$45$ビットの量子回路を考えてみましょう。この量子状態を記述するためには$2^{45} \\sim 32*10^{12}$の状態の重みを指定する必要があります。古典コンピュータの上でこれを表現する場合、各々の状態の複素数重みをdouble型(8バイト)として全体では$0.5 * 10^{15}$バイト、つまり$0.5$ペタのメモリが必要になります。\nこれはスーパーコンピュータを使って[やっとできるレベル](https://arxiv.org/abs/1704.01127)です。\nさらに4ビット増やして$49$ビットになれば8ペタのメモリが必要なので、スーパーコンピュータでも扱うことが難しくなります(京のメモリが1ペタ余り)。 \nちなみに私のmacbook Proで試したところ、$26$ビットはかろうじて動きまして、$27$ビットはフリーズしかけてしまい、ちょっと、慌てました。\n\nこのように量子ビット数が50を超えるあたりから量子回路の中でで起きている現象を古典コンピュータで扱いきれなくなってくるので、ナントなくこのあたりで量子コンピュータをうまく使えば古典コンピュータでは現実的な時間以内(例えば。。。太陽が冷めるまで、とか)で解けないことをやってのけられるかもしれません。それを量子優越性(quantum supremacy)と呼ばれたりしています。\n\nところで、量子優越性が目前にあるのもいいですが、それゆえに困ってしまうこともあります。\n量子コンピュータを作った場合、作ったものが正しく動作することを検証するためには古典コンピュータ上で量子ビットのシミュレーションをする必要があるからです。\n最近IBMの研究者は量子ビットの状態の情報をハードディスクに避難させ、一部だけをメモリに乗せて[シミュレーション](https://arxiv.org/pdf/1710.05867.pdf)したりしています。\n\n49ビットならメモリに乗らない情報をハードディスクに移すことでシミュレーションができるわけですが、これが300ビットになると、今度は必要となる重みの数が宇宙の全原子の数を超えてしまいますので、情報をハードディスクに記録することさえも不可能になってしまいます。\nそうなると量子コンピュータの動作確認にはもっと洗練された方法を考える必要が出てきます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# 量子アルゴリズム" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ここまでは数式に頼らずに理解できるように努力してきましたが、此処から先は数式を避けては通れないと思います。\nんで、ここまで読んできて頂いたが数式が嫌だという方、あるいはいろいろと御用とお急ぎの方のためにマトメを先に書きます。\n\n- 量子アルゴリズムはうまい具合にハマると指数的に早くなる(Bernstein-Vaziraniアルゴリズム)\n- ハンパにハマる場合もあって、そのときはハンバに早くなる(groverアルゴリズム)\n- 量子ビット間のコヒーレンスが重要だが、これがノイズに弱い\n- 多くのアルゴリズムでは量子ゲートを多数回作用させるので、これもノイズに弱い\n\n-> すぐに何かをしたい場合はNISQでがんばろう\n\nさて、ここからはブラケットの基本的な演算は知っているものと仮定して進めます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "## Bernstein-Vaziraniアルゴリズム" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "量子コンピュータの強さは重ね合わせ状態にあり、たくさんの状態を一度に扱うことができるところが肝です。\n\n「じゃあ、とりあえずたくさんの状態をいっぺんに作ってナニかにぶっこんで、こう…うまい具合やればスゴイことができそうじゃない?」と考えるのは自然の流れかと思います。この~~雑な考え方~~アイディアを具体的な形に落とし込むのはDeutsch-JozsaアルゴリズムやBernstein-Vaziraniアルゴリズムです。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ここでは~~ちょっとだけかっこいい~~Bernsein-Vaziraniの方を説明していきます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 理論" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "Bernstein-Vaziraniアルゴリズムでは解きたい問題は次の通りです。\n\n__今とあるブラックボックスがありました。パラメータ$s_1 \\cdots s_n$を持っており、$n$個の入力ビット$x_1\\cdots x_n \\in \\{0, 1 \\}^n $に対して\n$$\n\\begin{eqnarray}\nf_s(x) = \\sum^{n}_{i=1} s_i x_i \\ \\ \\ (mod \\ 2)\n\\end{eqnarray}\n$$\nを返します。パラメータ$s_i$を推定せよ。__" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$f_s(x)$の値は$0$か$1$しか取りません。古典的にこの問題を解く場合、$i$番目のパラメータ$s_i$を知りたければ、$i$番目の入力$x_i$だけが$1$の入力を作ってブラックボックスに入れればいいです。この場合、すべてのパラメータ$s_i$を特定するためには$f_s(x)$を$n$回使う必要があります。\n\n一方で量子性を利用するとこれが一回で済みます。\n\nアルゴリズムに入る前に、準備として問題のブラックボックスを量子的に表現します。\n次のようになります。\n$$\n\\begin{eqnarray}\nU_f \\ |x\\rangle \\otimes |y\\rangle = |x\\rangle \\otimes |f_s(x) \\oplus y\\rangle\n\\end{eqnarray}\n$$\n$U_f$はオラクル(神託)と呼ばれ、入力$x_i$に対し、結果$f_s$の値を補助ビット(ancilla、$|y\\rangle$)を通して伝えます。$f_s(x) \\oplus y$は排他的論理和で、$f_s(x)$と$y$の片方が$0$、もう片方が$1$のときにのみ$1$の値を取り、それ以外の場合は$0$の値を取ります。\n入力値$x_i$に対する出力$f_s(x)$を得るときにブラックボックスに問い合わせる行為は状態$|x\\rangle$に対して$U_f$を作用させることに対応します。\n量子力学の線形性から、いったん個々の$|x\\rangle$に対して$U_f$が与えられれば、問い合わせに使う状態をさまざまな$\\sum_{x'} |x'\\rangle$の重ね合わせ状態を使えば、\n一度の問い合わせで様々な$|x\\rangle$に対する答えがエンコーディングされた状態を得ることができます。\nただし、その答えがエンコーディングされた状態からほしい答えを引き出すのが一般的に容易ではなく、\nこの場合は知りたい情報をうまく取り出す方法が見つかっていてそれがBernstein-Vaziraniアルゴリズムです。\n\nBernstein-Vaziraniアルゴリズムは次の通りです。\n1. $1$から$n$番目の量子ビットにアダマールゲートを作用させ、そして$n+1$番目の量子ビットには$X$ゲートを作用させてからアダマールゲートを作用させます。\n2. オラクルに問い合わせます($U_f$を作用させます)。\n3. $1$から$n$番目の量子ビットに再びアダマールゲートを作用させます。\n4. $1$から$n$番目の量子ビットを観測して、それぞれの値が$s_i$に対応します。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "最初にすべてのビットは$|0\\rangle$の状態にあり、$X$ゲートは$|0\\rangle$を$|1\\rangle$に変えるので、ステップ1のあとで量子ビットの状態が次のようになります。\n$$\n\\begin{eqnarray}\n|0\\rangle^{\\otimes n+1}\n\\rightarrow\n\\frac{(|0\\rangle + |1\\rangle)^{\\otimes n}}{\\sqrt{2^{n}}} \\otimes \n\\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n= \\frac{1}{\\sqrt{N}} \\sum_{x=0}^{2^n-1} |x\\rangle \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ステップ2でオラクル$U_f$を作用させると次のようになります。\n$$\n\\begin{eqnarray}\n\\frac{1}{\\sqrt{N}} \\sum_{x}^{2^n-1} |x\\rangle \\otimes \\frac{|f_s(x)\\oplus 0\\rangle - |f_s(x) \\oplus 1\\rangle}{\\sqrt{2}}\n= \\frac{1}{\\sqrt{N}} \\sum_{x=0}^{2^n-1} (-1)^{f_s(x)} |x\\rangle \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n\\end{eqnarray}\n$$\nイコールでは$|f_s(x)\\oplus 0\\rangle - |f_s(x) \\oplus 1\\rangle=(-1)^{f_s(x)}(|0\\rangle - |1\\rangle)$を使いました。$f_s(x)$が$0$と$1$の場合を代入すると簡単に確認できます" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ステップ3で$|x\\rangle$の重ね合わせ状態にアダマールゲートを作用させると$|s\\rangle$に変わります。\n$$\n\\begin{eqnarray}\n\\frac{1}{\\sqrt{N}} \\sum^{2^n - 1}_{x=0}(-1)^{f_s(x)} H^{\\otimes n} |x\\rangle \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n= |s\\rangle \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "上の式は$(-1)^{f_s(x)}|x\\rangle = \\prod_{i=1}^n (-1)^{s_i x_i} |x_i\\rangle$\nに注意すれば\n$\\frac{1}{\\sqrt{N}} \\sum_x (-1)^{f_s(x)} |x\\rangle = \\prod_i^n \\frac{|0\\rangle + (-1)^{s_i}|1\\rangle}{\\sqrt{2}}= \\prod_i^n \\frac{H|s_i\\rangle}{\\sqrt{2}}$\nとなるので$HH=1$を使えば導出できます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "最後にステップ4でビットの値を観測すれば$s_i$が求められます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 実装" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "では、Bernstein-Vaziraniアルゴリズムを実装していきます。\n実装…とオオゲサに言っても、$X$ゲートとアダマールゲートを作用させるだけですね。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "入力ビット数を与えて、入力ビットと補助ビットを作ります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "def init_circuit(qubit_count):\n circuit = cirq.Circuit()\n input_qubits = [cirq.GridQubit(i, 0) for i in range(qubit_count)]\n ancilla_qubit = cirq.GridQubit(qubit_count, 0)\n return circuit, input_qubits, ancilla_qubit", | |
"execution_count": 23, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "次にステップ1の作業を行います。補助ビット(ancilla_qubit)に$X$ゲートを作用させてからアダマールゲート、入力ビットにはアダマールゲートだけを作用させます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "def step1(circuit, input_qubits, ancilla_qubit):\n circuit.append([\n cirq.X(ancilla_qubit),\n cirq.H(ancilla_qubit),\n cirq.H.on_each(input_qubits),\n ])\n return circuit", | |
"execution_count": 24, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "次にオラクルを作用…させたいですが、これはちょっと~~めんどう~~自明じゃない…ので一旦置いておいて、あとでちゃんとやります。このアルゴリズムの本質がオラクルはあるもの(与えられたもの)として、それをどう推定することにあるからです(つまり誰かが持ってきたブラックボックスの中身を推定するのが仕事)。オラクルの実装そのものが本質ではありません。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "# 一旦飛ばす\ndef step2(circuit, input_qubits, ancilla_qubit):\n return circuit", | |
"execution_count": 25, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "そして、ステップ3はまたアダマールゲートを作用させるだけですが、めんどうなのでステップ4の測定も一緒にやってしまいましょう" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "def step3to4(circuit, input_qubits, ancilla_qubit):\n circuit.append([\n cirq.H.on_each(input_qubits),\n cirq.measure(*input_qubits, key='result')\n ])\n return circuit", | |
"execution_count": 26, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "これで関数ができたので、実装してみましょう。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "circuit_sample_count = 3\nn_qubits = 8\n\ncircuit, input_qubits, ancilla_qubit = init_circuit(n_qubits)\ncircuit = step1(circuit, input_qubits, ancilla_qubit)\ncircuit = step2(circuit, input_qubits, ancilla_qubit)\ncircuit = step3to4(circuit, input_qubits, ancilla_qubit)\n\ndef bitstring(bits):\n return ''.join(str(int(b)) for b in bits)\n\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.run(circuit, repetitions=circuit_sample_count)\nfrequencies = result.histogram(key='result', fold_func=bitstring)\nprint('Sampled results:\\n{}'.format(frequencies))", | |
"execution_count": 27, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Sampled results:\nCounter({'00000000': 3})\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "この時点でオラクルが何もしていないので結果は常に$0$です(補助ビットが常にそのまま、つまりすべての$s_i$が$0$の状況に対応する)。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "#### オラクル" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ここは本質ではない部分なので、時間をかけることにあまり気乗りしないですが、これをやらないと実装が完成しません。\nなのでオラクルを実装します(量子ゲートを理解するのにいい練習だと思います)。\n定義を思い出しますと" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "\\begin{eqnarray}\nU_f \\ |x\\rangle \\otimes |y\\rangle = |x\\rangle \\otimes |f_s(x) \\oplus y\\rangle\n\\end{eqnarray}" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "オラクルは入力ビット$|x\\rangle$の値に応じて補助ビット$|y\\rangle$の値を変えるので、各々のビット$|x_i\\rangle$に応じて補助ビットを変えるゲートが必要になります。\nこれを行うにはCNOT(Controlled NOT)ゲートを使います。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\hat{C}_{NOT} |x\\rangle \\otimes |y\\rangle = |x\\rangle \\otimes |x \\oplus y \\rangle\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "この作用は$|x\\rangle$の値によって$|y\\rangle$の値を変えるので、所見では違和感を覚えるかもしれません。\nCNOTは決して$|x\\rangle$を測定してから$|y\\rangle$を操作するものではなく、単にこういうタイプの相互作用です。\n「CNOT implementation」で検索すればさまざまな実現方法が出てきます。\nまた、実際に行列表現に書き起こせばユニタリ性をチェックすることもできます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n C_{NOT} = \\left(\n \\begin{array}{cccc}\n 1 & 0 & 0 & 0\\\\\n 0 & 1 & 0 & 0 \\\\\n 0 & 0 & 0 & 1\\\\\n 0 & 0 & 1 & 0\n \\end{array}\n \\right)\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "ただし、ここではベクトルの成分は$|00\\rangle, |01\\rangle, |10\\rangle, |11\\rangle$となっています。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "CNOTを使ってオラクルを実装しましょう。\n定義$a \\oplus b = a+b \\ (mod \\ 2)$と結合則を使うと\n$$\n\\begin{eqnarray}\n\\sum_{i} s_i x_i \\oplus y \n= \\sum_{i} s_i x_i + y \\ (mod \\ 2)\n= \\sum_{i \\ for \\ s_i=1} x_i + y \\ (mod \\ 2)\n= \\sum_{\\oplus \\ with \\ i \\ for \\ s_i=1}^{} x_i \\oplus y\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "となるので、$s_i$が$1$の$i$に対して$i$番目の入力ビットと補助ビットに作用するCNOTゲート使えばいいです。\n実装は次のようになります。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "def make_oracle(circuit, input_qubits, ancilla_qubit, secret_bits):\n \n for qubit, bit in zip(input_qubits, secret_bits):\n if bit:\n circuit.append([cirq.CNOT(qubit, ancilla_qubit)])\n return circuit", | |
"execution_count": 37, | |
"outputs": [] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "オラクルができたので、Bernstein-Vaziraniアルゴリズムを動かして確認することができます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "circuit_sample_count = 3\nn_qubits = 8\n\n# パラメータs_iをランダムに生成する\nsecret_bits = np.random.randint(2, size=8)\ncircuit, input_qubits, ancilla_qubit = init_circuit(n_qubits)\ncircuit = step1(circuit, input_qubits, ancilla_qubit)\ncircuit = make_oracle(circuit, input_qubits, ancilla_qubit, secret_bits)\ncircuit = step3to4(circuit, input_qubits, ancilla_qubit)\n\ndef bitstring(bits):\n return ''.join(str(int(b)) for b in bits)\n\nsimulator = cirq.google.XmonSimulator()\nresult = simulator.run(circuit, repetitions=circuit_sample_count)\nfrequencies = result.histogram(key='result', fold_func=bitstring)\nprint('Sampled results:\\n{}'.format(frequencies))", | |
"execution_count": 44, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": "Sampled results:\nCounter({'01100011': 3})\n" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "出力が得られたので、もとの$s_i$を確認してみます。" | |
}, | |
{ | |
"metadata": { | |
"trusted": true | |
}, | |
"cell_type": "code", | |
"source": "secret_bits", | |
"execution_count": 45, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": "array([0, 1, 1, 0, 0, 0, 1, 1])" | |
}, | |
"execution_count": 45, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
] | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "いっちしました。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 考察" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "Bernstein-Vaziraniアルゴリズムは量子コンピュータの仕組みを説明するのに適していますが、実用的ではありません。\n\n重要なポイントは量子ビット$x$に対して関数$f(x)$の働きをする操作(オラクル)が存在すれば、\n非常に低コスト(N個の状態を$\\log{N}$回の操作)ですべての状態を作っていっぺんに試すことができることです。\n\nしかし理論の部分でも見た通り、このケースではたまたまアダマールゲートを使って目的の情報$s_i$を出力ビットに反映させて取り出すことができたので、\n従来のコンピュータに対して指数的に速い計算スピードを得ることができました。\n一般的にこれがうまくいかないケースが多いです。\n次にみるgroverアルゴリズムのように、問題によっては目的の情報を出力ビットに反映させることが難しい場合もあり、この場合量子コンピュータを使うことによって得られる恩恵小さくなります(指数的には速くならず、ルートで速くなります)。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "## grover アルゴリズム" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "__$f(x)$という関数があって、$f(x_0)=1$でそれ以外の$x$では$f(x)=0$となります。$x_0$を求めよう。__" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "groverアルゴリズムは「検索のアルゴリズム」として紹介されることが多いですが、元論文の書き方もあってか、データベースの検索タスクを連想させてしまいますが、実際には「解の検索」問題として捉えたほうが適切です。\n$f(x)$の働きをするオラクル$U_f$が与えられたとして、$x_0$を探す問題になります。\n\nこの問題もBernstein-Vaziraniアルゴリズム同様、古典コンピュータではしらみつぶしに$x_0$を一つずつ試すしかないので、$x$の取りうる数を$N$個だとして最悪$N$回探さなければ答えが見つかりません。\n量子性を利用すると低いコストですべての$x$状態をいっぺんにオラクルに問い合わせることができるので、古典コンピュータより速く(少ない手順で)答えにたどり着きます。\nしかしBernstein-Vaziraniアルゴリズムの場合と違って、この場合、答えを引き出すのが簡単ではありません。\n\nこの場合も補助ビットと入力ビットを使って、\n1. $1$から$n$番目の量子ビットにアダマールゲートを作用させ、そして$n+1$番目の量子ビットには$X$ゲートを作用させてからアダマールゲートを作用させます。\n2. オラクルに問い合わせます($U_f$を作用させます)。\n\nを行うと、次のようになります。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\frac{1}{\\sqrt{N}} \\sum_{x=0}^{2^n-1} (-1)^{f_s(x)} |x\\rangle \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n= \\frac{1}{\\sqrt{N}} \\left(-|x_0\\rangle + \\sum_{x\\neq x_0} |x\\rangle \\right) \\otimes \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "この場合ターゲットとなる|x_0\\rangleだけ確率振幅がマイナスになっていますが、この状態では確率$\\frac{1}{\\sqrt{N}}$でしか$|x_0\\rangle$を観測できないので、メリットがありません。\n確率振幅の符号がマイナスになっていることを利用して$|x_0\\rangle$の確率を増幅するのがgroverアルゴリズムです。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 確率振幅増幅" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "まず次のように書き換えます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\frac{1}{\\sqrt{N}}\n\\left(-|x_0\\rangle + \\sum_{x\\neq x_0} |x\\rangle \\right)\n= \\frac{1}{\\sqrt{N}}\n\\left(-2|x_0\\rangle + \\sum_{x} |x\\rangle\\right)\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$\\sum_x |x\\rangle$\nの部分は入力ビットにアダマールゲートを作用させることで生成されるので、入力ビットに再びアダマールゲートを作用させると$|0\\rangle$に戻ります。\n一方で$|x_0\\rangle$の部分はアダマールゲートを作用させるとさまざまな$|x\\rangle$の重ね合わせ状態になります。\nここで$|x=0\\rangle$だけを$-|x=0\\rangle$と確率振幅の符号をひっくり返して、それ以外の状態をそのままになるように操作し、そして再びすべてのアダマールゲートを作用させることを考えよう、$|0\\rangle$は$\\sum_x |x\\rangle$に戻りますが、それ以外の$|x\\rangle$部分を$|x_0\\rangle$へ戻すには$\\frac{2}{N}|0\\rangle$だけ足りないはずです。\nその分を補い、残りを変換前の$|0\\rangle$で吸収することを考えると、変換後の$\\sum_x |x\\rangle$の振幅はその分小さくなり、$\\frac{1-4/N}{\\sqrt{N}}$となっているはずです。\nそして確率の保存を考えると最終的に$|x_0\\rangle$の振幅が$\\frac{3-4/N}{\\sqrt{N}}$と変換前より増幅されたことになります。\n\n具体的に数式にすると次のようになります。\nまず入力ビットすべてにアダマールゲートを作用させる" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\rightarrow - \\frac{2}{N}\\sum_{x'} (-1)^{<x', x_0>}|x'\\rangle + |0\\rangle\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$|0\\rangle$だけひっくり返して、他の成分をそのままにする(実現方法については次節で)" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\rightarrow \n- \\frac{2}{N}\\sum_{x'\\neq 0} (-1)^{<x', x_0>}|x'\\rangle - (1-2/N)|0\\rangle\n= - \\frac{2}{N} \\sum_{x'} (-1)^{<x', x_0>} |x' \\rangle - (1-4/N)|0\\rangle\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "再びすべての入力ビットにアダマールゲートを作用させる" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "$$\n\\begin{eqnarray}\n\\rightarrow \n\\frac{1}{\\sqrt{N}}\n\\left(-2|x_0\\rangle \n- (1-4/N) \\sum_{x} |x\\rangle\\right)\n= \\frac{1}{\\sqrt{N}}\n\\left(-(3-1/N)|x_0\\rangle \n- (1-4/N) \\sum_{x \\neq x_0} |x\\rangle\\right)\n\\end{eqnarray}\n$$" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "という計算になります。増幅したあとに$|x\\rangle$の符号が揃ったので、再び$|x_0\\rangle$を増幅させるにはもう一度オラクルを作用させる必要があります。オラクルと増幅を繰り返していけば最終的に$|x_0\\rangle$が高い確率で観測されるように持っていくことができます。\n一度繰り返すたびに$|x_0\\rangle$の増幅幅はおおよそ$\\frac{2}{\\sqrt{N}}$のオーダーなので、これを大きな値にするには大体$\\sqrt{N}$回繰り返す必要があります。\nゆえにgroverアルゴリズムでは指数的にではなく$\\sqrt{N}$程度に速くなります。\nそれでも$N$が1億程度なら10000倍速くなるので、実現されれば十分価値あるものになります。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 制御ゲート" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "確率振幅を増幅する過程で$|0\\rangle$の符号だけをひっくり返して他の状態をそのままにする操作を仮定しましたが、CNOTゲートの拡張を考えると実現できます。\n入力ゲートを一つから複数にします。つまり複数の入力ゲートの値がすべて$1$の場合にのみ補助ゲートの値を変えます(具体的な実現方法については「Multiple-Controlled gate」で検索するといろいろ論文が出てきます)。\nすべてのビットの値が揃ったときにのみ動作するものを作るには、二回作用させれば元にもどるゲートをToffoliゲートの両辺で挟み、補助ビットにNOTゲートがかかるときに符号が変わるようにすればいいです。\n$|0\\rangle$のときに反応させたいのですべてのビットにXゲートを作用させます、そして補助ビットの符号をひっくり返すためにはアダマールゲートを使えばできます。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "### 考察" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "groverアルゴリズムは応用価値がありそうですが、実際には$\\sqrt{N}$の速さを得るのに$\\sqrt{N}$回もゲート操作を繰り返す必要があるため、現在の技術で実現するのが難しそうです。実用的なアルゴリズムではどうしても量子ゲートを多くの回数作用させることになります。そのたびにノイズが加算されると有意な結果が得られなくなってしいます。これを乗り越えるために現在さまざまな方法が提案されています。その中でも量子計算と古典計算を組み合わせて問題を解くアプローチが近い将来力を発揮するかもしれません。" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "# 参考文献" | |
}, | |
{ | |
"metadata": {}, | |
"cell_type": "markdown", | |
"source": "- 教科書 \n - [現代量子物理学―基礎と応用](https://www.amazon.co.jp/%E7%8F%BE%E4%BB%A3%E9%87%8F%E5%AD%90%E7%89%A9%E7%90%86%E5%AD%A6%E2%80%95%E5%9F%BA%E7%A4%8E%E3%81%A8%E5%BF%9C%E7%94%A8-%E4%B8%8A%E7%94%B0-%E6%AD%A3%E4%BB%81/dp/4563022659/ref=sr_1_1?s=books&ie=UTF8&qid=1544261920&sr=1-1&keywords=%E9%87%8F%E5%AD%90%E5%8A%9B%E5%AD%A6%E3%80%80%E4%B8%8A%E7%94%B0):量子力学の教科書です。量子情報に一章を割いています。本質をわかりやすく説明してくれています。\n - [量子情報科学入門](https://www.amazon.co.jp/%E9%87%8F%E5%AD%90%E6%83%85%E5%A0%B1%E7%A7%91%E5%AD%A6%E5%85%A5%E9%96%80-%E7%9F%B3%E5%9D%82-%E6%99%BA/dp/4320122992):基本的なアルゴリズムを丁寧に導出してくれるだけでなく、考え方についても述べています。\n- 論文\n - [Quantum Algorithm Implementations for Beginners](https://arxiv.org/pdf/1804.03719.pdf):いろんなアルゴリズムと実装が書かれています。手軽に動かせるようにIBM Qで構成するサンプルも用意されています。\n - [Quantum computational chemistry](https://arxiv.org/abs/1808.10402): 量子コンピュータ威力を発揮しそうな分野だからやっぱり気になりますよね。基本的なことがまとめられているようなので、読みたい(つまりまだよんでいない)\n - [The theory of variational hybrid quantum-classical algorithms](https://arxiv.org/pdf/1509.04279.pdf): VQEの論文\n- その他資料\n - [Qiskit Tutorial](https://github.com/Qiskit/qiskit-tutorial): 基本的なことから最近の論文まで、幅広く面白いjupyter notebookがたくさんあって、漁るの楽し(私のお気に入りはこちらの[量子絵文字](https://github.com/Qiskit/qiskit-tutorial/blob/master/community/hello_world/quantum_emoticon.ipynb)、笑えるので、ぜひ!ちなみに[量子機械学習](https://github.com/Qiskit/qiskit-tutorial/tree/master/community/teach_me_qiskit_2018/quantum_machine_learning)関連もあります)\n - アニーリング系:本文では触れませんでしたが、現状では量子ゲートマシンよりもアニーリングマシンのほうが一歩先を行っている感じがします。こちらの資料です。\n - [Wildqat example](https://github.com/mdrft/Wildqat): 日本語のjupyter notebookが豊富です。「最適化問題」とだけ言われてもピンと来ませんが、これを読めば、本当にいろんなことができそうだということがわかります。[MDR](http://mdrft.com/)社に感謝。\n - [D-Wave Leap](https://cloud.dwavesys.com/leap/login/?next=/leap/): D-Wave社の入門サイト、動画もあってわかりやすい。内容いろいろあって楽しいです。\n - [量子コンピュータの現状と未来](http://www.scat.or.jp/scatline/scatline104/pdf/scat104_seminar_02.pdf): 量子アニーリングの生みの親である西森先生の講演資料です。わかりやすい(関係ないことですが、西森先生といえばわたくしなどはこちらの[シュレ-ディンが音頭](https://www.qu-bit.com/members/nonaka/schrodinger/index-j.html)を真っ先に思い浮かびますが、ご兄弟らしいです)" | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"name": "qiskit", | |
"display_name": "qiskit", | |
"language": "python" | |
}, | |
"language_info": { | |
"name": "python", | |
"version": "3.6.4", | |
"mimetype": "text/x-python", | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"pygments_lexer": "ipython3", | |
"nbconvert_exporter": "python", | |
"file_extension": ".py" | |
}, | |
"toc": { | |
"nav_menu": {}, | |
"number_sections": true, | |
"sideBar": false, | |
"skip_h1_title": false, | |
"toc_cell": false, | |
"toc_position": { | |
"height": "366px", | |
"left": "1623px", | |
"right": "20px", | |
"top": "140px", | |
"width": "212px" | |
}, | |
"toc_section_display": "block", | |
"toc_window_display": true | |
}, | |
"gist": { | |
"id": "", | |
"data": { | |
"description": "play_network/src/quantum_computing/cirq-tuto.ipynb", | |
"public": true | |
} | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment