{ "cells": [ { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "6a565a69-3d02-4666-8517-781b8d3ff6a0" } }, "source": [ "# 量子编译简介\n", "\n", "本文档介绍 *Qubiter* 所用的正余弦分解（CSD, Cosine-Sine decomposition）量子编译器及其性能。\n", "\n", "量子编译器指以任意 $N=2^n$ 维的幺正矩阵 $U$ 作为输入，能够输出等价于矩阵 $U$ 的基本操作序列（比如 CNOT 受控反门和单量子比特旋转门）的计算机程序，可以有很多种。通常幺正矩阵 $U$ 的形式为 $U=e^{-itH}$，其中 $t$ 和 $H$ 分别代表时间和哈密顿算符。在物理学和量子化学领域中，$H$ 的具体形式往往可以先验已知，通常的做法是用 Trotter-Suzuki 近似对 $U$ 进行展开。而在人工智能等领域，哈密顿量 $H$ 的具体形式一般不能先验已知，这时候则推荐使用线性代数中正余弦分解（CSD）来处理矩阵。这两种不同的编译方式都可以使用 *Qubiter* 实现，此文档着重介绍正余弦分解编译方法。\n", "\n", "使用 *Qubiter* 进行 CSD 量子编译需要调用 'quantum_CSD_compiler' 文件夹中的类文件。这些类的使用除了需要 *Qubiter* 的 Python 文件包和安装了 numpy、scipy 库的 Python 环境（例如 Anaconda ）外，还需要[安装由 Artiste-qb.net 提供的二进制库](https://github.com/artiste-qb-net/Python-CS-Decomposition#installation)。此库包括了 Python 封装的进行正余弦分解的 LAPACK 子程序 'cuncsd.f'。复述本文档中的计算需要安装所有必要的文件和库。\n", "\n", "在 'quantum_CSD_compiler' 文件夹中的 ['csd-intro.pdf'](https://github.com/artiste-qb-net/qubiter/blob/master/quantum_CSD_compiler/csd-intro.pdf) 文件提供了 CSD（正余弦分解）的介绍。其他参考文献有：\n", "\n", "1. [R.R. Tucci,《初级量子编译》（第二版）](https://arxiv.org/abs/quant-ph/9902062)\n", "\n", "2. Qubiter 1.11: 基于 C++ 的原始 *Qubiter* 版本。最初一版 *Qubiter 1.11* 和文献1同步发布。在新的 *Qubiter* 版本（基于 Python）的 'quantum_CSD_compiler/LEGACY' 文件夹中包含了 *Qubiter 1.11* 原始程序。\n", "\n", "3. R.R. Tucci,[《量子快速傅立叶变换 - 正余弦分解递归应用举例》](https://arxiv.org/abs/quant-ph/0411097)\n" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "95230611-c19b-4b8c-acb0-81b196ca655c" } }, "source": [ "*Qubiter* 通过递归调用 CSD 来建立由节点矩阵构成的树结构。这些节点矩阵通过正确的顺序读取后是和输入矩阵 $U$ 完全等价的。\n", "\n", "在这里以三个量子比特的量子傅立叶矩阵 $U$ 为例，用如下方式构建类树的对象：" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "/home/rrtucci/PycharmProjects/qubiter/qubiter/jupyter_notebooks\n", "/home/rrtucci/PycharmProjects/qubiter\n" ] } ], "source": [ "import os\n", "import sys\n", "print(os.getcwd())\n", "os.chdir('../../')\n", "print(os.getcwd())\n", "sys.path.insert(0,os.getcwd())" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "nbpresent": { "id": "ea26bc82-841b-425d-b0c4-74540869ad6a" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "loaded OneBitGates, WITHOUT autograd.numpy\n" ] } ], "source": [ "import numpy as np\n", "import cuncsd_sq as csd\n", "\n", "import math\n", "from qubiter.FouSEO_writer import *\n", "from qubiter.quantum_CSD_compiler.Tree import *\n", "from qubiter.quantum_CSD_compiler.DiagUnitarySEO_writer import *\n", "from qubiter.quantum_CSD_compiler.MultiplexorSEO_writer import *" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "nbpresent": { "id": "cbcd576b-5021-4e60-892f-b82890a8c8d2" }, "scrolled": true }, "outputs": [], "source": [ "num_bits = 3\n", "init_unitary_mat = FouSEO_writer.fourier_trans_mat(1 << num_bits)\n", "emb = CktEmbedder(num_bits, num_bits)\n", "file_prefix = 'csd_test'\n", "t = Tree(True, file_prefix, emb, init_unitary_mat, verbose=False)\n", "t.close_files()" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "8202ff8a-30da-444a-8c15-38428e6aa911" } }, "source": [ "上述代码自动将矩阵 $U$ 展开并创建 DIAG 和 MP_Y 线路，其图形化文件（Picture file）为：" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "

1	%---%---%
2	%---%---Ry
3	%---%---%
4	%---Ry--%
5	%---%---%
6	%---%---Ry
7	%---%---%
8	Ry--%---%
9	%---%---%
10	%---%---Ry
11	%---%---%
12	%---Ry--%
13	%---%---%
14	%---%---Ry
15	%---%---%

" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "t.print_pic_file(jup=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "cbaa3fbd-53cb-4466-84b3-16b25b728381" } }, "source": [ "\n", "相应的，创建的文字化文件（English file）为：" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "

1	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t67.500000\t0.000000\t-112.499998\t0.000000\t-112.499998\t0.000000\t67.500000
2	MP_Y\tAT\t0\tIF\t2:1\t1:0\t\tBY\t44.999981\t45.000022\t44.999991\t45.000008
3	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t180.000005\t135.000000\t134.999987\t0.000000\t0.000000\t135.000028\t-44.999994
4	MP_Y\tAT\t1\tIF\t2:1\t0:0\t\tBY\t17.632183\t72.367794\t17.632188\t72.367815
5	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t-179.999991\t0.000000\t0.000009\t0.000000\t0.000002\t0.000000\t-179.999964
6	MP_Y\tAT\t0\tIF\t2:1\t1:0\t\tBY\t45.000011\t45.000001\t45.000005\t45.000015
7	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t-179.999991\t179.999991\t179.999991\t179.999991\t90.000003\t-89.999996\t89.999962\t-90.000003
8	MP_Y\tAT\t2\tIF\t1:1\t0:0\t\tBY\t3.749999\t26.249993\t63.750008\t86.249996
9	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t-89.999996\t0.000000\t-90.000023\t0.000000\t89.999996\t0.000000\t90.000003
10	MP_Y\tAT\t0\tIF\t2:1\t1:0\t\tBY\t45.000008\t45.000001\t44.999991\t45.000001
11	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t0.000000\t0.000019\t179.999978\t180.000005\t180.000005\t-179.999991\t-0.000019
12	MP_Y\tAT\t1\tIF\t2:1\t0:0\t\tBY\t17.632203\t72.367801\t17.632198\t72.367801
13	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t0.000000\t0.000002\t0.000000\t179.999991\t0.000000\t0.000017\t0.000000\t-179.999991
14	MP_Y\tAT\t0\tIF\t2:1\t1:0\t\tBY\t44.999988\t44.999991\t44.999994\t44.999988
15	DIAG\tIF\t2:2\t1:1\t0:0\t\tBY\t67.500014\t-44.999998\t22.500001\t89.999982\t-22.500001\t44.999994\t-67.500014\t-180.000005

" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "t.print_eng_file(jup=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "47e7dac1-0f1f-4f0b-95fe-4d88ec2023cd" } }, "source": [ "在图形化文件中，一个 DIAG 线路作为一个百分号链出现，而一个 MP_Y 线路作为百分号链加 Ry 门出现。我们可以看到，相对于较复杂的文字化文件，图形化文件可以很直观地给出 DIAG 和 MP_Y 门的概览。在 *Qubiter* 的诠释文件 [qubiter_rosetta_stone.pdf](https://github.com/artiste-qb-net/qubiter/blob/master/qubiter_rosetta_stone.pdf) 中可以了解更多 DIAG 和 MP_Y 线路的解释和举例。\n", "\n", "在这里，每一个 DIAG 线路都代表一个由单位尺度大小的复数构成的对角矩阵，从而保证了矩阵的幺正性。同时每一个 MP_Y 线路代表了具有如下形式的矩阵，\n", "\n", "$\\left[\\begin{array}{cc} cc & ss \\\\ -ss & cc \\end{array}\\right]$，\n", "\n", "其中 $cc$ and $ss$ 是相同大小的实对角矩阵从而满足 $cc^2 + ss^2 = 1$.\n" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "fc94a4d8-1113-46d5-a6a1-d48b5a54a622" } }, "source": [ "对每一个输入的文字化文件，'DiagUnitaryExpander' 类都会生成新的文字化文件和图形化文件，其中：\n", "\n", "* 所有非 'DIAG' 开始的行都被回显，\n", "* 所有以 'DIAG' 开始的行都被其精确或近似的多线路展开所替换。\n", "\n", "同样的，'MultiplexorExpander' 也将任一输入的文字化文件输出为新的文字化文件和图形化文件，其中：\n", "\n", "* 所有非 'MP_Y' 开始的行都被回显，\n", "* 所有以 'MP_Y' 开始的行都被其精确或近似的多线路展开所替换。\n", "\n", "所有之前的文字化文件都可以被这两个类展开并且构建为新的文字化和图形化文件，最终会得到一个只包含 CNOT 门和单量子比特旋转的文字化文件。而此文件中的逻辑门相乘后和原始矩阵 $U$ 是完全等价的。鉴于最终的文字化文件较长且不适合展示，这里仅以单个 DIAG 和单个 MP_Y 线路的精确展开为例做演示：\n" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "005a517d-218d-4ba8-a17d-a5b2d2183291" } }, "source": [ "首先对于一个四量子比特门\n", "\n", "%---%---%---%\n", "\n", "我们创建包含其展开的文字化文件和图形化文件。这代表一个幺正对角矩阵，其相位角是随机生成的并存储为变量 'rad_angles'。其图形化文件为：" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "nbpresent": { "id": "5b7f9712-6755-492b-834d-1bd68521c11c" } }, "outputs": [ { "data": { "text/html": [ "

1	\| \| \| Ph
2	\| \| \| Rz
3	\| \| @---X
4	\| \| \| Rz
5	\| \| @---X
6	\| \| Rz \|
7	\| @---X \|
8	\| \| Rz \|
9	\| @---X \|
10	\| \| @---X
11	\| @---+---X
12	\| \| \| Rz
13	\| \| @---X
14	\| \| \| Rz
15	\| @---+---X
16	\| Rz \| \|
17	@---X \| \|
18	\| Rz \| \|
19	@---X \| \|
20	\| @---+---X
21	@---+---+---X
22	\| \| \| Rz
23	\| \| @---X
24	\| \| \| Rz
25	\| \| @---X
26	\| @---+---X
27	@---+---+---X
28	\| @---X \|
29	@---+---X \|
30	\| \| Rz \|
31	\| @---X \|
32	\| \| Rz \|
33	@---+---X \|
34	\| \| @---X
35	@---+---+---X
36	\| \| \| Rz
37	\| \| @---X
38	\| \| \| Rz
39	@---+---+---X
40	Rz \| \| \|

" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "file_prefix = \"d_unitary_exact_check\"\n", "num_bits = 4\n", "num_angles = (1 << num_bits)\n", "emb = CktEmbedder(num_bits, num_bits)\n", "rad_angles = list(np.random.rand(num_angles)*2*np.pi)\n", "wr = DiagUnitarySEO_writer(file_prefix, emb, 'exact', rad_angles)\n", "wr.write()\n", "wr.close_files()\n", "wr.print_pic_file(jup=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "f4f86caa-cf9f-4c5a-ab9c-130b5a22dc02" } }, "source": [ "可以通过如下方式检验此精确展开的正确性：将展开后的门操作用 'SEO_MatrixProduct' 类进行相乘，并存储乘积为 'matpro.prod_arr'。利用 'rad_angles' 中的相位角精确重建对角矩阵并存为 'exact_mat'。将两结果差值（即 matpro.prod_arr - exact_mat）的标准差存储为 'err'　并输出：\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "nbpresent": { "id": "51e1a777-aafa-4e50-bec3-fe6369bfe552" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "diag unitary error= 6.711730049618337e-08\n" ] } ], "source": [ "matpro = SEO_MatrixProduct(file_prefix, num_bits)\n", "exact_mat = DiagUnitarySEO_writer.du_mat(rad_angles)\n", "err = np.linalg.norm(matpro.prod_arr - exact_mat)\n", "print(\"diag unitary error=\", err)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "11cee14b-e769-4a6a-a487-2c5d9d67d9b8" } }, "source": [ "接下来，对另一个四量子比特门\n", "\n", "Ry--%---%---%\n", "\n", "我们构建展开后的文字化文件和图形化文件。这是一个多路复用器矩阵（multiplexor matrix），其随机相位角存储为变量 'rad_angles'。其图形化文件为：\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "nbpresent": { "id": "7909a750-1d68-4275-ae25-8fadbc3551be" } }, "outputs": [ { "data": { "text/html": [ "

1	Ry \| \| \|
2	X---+---+---@
3	Ry \| \| \|
4	X---+---@ \|
5	Ry \| \| \|
6	X---+---+---@
7	Ry \| \| \|
8	X---@ \| \|
9	Ry \| \| \|
10	X---+---+---@
11	Ry \| \| \|
12	X---+---@ \|
13	Ry \| \| \|
14	X---+---+---@
15	Ry \| \| \|
16	X---@ \| \|

" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "file_prefix = \"plexor_exact_check\"\n", "num_bits = 4\n", "num_angles = (1 << (num_bits-1))\n", "emb = CktEmbedder(num_bits, num_bits)\n", "rad_angles = list(np.random.rand(num_angles)*2*np.pi)\n", "wr = MultiplexorSEO_writer(file_prefix, emb, 'exact', rad_angles)\n", "wr.write()\n", "wr.close_files()\n", "wr.print_pic_file(jup=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "96ad7095-cdce-49bd-9d31-9fa7209592a9" } }, "source": [ "同前面一样，可以通过如下方式检验此精确展开的正确性：将展开后的门操作用 'SEO_MatrixProduct' 进行相乘，并存储乘积为 'matpro.prod_arr'。利用 'rad_angles' 中的相位角精确重建对角矩阵并存为 'exact_mat'。将两结果差值（即 matpro.prod_arr - exact_mat）的标准差存储为 'err'　并输出：" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "nbpresent": { "id": "a44258b5-c8c1-47fd-a041-86a38804e28f" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "multiplexor error= 5.980011774661497e-08\n" ] } ], "source": [ "matpro = SEO_MatrixProduct(file_prefix, num_bits)\n", "exact_mat = MultiplexorSEO_writer.mp_mat(rad_angles)\n", "err = np.linalg.norm(matpro.prod_arr - exact_mat)\n", "print(\"multiplexor error=\", err)" ] }, { "cell_type": "markdown", "metadata": { "nbpresent": { "id": "c7e4a893-42ab-4e39-833a-e0a29188fccd" } }, "source": [ "上述计算意味着，对量子傅立叶变换（QFT）盲目使用 CSD 量子编译会得到一个随量子比特数 $n$ 指数增长的操作序列。而我们知道对 QFT 使用 Coppersmith 分解仅得到随着 $n$ 多项式增长的结果。不过由于 CSD 的非惟一性，在文献3中介绍了如何用 CSD 编译以得到优于 Coppersmith 分解的方法。\n", "\n", "对于 $n$ 个量子比特，$U$ 是一个 $N = 2^n$ 维的幺正矩阵并且具有 $N^2$ 个自由度（真实自由度）。这是由于 $U$ 具有 $N^2$ 个复数参量（即 $2N^2$ 个实数参量）以及 $N$ 个实约束条件和 $N(N-1)/2$ 个复约束条件（即总共 $N^2$ 个实约束条件）。真实自由度为 $2N^2$ 个实数参量减去 $N^2$ 个实约束条件，即为 $N^2$ 个自由度。\n", "\n", "(a) 矩阵 $U$ 的正余弦分解含有 $N$ 个DIAG 和 $N$ 个 MP_Y 线路，而每个 DIAG（或 MP_Y）线路都依赖于 $N$ (或 $N/2$) 个相位角。仅 DIAG 线路就具有足够多的 $N^2$ 自由度来构建 $U$ 的 $N^2$ 个自由度。显然 *Qubiter* 所用的 CSD 会产生冗余量。不过由于正余弦分解的非唯一性，可以通过寻找在 DIAG 和 MP_Y 线路中不产生额外相位角的正余弦分解来解决这个问题。\n", "\n", "(b) 此正余弦分解会得到 $N^2 = 2^{2n}$ 量级的 CNOT 门和单量子比特旋转，所以对于 $N$ 比较小的情况比较适合。而当 $N$ 非常大的情况下，此方法不再适用。此时可以通过寻找对单个 MP_Y 和 DIAG 线路的近似来简化问题。\n", "\n", "显然，对于问题（a）和（b）还有很大的改进空间。" ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.10.9" }, "nbpresent": { "slides": {}, "themes": { "default": "a50a26ea-9250-4d78-a796-a4577cc9eaa1", "theme": { "a50a26ea-9250-4d78-a796-a4577cc9eaa1": { "id": "a50a26ea-9250-4d78-a796-a4577cc9eaa1", "palette": { "19cc588f-0593-49c9-9f4b-e4d7cc113b1c": { "id": "19cc588f-0593-49c9-9f4b-e4d7cc113b1c", "rgb": [ 252, 252, 252 ] }, "31af15d2-7e15-44c5-ab5e-e04b16a89eff": { "id": "31af15d2-7e15-44c5-ab5e-e04b16a89eff", "rgb": [ 68, 68, 68 ] }, "50f92c45-a630-455b-aec3-788680ec7410": { "id": "50f92c45-a630-455b-aec3-788680ec7410", "rgb": [ 155, 177, 192 ] }, "c5cc3653-2ee1-402a-aba2-7caae1da4f6c": { "id": "c5cc3653-2ee1-402a-aba2-7caae1da4f6c", "rgb": [ 43, 126, 184 ] }, "efa7f048-9acb-414c-8b04-a26811511a21": { "id": "efa7f048-9acb-414c-8b04-a26811511a21", "rgb": [ 25.118061674008803, 73.60176211453744, 107.4819383259912 ] } }, "rules": { "blockquote": { "color": "50f92c45-a630-455b-aec3-788680ec7410" }, "code": { "font-family": "Anonymous Pro" }, "h1": { "color": "c5cc3653-2ee1-402a-aba2-7caae1da4f6c", "font-family": "Lato", "font-size": 8 }, "h2": { "color": "c5cc3653-2ee1-402a-aba2-7caae1da4f6c", "font-family": "Lato", "font-size": 6 }, "h3": { "color": "50f92c45-a630-455b-aec3-788680ec7410", "font-family": "Lato", "font-size": 5.5 }, "h4": { "color": "c5cc3653-2ee1-402a-aba2-7caae1da4f6c", "font-family": "Lato", "font-size": 5 }, "h5": { "font-family": "Lato" }, "h6": { "font-family": "Lato" }, "h7": { "font-family": "Lato" }, "pre": { "font-family": "Anonymous Pro", "font-size": 4 } }, "text-base": { "font-family": "Merriweather", "font-size": 4 } } } } }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "30px", "width": "252px" }, "navigate_menu": true, "number_sections": false, "sideBar": true, "threshold": 4, "toc_cell": false, "toc_section_display": "block", "toc_window_display": false, "widenNotebook": false } }, "nbformat": 4, "nbformat_minor": 4 }