{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Quantum CSD Compiling Intro\n", "\n", "The purpose of this notebook is to give a quick introduction to Qubiter's \n", "CSD quantum compiler capabilities. \n", "\n", "By a quantum complier, we mean\n", "a computer program that takes as input an arbitrary unitary matrix $U$ of dimension $N=2^n$\n", "and returns a SEO (sequence of elementary operations, in this case CNOTs and single qubit\n", "rotations) that equals $U$. There are various kinds of quantum \n", "compilers. Suppose $U$ is of the form $U=e^{-itH}$, where $t$ is time and $H$ is\n", "the Hamiltonian operator. If $H$ has a form which is known a priori, a situation\n", "that is common in Physics and Chemistry, then a popular way of expanding $U$\n", "is by using the Trotter-Suzuki approximation. If the form of $H$ is not\n", "known a priori as is common in Artificial Intelligence, then\n", "we recommend using the CS (Cosine-Sine) decomposition of Linear Algebra.\n", "Both methods are already implemented in Qubiter, but this notebook is about\n", "the CSD.\n", "\n", "Doing CSD quantum compiling with Qubiter requires using the classes in the quantum_CSD_compiler\n", "folder, which will only work properly if you install, besides all the Qubiter\n", "Python files and a Python distro that includes numpy and scipy (for example, Anaconda),\n", "some binary libraries prepared by Artiste-q.net which include\n", "a Python wrapper for a LAPACK subroutine\n", "called cuncsd.f that performs CSDs. How to install those binary libraries\n", "is explained elsewhere in this site. Henceforth, we will assume \n", "all the necessary files have been installed on your computer if you want to redo the calculations.\n", "\n", "The quantum_CSD_compiler folder includes a pdf called csd-intro.pdf that gives\n", "an introduction to the CSD. \n", "\n", "Some external references:\n", "\n", "\n", "1. R.R. Tucci, A Rudimentary Quantum Compiler(2cnd Ed.)\n", " https://arxiv.org/abs/quant-ph/9902062\n", "\n", "2. Qubiter 1.11, a C++ program whose first version was released together\n", " with Ref.1 above. Qubiter 1.11 is included in the\n", " quantum_CSD_compiler/LEGACY folder of this newer, pythonic version of Qubiter\n", " \n", "3. R.R. Tucci, Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition, https://arxiv.org/abs/quant-ph/0411097\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Qubiter applies CSD recursively\n", "to build a tree of node matrices. The product of those node matrices,\n", "if read in the correct order, is equal to the input matrix $U$.\n", "\n", "As an example, let us use for $U$ a 3 qubit quantum Fourier matrix.\n", "We can create an object of class Tree with $U$ \n", "as input as follows" ] }, { "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": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "loaded OneQubitGate, WITHOUT autograd.numpy\n" ] } ], "source": [ "import numpy as np\n", "import cuncsd_sq as csd\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": {}, "outputs": [], "source": [ "num_qbits = 3\n", "init_unitary_mat = FouSEO_writer.fourier_trans_mat(1 << num_qbits)\n", "emb = CktEmbedder(num_qbits, num_qbits)\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": {}, "source": [ "The above code automatically creates an expansion of $U$ \n", "into DIAG and MP_Y lines. Next we print the Picture file that was created." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "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": {}, "source": [ "Let us also print the corresponding English file that was created." ] }, { "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": {}, "source": [ "In the Picture files, a DIAG\n", "appears as a chain of percents, whereas an MP_Y appears as a chain of percents\n", "and an additional Ry gate. As you can\n", "see, the Picture file gives a nice picture of the DIAG and MP_Y gates,\n", "but the English file is much more specific. Look at Qubiter's Rosetta Stone\n", "(qubiter_rosetta_stone.pdf)\n", "if you want to understand how to interpret \n", "the parameters of DIAG and MP_Y lines.\n", "\n", "A DIAG represents a diagonal matrix with diagonal entries that\n", "are unit magnitude complex numbers, making the matrix unitary.\n", "\n", "An MP_Y represents a matrix of the form\n", "\n", "$\\left[\\begin{array}{cc} cc & ss \\\\ -ss & cc \\end{array}\\right]$\n", "\n", "where $cc$ and $ss$ are real diagonal matrices of the same size \n", "such that $cc^2 + ss^2 = 1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The class DiagUnitaryExpander\n", "will take any English file and \n", "write new English and Picture files wherein \n", "\n", "* all lines except those starting with DIAG are echoed,\n", "* lines starting with DIAG are replaced by an exact or approximate\n", "multiline expansion. \n", "\n", "Likewise, the class MultiplexorExpander\n", "will take any English file and \n", "write new English and Picture files wherein \n", "\n", "* all lines except those starting with MP_Y are echoed,\n", "* lines starting with MP_Y are replaced by an exact or approximate\n", "multiline expansion. \n", "\n", "We could use these 2 expander\n", "classes to construct new English and Picture files from the English \n", "file printed above. This would lead to an English file\n", "that consisted of only CNOTs and qubit rotations. If the \n", "gates of that new English file were multiplied,\n", "the product would equal the original $U$. Such an English file would\n", "be very long and not too instructive so we won't show it here.\n", "Instead, we will show an exact expansion of a single DIAG and \n", "of a single MP_Y.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, we create English and Picture files containing\n", "an expansion of the 4 qubit gate\n", "\n", "%---%---%---%\n", "\n", "This represents a diagonal unitary matrix. The \n", "angles are chosen at random and stored in the variable rad_angles.\n", "We then print the Picture file." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "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_qbits = 4\n", "num_angles = (1 << num_qbits)\n", "emb = CktEmbedder(num_qbits, num_qbits)\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": {}, "source": [ "We can check that our exact expansion is correct\n", "as follows. We can multiply the gates of the expansion\n", "using the class SEO_MatrixProduct. Call the gate product matpro.prod_arr.\n", "Using the angles rad_angles that we stored,\n", "we can construct the exact diagonal unitary, call it exact_mat.\n", "Call err the norm of matpro.prod_arr - exact_mat,\n", "and print err." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "diag unitary error= 8.097806875329685e-08\n" ] } ], "source": [ "matpro = SEO_MatrixProduct(file_prefix, num_qbits)\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": {}, "source": [ "Next, we create English and Picture files containing\n", "an expansion of the 4 qubit gate\n", "\n", "Ry--%---%---%\n", "\n", "This represents a multiplexor matrix. The \n", "angles are chosen at random and stored in the variable rad_angles.\n", "We then print the Picture file." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "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_qbits = 4\n", "num_angles = (1 << (num_qbits-1))\n", "emb = CktEmbedder(num_qbits, num_qbits)\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": {}, "source": [ "We can check that our exact expansion is correct\n", "as follows. We can multiply the gates of the expansion\n", "using the class SEO_MatrixProduct. Call the gate product matpro.prod_arr.\n", "Using the angles rad_angles that we stored,\n", "we can construct the exact multiplexor matrix, call it exact_mat.\n", "Call err the norm of matpro.prod_arr - exact_mat,\n", "and print err." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "multiplexor error= 3.855018685550896e-08\n" ] } ], "source": [ "matpro = SEO_MatrixProduct(file_prefix, num_qbits)\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": {}, "source": [ "A moral of the above calculations is that using CSD\n", "quantum compiling blindly will give a SEO for a quantum Fourier Transform QFT that is exponential in the number of qubits $n$. And yet we know that Coppersmith came up with an expansion for the QFT that is polynomial in $n$. But there is hope: CSD is not a unique decomposition.\n", "Ref.3 explains how one can coax a CSD compiler to yield Coppersmith's decompostion.\n", "\n", "Let $U$ be N dimensional, with $N = 2^n$, where $n$ = number of\n", "qubits. A general N dimensional unitary matrix has $N^2$ dofs (real\n", "degrees of freedom). That's because it has $N^2$ complex entries, so $2N^2$\n", "real parameters, but those parameters are subject to N real constraints\n", "and N(N-1)/2 complex constraints, for a total of $N^2$ real constraints.\n", "So $2N^2$ real parameters minus N^2 real constraints gives $N^2$ dofs.\n", "\n", "(a) Each DIAG (MP_Y, resp.) line of the CS decomp of $U$\n", "depends on N (N/2, resp.) angles and there are about N DIAG and N MP_Y\n", "lines. So the DIAG lines alone have enough dofs, $N^2$ of them, to cover\n", "all $N^2$ dofs of $U$. So clearly, there is a lot of\n", "redundancy in the CS decomp used by Qubiter. But, there is hope: the CS\n", "decomp is not unique, and it might be possible to choose a CS decomp\n", "that makes zero many of the angles in the DIAG and MP_Y lines. \n", "\n", "(b) The CS decomp as used here leads to order $N^2 = 2^{2n}$ cnots and\n", "qubit rotations so it is impractical for large N. But for small N,\n", "it can be useful. For large N, it might be possible to discover\n", "approximations to individual MP_Y and DIAG lines.\n", " \n", "Clearly, there is much room for future research to improve (a) and (b).\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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": true, "sideBar": true, "threshold": 4, "toc_cell": false, "toc_section_display": "block", "toc_window_display": false, "widenNotebook": false } }, "nbformat": 4, "nbformat_minor": 4 }