depth_cost.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Depth Cost\n",
    "\n",
    "In this notebook, we will check if our assumed depth count model, denoted as $\\textsf{depth}(\\cdot)$, is valid. The depth is derived as moment length over a quantum circuit when decomposed into $CNOT$ and single-qubit gates. For simplicity, we did not assume single-qubit gate merging between the moments of the circuit. The depth costs of the following quantum circuits are included :  \n",
    "- Draper Adder \n",
    "- Doubly Controlled-Draper Adder\n",
    "- Grover Iterate.\n",
    "\n",
    "\n",
    "### Check Unitary Equivalence \n",
    "\n",
    "The cost derivation is done by decomposing quantum circuits into CNOT and single-qubit gates. The decomposition rules are known ones, but to ensure correctness, we added an equivalence check between the original quantum circuit and the decomposed one, which involves unitary matrix calculations. This requires a lot of computation power for larger qubit size (n). To bypass the equivalence check, comment out the code `cirq.allclose_up_to_global_phase`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Draper Adder\n",
    "\n",
    "The decomposition of Draper Adder is done by decomposing QFT and (single-)controlled phases.\n",
    "Firstly, Drapper Adder is implemented via $CR_k$ gates and $QFT$, then each gate is decomposed into $CNOT$+single qubit gates by defined rule which is implemented in `./casestudy_pgm/draper_related_utils.py`. Check that custom gate class `my_QFT` and `my_C_R_k_gate`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of Draper Adder : 10*n - 20\n",
      "Target Program Qubit Len : 4\n",
      "Decomposed circuit\n",
      "                                                            ┌─────┐\n",
      "0: ──────────────────────────────@───────────────────────────────────────────────────────────────────\n",
      "                                 │\n",
      "1: ───T──────────────────────────┼───────────@──────────@────@───────────────────────────────────────\n",
      "                                 │           │          │    │\n",
      "2: ───H───T───X───T^-1───X───H───X───H───T───X───T^-1───X────┼T^-1───────────────────X───T───X───H───\n",
      "              │          │                                   │                       │       │\n",
      "3: ───T───────@──────────@───H───H───────────────────────────X────────H───H───T^-1───@───────@───────\n",
      "                                                            └─────┘\n",
      "Target Program Qubit Len : 6\n",
      "Decomposed circuit\n",
      "                                             ┌──┐                                                    ┌────────┐                                                ┌─────┐                                         ┌─────┐\n",
      "0: ────────────────────────────────────────────────────────────────────@──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                       │\n",
      "1: ───T────────────────────────────────────────────────────────────────┼──────────────@──────────@────@───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                       │              │          │    │\n",
      "2: ───Z^(1/8)──────────────────────────────────────────────────────────┼──────────────┼──────────┼────┼───────────@──────────────@───T──────────@──────────@────@─────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                       │              │          │    │           │              │              │          │    │\n",
      "3: ───H─────────T───X───T^-1───X───Z^(1/8)────X─────Z^(-1/8)───X───H───X───H──────T───X───T^-1───X────┼Z^(1/8)────X───Z^(-1/8)───X───Z^(-1/8)───┼──────────┼────┼───────────────────────────────────────────────X────────Z^(1/8)───X───T^-1───X───T───X───H───\n",
      "                    │          │              │                │                                      │                                         │          │    │                                               │                  │          │       │\n",
      "4: ───T─────────────@──────────@───H──────────┼T───────────────┼───────X───T^-1───X───H───────────────X───────────H───T─────────────────────────X───T^-1───X────┼T^-1───────────────────X───T───X───H───────────┼T^-1──────────────┼──────────@───────@───────\n",
      "                                              │                │       │          │                                                                             │                       │       │               │                  │\n",
      "5: ───Z^(1/8)─────────────────────────────────@────────────────@───T───@──────────@───H───H─────────────────────────────────────────────────────────────────────X────────H───H───T^-1───@───────@───Z^(-1/8)────@──────────────────@──────────────────────────\n",
      "                                             └──┘                                                    └────────┘                                                └─────┘                                         └─────┘\n",
      "Target Program Qubit Len : 8\n",
      "Decomposed circuit\n",
      "                                              ┌──┐                             ┌──┐               ┌──┐             ┌──┐                                    ┌────────┐                                 ┌──┐               ┌──┐   ┌──────────┐                                                ┌─────┐                                         ┌─────┐                             ┌──┐              ┌──┐              ┌─────┐\n",
      "0: ─────────────────────────────────────────────────────────────────────────────────────────────────────────────────@──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                                                                    │\n",
      "1: ───T─────────────────────────────────────────────────────────────────────────────────────────────────────────────┼────────────────────@──────────@───────@──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                                                                    │                    │          │       │\n",
      "2: ───Z^(1/8)───────────────────────────────────────────────────────────────────────────────────────────────────────┼────────────────────┼──────────┼───────┼───────────@──────────────@───T───────────@──────────────────@──────@─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                                                                    │                    │          │       │           │              │               │                  │      │\n",
      "3: ───Z^(1/16)──────────────────────────────────────────────────────────────────────────────────────────────────────┼────────────────────┼──────────┼───────┼───────────┼──────────────┼───────────────┼@─────────────────┼@─────┼Z^(1/8)──────@──────────────@───T──────────@──────────@────@─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                                                                    │                    │          │       │           │              │               ││                 ││     │             │              │              │          │    │\n",
      "4: ───H──────────T───X───T^-1───X───Z^(1/8)────X─────Z^(-1/8)───X───Z^(1/16)────X─────Z^(-1/16)────X─────H──────────X─────H──────────T───X───T^-1───X───────┼Z^(1/8)────X───Z^(-1/8)───X───Z^(1/16)────┼X────Z^(-1/16)────┼X─────┼Z^(-1/16)────┼──────────────┼──────────────┼──────────┼────┼────────────────────────────────────────────────────────────────────────────────────X────Z^(1/16)─────X────Z^(-1/8)────X────────Z^(1/8)───X───T^-1───X───T───X───H───\n",
      "                     │          │              │                │               │                  │                                                        │                                          │                  │      │             │              │              │          │    │                                                                                    │                 │                │                  │          │       │\n",
      "5: ───T──────────────@──────────@───H──────────┼T───────────────┼───────────────┼X────T^-1─────────┼X────Z^(1/8)────X─────Z^(-1/8)───X───H──────────────────X───────────H───T──────────────────────────X─────T^-1─────────X──────┼Z^(1/8)──────X───Z^(-1/8)───X───Z^(-1/8)───┼──────────┼────┼───────────────────────────────────────────────X────────Z^(1/8)───X───T^-1─────────X┼────T───────────X┼────H───────────┼T^-1──────────────┼──────────@───────@───────\n",
      "                                               │                │               ││                 ││               │                │                                                                                           │                                           │          │    │                                               │                  │                ││                ││                │                  │\n",
      "6: ───Z^(1/8)──────────────────────────────────@────────────────@───T───────────┼@─────────────────┼@────H──────────┼T───────────────┼───────X──────T^-1────X───────────H────────────────────────────────────────────────────────X─────────────H───T─────────────────────────X───T^-1───X────┼T^-1───────────────────X───T───X───H───────────┼T^-1──────────────┼────────────────@┼────────────────@┼────Z^(-1/8)────@──────────────────@──────────────────────────\n",
      "                                                                                │                  │                │                │       │              │                                                                                                                                │                       │       │               │                  │                 │                 │\n",
      "7: ───Z^(1/16)──────────────────────────────────────────────────────────────────@──────────────────@─────Z^(1/8)────@────────────────@───T───@──────────────@───────────H───H────────────────────────────────────────────────────────────────────────────────────────────────────────────────X────────H───H───T^-1───@───────@───Z^(-1/8)────@──────────────────@───Z^(-1/16)─────@─────────────────@──────────────────────────────────────────────────────────────\n",
      "                                              └──┘                             └──┘               └──┘             └──┘                                    └────────┘                                 └──┘               └──┘   └──────────┘                                                └─────┘                                         └─────┘                             └──┘              └──┘              └─────┘\n",
      "Assertion Passed\n"
     ]
    }
   ],
   "source": [
    "from sympy import symbols\n",
    "import cirq\n",
    "from casestudy_pgm.draper_adder.draper_correct import draper_true, my_draper_true\n",
    "from qruntest.symbolic_cost_model import sym_moment_cost_for_my_draper\n",
    "from qruntest.utils import keep\n",
    "num_qbit_for_pgm = symbols(\"n\") \n",
    "depth_cost_fmla = sym_moment_cost_for_my_draper()\n",
    "print(f\"Depth of Draper Adder : {depth_cost_fmla}\")\n",
    "for n in range(4,10,2):  # since classic simulation(=unitary simulation) in equivalence check between original one and decomposed on may expensive ,\n",
    "                         #  only try on small qubits\n",
    "                         # if not to check \n",
    "    print(f\"Target Program Qubit Len : {n}\")\n",
    "    m = int(n/2)\n",
    "    ref_qc  = draper_true(m)\n",
    "    decomposed = cirq.Circuit([x for x in cirq.decompose(my_draper_true(m = m ), keep=keep)])\n",
    "    assert cirq.allclose_up_to_global_phase(cirq.unitary(ref_qc), cirq.unitary(decomposed))\n",
    "    depth_cost_fmla = sym_moment_cost_for_my_draper()\n",
    "    assert len(decomposed) == depth_cost_fmla.subs({num_qbit_for_pgm : n})\n",
    "    print(\"Decomposed circuit\")\n",
    "    print(decomposed)\n",
    "print(\"Assertion Passed\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Controlled Draper Adder\n",
    "\n",
    "The decomposition of Draper Adder is done by decomposing QFT and (double-)controlled phases. Firstly, Drapper Adder is implemented via $CCCR_k$ gates and $QFT$, then each gate is decomposed into $CNOT$+single qubit gates by defined rule which is implemented in `./casestudy_pgm/draper_related_utils.py`. Check that custom gate class `my_QFT` and `my_triple_C_R_k_gate`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import symbols\n",
    "import cirq\n",
    "from casestudy_pgm.double_con_draper_adder.double_con_draper_correct import double_con_draper_true, my_double_con_draper_true\n",
    "from qruntest.symbolic_cost_model import sym_moment_cost_for_my_double_con_draper\n",
    "from qruntest.utils import keep\n",
    "num_qbit_for_pgm = symbols(\"n\") \n",
    "depth_cost_fmla = sym_moment_cost_for_my_double_con_draper()\n",
    "\n",
    "print(f\"Depth of Draper Adder : {depth_cost_fmla}\")\n",
    "for n in range(6,12,2):  # since classic simulation(=unitary simulation) may expensive, only try on small qubits\n",
    "    print(f\"Target Program Qubit Len : {n}\")\n",
    "    m = int((n-2)/2)\n",
    "    ref_qc  = double_con_draper_true(m)\n",
    "    decomposed = cirq.Circuit([x for x in cirq.decompose(my_double_con_draper_true(m = m), keep=keep)])\n",
    "    assert cirq.allclose_up_to_global_phase(cirq.unitary(ref_qc), cirq.unitary(decomposed))\n",
    "    assert len(decomposed) == depth_cost_fmla.subs({num_qbit_for_pgm : n})\n",
    "print(\"Assertion Passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover Iterate (denoted as $G$ in the paper)\n",
    "\n",
    "The decomposition of Draper Adder is done by decomposing multiple anti-controlled gates $NC^mX$.\n",
    "Firstly, $NC^mX$ is decomposed into $NCNCX$, and then $NCNCX$ is further decomposed into $X$ and $CNOT$. The rules are defined in `./qruntest/qc_utils.py` within the custom gate class `my_antianti_con_toff`.\n",
    "\n",
    "Note that the depth cost of $G$ is a function of $n$, which is the qubit size of the target program to test, NOT the qubit size of $G$.\n",
    "When $G$ is applied for testing an $n$-qubit target prgoram (as part of running $s$-FPAA), its decomposed circuit is in $2n$-qubit register.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of Single Grover Operator : 42*n + 2*x - 52\n",
      "Target Program Qubit Len : 4\n",
      "                                                                    ┌──────────────┐                           ┌────────────┐\n",
      "0: ───(0)───────────────────────────────────────────────(0)───PGM───────────────(0)───────────────────────────────────────────────────────────────(0)───PGM───\n",
      "      │                                                 │     │                 │                                                                 │     │\n",
      "1: ───(0)───────────────────────────────────────────────(0)───PGM───────────────(0)───────────────────────────────────────────────────────────────(0)───PGM───\n",
      "      │                                                 │     │                 │                                                                 │     │\n",
      "2: ───┼─────(0)───────────────────────────────────(0)───┼─────PGM───────────────┼──────(0)──────────────────────────────────────────────────(0)───┼─────PGM───\n",
      "      │     │                                     │     │     │                 │      │                                                    │     │     │\n",
      "3: ───┼─────┼─────(0)───────────────────────(0)───┼─────┼─────PGM────Rz(-0.762π)┼──────┼─────X───Rz(-0.762π)───────────────X────Rz(1.52π)───┼─────┼─────PGM───\n",
      "      │     │     │                         │     │     │                       │      │     │                             │                │     │\n",
      "4: ───┼─────┼─────┼─────X───Rz(1.52π)───X───┼─────┼─────┼───────────────────────┼──────┼─────┼───X──────────────Rz(-0.762π)┼────X───────────┼─────┼───────────\n",
      "      │     │     │     │               │   │     │     │                       │      │     │   │                         │    │           │     │\n",
      "5: ───X─────@─────┼─────┼───────────────┼───┼─────@─────X───────────────────────X──────@─────┼───┼─────────────────────────┼────┼───────────@─────X───────────\n",
      "            │     │     │               │   │     │                                    │     │   │                         │    │           │\n",
      "6: ─────────X─────@─────┼───────────────┼───@─────X────────────────────────────────────X─────@───@─────────────────────────@────@───────────X─────────────────\n",
      "                  │     │               │   │\n",
      "7: ───────────────X─────@───────────────@───X─────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                    └──────────────┘                           └────────────┘\n",
      "Assertion Passed\n",
      "Target Program Qubit Len : 6\n",
      "                                                                                             ┌──────────────┐                                       ┌────────────┐\n",
      "0: ────(0)───────────────────────────────────────────────────────────────────────(0)───PGM───────────────(0)───────────────────────────────────────────────────────────────────────────────────────(0)───PGM───\n",
      "       │                                                                         │     │                 │                                                                                         │     │\n",
      "1: ────(0)───────────────────────────────────────────────────────────────────────(0)───PGM───────────────(0)───────────────────────────────────────────────────────────────────────────────────────(0)───PGM───\n",
      "       │                                                                         │     │                 │                                                                                         │     │\n",
      "2: ────┼─────(0)───────────────────────────────────────────────────────────(0)───┼─────PGM───────────────┼──────(0)──────────────────────────────────────────────────────────────────────────(0)───┼─────PGM───\n",
      "       │     │                                                             │     │     │                 │      │                                                                            │     │     │\n",
      "3: ────┼─────┼─────(0)───────────────────────────────────────────────(0)───┼─────┼─────PGM───────────────┼──────┼─────(0)──────────────────────────────────────────────────────────────(0)───┼─────┼─────PGM───\n",
      "       │     │     │                                                 │     │     │     │                 │      │     │                                                                │     │     │     │\n",
      "4: ────┼─────┼─────┼─────(0)───────────────────────────────────(0)───┼─────┼─────┼─────PGM───────────────┼──────┼─────┼─────(0)──────────────────────────────────────────────────(0)───┼─────┼─────┼─────PGM───\n",
      "       │     │     │     │                                     │     │     │     │     │                 │      │     │     │                                                    │     │     │     │     │\n",
      "5: ────┼─────┼─────┼─────┼─────(0)───────────────────────(0)───┼─────┼─────┼─────┼─────PGM────Rz(-0.762π)┼──────┼─────┼─────┼─────X───Rz(-0.762π)───────────────X────Rz(1.52π)───┼─────┼─────┼─────┼─────PGM───\n",
      "       │     │     │     │     │                         │     │     │     │     │                       │      │     │     │     │                             │                │     │     │     │\n",
      "6: ────┼─────┼─────┼─────┼─────┼─────X───Rz(1.52π)───X───┼─────┼─────┼─────┼─────┼───────────────────────┼──────┼─────┼─────┼─────┼───X──────────────Rz(-0.762π)┼────X───────────┼─────┼─────┼─────┼───────────\n",
      "       │     │     │     │     │     │               │   │     │     │     │     │                       │      │     │     │     │   │                         │    │           │     │     │     │\n",
      "7: ────X─────@─────┼─────┼─────┼─────┼───────────────┼───┼─────┼─────┼─────@─────X───────────────────────X──────@─────┼─────┼─────┼───┼─────────────────────────┼────┼───────────┼─────┼─────@─────X───────────\n",
      "             │     │     │     │     │               │   │     │     │     │                                    │     │     │     │   │                         │    │           │     │     │\n",
      "8: ──────────X─────@─────┼─────┼─────┼───────────────┼───┼─────┼─────@─────X────────────────────────────────────X─────@─────┼─────┼───┼─────────────────────────┼────┼───────────┼─────@─────X─────────────────\n",
      "                   │     │     │     │               │   │     │     │                                                │     │     │   │                         │    │           │     │\n",
      "9: ────────────────X─────@─────┼─────┼───────────────┼───┼─────@─────X────────────────────────────────────────────────X─────@─────┼───┼─────────────────────────┼────┼───────────@─────X───────────────────────\n",
      "                         │     │     │               │   │     │                                                            │     │   │                         │    │           │\n",
      "10: ─────────────────────X─────@─────┼───────────────┼───@─────X────────────────────────────────────────────────────────────X─────@───@─────────────────────────@────@───────────X─────────────────────────────\n",
      "                               │     │               │   │\n",
      "11: ───────────────────────────X─────@───────────────@───X─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────\n",
      "                                                                                             └──────────────┘                                       └────────────┘\n",
      "Assertion Passed\n"
     ]
    }
   ],
   "source": [
    "from qruntest.fpaa_circuit import fpaa_in_circuit\n",
    "from qruntest.utils import keep\n",
    "from qruntest.symbolic_cost_model import sym_static_moment_cost_one_grover_iterate\n",
    "from sympy import symbols\n",
    "import math,cirq\n",
    "\n",
    "num_qbit = symbols(\"n\")\n",
    "pgm_cost = symbols(\"x\") \n",
    "depth_cost_fmla = sym_static_moment_cost_one_grover_iterate()\n",
    "print(f\"Depth of Single Grover Operator : {depth_cost_fmla} (x for target program cost )\")\n",
    "for n in [4,6]: # simulation for checking unitary equivalence on >=6 qubits raises significant running time expense (or memory out).\n",
    "    print(f\"Target Program Qubit Len : {n}\")\n",
    "    targ_pgm_qbits = cirq.LineQubit.range(n)\n",
    "    temp_hadamards = cirq.Circuit([cirq.H(x) for x in targ_pgm_qbits]) # assuming target program depth cost to be 1\n",
    "    fpaa_one_grover_iterate = fpaa_in_circuit(pgm_qc = temp_hadamards,\n",
    "                                                l = 1,\n",
    "                                                delta = math.sqrt(0.05),\n",
    "                                                targ_reduce=True)\n",
    "    decomposed = cirq.Circuit( [x for x in cirq.decompose(fpaa_one_grover_iterate, keep=keep)])\n",
    "    fmal_res = depth_cost_fmla.subs({pgm_cost : 1, num_qbit:n})\n",
    "    assert len(decomposed) == fmal_res \n",
    "    assert cirq.allclose_up_to_global_phase(cirq.unitary(fpaa_one_grover_iterate), cirq.unitary(decomposed)) # to skip the simulation, comment here\n",
    "    print(fpaa_one_grover_iterate)\n",
    "    print(\"Assertion Passed\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.9.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}