reverse-carry-select-adder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Author: Edoardo Gabrielli\n",
    "\n",
    "Contact: gabrielli.1693726@studenti.uniroma1.it\n",
    "\n",
    "Based on the work of P.Sudheer Kumar Reddy and G. Saini for the paper \"Design of Carry Select Adder with Online Testability Using Reversible Gates, 2019\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit, transpile, QuantumRegister, ClassicalRegister, Aer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Define Gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Peres Gate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">               \n",
       "q_0: ──■────■──\n",
       "       │  ┌─┴─┐\n",
       "q_1: ──■──┤ X ├\n",
       "     ┌─┴─┐└───┘\n",
       "q_2: ┤ X ├─────\n",
       "     └───┘     </pre>"
      ],
      "text/plain": [
       "               \n",
       "q_0: ──■────■──\n",
       "       │  ┌─┴─┐\n",
       "q_1: ──■──┤ X ├\n",
       "     ┌─┴─┐└───┘\n",
       "q_2: ┤ X ├─────\n",
       "     └───┘     "
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Input: a, b, c\n",
    "\n",
    "Output:\n",
    "P = a\n",
    "Q = a + b\n",
    "R = a*b + c\n",
    "\"\"\"\n",
    "c = QuantumCircuit(3)\n",
    "c.ccx(0,1,2)\n",
    "c.cx(0,1)\n",
    "peres = c.to_gate(label=\"Peres\")\n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "in: 000 r: 000\n",
      "in: 001 r: 001\n",
      "in: 010 r: 010\n",
      "in: 011 r: 011\n",
      "in: 100 r: 110\n",
      "in: 101 r: 111\n",
      "in: 110 r: 101\n",
      "in: 111 r: 100\n"
     ]
    }
   ],
   "source": [
    "def generate_peres(a,b,c):\n",
    "    circuit = QuantumCircuit(3, 0)\n",
    "    if (a == '1'):\n",
    "        circuit.x(0)\n",
    "    if (b == '1'):\n",
    "        circuit.x(1)\n",
    "    if (c == '1'):\n",
    "        circuit.x(2)\n",
    "    circuit.ccx(0,1,2)\n",
    "    circuit.cx(0,1)\n",
    "    circuit.measure_all()\n",
    "    return circuit\n",
    "\n",
    "inputs = ['0', '1']\n",
    "for i in range(len(inputs)):\n",
    "    for j in range(len(inputs)):\n",
    "        for k in range(len(inputs)):\n",
    "            c = generate_peres(inputs[i], inputs[j], inputs[k])\n",
    "            usim = Aer.get_backend('unitary_simulator')\n",
    "            transpiled = transpile(c, backend=usim)\n",
    "            backend = Aer.get_backend('aer_simulator')\n",
    "            job = backend.run(transpiled, shots=1, memory=True)\n",
    "            output = job.result().get_memory()[0]\n",
    "            print(\"in: \"+inputs[i]+inputs[j]+inputs[k]+\" r: \"+output[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">        ┌───┐           ░ ┌─┐      \n",
       "   q_0: ┤ X ├──■────■───░─┤M├──────\n",
       "        ├───┤  │  ┌─┴─┐ ░ └╥┘┌─┐   \n",
       "   q_1: ┤ X ├──■──┤ X ├─░──╫─┤M├───\n",
       "        ├───┤┌─┴─┐└───┘ ░  ║ └╥┘┌─┐\n",
       "   q_2: ┤ X ├┤ X ├──────░──╫──╫─┤M├\n",
       "        └───┘└───┘      ░  ║  ║ └╥┘\n",
       "meas: 3/═══════════════════╩══╩══╩═\n",
       "                           0  1  2 </pre>"
      ],
      "text/plain": [
       "        ┌───┐           ░ ┌─┐      \n",
       "   q_0: ┤ X ├──■────■───░─┤M├──────\n",
       "        ├───┤  │  ┌─┴─┐ ░ └╥┘┌─┐   \n",
       "   q_1: ┤ X ├──■──┤ X ├─░──╫─┤M├───\n",
       "        ├───┤┌─┴─┐└───┘ ░  ║ └╥┘┌─┐\n",
       "   q_2: ┤ X ├┤ X ├──────░──╫──╫─┤M├\n",
       "        └───┘└───┘      ░  ║  ║ └╥┘\n",
       "meas: 3/═══════════════════╩══╩══╩═\n",
       "                           0  1  2 "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Full Adder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">     ┌────────┐             \n",
       "q_0: ┤0       ├─────────────\n",
       "     │        │   ┌────────┐\n",
       "q_1: ┤1 Peres ├───┤0       ├\n",
       "     │        │   │        │\n",
       "q_2: ┤2       ├─X─┤1 Peres ├\n",
       "     └────────┘ │ │        │\n",
       "q_3: ───────────X─┤2       ├\n",
       "                  └────────┘</pre>"
      ],
      "text/plain": [
       "     ┌────────┐             \n",
       "q_0: ┤0       ├─────────────\n",
       "     │        │   ┌────────┐\n",
       "q_1: ┤1 Peres ├───┤0       ├\n",
       "     │        │   │        │\n",
       "q_2: ┤2       ├─X─┤1 Peres ├\n",
       "     └────────┘ │ │        │\n",
       "q_3: ───────────X─┤2       ├\n",
       "                  └────────┘"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Input: \n",
    "a = 1st operand, \n",
    "b = 2nd operand, \n",
    "c = 0, \n",
    "d = c_in\n",
    "\n",
    "Output: \n",
    "P = garbage, \n",
    "Q = garbage, \n",
    "R = sum, \n",
    "T = carry\n",
    "\"\"\"\n",
    "c = QuantumCircuit(4)\n",
    "c.append(peres, [0,1,2])\n",
    "c.swap(2,3)\n",
    "c.append(peres, [1,2,3])\n",
    "#c = c.reverse_bits()\n",
    "fa = c.to_gate(label=\"RFA\")\n",
    "c.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                         \n",
       "q_0: ──■────■────────────\n",
       "       │  ┌─┴─┐          \n",
       "q_1: ──■──┤ X ├──■────■──\n",
       "     ┌─┴─┐└───┘  │  ┌─┴─┐\n",
       "q_2: ┤ X ├──X────■──┤ X ├\n",
       "     └───┘  │  ┌─┴─┐└───┘\n",
       "q_3: ───────X──┤ X ├─────\n",
       "               └───┘     </pre>"
      ],
      "text/plain": [
       "                         \n",
       "q_0: ──■────■────────────\n",
       "       │  ┌─┴─┐          \n",
       "q_1: ──■──┤ X ├──■────■──\n",
       "     ┌─┴─┐└───┘  │  ┌─┴─┐\n",
       "q_2: ┤ X ├──X────■──┤ X ├\n",
       "     └───┘  │  ┌─┴─┐└───┘\n",
       "q_3: ───────X──┤ X ├─────\n",
       "               └───┘     "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = QuantumCircuit(4)\n",
    "c.append(fa, [0,1,2,3])\n",
    "transpiled = transpile(c, backend=usim)\n",
    "transpiled.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "in: 000 r: 00\n",
      "in: 001 r: 01\n",
      "in: 010 r: 01\n",
      "in: 011 r: 10\n",
      "in: 100 r: 01\n",
      "in: 101 r: 10\n",
      "in: 110 r: 10\n",
      "in: 111 r: 11\n"
     ]
    }
   ],
   "source": [
    "def generate_fa(a,b,d):\n",
    "    '''\n",
    "    a = first addend\n",
    "    b = second addend\n",
    "    d = carry input\n",
    "    '''\n",
    "    circuit = QuantumCircuit(4, 2)\n",
    "    if (a == '1'):\n",
    "        circuit.x(0)\n",
    "    if (b == '1'):\n",
    "        circuit.x(1)\n",
    "    if (d == '1'):\n",
    "        circuit.x(3)\n",
    "    circuit.append(peres, [0,1,2])\n",
    "    circuit.append(peres, [1,3,2])\n",
    "    circuit.measure(3,0)\n",
    "    circuit.measure(2,1)\n",
    "    #circuit.measure_all()\n",
    "    return circuit\n",
    "\n",
    "inputs = ['0','1']\n",
    "for i in range(len(inputs)):\n",
    "    for j in range(len(inputs)):\n",
    "        for k in range(len(inputs)):\n",
    "            c = generate_fa(inputs[i], inputs[j], inputs[k])\n",
    "            usim = Aer.get_backend('unitary_simulator')\n",
    "            transpiled = transpile(c, backend=usim)\n",
    "            backend = Aer.get_backend('aer_simulator')\n",
    "            job = backend.run(transpiled, shots=1, memory=True)\n",
    "            output = job.result().get_memory()[0]\n",
    "            print(\"in: \"+inputs[i]+inputs[j]+inputs[k]+\" r: \"+output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSA Design-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each stage of the CSA can be designed as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                       ┌──────┐                   \n",
       "     a: ───────■───────┤0     ├───────────────────\n",
       "               │       │      │                   \n",
       "     b: ───────┼────■──┤1     ├───────────────────\n",
       "             ┌─┴─┐  │  │      │┌──────┐           \n",
       "    a': ─|0>─┤ X ├──┼──┤      ├┤0     ├───────────\n",
       "             └───┘┌─┴─┐│      ││      │           \n",
       "    b': ─|0>──────┤ X ├┤  RFA ├┤1     ├───────────\n",
       "                  └───┘│      ││      │           \n",
       "   c_0: ─|0>───────────┤3     ├┤      ├────X───■──\n",
       "             ┌───┐     │      ││  RFA │    │   │  \n",
       "   c_1: ─|0>─┤ X ├─────┤      ├┤3     ├────X───┼──\n",
       "             └───┘     │      ││      │    │   │  \n",
       "zero_0: ─|0>───────────┤2     ├┤      ├─X──┼───┼──\n",
       "                       └──────┘│      │ │  │   │  \n",
       "zero_1: ─|0>───────────────────┤2     ├─X──┼───┼──\n",
       "                               └──────┘ │  │ ┌─┴─┐\n",
       "zero_2: ────────────────────────────────┼──┼─┤ X ├\n",
       "                                        │  │ └───┘\n",
       "c_in_0: ───────■────────────────────────┼──■──────\n",
       "             ┌─┴─┐                      │         \n",
       "c_in_1: ─|0>─┤ X ├──────────────────────■─────────\n",
       "             └───┘                                </pre>"
      ],
      "text/plain": [
       "                       ┌──────┐                   \n",
       "     a: ───────■───────┤0     ├───────────────────\n",
       "               │       │      │                   \n",
       "     b: ───────┼────■──┤1     ├───────────────────\n",
       "             ┌─┴─┐  │  │      │┌──────┐           \n",
       "    a': ─|0>─┤ X ├──┼──┤      ├┤0     ├───────────\n",
       "             └───┘┌─┴─┐│      ││      │           \n",
       "    b': ─|0>──────┤ X ├┤  RFA ├┤1     ├───────────\n",
       "                  └───┘│      ││      │           \n",
       "   c_0: ─|0>───────────┤3     ├┤      ├────X───■──\n",
       "             ┌───┐     │      ││  RFA │    │   │  \n",
       "   c_1: ─|0>─┤ X ├─────┤      ├┤3     ├────X───┼──\n",
       "             └───┘     │      ││      │    │   │  \n",
       "zero_0: ─|0>───────────┤2     ├┤      ├─X──┼───┼──\n",
       "                       └──────┘│      │ │  │   │  \n",
       "zero_1: ─|0>───────────────────┤2     ├─X──┼───┼──\n",
       "                               └──────┘ │  │ ┌─┴─┐\n",
       "zero_2: ────────────────────────────────┼──┼─┤ X ├\n",
       "                                        │  │ └───┘\n",
       "c_in_0: ───────■────────────────────────┼──■──────\n",
       "             ┌─┴─┐                      │         \n",
       "c_in_1: ─|0>─┤ X ├──────────────────────■─────────\n",
       "             └───┘                                "
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "This circuit represents a single stage of the CSA with the optimization.\n",
    "\n",
    "Input:\n",
    "1 = first operand, represents \"a\"\n",
    "2 = second operand, represents \"b\"\n",
    "3 = 0, ancilla, copy of \"a\"\n",
    "4 = 0, ancilla, copy of \"b\"\n",
    "5 = 0, ancilla, represents \"c=0\"\n",
    "6 = 1, ancilla, represents \"c=1\"\n",
    "7 = 0, ancilla\n",
    "8 = 0, ancilla\n",
    "9 = 0, ancilla\n",
    "10 = input carry\n",
    "11 = 0, ancilla\n",
    "\n",
    "Output:\n",
    "1 = g\n",
    "2 = g\n",
    "3 = g\n",
    "4 = g\n",
    "5 = carry\n",
    "6 = g\n",
    "7 = sum\n",
    "8 = g\n",
    "9 = carry\n",
    "10 = g\n",
    "11 = g\n",
    "\n",
    "8 ancilla bits and 8 garbage bits (the copy of the carry is not garbage since it is used by the next stages).\n",
    "\"\"\"\n",
    "\n",
    "a_in = QuantumRegister(1, name=\"a\")\n",
    "b_in = QuantumRegister(1, name=\"b\")\n",
    "a_copies = QuantumRegister(1, name=\"a'\")\n",
    "b_copies = QuantumRegister(1, name=\"b'\")\n",
    "carries = QuantumRegister(2, name=\"c\")\n",
    "zero = QuantumRegister(3, name=\"zero\")\n",
    "c_in = QuantumRegister(2, name=\"c_in\")\n",
    "\n",
    "csa = QuantumCircuit(a_in, b_in, a_copies, b_copies, carries, zero, c_in)\n",
    "csa.reset(a_copies[0])\n",
    "csa.reset(b_copies[0])\n",
    "csa.cx(a_in[0], a_copies[0])                                        # a' = a\n",
    "csa.cx(b_in[0], b_copies[0])                                        # b' = b\n",
    "csa.reset(carries[0])                                               # c = 0\n",
    "csa.reset(carries[1])\n",
    "csa.x(carries[1])                                                   # c = 1\n",
    "csa.reset(zero[0])\n",
    "csa.reset(zero[1])\n",
    "csa.reset(c_in[1])                                                  # c_in' = c_in\n",
    "\n",
    "csa.cx(c_in[0], c_in[1])\n",
    "csa.append(fa, [a_in[0], b_in[0], zero[0], carries[0]])\n",
    "csa.append(fa, [a_copies[0], b_copies[0], zero[1], carries[1]])\n",
    "csa.fredkin(c_in[1], zero[0], zero[1])\n",
    "csa.fredkin(c_in[0], carries[0], carries[1])\n",
    "\n",
    "csa.cx(carries[0], zero[2])                                         # Buffer\n",
    "\n",
    "csa.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design-1 opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since c_in[0] is left unused after the FG gate, we can reset and give it in input to the CNOT gate, saving one qubit. Below is shown that this apparent optimization comes not free in terms of delay."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                       ┌──────┐                        \n",
       "     a: ───────■───────┤0     ├────────────────────────\n",
       "               │       │      │                        \n",
       "     b: ───────┼────■──┤1     ├────────────────────────\n",
       "             ┌─┴─┐  │  │      │┌──────┐                \n",
       "    a': ─|0>─┤ X ├──┼──┤      ├┤0     ├────────────────\n",
       "             └───┘┌─┴─┐│      ││      │                \n",
       "    b': ─|0>──────┤ X ├┤  RFA ├┤1     ├────────────────\n",
       "                  └───┘│      ││      │                \n",
       "   c_0: ─|0>───────────┤3     ├┤      ├────X────────■──\n",
       "             ┌───┐     │      ││  RFA │    │        │  \n",
       "   c_1: ─|0>─┤ X ├─────┤      ├┤3     ├────X────────┼──\n",
       "             └───┘     │      ││      │    │        │  \n",
       "zero_0: ─|0>───────────┤2     ├┤      ├─X──┼────────┼──\n",
       "                       └──────┘│      │ │  │        │  \n",
       "zero_1: ─|0>───────────────────┤2     ├─X──┼────────┼──\n",
       "                               └──────┘ │  │      ┌─┴─┐\n",
       "c_in_0: ───────■────────────────────────┼──■──|0>─┤ X ├\n",
       "             ┌─┴─┐                      │         └───┘\n",
       "c_in_1: ─|0>─┤ X ├──────────────────────■──────────────\n",
       "             └───┘                                     </pre>"
      ],
      "text/plain": [
       "                       ┌──────┐                        \n",
       "     a: ───────■───────┤0     ├────────────────────────\n",
       "               │       │      │                        \n",
       "     b: ───────┼────■──┤1     ├────────────────────────\n",
       "             ┌─┴─┐  │  │      │┌──────┐                \n",
       "    a': ─|0>─┤ X ├──┼──┤      ├┤0     ├────────────────\n",
       "             └───┘┌─┴─┐│      ││      │                \n",
       "    b': ─|0>──────┤ X ├┤  RFA ├┤1     ├────────────────\n",
       "                  └───┘│      ││      │                \n",
       "   c_0: ─|0>───────────┤3     ├┤      ├────X────────■──\n",
       "             ┌───┐     │      ││  RFA │    │        │  \n",
       "   c_1: ─|0>─┤ X ├─────┤      ├┤3     ├────X────────┼──\n",
       "             └───┘     │      ││      │    │        │  \n",
       "zero_0: ─|0>───────────┤2     ├┤      ├─X──┼────────┼──\n",
       "                       └──────┘│      │ │  │        │  \n",
       "zero_1: ─|0>───────────────────┤2     ├─X──┼────────┼──\n",
       "                               └──────┘ │  │      ┌─┴─┐\n",
       "c_in_0: ───────■────────────────────────┼──■──|0>─┤ X ├\n",
       "             ┌─┴─┐                      │         └───┘\n",
       "c_in_1: ─|0>─┤ X ├──────────────────────■──────────────\n",
       "             └───┘                                     "
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "This circuit represents a single stage of the CSA with the optimization.\n",
    "\"\"\"\n",
    "\n",
    "a_in = QuantumRegister(1, name=\"a\")\n",
    "b_in = QuantumRegister(1, name=\"b\")\n",
    "a_copies = QuantumRegister(1, name=\"a'\")\n",
    "b_copies = QuantumRegister(1, name=\"b'\")\n",
    "carries = QuantumRegister(2, name=\"c\")\n",
    "zero = QuantumRegister(2, name=\"zero\")\n",
    "c_in = QuantumRegister(2, name=\"c_in\")\n",
    "\n",
    "csa = QuantumCircuit(a_in, b_in, a_copies, b_copies, carries, zero, c_in)\n",
    "csa.reset(a_copies[0])\n",
    "csa.reset(b_copies[0])\n",
    "csa.cx(a_in[0], a_copies[0])                                        # a' = a\n",
    "csa.cx(b_in[0], b_copies[0])                                        # b' = b\n",
    "csa.reset(carries[0])                                               # c = 0\n",
    "csa.reset(carries[1])\n",
    "csa.x(carries[1])                                                   # c = 1\n",
    "csa.reset(zero[0])\n",
    "csa.reset(zero[1])\n",
    "csa.reset(c_in[1])                                                  # c_in' = c_in\n",
    "\n",
    "csa.cx(c_in[0], c_in[1])\n",
    "csa.append(fa, [a_in[0], b_in[0], zero[0], carries[0]])\n",
    "csa.append(fa, [a_copies[0], b_copies[0], zero[1], carries[1]])\n",
    "csa.fredkin(c_in[1], zero[0], zero[1])\n",
    "csa.fredkin(c_in[0], carries[0], carries[1])\n",
    "\n",
    "csa.reset(c_in[0])                                                  # Recycle c_in for the output of buffers\n",
    "\n",
    "csa.cx(carries[0], c_in[0])                                         # Buffer\n",
    "\n",
    "csa.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that although the logic gates are represented in series, the circuit will be re-arranged by the transpiler in order to execute gates in parallel where possible. For instance, if you swap the position of \"b\" with \"a'\" it is clear that the two CNOTs at the beginning of the circuit can be run simultaneously.\n",
    "\n",
    "If we want to make a two stage CSA, we have to connect the input qubits \"i\" and \"l\" (the carries propagated by the first stage) of the second CSA to the output T and X of the first one. To force the parallel execution of the four RFAs instead, we have to use 9 qubits for the first stage and 9 more qubits for the second stage. Therefore the total number of qubits used to implement the circuit is 9n-3.\n",
    "\n",
    "The number of garbage bits is given by 9n-3-(n+1) = 8n-4, where n+1 is given by: \"n\" for the number of bits representing the result and 1 for the carry out. \n",
    "\n",
    "Ancilla bits are instead 7n-1, because we have n copy of \"a\", n copy of \"b\", 2n copies of zeros, n copies of input carries (c=0 and c=1) and n-1 zeros for the buffers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                                                                        \n",
       "     a: ──■─────────■────■──────────────────────────────────────────────\n",
       "          │         │  ┌─┴─┐                                            \n",
       "     b: ──┼────■────■──┤ X ├──────────■─────────■───────────────────────\n",
       "        ┌─┴─┐  │    │  └───┘          │         │                       \n",
       "    a': ┤ X ├──┼────┼────■────■───────┼─────────┼───────────────────────\n",
       "        └───┘┌─┴─┐  │    │  ┌─┴─┐     │         │                       \n",
       "    b': ─────┤ X ├──┼────■──┤ X ├─────┼────■────┼────■──────────────────\n",
       "             └───┘  │    │  └───┘   ┌─┴─┐  │    │    │                  \n",
       "   c_0: ────────────┼────┼────X─────┤ X ├──┼────┼────┼───X───────────■──\n",
       "             ┌───┐  │    │    │     └─┬─┘┌─┴─┐  │    │   │           │  \n",
       "   c_1: ─────┤ X ├──┼────┼────┼───X───┼──┤ X ├──┼────┼───X───────────┼──\n",
       "             └───┘┌─┴─┐  │    │   │   │  └─┬─┘┌─┴─┐  │   │           │  \n",
       "zero_0: ──────────┤ X ├──┼────X───┼───■────┼──┤ X ├──┼───┼───────X───┼──\n",
       "                  └───┘┌─┴─┐      │        │  └───┘┌─┴─┐ │       │   │  \n",
       "zero_1: ───────────────┤ X ├──────X────────■───────┤ X ├─┼───────X───┼──\n",
       "                       └───┘                       └───┘ │       │ ┌─┴─┐\n",
       "c_in_0: ───────■─────────────────────────────────────────■──|0>──┼─┤ X ├\n",
       "             ┌─┴─┐                                               │ └───┘\n",
       "c_in_1: ─────┤ X ├───────────────────────────────────────────────■──────\n",
       "             └───┘                                                      </pre>"
      ],
      "text/plain": [
       "                                                                        \n",
       "     a: ──■─────────■────■──────────────────────────────────────────────\n",
       "          │         │  ┌─┴─┐                                            \n",
       "     b: ──┼────■────■──┤ X ├──────────■─────────■───────────────────────\n",
       "        ┌─┴─┐  │    │  └───┘          │         │                       \n",
       "    a': ┤ X ├──┼────┼────■────■───────┼─────────┼───────────────────────\n",
       "        └───┘┌─┴─┐  │    │  ┌─┴─┐     │         │                       \n",
       "    b': ─────┤ X ├──┼────■──┤ X ├─────┼────■────┼────■──────────────────\n",
       "             └───┘  │    │  └───┘   ┌─┴─┐  │    │    │                  \n",
       "   c_0: ────────────┼────┼────X─────┤ X ├──┼────┼────┼───X───────────■──\n",
       "             ┌───┐  │    │    │     └─┬─┘┌─┴─┐  │    │   │           │  \n",
       "   c_1: ─────┤ X ├──┼────┼────┼───X───┼──┤ X ├──┼────┼───X───────────┼──\n",
       "             └───┘┌─┴─┐  │    │   │   │  └─┬─┘┌─┴─┐  │   │           │  \n",
       "zero_0: ──────────┤ X ├──┼────X───┼───■────┼──┤ X ├──┼───┼───────X───┼──\n",
       "                  └───┘┌─┴─┐      │        │  └───┘┌─┴─┐ │       │   │  \n",
       "zero_1: ───────────────┤ X ├──────X────────■───────┤ X ├─┼───────X───┼──\n",
       "                       └───┘                       └───┘ │       │ ┌─┴─┐\n",
       "c_in_0: ───────■─────────────────────────────────────────■──|0>──┼─┤ X ├\n",
       "             ┌─┴─┐                                               │ └───┘\n",
       "c_in_1: ─────┤ X ├───────────────────────────────────────────────■──────\n",
       "             └───┘                                                      "
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transpiled = transpile(csa, backend=usim)\n",
    "transpiled.draw()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transpiled.depth()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterative construction of Design-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the discussion above, here's an iterative fucntion to build CSAs operating on n-qubits numbers. Measurments and output registers to store classical bits are added to test the circuit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_CSA1_n_qubits(n, a, b, c, opt=False, measure=False):\n",
    "    '''\n",
    "    n = length of addends\n",
    "    a = first addend\n",
    "    b = second addend\n",
    "    c = carry in\n",
    "    opt = if true, apply the optimization to save one qubit\n",
    "    measure = if true, measure results and initialize qubits\n",
    "    '''\n",
    "    \n",
    "    if len(a) != n or len(b) != n:\n",
    "        return \"Length of inputs differs from length of n.\"\n",
    "    a = a[::-1]\n",
    "    b = b[::-1]\n",
    "\n",
    "    a_in = QuantumRegister(n, name=\"a\")\n",
    "    b_in = QuantumRegister(n, name=\"b\")\n",
    "    a_copies = QuantumRegister(n, name=\"a'\")\n",
    "    b_copies = QuantumRegister(n, name=\"b'\")\n",
    "    carries = QuantumRegister(n, name=\"c\")\n",
    "    carries_copies = QuantumRegister(n, name=\"c'\")\n",
    "    zero = QuantumRegister(n, name=\"zero\")\n",
    "    zero_copies = QuantumRegister(n, name=\"zero'\")\n",
    "    if (not opt):\n",
    "        zero_buffers = QuantumRegister(n-1, name=\"zero_buff\")\n",
    "    c_in = QuantumRegister(2, name=\"c_in\")\n",
    "\n",
    "    output = ClassicalRegister(n+1, name='output')\n",
    "\n",
    "    if (opt):\n",
    "        csa = QuantumCircuit(a_in, b_in, a_copies, b_copies, carries, carries_copies, zero, zero_copies, c_in, output)\n",
    "    else:\n",
    "        csa = QuantumCircuit(a_in, b_in, a_copies, b_copies, carries, carries_copies, zero, zero_copies, zero_buffers, c_in, output)\n",
    "\n",
    "    if (measure):\n",
    "        if (c == '1'):  \n",
    "            csa.x(c_in[0])\n",
    "            \n",
    "        for i in range(n):\n",
    "            if (a[i] == '1'):\n",
    "                csa.x(a_in[i])\n",
    "            if (b[i] == '1'):\n",
    "                csa.x(b_in[i]) \n",
    "            csa.reset(a_copies[i])\n",
    "            csa.reset(b_copies[i])\n",
    "            csa.cx(a_in[i], a_copies[i])                                                        # a' = a\n",
    "            csa.cx(b_in[i], b_copies[i])                                                        # b' = b\n",
    "            csa.reset(carries[i])                                                               # c = 0\n",
    "            csa.reset(carries_copies[i])\n",
    "            csa.x(carries_copies[i])                                                            # c = 1\n",
    "            csa.reset(zero[i])\n",
    "            csa.reset(zero_copies[i])\n",
    "        csa.reset(c_in[1])                                                                      # c_in' = c_in\n",
    "        csa.cx(c_in[0], c_in[1])\n",
    "    \n",
    "    for i in range(n):\n",
    "        csa.append(fa, [a_in[i], b_in[i], zero[i], carries[i]])\n",
    "        csa.append(fa, [a_copies[i], b_copies[i], zero_copies[i], carries_copies[i]])\n",
    "        if i == 0:\n",
    "            csa.fredkin(c_in[1], zero[i], zero_copies[i])                                    # mux for the sum qubits\n",
    "        else:\n",
    "            csa.fredkin(carries[i-1], zero[i], zero_copies[i])\n",
    "        if (opt or i == 0):\n",
    "            csa.fredkin(c_in[0], carries[i], carries_copies[i])                                  # mux for the carry qubits\n",
    "        else:\n",
    "            csa.fredkin(zero_buffers[i-1], carries[i], carries_copies[i])\n",
    "\n",
    "        if (measure):\n",
    "            csa.measure(zero[i], output[i])\n",
    "\n",
    "        if (i < n-1):\n",
    "            if (opt):\n",
    "                csa.reset(c_in[0])                                                              # Recycle c_in for the output of buffers\n",
    "                csa.cx(carries[i], c_in[0])                                                     # Buffer\n",
    "            else:\n",
    "                csa.cx(carries[i], zero_buffers[i])\n",
    "        else:\n",
    "            if (measure):\n",
    "                csa.measure(carries[i], output[i+1])                                            # Measure the carry out if it's the last stage\n",
    "    #csa.measure_all()\n",
    "    return csa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is how a two-qubit CSA looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">           ┌──────┐                                         \n",
       "      a_0: ┤0     ├─────────────────────────────────────────\n",
       "           │      │        ┌──────┐                         \n",
       "      a_1: ┤      ├────────┤0     ├─────────────────────────\n",
       "           │      │        │      │                         \n",
       "      b_0: ┤1     ├────────┤      ├─────────────────────────\n",
       "           │      │        │      │                         \n",
       "      b_1: ┤      ├────────┤1     ├─────────────────────────\n",
       "           │      │┌──────┐│      │                         \n",
       "     a'_0: ┤      ├┤0     ├┤      ├─────────────────────────\n",
       "           │      ││      ││      │┌──────┐                 \n",
       "     a'_1: ┤      ├┤      ├┤      ├┤0     ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "     b'_0: ┤  RFA ├┤1     ├┤      ├┤      ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "     b'_1: ┤      ├┤      ├┤  RFA ├┤1     ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "      c_0: ┤3     ├┤      ├┤      ├┤      ├────X───■───■────\n",
       "           │      ││      ││      ││      │    │   │   │    \n",
       "      c_1: ┤      ├┤  RFA ├┤3     ├┤      ├────┼───┼───┼──X─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "     c'_0: ┤      ├┤3     ├┤      ├┤  RFA ├────X───┼───┼──┼─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "     c'_1: ┤      ├┤      ├┤      ├┤3     ├────┼───┼───┼──X─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "   zero_0: ┤2     ├┤      ├┤      ├┤      ├─X──┼───┼───┼──┼─\n",
       "           └──────┘│      ││      ││      │ │  │   │   │  │ \n",
       "   zero_1: ────────┤      ├┤2     ├┤      ├─┼──┼───┼───X──┼─\n",
       "                   │      │└──────┘│      │ │  │   │   │  │ \n",
       "  zero'_0: ────────┤2     ├────────┤      ├─X──┼───┼───┼──┼─\n",
       "                   └──────┘        │      │ │  │   │   │  │ \n",
       "  zero'_1: ────────────────────────┤2     ├─┼──┼───┼───X──┼─\n",
       "                                   └──────┘ │  │ ┌─┴─┐    │ \n",
       "zero_buff: ─────────────────────────────────┼──┼─┤ X ├────■─\n",
       "                                            │  │ └───┘      \n",
       "   c_in_0: ─────────────────────────────────┼──■────────────\n",
       "                                            │               \n",
       "   c_in_1: ─────────────────────────────────■───────────────\n",
       "                                                            \n",
       " output: 3/═════════════════════════════════════════════════\n",
       "                                                            </pre>"
      ],
      "text/plain": [
       "           ┌──────┐                                         \n",
       "      a_0: ┤0     ├─────────────────────────────────────────\n",
       "           │      │        ┌──────┐                         \n",
       "      a_1: ┤      ├────────┤0     ├─────────────────────────\n",
       "           │      │        │      │                         \n",
       "      b_0: ┤1     ├────────┤      ├─────────────────────────\n",
       "           │      │        │      │                         \n",
       "      b_1: ┤      ├────────┤1     ├─────────────────────────\n",
       "           │      │┌──────┐│      │                         \n",
       "     a'_0: ┤      ├┤0     ├┤      ├─────────────────────────\n",
       "           │      ││      ││      │┌──────┐                 \n",
       "     a'_1: ┤      ├┤      ├┤      ├┤0     ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "     b'_0: ┤  RFA ├┤1     ├┤      ├┤      ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "     b'_1: ┤      ├┤      ├┤  RFA ├┤1     ├─────────────────\n",
       "           │      ││      ││      ││      │                 \n",
       "      c_0: ┤3     ├┤      ├┤      ├┤      ├────X───■───■────\n",
       "           │      ││      ││      ││      │    │   │   │    \n",
       "      c_1: ┤      ├┤  RFA ├┤3     ├┤      ├────┼───┼───┼──X─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "     c'_0: ┤      ├┤3     ├┤      ├┤  RFA ├────X───┼───┼──┼─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "     c'_1: ┤      ├┤      ├┤      ├┤3     ├────┼───┼───┼──X─\n",
       "           │      ││      ││      ││      │    │   │   │  │ \n",
       "   zero_0: ┤2     ├┤      ├┤      ├┤      ├─X──┼───┼───┼──┼─\n",
       "           └──────┘│      ││      ││      │ │  │   │   │  │ \n",
       "   zero_1: ────────┤      ├┤2     ├┤      ├─┼──┼───┼───X──┼─\n",
       "                   │      │└──────┘│      │ │  │   │   │  │ \n",
       "  zero'_0: ────────┤2     ├────────┤      ├─X──┼───┼───┼──┼─\n",
       "                   └──────┘        │      │ │  │   │   │  │ \n",
       "  zero'_1: ────────────────────────┤2     ├─┼──┼───┼───X──┼─\n",
       "                                   └──────┘ │  │ ┌─┴─┐    │ \n",
       "zero_buff: ─────────────────────────────────┼──┼─┤ X ├────■─\n",
       "                                            │  │ └───┘      \n",
       "   c_in_0: ─────────────────────────────────┼──■────────────\n",
       "                                            │               \n",
       "   c_in_1: ─────────────────────────────────■───────────────\n",
       "                                                            \n",
       " output: 3/═════════════════════════════════════════════════\n",
       "                                                            "
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "csa2q = generate_CSA1_n_qubits(2, '00', '00', '0')\n",
    "csa2q.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Correctness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I am going to test if the CSA exactly reproduce the truth table of a classical one-bit CSA, that is:\n",
    "\n",
    "    a   b   c   |   out\n",
    "    --------------------\n",
    "    0   0   0   |   00\n",
    "    0   0   1   |   01\n",
    "    0   1   0   |   01\n",
    "    0   1   1   |   10\n",
    "    1   0   0   |   01\n",
    "    1   0   1   |   10\n",
    "    1   1   0   |   10\n",
    "    1   1   1   |   11\n",
    "\n",
    "Where the MSB of \"out\" is the carry out and the LSB is the sum. As you can see from the results below, the circuit works properly:\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "def check_correctness(n: int, carry_in: str, circuitGenerator):\n",
    "    '''\n",
    "    Function which prints the truth table of any adder.\n",
    "    '''\n",
    "    inputs = [\"\".join(seq) for seq in itertools.product(\"01\", repeat=n)]\n",
    "    print(inputs)\n",
    "    for i in range(len(inputs)):\n",
    "        for j in range(len(inputs)):\n",
    "            circuit = circuitGenerator(n, inputs[i], inputs[j], carry_in, measure=True)\n",
    "            usim = Aer.get_backend('unitary_simulator')\n",
    "            transpiled = transpile(circuit, backend=usim)\n",
    "            backend = Aer.get_backend('aer_simulator')\n",
    "            job = backend.run(transpiled, shots=1, memory=True)\n",
    "            output = job.result().get_memory()[0]\n",
    "            print(\"a: \"+inputs[i]+\" b: \"+inputs[j]+\" c_in: \"+carry_in+\" r: \"+output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0', '1']\n",
      "a: 0 b: 0 c_in: 0 r: 00\n",
      "a: 0 b: 1 c_in: 0 r: 01\n",
      "a: 1 b: 0 c_in: 0 r: 01\n",
      "a: 1 b: 1 c_in: 0 r: 10\n"
     ]
    }
   ],
   "source": [
    "check_correctness(1, '0', generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0', '1']\n",
      "a: 0 b: 0 c_in: 1 r: 01\n",
      "a: 0 b: 1 c_in: 1 r: 10\n",
      "a: 1 b: 0 c_in: 1 r: 10\n",
      "a: 1 b: 1 c_in: 1 r: 11\n"
     ]
    }
   ],
   "source": [
    "check_correctness(1, '1', generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(the first bit is the carry out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some other tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['00', '01', '10', '11']\n",
      "a: 00 b: 00 c_in: 0 r: 000\n",
      "a: 00 b: 01 c_in: 0 r: 001\n",
      "a: 00 b: 10 c_in: 0 r: 010\n",
      "a: 00 b: 11 c_in: 0 r: 011\n",
      "a: 01 b: 00 c_in: 0 r: 001\n",
      "a: 01 b: 01 c_in: 0 r: 010\n",
      "a: 01 b: 10 c_in: 0 r: 011\n",
      "a: 01 b: 11 c_in: 0 r: 100\n",
      "a: 10 b: 00 c_in: 0 r: 010\n",
      "a: 10 b: 01 c_in: 0 r: 011\n",
      "a: 10 b: 10 c_in: 0 r: 100\n",
      "a: 10 b: 11 c_in: 0 r: 101\n",
      "a: 11 b: 00 c_in: 0 r: 011\n",
      "a: 11 b: 01 c_in: 0 r: 100\n",
      "a: 11 b: 10 c_in: 0 r: 101\n",
      "a: 11 b: 11 c_in: 0 r: 110\n"
     ]
    }
   ],
   "source": [
    "check_correctness(2, '0', generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['00', '01', '10', '11']\n",
      "a: 00 b: 00 c_in: 1 r: 001\n",
      "a: 00 b: 01 c_in: 1 r: 010\n",
      "a: 00 b: 10 c_in: 1 r: 011\n",
      "a: 00 b: 11 c_in: 1 r: 100\n",
      "a: 01 b: 00 c_in: 1 r: 010\n",
      "a: 01 b: 01 c_in: 1 r: 011\n",
      "a: 01 b: 10 c_in: 1 r: 100\n",
      "a: 01 b: 11 c_in: 1 r: 101\n",
      "a: 10 b: 00 c_in: 1 r: 011\n",
      "a: 10 b: 01 c_in: 1 r: 100\n",
      "a: 10 b: 10 c_in: 1 r: 101\n",
      "a: 10 b: 11 c_in: 1 r: 110\n",
      "a: 11 b: 00 c_in: 1 r: 100\n",
      "a: 11 b: 01 c_in: 1 r: 101\n",
      "a: 11 b: 10 c_in: 1 r: 110\n",
      "a: 11 b: 11 c_in: 1 r: 111\n"
     ]
    }
   ],
   "source": [
    "check_correctness(2, '1', generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']\n",
      "a: 0000 b: 0000 c_in: 0 r: 00000\n",
      "a: 0000 b: 0001 c_in: 0 r: 00001\n",
      "a: 0000 b: 0010 c_in: 0 r: 00010\n",
      "a: 0000 b: 0011 c_in: 0 r: 00011\n",
      "a: 0000 b: 0100 c_in: 0 r: 00100\n",
      "a: 0000 b: 0101 c_in: 0 r: 00101\n",
      "a: 0000 b: 0110 c_in: 0 r: 00110\n",
      "a: 0000 b: 0111 c_in: 0 r: 00111\n",
      "a: 0000 b: 1000 c_in: 0 r: 01000\n",
      "a: 0000 b: 1001 c_in: 0 r: 01001\n",
      "a: 0000 b: 1010 c_in: 0 r: 01010\n",
      "a: 0000 b: 1011 c_in: 0 r: 01011\n",
      "a: 0000 b: 1100 c_in: 0 r: 01100\n",
      "a: 0000 b: 1101 c_in: 0 r: 01101\n",
      "a: 0000 b: 1110 c_in: 0 r: 01110\n",
      "a: 0000 b: 1111 c_in: 0 r: 01111\n",
      "a: 0001 b: 0000 c_in: 0 r: 00001\n",
      "a: 0001 b: 0001 c_in: 0 r: 00010\n",
      "a: 0001 b: 0010 c_in: 0 r: 00011\n",
      "a: 0001 b: 0011 c_in: 0 r: 00100\n",
      "a: 0001 b: 0100 c_in: 0 r: 00101\n",
      "a: 0001 b: 0101 c_in: 0 r: 00110\n",
      "a: 0001 b: 0110 c_in: 0 r: 00111\n",
      "a: 0001 b: 0111 c_in: 0 r: 01000\n",
      "a: 0001 b: 1000 c_in: 0 r: 01001\n",
      "a: 0001 b: 1001 c_in: 0 r: 01010\n",
      "a: 0001 b: 1010 c_in: 0 r: 01011\n",
      "a: 0001 b: 1011 c_in: 0 r: 01100\n",
      "a: 0001 b: 1100 c_in: 0 r: 01101\n",
      "a: 0001 b: 1101 c_in: 0 r: 01110\n",
      "a: 0001 b: 1110 c_in: 0 r: 01111\n",
      "a: 0001 b: 1111 c_in: 0 r: 10000\n",
      "a: 0010 b: 0000 c_in: 0 r: 00010\n",
      "a: 0010 b: 0001 c_in: 0 r: 00011\n",
      "a: 0010 b: 0010 c_in: 0 r: 00100\n",
      "a: 0010 b: 0011 c_in: 0 r: 00101\n",
      "a: 0010 b: 0100 c_in: 0 r: 00110\n",
      "a: 0010 b: 0101 c_in: 0 r: 00111\n",
      "a: 0010 b: 0110 c_in: 0 r: 01000\n",
      "a: 0010 b: 0111 c_in: 0 r: 01001\n",
      "a: 0010 b: 1000 c_in: 0 r: 01010\n",
      "a: 0010 b: 1001 c_in: 0 r: 01011\n",
      "a: 0010 b: 1010 c_in: 0 r: 01100\n",
      "a: 0010 b: 1011 c_in: 0 r: 01101\n",
      "a: 0010 b: 1100 c_in: 0 r: 01110\n",
      "a: 0010 b: 1101 c_in: 0 r: 01111\n",
      "a: 0010 b: 1110 c_in: 0 r: 10000\n",
      "a: 0010 b: 1111 c_in: 0 r: 10001\n",
      "a: 0011 b: 0000 c_in: 0 r: 00011\n",
      "a: 0011 b: 0001 c_in: 0 r: 00100\n",
      "a: 0011 b: 0010 c_in: 0 r: 00101\n",
      "a: 0011 b: 0011 c_in: 0 r: 00110\n",
      "a: 0011 b: 0100 c_in: 0 r: 00111\n",
      "a: 0011 b: 0101 c_in: 0 r: 01000\n",
      "a: 0011 b: 0110 c_in: 0 r: 01001\n",
      "a: 0011 b: 0111 c_in: 0 r: 01010\n",
      "a: 0011 b: 1000 c_in: 0 r: 01011\n",
      "a: 0011 b: 1001 c_in: 0 r: 01100\n",
      "a: 0011 b: 1010 c_in: 0 r: 01101\n",
      "a: 0011 b: 1011 c_in: 0 r: 01110\n",
      "a: 0011 b: 1100 c_in: 0 r: 01111\n",
      "a: 0011 b: 1101 c_in: 0 r: 10000\n",
      "a: 0011 b: 1110 c_in: 0 r: 10001\n",
      "a: 0011 b: 1111 c_in: 0 r: 10010\n",
      "a: 0100 b: 0000 c_in: 0 r: 00100\n",
      "a: 0100 b: 0001 c_in: 0 r: 00101\n",
      "a: 0100 b: 0010 c_in: 0 r: 00110\n",
      "a: 0100 b: 0011 c_in: 0 r: 00111\n",
      "a: 0100 b: 0100 c_in: 0 r: 01000\n",
      "a: 0100 b: 0101 c_in: 0 r: 01001\n",
      "a: 0100 b: 0110 c_in: 0 r: 01010\n",
      "a: 0100 b: 0111 c_in: 0 r: 01011\n",
      "a: 0100 b: 1000 c_in: 0 r: 01100\n",
      "a: 0100 b: 1001 c_in: 0 r: 01101\n",
      "a: 0100 b: 1010 c_in: 0 r: 01110\n",
      "a: 0100 b: 1011 c_in: 0 r: 01111\n",
      "a: 0100 b: 1100 c_in: 0 r: 10000\n",
      "a: 0100 b: 1101 c_in: 0 r: 10001\n",
      "a: 0100 b: 1110 c_in: 0 r: 10010\n",
      "a: 0100 b: 1111 c_in: 0 r: 10011\n",
      "a: 0101 b: 0000 c_in: 0 r: 00101\n",
      "a: 0101 b: 0001 c_in: 0 r: 00110\n",
      "a: 0101 b: 0010 c_in: 0 r: 00111\n",
      "a: 0101 b: 0011 c_in: 0 r: 01000\n",
      "a: 0101 b: 0100 c_in: 0 r: 01001\n",
      "a: 0101 b: 0101 c_in: 0 r: 01010\n",
      "a: 0101 b: 0110 c_in: 0 r: 01011\n",
      "a: 0101 b: 0111 c_in: 0 r: 01100\n",
      "a: 0101 b: 1000 c_in: 0 r: 01101\n",
      "a: 0101 b: 1001 c_in: 0 r: 01110\n",
      "a: 0101 b: 1010 c_in: 0 r: 01111\n",
      "a: 0101 b: 1011 c_in: 0 r: 10000\n",
      "a: 0101 b: 1100 c_in: 0 r: 10001\n",
      "a: 0101 b: 1101 c_in: 0 r: 10010\n",
      "a: 0101 b: 1110 c_in: 0 r: 10011\n",
      "a: 0101 b: 1111 c_in: 0 r: 10100\n",
      "a: 0110 b: 0000 c_in: 0 r: 00110\n",
      "a: 0110 b: 0001 c_in: 0 r: 00111\n",
      "a: 0110 b: 0010 c_in: 0 r: 01000\n",
      "a: 0110 b: 0011 c_in: 0 r: 01001\n",
      "a: 0110 b: 0100 c_in: 0 r: 01010\n",
      "a: 0110 b: 0101 c_in: 0 r: 01011\n",
      "a: 0110 b: 0110 c_in: 0 r: 01100\n",
      "a: 0110 b: 0111 c_in: 0 r: 01101\n",
      "a: 0110 b: 1000 c_in: 0 r: 01110\n",
      "a: 0110 b: 1001 c_in: 0 r: 01111\n",
      "a: 0110 b: 1010 c_in: 0 r: 10000\n",
      "a: 0110 b: 1011 c_in: 0 r: 10001\n",
      "a: 0110 b: 1100 c_in: 0 r: 10010\n",
      "a: 0110 b: 1101 c_in: 0 r: 10011\n",
      "a: 0110 b: 1110 c_in: 0 r: 10100\n",
      "a: 0110 b: 1111 c_in: 0 r: 10101\n",
      "a: 0111 b: 0000 c_in: 0 r: 00111\n",
      "a: 0111 b: 0001 c_in: 0 r: 01000\n",
      "a: 0111 b: 0010 c_in: 0 r: 01001\n",
      "a: 0111 b: 0011 c_in: 0 r: 01010\n",
      "a: 0111 b: 0100 c_in: 0 r: 01011\n",
      "a: 0111 b: 0101 c_in: 0 r: 01100\n",
      "a: 0111 b: 0110 c_in: 0 r: 01101\n",
      "a: 0111 b: 0111 c_in: 0 r: 01110\n",
      "a: 0111 b: 1000 c_in: 0 r: 01111\n",
      "a: 0111 b: 1001 c_in: 0 r: 10000\n",
      "a: 0111 b: 1010 c_in: 0 r: 10001\n",
      "a: 0111 b: 1011 c_in: 0 r: 10010\n",
      "a: 0111 b: 1100 c_in: 0 r: 10011\n",
      "a: 0111 b: 1101 c_in: 0 r: 10100\n",
      "a: 0111 b: 1110 c_in: 0 r: 10101\n",
      "a: 0111 b: 1111 c_in: 0 r: 10110\n",
      "a: 1000 b: 0000 c_in: 0 r: 01000\n",
      "a: 1000 b: 0001 c_in: 0 r: 01001\n",
      "a: 1000 b: 0010 c_in: 0 r: 01010\n",
      "a: 1000 b: 0011 c_in: 0 r: 01011\n",
      "a: 1000 b: 0100 c_in: 0 r: 01100\n",
      "a: 1000 b: 0101 c_in: 0 r: 01101\n",
      "a: 1000 b: 0110 c_in: 0 r: 01110\n",
      "a: 1000 b: 0111 c_in: 0 r: 01111\n",
      "a: 1000 b: 1000 c_in: 0 r: 10000\n",
      "a: 1000 b: 1001 c_in: 0 r: 10001\n",
      "a: 1000 b: 1010 c_in: 0 r: 10010\n",
      "a: 1000 b: 1011 c_in: 0 r: 10011\n",
      "a: 1000 b: 1100 c_in: 0 r: 10100\n",
      "a: 1000 b: 1101 c_in: 0 r: 10101\n",
      "a: 1000 b: 1110 c_in: 0 r: 10110\n",
      "a: 1000 b: 1111 c_in: 0 r: 10111\n",
      "a: 1001 b: 0000 c_in: 0 r: 01001\n",
      "a: 1001 b: 0001 c_in: 0 r: 01010\n",
      "a: 1001 b: 0010 c_in: 0 r: 01011\n",
      "a: 1001 b: 0011 c_in: 0 r: 01100\n",
      "a: 1001 b: 0100 c_in: 0 r: 01101\n",
      "a: 1001 b: 0101 c_in: 0 r: 01110\n",
      "a: 1001 b: 0110 c_in: 0 r: 01111\n",
      "a: 1001 b: 0111 c_in: 0 r: 10000\n",
      "a: 1001 b: 1000 c_in: 0 r: 10001\n",
      "a: 1001 b: 1001 c_in: 0 r: 10010\n",
      "a: 1001 b: 1010 c_in: 0 r: 10011\n",
      "a: 1001 b: 1011 c_in: 0 r: 10100\n",
      "a: 1001 b: 1100 c_in: 0 r: 10101\n",
      "a: 1001 b: 1101 c_in: 0 r: 10110\n",
      "a: 1001 b: 1110 c_in: 0 r: 10111\n",
      "a: 1001 b: 1111 c_in: 0 r: 11000\n",
      "a: 1010 b: 0000 c_in: 0 r: 01010\n",
      "a: 1010 b: 0001 c_in: 0 r: 01011\n",
      "a: 1010 b: 0010 c_in: 0 r: 01100\n",
      "a: 1010 b: 0011 c_in: 0 r: 01101\n",
      "a: 1010 b: 0100 c_in: 0 r: 01110\n",
      "a: 1010 b: 0101 c_in: 0 r: 01111\n",
      "a: 1010 b: 0110 c_in: 0 r: 10000\n",
      "a: 1010 b: 0111 c_in: 0 r: 10001\n",
      "a: 1010 b: 1000 c_in: 0 r: 10010\n",
      "a: 1010 b: 1001 c_in: 0 r: 10011\n",
      "a: 1010 b: 1010 c_in: 0 r: 10100\n",
      "a: 1010 b: 1011 c_in: 0 r: 10101\n",
      "a: 1010 b: 1100 c_in: 0 r: 10110\n",
      "a: 1010 b: 1101 c_in: 0 r: 10111\n",
      "a: 1010 b: 1110 c_in: 0 r: 11000\n",
      "a: 1010 b: 1111 c_in: 0 r: 11001\n",
      "a: 1011 b: 0000 c_in: 0 r: 01011\n",
      "a: 1011 b: 0001 c_in: 0 r: 01100\n",
      "a: 1011 b: 0010 c_in: 0 r: 01101\n",
      "a: 1011 b: 0011 c_in: 0 r: 01110\n",
      "a: 1011 b: 0100 c_in: 0 r: 01111\n",
      "a: 1011 b: 0101 c_in: 0 r: 10000\n",
      "a: 1011 b: 0110 c_in: 0 r: 10001\n",
      "a: 1011 b: 0111 c_in: 0 r: 10010\n",
      "a: 1011 b: 1000 c_in: 0 r: 10011\n",
      "a: 1011 b: 1001 c_in: 0 r: 10100\n",
      "a: 1011 b: 1010 c_in: 0 r: 10101\n",
      "a: 1011 b: 1011 c_in: 0 r: 10110\n",
      "a: 1011 b: 1100 c_in: 0 r: 10111\n",
      "a: 1011 b: 1101 c_in: 0 r: 11000\n",
      "a: 1011 b: 1110 c_in: 0 r: 11001\n",
      "a: 1011 b: 1111 c_in: 0 r: 11010\n",
      "a: 1100 b: 0000 c_in: 0 r: 01100\n",
      "a: 1100 b: 0001 c_in: 0 r: 01101\n",
      "a: 1100 b: 0010 c_in: 0 r: 01110\n",
      "a: 1100 b: 0011 c_in: 0 r: 01111\n",
      "a: 1100 b: 0100 c_in: 0 r: 10000\n",
      "a: 1100 b: 0101 c_in: 0 r: 10001\n",
      "a: 1100 b: 0110 c_in: 0 r: 10010\n",
      "a: 1100 b: 0111 c_in: 0 r: 10011\n",
      "a: 1100 b: 1000 c_in: 0 r: 10100\n",
      "a: 1100 b: 1001 c_in: 0 r: 10101\n",
      "a: 1100 b: 1010 c_in: 0 r: 10110\n",
      "a: 1100 b: 1011 c_in: 0 r: 10111\n",
      "a: 1100 b: 1100 c_in: 0 r: 11000\n",
      "a: 1100 b: 1101 c_in: 0 r: 11001\n",
      "a: 1100 b: 1110 c_in: 0 r: 11010\n",
      "a: 1100 b: 1111 c_in: 0 r: 11011\n",
      "a: 1101 b: 0000 c_in: 0 r: 01101\n",
      "a: 1101 b: 0001 c_in: 0 r: 01110\n",
      "a: 1101 b: 0010 c_in: 0 r: 01111\n",
      "a: 1101 b: 0011 c_in: 0 r: 10000\n",
      "a: 1101 b: 0100 c_in: 0 r: 10001\n",
      "a: 1101 b: 0101 c_in: 0 r: 10010\n",
      "a: 1101 b: 0110 c_in: 0 r: 10011\n",
      "a: 1101 b: 0111 c_in: 0 r: 10100\n",
      "a: 1101 b: 1000 c_in: 0 r: 10101\n",
      "a: 1101 b: 1001 c_in: 0 r: 10110\n",
      "a: 1101 b: 1010 c_in: 0 r: 10111\n",
      "a: 1101 b: 1011 c_in: 0 r: 11000\n",
      "a: 1101 b: 1100 c_in: 0 r: 11001\n",
      "a: 1101 b: 1101 c_in: 0 r: 11010\n",
      "a: 1101 b: 1110 c_in: 0 r: 11011\n",
      "a: 1101 b: 1111 c_in: 0 r: 11100\n",
      "a: 1110 b: 0000 c_in: 0 r: 01110\n",
      "a: 1110 b: 0001 c_in: 0 r: 01111\n",
      "a: 1110 b: 0010 c_in: 0 r: 10000\n",
      "a: 1110 b: 0011 c_in: 0 r: 10001\n",
      "a: 1110 b: 0100 c_in: 0 r: 10010\n",
      "a: 1110 b: 0101 c_in: 0 r: 10011\n",
      "a: 1110 b: 0110 c_in: 0 r: 10100\n",
      "a: 1110 b: 0111 c_in: 0 r: 10101\n",
      "a: 1110 b: 1000 c_in: 0 r: 10110\n",
      "a: 1110 b: 1001 c_in: 0 r: 10111\n",
      "a: 1110 b: 1010 c_in: 0 r: 11000\n",
      "a: 1110 b: 1011 c_in: 0 r: 11001\n",
      "a: 1110 b: 1100 c_in: 0 r: 11010\n",
      "a: 1110 b: 1101 c_in: 0 r: 11011\n",
      "a: 1110 b: 1110 c_in: 0 r: 11100\n",
      "a: 1110 b: 1111 c_in: 0 r: 11101\n",
      "a: 1111 b: 0000 c_in: 0 r: 01111\n",
      "a: 1111 b: 0001 c_in: 0 r: 10000\n",
      "a: 1111 b: 0010 c_in: 0 r: 10001\n",
      "a: 1111 b: 0011 c_in: 0 r: 10010\n",
      "a: 1111 b: 0100 c_in: 0 r: 10011\n",
      "a: 1111 b: 0101 c_in: 0 r: 10100\n",
      "a: 1111 b: 0110 c_in: 0 r: 10101\n",
      "a: 1111 b: 0111 c_in: 0 r: 10110\n",
      "a: 1111 b: 1000 c_in: 0 r: 10111\n",
      "a: 1111 b: 1001 c_in: 0 r: 11000\n",
      "a: 1111 b: 1010 c_in: 0 r: 11001\n",
      "a: 1111 b: 1011 c_in: 0 r: 11010\n",
      "a: 1111 b: 1100 c_in: 0 r: 11011\n",
      "a: 1111 b: 1101 c_in: 0 r: 11100\n",
      "a: 1111 b: 1110 c_in: 0 r: 11101\n",
      "a: 1111 b: 1111 c_in: 0 r: 11110\n"
     ]
    }
   ],
   "source": [
    "check_correctness(4, '0', generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Measurments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evluate_circuit(n, circuitGenerator):\n",
    "    '''\n",
    "    Evaluate circuit which accepts addends of length n.\n",
    "    '''\n",
    "    input = '0' * n\n",
    "    circuit = circuitGenerator(n, input, input, '0', opt=False, measure=True)\n",
    "    usim = Aer.get_backend('unitary_simulator')\n",
    "    transpiled = transpile(circuit, backend=usim, optimization_level=3)\n",
    "    print(\"Depth of circuit with addends of \"+ str(n) +\" qubits is: \"+str(transpiled.depth()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depth of the circuit should be given by:\n",
    "- To run the **RFA** we need 4 steps, regardless of the length of the addends since they can be run in parallel;\n",
    "- **Fredking** gates need 1 step (they run in parallel within the same stage) as for the **CNOT** gates (used as buffers) and they are run in series, so in total it is 2n-1 (last stage has no CNOT);\n",
    "- **Initialization of qubits** takes 1 step;\n",
    "- **Measurments** add 1 step;\n",
    "- Also the reset of c_in[0] used to save one wire add n step\n",
    "\n",
    "The total is 4 + 2n - 1 + 1 + 1 + 1 = 2n + 6 = 2(n + 3). But if we remove the measurments and the initializations (that in the authors' circuit are not considered) and the reset of c_in[0] we get **2n + 3**.\n",
    "\n",
    "Total in authors' circuit: 2n - 1 + 4 = **2n + 3**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 2 qubits is: 7\n",
      "Depth of circuit with addends of 3 qubits is: 10\n",
      "Depth of circuit with addends of 4 qubits is: 13\n",
      "Depth of circuit with addends of 5 qubits is: 16\n",
      "Depth of circuit with addends of 6 qubits is: 19\n",
      "Depth of circuit with addends of 7 qubits is: 22\n",
      "Depth of circuit with addends of 8 qubits is: 25\n",
      "Depth of circuit with addends of 9 qubits is: 28\n",
      "Depth of circuit with addends of 10 qubits is: 31\n",
      "Depth of circuit with addends of 11 qubits is: 34\n",
      "Depth of circuit with addends of 12 qubits is: 37\n",
      "Depth of circuit with addends of 13 qubits is: 40\n",
      "Depth of circuit with addends of 14 qubits is: 43\n",
      "Depth of circuit with addends of 15 qubits is: 46\n",
      "Depth of circuit with addends of 16 qubits is: 49\n"
     ]
    }
   ],
   "source": [
    "# Measure = False, opt = True\n",
    "for i in range(2,17):\n",
    "    evluate_circuit(i, generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 2 qubits is: 6\n",
      "Depth of circuit with addends of 3 qubits is: 8\n",
      "Depth of circuit with addends of 4 qubits is: 10\n",
      "Depth of circuit with addends of 5 qubits is: 12\n",
      "Depth of circuit with addends of 6 qubits is: 14\n",
      "Depth of circuit with addends of 7 qubits is: 16\n",
      "Depth of circuit with addends of 8 qubits is: 18\n",
      "Depth of circuit with addends of 9 qubits is: 20\n",
      "Depth of circuit with addends of 10 qubits is: 22\n",
      "Depth of circuit with addends of 11 qubits is: 24\n",
      "Depth of circuit with addends of 12 qubits is: 26\n",
      "Depth of circuit with addends of 13 qubits is: 28\n",
      "Depth of circuit with addends of 14 qubits is: 30\n",
      "Depth of circuit with addends of 15 qubits is: 32\n",
      "Depth of circuit with addends of 16 qubits is: 34\n"
     ]
    }
   ],
   "source": [
    "# Measure = False, opt = False\n",
    "for i in range(2,17):\n",
    "    evluate_circuit(i, generate_CSA1_n_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depth is lower than expected because the transpiler relizes that while computing the last stage of the RFAs (the one with CNOTs), it can run some of the Fredking gates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Baseline depth Ripple Carry Adder implementation of Cuccaro et al.: **2n+6** (without measurments)\n",
    "\n",
    "Expectations vs. reality shows how much is the improvment given by the transpiler:\n",
    "    \n",
    "    Expectations:                           Reality:\n",
    "\n",
    "    OPT   MEASURE   |   RES                 OPT   MEASURE   |   RES \n",
    "    ------------------------                ------------------------\n",
    "    F       F       |   2n+3                F       F       |   2n+2\n",
    "    F       T       |   2n+5                F       T       |   2n+4\n",
    "    T       F       |   3n+3                T       F       |   3n+1\n",
    "    T       T       |   3n+5                T       T       |   3n+3\n",
    "\n",
    "Authors' RCA depth (no measure and no opt of course): **2n+3**\n",
    "\n",
    "RCA implementation: **2n+2**\n",
    "\n",
    "(all measurments are performed by using transpiled versions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 2 qubits is: 6\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                                                                             »\n",
       "      a_0: ──■─────────■─────────────────────────────────────────────────────»\n",
       "             │         │                                                     »\n",
       "      a_1: ──┼────■────┼────■────────────────────────────────────────────────»\n",
       "             │    │  ┌─┴─┐  │                                                »\n",
       "      b_0: ──■────┼──┤ X ├──┼────────────────────■───────────────────■───────»\n",
       "             │    │  └───┘┌─┴─┐                  │                   │       »\n",
       "      b_1: ──┼────■───────┤ X ├──────────────────┼────■──────────────┼────■──»\n",
       "             │    │       └───┘                  │    │              │    │  »\n",
       "     a'_0: ──┼────┼────■─────────■───────────────┼────┼──────────────┼────┼──»\n",
       "             │    │    │         │               │    │              │    │  »\n",
       "     a'_1: ──┼────┼────┼────■────┼────■──────────┼────┼──────────────┼────┼──»\n",
       "             │    │    │    │  ┌─┴─┐  │          │    │              │    │  »\n",
       "     b'_0: ──┼────┼────■────┼──┤ X ├──┼──────────┼────┼────■─────────┼────┼──»\n",
       "             │    │    │    │  └───┘┌─┴─┐        │    │    │         │    │  »\n",
       "     b'_1: ──┼────┼────┼────■───────┤ X ├────────┼────┼────┼────■────┼────┼──»\n",
       "             │    │    │    │       └───┘      ┌─┴─┐  │    │    │    │    │  »\n",
       "      c_0: ──┼────┼────┼────┼────X─────────────┤ X ├──┼────┼────┼────┼────┼──»\n",
       "             │    │    │    │    │             └─┬─┘┌─┴─┐  │    │    │    │  »\n",
       "      c_1: ──┼────┼────┼────┼────┼────X──────────┼──┤ X ├──┼────┼────┼────┼──»\n",
       "             │    │    │    │    │    │          │  └─┬─┘┌─┴─┐  │    │    │  »\n",
       "     c'_0: ──┼────┼────┼────┼────┼────┼───X──────┼────┼──┤ X ├──┼────┼────┼──»\n",
       "             │    │    │    │    │    │   │      │    │  └─┬─┘┌─┴─┐  │    │  »\n",
       "     c'_1: ──┼────┼────┼────┼────┼────┼───┼──X───┼────┼────┼──┤ X ├──┼────┼──»\n",
       "           ┌─┴─┐  │    │    │    │    │   │  │   │    │    │  └─┬─┘┌─┴─┐  │  »\n",
       "   zero_0: ┤ X ├──┼────┼────┼────X────┼───┼──┼───■────┼────┼────┼──┤ X ├──┼──»\n",
       "           └───┘┌─┴─┐  │    │         │   │  │        │    │    │  └───┘┌─┴─┐»\n",
       "   zero_1: ─────┤ X ├──┼────┼─────────X───┼──┼────────■────┼────┼───────┤ X ├»\n",
       "                └───┘┌─┴─┐  │             │  │             │    │       └───┘»\n",
       "  zero'_0: ──────────┤ X ├──┼─────────────X──┼─────────────■────┼────────────»\n",
       "                     └───┘┌─┴─┐              │                  │            »\n",
       "  zero'_1: ───────────────┤ X ├──────────────X──────────────────■────────────»\n",
       "                          └───┘                                              »\n",
       "zero_buff: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       "   c_in_0: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       "   c_in_1: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       " output: 3/══════════════════════════════════════════════════════════════════»\n",
       "                                                                             »\n",
       "«                                      \n",
       "«      a_0: ───────────────────────────\n",
       "«                                      \n",
       "«      a_1: ───────────────────────────\n",
       "«                                      \n",
       "«      b_0: ───────────────────────────\n",
       "«                                      \n",
       "«      b_1: ───────────────────────────\n",
       "«                                      \n",
       "«     a'_0: ───────────────────────────\n",
       "«                                      \n",
       "«     a'_1: ───────────────────────────\n",
       "«                                      \n",
       "«     b'_0: ──■────────────────────────\n",
       "«             │                        \n",
       "«     b'_1: ──┼────■───────────────────\n",
       "«             │    │                   \n",
       "«      c_0: ──┼────┼───X───■─────────■─\n",
       "«             │    │   │   │         │ \n",
       "«      c_1: ──┼────┼───┼───┼──────X──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«     c'_0: ──┼────┼───X───┼──────┼──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«     c'_1: ──┼────┼───┼───┼──────X──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«   zero_0: ──┼────┼───┼───┼───X──┼──┼─\n",
       "«             │    │   │   │   │  │  │ \n",
       "«   zero_1: ──┼────┼───┼───┼───┼──┼──X─\n",
       "«           ┌─┴─┐  │   │   │   │  │  │ \n",
       "«  zero'_0: ┤ X ├──┼───┼───┼───X──┼──┼─\n",
       "«           └───┘┌─┴─┐ │   │   │  │  │ \n",
       "«  zero'_1: ─────┤ X ├─┼───┼───┼──┼──X─\n",
       "«                └───┘ │ ┌─┴─┐ │  │    \n",
       "«zero_buff: ───────────┼─┤ X ├─┼──■────\n",
       "«                      │ └───┘ │       \n",
       "«   c_in_0: ───────────■───────┼───────\n",
       "«                              │       \n",
       "«   c_in_1: ───────────────────■───────\n",
       "«                                      \n",
       "« output: 3/═══════════════════════════\n",
       "«                                      </pre>"
      ],
      "text/plain": [
       "                                                                             »\n",
       "      a_0: ──■─────────■─────────────────────────────────────────────────────»\n",
       "             │         │                                                     »\n",
       "      a_1: ──┼────■────┼────■────────────────────────────────────────────────»\n",
       "             │    │  ┌─┴─┐  │                                                »\n",
       "      b_0: ──■────┼──┤ X ├──┼────────────────────■───────────────────■───────»\n",
       "             │    │  └───┘┌─┴─┐                  │                   │       »\n",
       "      b_1: ──┼────■───────┤ X ├──────────────────┼────■──────────────┼────■──»\n",
       "             │    │       └───┘                  │    │              │    │  »\n",
       "     a'_0: ──┼────┼────■─────────■───────────────┼────┼──────────────┼────┼──»\n",
       "             │    │    │         │               │    │              │    │  »\n",
       "     a'_1: ──┼────┼────┼────■────┼────■──────────┼────┼──────────────┼────┼──»\n",
       "             │    │    │    │  ┌─┴─┐  │          │    │              │    │  »\n",
       "     b'_0: ──┼────┼────■────┼──┤ X ├──┼──────────┼────┼────■─────────┼────┼──»\n",
       "             │    │    │    │  └───┘┌─┴─┐        │    │    │         │    │  »\n",
       "     b'_1: ──┼────┼────┼────■───────┤ X ├────────┼────┼────┼────■────┼────┼──»\n",
       "             │    │    │    │       └───┘      ┌─┴─┐  │    │    │    │    │  »\n",
       "      c_0: ──┼────┼────┼────┼────X─────────────┤ X ├──┼────┼────┼────┼────┼──»\n",
       "             │    │    │    │    │             └─┬─┘┌─┴─┐  │    │    │    │  »\n",
       "      c_1: ──┼────┼────┼────┼────┼────X──────────┼──┤ X ├──┼────┼────┼────┼──»\n",
       "             │    │    │    │    │    │          │  └─┬─┘┌─┴─┐  │    │    │  »\n",
       "     c'_0: ──┼────┼────┼────┼────┼────┼───X──────┼────┼──┤ X ├──┼────┼────┼──»\n",
       "             │    │    │    │    │    │   │      │    │  └─┬─┘┌─┴─┐  │    │  »\n",
       "     c'_1: ──┼────┼────┼────┼────┼────┼───┼──X───┼────┼────┼──┤ X ├──┼────┼──»\n",
       "           ┌─┴─┐  │    │    │    │    │   │  │   │    │    │  └─┬─┘┌─┴─┐  │  »\n",
       "   zero_0: ┤ X ├──┼────┼────┼────X────┼───┼──┼───■────┼────┼────┼──┤ X ├──┼──»\n",
       "           └───┘┌─┴─┐  │    │         │   │  │        │    │    │  └───┘┌─┴─┐»\n",
       "   zero_1: ─────┤ X ├──┼────┼─────────X───┼──┼────────■────┼────┼───────┤ X ├»\n",
       "                └───┘┌─┴─┐  │             │  │             │    │       └───┘»\n",
       "  zero'_0: ──────────┤ X ├──┼─────────────X──┼─────────────■────┼────────────»\n",
       "                     └───┘┌─┴─┐              │                  │            »\n",
       "  zero'_1: ───────────────┤ X ├──────────────X──────────────────■────────────»\n",
       "                          └───┘                                              »\n",
       "zero_buff: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       "   c_in_0: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       "   c_in_1: ──────────────────────────────────────────────────────────────────»\n",
       "                                                                             »\n",
       " output: 3/══════════════════════════════════════════════════════════════════»\n",
       "                                                                             »\n",
       "«                                      \n",
       "«      a_0: ───────────────────────────\n",
       "«                                      \n",
       "«      a_1: ───────────────────────────\n",
       "«                                      \n",
       "«      b_0: ───────────────────────────\n",
       "«                                      \n",
       "«      b_1: ───────────────────────────\n",
       "«                                      \n",
       "«     a'_0: ───────────────────────────\n",
       "«                                      \n",
       "«     a'_1: ───────────────────────────\n",
       "«                                      \n",
       "«     b'_0: ──■────────────────────────\n",
       "«             │                        \n",
       "«     b'_1: ──┼────■───────────────────\n",
       "«             │    │                   \n",
       "«      c_0: ──┼────┼───X───■─────────■─\n",
       "«             │    │   │   │         │ \n",
       "«      c_1: ──┼────┼───┼───┼──────X──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«     c'_0: ──┼────┼───X───┼──────┼──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«     c'_1: ──┼────┼───┼───┼──────X──┼─\n",
       "«             │    │   │   │      │  │ \n",
       "«   zero_0: ──┼────┼───┼───┼───X──┼──┼─\n",
       "«             │    │   │   │   │  │  │ \n",
       "«   zero_1: ──┼────┼───┼───┼───┼──┼──X─\n",
       "«           ┌─┴─┐  │   │   │   │  │  │ \n",
       "«  zero'_0: ┤ X ├──┼───┼───┼───X──┼──┼─\n",
       "«           └───┘┌─┴─┐ │   │   │  │  │ \n",
       "«  zero'_1: ─────┤ X ├─┼───┼───┼──┼──X─\n",
       "«                └───┘ │ ┌─┴─┐ │  │    \n",
       "«zero_buff: ───────────┼─┤ X ├─┼──■────\n",
       "«                      │ └───┘ │       \n",
       "«   c_in_0: ───────────■───────┼───────\n",
       "«                              │       \n",
       "«   c_in_1: ───────────────────■───────\n",
       "«                                      \n",
       "« output: 3/═══════════════════════════\n",
       "«                                      "
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=2\n",
    "input = '0' * n\n",
    "circuit = generate_CSA1_n_qubits(n, input, input, '0', measure=False)\n",
    "usim = Aer.get_backend('unitary_simulator')\n",
    "transpiled = transpile(circuit, backend=usim, optimization_level=3)\n",
    "print(\"Depth of circuit with addends of \"+ str(n) +\" qubits is: \"+str(transpiled.depth()))\n",
    "transpiled.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quantum Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(visual inspection, since Qiskit does not provide anything to count the number of gates)\n",
    "\n",
    "**CSA:** n-1 CNOT + 4n Peres + 2n Fredkin = n-1 + 16n + 10n = **27n - 1**\n",
    "\n",
    "**Ripple Carry Adder:** 5n+1 CNOT, 2n-1 Toffoli, 2n-1 negations = 5n+1 + 10n-1 = **15n**\n",
    "\n",
    "\n",
    "Quantum costs of basis gates: 1 CNOT, 5 Toffoli, 5 Fredkin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Number of qubits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QUBITS\n",
    "\n",
    "**CSA:**            9n-3      \n",
    "\n",
    "**CSA w/ opt:**     8n+2      \n",
    "\n",
    "**RCA:**            2n+2      \n",
    "\n",
    "----------------------------------\n",
    "\n",
    "ANCILLA\n",
    "\n",
    "**CSA:**            7n-1\n",
    "\n",
    "**CSA w/ opt:**     6n\n",
    "\n",
    "**RCA:**            0 or 1\n",
    "\n",
    "----------------------------------\n",
    "\n",
    "GARBAGE\n",
    "\n",
    "**CSA:**            8n-4\n",
    "\n",
    "**CSA w/ opt:**     7n+1\n",
    "\n",
    "**RCA:**            n+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Another alternative implementation of Design-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To save some qubits, it can be implemented a CSA version where RFAs are run in series within the same stages. That would increase the depth of the circuit of a constant factor, in exchange of decreasing the number of qubits by 2n: \n",
    "- Depth: 8 + 2n - 1 = 2n + 7\n",
    "- Qubits: 9n-3 - 2n = 7n - 3\n",
    "\n",
    "Transpiler could eventually optimize the depth of the circuit by some constant factor, but still, this does not justify the higher cost of the CSA in respect to the Ripple Carry Adder."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSA Design-2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This design drops the Full Adder gates in favour of cheaper gates in terms of quantum cost. Furthermore, according to the authors, this design should be cheaper in terms of ancilla bits, but is actually more expensive as shown below. The reasons for that might be either because my implementation is not optimal or because the authors did not actually implement the circuit. Indeed according to their scheme (Fig. 8 in the paper) the ancilla bits are:\n",
    "\n",
    "1. The zero in the first peres gate\n",
    "2. The one in the second peres gate\n",
    "3. And the zero in the CNOT (buffer)\n",
    "\n",
    "The authors do not take into account that in order to run in parallel the CNOT gates and the Peres gates (as the CLA would do so as the paper let intended), the input bits \"a\" and \"b\" should be copied on extra lines, as I did in the first design. The alternative, in order to lower ancilla bits (and thus the garbage bits), is to run in series some of the gates and that means increasing the delay of the circuit.\n",
    "\n",
    "Even thought results are not the same as in the paper, I agree with the authors when they say this design is better. As a metter of fact the circuit uses less and simpler gates: 3n CNOTs, 2n Peres and 2n Fredkins (ignoring initialization gates which can be omitted). On the countrary Design-1 uses 2n RFA (4n Peres + 2n swap gates), 2n Fredkins and n-1 CNOTs. So, using more qubits, we can have a faster, simpler and cheaper (in terms of quantum cost) Carry Select Adder."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterative constrution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_CSA2_n_qubits(n, a, b, c, measure=False, opt=False):\n",
    "    '''\n",
    "    Generate a CSA based on design-2.\n",
    "    n = number of addends\n",
    "    a = first addend\n",
    "    b = second addend\n",
    "    c = carry input\n",
    "    measure = whether to initialize and measure the results\n",
    "    opt = dummy argument to make the function compatible with the depth function\n",
    "    '''\n",
    "    if len(a) != n or len(b) != n:\n",
    "        return \"Length of inputs differs from length of n.\"\n",
    "    a = a[::-1]\n",
    "    b = b[::-1]\n",
    "    \n",
    "    a_in = QuantumRegister(n, name=\"a\")\n",
    "    b_in = QuantumRegister(n, name=\"b\")\n",
    "    a_copies = QuantumRegister(n, name=\"a'\")\n",
    "    b_copies = QuantumRegister(n, name=\"b'\")\n",
    "    b_copies2 = QuantumRegister(n, name=\"b''\")\n",
    "    a_not = QuantumRegister(n, name=\"a_not\")\n",
    "    b_not = QuantumRegister(n, name=\"b_not\")\n",
    "    a_not_copies = QuantumRegister(n, name=\"a_not'\")\n",
    "    zero = QuantumRegister(n, name=\"zero\")\n",
    "    zero_buffers = QuantumRegister(n-1, name=\"zero_buff\")\n",
    "    one = QuantumRegister(n, name=\"one\")\n",
    "    c_in = QuantumRegister(2, name=\"c_in\")\n",
    "    output = ClassicalRegister(n+1, name=\"output\")\n",
    "\n",
    "    csa2 = QuantumCircuit(a_in, b_in, a_copies, b_copies, b_copies2, a_not, b_not, a_not_copies, zero, zero_buffers, one, c_in, output)\n",
    "\n",
    "    if (measure):\n",
    "        if (c == '1'):\n",
    "            csa2.x(c_in[0])\n",
    "        for i in range(n):\n",
    "            # Initialization of qubit states\n",
    "            if (a[i] == '1'):\n",
    "                csa2.x(a_in[i])\n",
    "            if (b[i] == '1'):\n",
    "                csa2.x(b_in[i])\n",
    "            csa2.reset(a_copies[i])\n",
    "            csa2.reset(b_copies[i])\n",
    "            csa2.reset(b_copies2[i])\n",
    "            csa2.cx(a_in[i], a_copies[i])\n",
    "            csa2.cx(b_in[i], b_copies[i])\n",
    "            csa2.cx(b_in[i], b_copies2[i])\n",
    "            csa2.reset(a_not[i])\n",
    "            csa2.cx(a_in[i], a_not[i])\n",
    "            csa2.reset(b_not[i])\n",
    "            csa2.cx(b_in[i], b_not[i])\n",
    "            csa2.x(a_not[i])\n",
    "            csa2.x(b_not[i])\n",
    "            csa2.reset(a_not_copies[i])\n",
    "            csa2.cx(a_not[i], a_not_copies[i])\n",
    "            csa2.reset(zero[i])\n",
    "            csa2.reset(one[i])\n",
    "            csa2.x(one[i])\n",
    "        csa2.reset(c_in[1])\n",
    "        csa2.cx(c_in[0], c_in[1])\n",
    "        #csa2.barrier()\n",
    "        \n",
    "    for i in range(n):\n",
    "        # Circuit\n",
    "        csa2.cx(a_in[i], b_in[i])\n",
    "        csa2.cx(a_not[i], b_copies[i])\n",
    "        if i == 0:\n",
    "            csa2.fredkin(c_in[0], b_in[i], b_copies[i])                          # Sum is on b_in[0]\n",
    "        else:\n",
    "            csa2.fredkin(zero[i-1], b_in[i], b_copies[i])\n",
    "        \n",
    "        if (measure):\n",
    "            csa2.measure(b_in[i], output[i])\n",
    "\n",
    "        csa2.append(peres, [a_copies[i], b_copies2[i], zero[i]])                 # Carry 1 is on zero[0]\n",
    "        csa2.append(peres, [a_not_copies[i], b_not[i], one[i]])                  # Carry 2 is on one[0]\n",
    "        if i == 0:\n",
    "            csa2.fredkin(c_in[1], zero[i], one[i])                               # Carry is on zero[0]\n",
    "        else:\n",
    "            csa2.fredkin(zero_buffers[i-1], zero[i], one[i])\n",
    "\n",
    "        if (i < n-1):\n",
    "            csa2.cx(zero[i], zero_buffers[i])\n",
    "    \n",
    "    if (measure):\n",
    "        csa2.measure(zero[i], output[i+1])\n",
    "\n",
    "    return csa2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                                    \n",
       "       a: ────■─────────────────────\n",
       "            ┌─┴─┐                   \n",
       "       b: ──┤ X ├──────────────X────\n",
       "            └───┘   ┌────────┐ │    \n",
       "      a': ──────────┤0       ├─┼────\n",
       "            ┌───┐   │        │ │    \n",
       "      b': ──┤ X ├───┤        ├─X────\n",
       "            └─┬─┘   │        │ │    \n",
       "     b'': ────┼─────┤1       ├─┼────\n",
       "              │     │        │ │    \n",
       "   a_not: ────■─────┤  Peres ├─┼────\n",
       "          ┌────────┐│        │ │    \n",
       "   b_not: ┤1       ├┤        ├─┼────\n",
       "          │        ││        │ │    \n",
       "  a_not': ┤0       ├┤        ├─┼────\n",
       "          │  Peres ││        │ │    \n",
       "    zero: ┤        ├┤2       ├─┼──X─\n",
       "          │        │└────────┘ │  │ \n",
       "     one: ┤2       ├───────────┼──X─\n",
       "          └────────┘           │  │ \n",
       "  c_in_0: ─────────────────────■──┼─\n",
       "                                  │ \n",
       "  c_in_1: ────────────────────────■─\n",
       "                                    \n",
       "output: 2/══════════════════════════\n",
       "                                    </pre>"
      ],
      "text/plain": [
       "                                    \n",
       "       a: ────■─────────────────────\n",
       "            ┌─┴─┐                   \n",
       "       b: ──┤ X ├──────────────X────\n",
       "            └───┘   ┌────────┐ │    \n",
       "      a': ──────────┤0       ├─┼────\n",
       "            ┌───┐   │        │ │    \n",
       "      b': ──┤ X ├───┤        ├─X────\n",
       "            └─┬─┘   │        │ │    \n",
       "     b'': ────┼─────┤1       ├─┼────\n",
       "              │     │        │ │    \n",
       "   a_not: ────■─────┤  Peres ├─┼────\n",
       "          ┌────────┐│        │ │    \n",
       "   b_not: ┤1       ├┤        ├─┼────\n",
       "          │        ││        │ │    \n",
       "  a_not': ┤0       ├┤        ├─┼────\n",
       "          │  Peres ││        │ │    \n",
       "    zero: ┤        ├┤2       ├─┼──X─\n",
       "          │        │└────────┘ │  │ \n",
       "     one: ┤2       ├───────────┼──X─\n",
       "          └────────┘           │  │ \n",
       "  c_in_0: ─────────────────────■──┼─\n",
       "                                  │ \n",
       "  c_in_1: ────────────────────────■─\n",
       "                                    \n",
       "output: 2/══════════════════════════\n",
       "                                    "
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generate_CSA2_n_qubits(1, '0', '0', '0', measure=False).draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Correctness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Results of summations are correct as shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0', '1']\n",
      "a: 0 b: 0 c_in: 0 r: 00\n",
      "a: 0 b: 1 c_in: 0 r: 01\n",
      "a: 1 b: 0 c_in: 0 r: 01\n",
      "a: 1 b: 1 c_in: 0 r: 10\n"
     ]
    }
   ],
   "source": [
    "check_correctness(1, '0', generate_CSA2_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['00', '01', '10', '11']\n",
      "a: 00 b: 00 c_in: 0 r: 000\n",
      "a: 00 b: 01 c_in: 0 r: 001\n",
      "a: 00 b: 10 c_in: 0 r: 010\n",
      "a: 00 b: 11 c_in: 0 r: 011\n",
      "a: 01 b: 00 c_in: 0 r: 001\n",
      "a: 01 b: 01 c_in: 0 r: 010\n",
      "a: 01 b: 10 c_in: 0 r: 011\n",
      "a: 01 b: 11 c_in: 0 r: 100\n",
      "a: 10 b: 00 c_in: 0 r: 010\n",
      "a: 10 b: 01 c_in: 0 r: 011\n",
      "a: 10 b: 10 c_in: 0 r: 100\n",
      "a: 10 b: 11 c_in: 0 r: 101\n",
      "a: 11 b: 00 c_in: 0 r: 011\n",
      "a: 11 b: 01 c_in: 0 r: 100\n",
      "a: 11 b: 10 c_in: 0 r: 101\n",
      "a: 11 b: 11 c_in: 0 r: 110\n"
     ]
    }
   ],
   "source": [
    "check_correctness(2, '0', generate_CSA2_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['00', '01', '10', '11']\n",
      "a: 00 b: 00 c_in: 1 r: 001\n",
      "a: 00 b: 01 c_in: 1 r: 010\n",
      "a: 00 b: 10 c_in: 1 r: 011\n",
      "a: 00 b: 11 c_in: 1 r: 100\n",
      "a: 01 b: 00 c_in: 1 r: 010\n",
      "a: 01 b: 01 c_in: 1 r: 011\n",
      "a: 01 b: 10 c_in: 1 r: 100\n",
      "a: 01 b: 11 c_in: 1 r: 101\n",
      "a: 10 b: 00 c_in: 1 r: 011\n",
      "a: 10 b: 01 c_in: 1 r: 100\n",
      "a: 10 b: 10 c_in: 1 r: 101\n",
      "a: 10 b: 11 c_in: 1 r: 110\n",
      "a: 11 b: 00 c_in: 1 r: 100\n",
      "a: 11 b: 01 c_in: 1 r: 101\n",
      "a: 11 b: 10 c_in: 1 r: 110\n",
      "a: 11 b: 11 c_in: 1 r: 111\n"
     ]
    }
   ],
   "source": [
    "check_correctness(2, '1', generate_CSA2_n_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With measure = false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 2 qubits is: 4\n",
      "Depth of circuit with addends of 3 qubits is: 6\n",
      "Depth of circuit with addends of 4 qubits is: 8\n",
      "Depth of circuit with addends of 5 qubits is: 10\n",
      "Depth of circuit with addends of 6 qubits is: 12\n",
      "Depth of circuit with addends of 7 qubits is: 14\n",
      "Depth of circuit with addends of 8 qubits is: 16\n",
      "Depth of circuit with addends of 9 qubits is: 18\n",
      "Depth of circuit with addends of 10 qubits is: 20\n",
      "Depth of circuit with addends of 11 qubits is: 22\n",
      "Depth of circuit with addends of 12 qubits is: 24\n",
      "Depth of circuit with addends of 13 qubits is: 26\n",
      "Depth of circuit with addends of 14 qubits is: 28\n",
      "Depth of circuit with addends of 15 qubits is: 30\n",
      "Depth of circuit with addends of 16 qubits is: 32\n"
     ]
    }
   ],
   "source": [
    "for i in range(2,17):\n",
    "    evluate_circuit(i, generate_CSA2_n_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With measure = true. Initialization of qubits takes quite a lot of space (5 steps) because there are a lot of bits to copy and then negate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 2 qubits is: 9\n",
      "Depth of circuit with addends of 3 qubits is: 11\n",
      "Depth of circuit with addends of 4 qubits is: 13\n",
      "Depth of circuit with addends of 5 qubits is: 15\n",
      "Depth of circuit with addends of 6 qubits is: 17\n",
      "Depth of circuit with addends of 7 qubits is: 19\n",
      "Depth of circuit with addends of 8 qubits is: 21\n",
      "Depth of circuit with addends of 9 qubits is: 23\n",
      "Depth of circuit with addends of 10 qubits is: 25\n",
      "Depth of circuit with addends of 11 qubits is: 27\n",
      "Depth of circuit with addends of 12 qubits is: 29\n",
      "Depth of circuit with addends of 13 qubits is: 31\n",
      "Depth of circuit with addends of 14 qubits is: 33\n",
      "Depth of circuit with addends of 15 qubits is: 35\n",
      "Depth of circuit with addends of 16 qubits is: 37\n"
     ]
    }
   ],
   "source": [
    "for i in range(2,17):\n",
    "    evluate_circuit(i, generate_CSA2_n_qubits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Depth of circuit with addends of 1 qubits is: 2\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"word-wrap: normal;white-space: pre;background: #fff0;line-height: 1.1;font-family: &quot;Courier New&quot;,Courier,monospace\">                                    \n",
       "       a: ────■─────────────────────\n",
       "            ┌─┴─┐                   \n",
       "       b: ──┤ X ├──────────────X────\n",
       "            └───┘   ┌────────┐ │    \n",
       "      a': ──────────┤0       ├─┼────\n",
       "            ┌───┐   │        │ │    \n",
       "      b': ──┤ X ├───┤        ├─X────\n",
       "            └─┬─┘   │        │ │    \n",
       "     b'': ────┼─────┤1       ├─┼────\n",
       "              │     │        │ │    \n",
       "   a_not: ────■─────┤  Peres ├─┼────\n",
       "          ┌────────┐│        │ │    \n",
       "   b_not: ┤1       ├┤        ├─┼────\n",
       "          │        ││        │ │    \n",
       "  a_not': ┤0       ├┤        ├─┼────\n",
       "          │  Peres ││        │ │    \n",
       "    zero: ┤        ├┤2       ├─┼──X─\n",
       "          │        │└────────┘ │  │ \n",
       "     one: ┤2       ├───────────┼──X─\n",
       "          └────────┘           │  │ \n",
       "  c_in_0: ─────────────────────■──┼─\n",
       "                                  │ \n",
       "  c_in_1: ────────────────────────■─\n",
       "                                    \n",
       "output: 2/══════════════════════════\n",
       "                                    </pre>"
      ],
      "text/plain": [
       "                                    \n",
       "       a: ────■─────────────────────\n",
       "            ┌─┴─┐                   \n",
       "       b: ──┤ X ├──────────────X────\n",
       "            └───┘   ┌────────┐ │    \n",
       "      a': ──────────┤0       ├─┼────\n",
       "            ┌───┐   │        │ │    \n",
       "      b': ──┤ X ├───┤        ├─X────\n",
       "            └─┬─┘   │        │ │    \n",
       "     b'': ────┼─────┤1       ├─┼────\n",
       "              │     │        │ │    \n",
       "   a_not: ────■─────┤  Peres ├─┼────\n",
       "          ┌────────┐│        │ │    \n",
       "   b_not: ┤1       ├┤        ├─┼────\n",
       "          │        ││        │ │    \n",
       "  a_not': ┤0       ├┤        ├─┼────\n",
       "          │  Peres ││        │ │    \n",
       "    zero: ┤        ├┤2       ├─┼──X─\n",
       "          │        │└────────┘ │  │ \n",
       "     one: ┤2       ├───────────┼──X─\n",
       "          └────────┘           │  │ \n",
       "  c_in_0: ─────────────────────■──┼─\n",
       "                                  │ \n",
       "  c_in_1: ────────────────────────■─\n",
       "                                    \n",
       "output: 2/══════════════════════════\n",
       "                                    "
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=1\n",
    "input = '0' * n\n",
    "circuit = generate_CSA2_n_qubits(n, input, input, '0', measure=False)\n",
    "usim = Aer.get_backend('unitary_simulator')\n",
    "transpiled = transpile(circuit, backend=usim, optimization_level=3)\n",
    "print(\"Depth of circuit with addends of \"+ str(n) +\" qubits is: \"+str(transpiled.depth()))\n",
    "circuit.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depth:\n",
    "\n",
    "**Ripple Carry Adder:** 2n+6\n",
    "\n",
    "**CSA-1:** 2n+2\n",
    "\n",
    "**CSA-2:** 2n\n",
    "\n",
    "    MEASURE   |   RES \n",
    "    ------------------\n",
    "      F       |   2n\n",
    "      T       |   2n+5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Design-2:\n",
    "\n",
    "- 2n CNOTs\n",
    "- 2n Peres\n",
    "- 2n Fredkin\n",
    "- n-1 CNOTs\n",
    "\n",
    "**Total:** 21n - 1\n",
    "\n",
    "**CSA-1:** 27n - 1\n",
    "\n",
    "**Ripple Carry Adder:** 15n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Number of qubits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Number of qubits is as follows:\n",
    "- 2n for the addends\n",
    "- n qubits to copy addend 'a'\n",
    "- 2n qubits to copy addend 'b'\n",
    "- 2n qubits for the complements of 'a'\n",
    "- n qubits for the complements of 'b'\n",
    "- n zeros\n",
    "- n ones\n",
    "- n-1 zeros for buffers\n",
    "- 2 qubits for carry-in\n",
    "\n",
    "**Total:** 11n+1.\n",
    "\n",
    "**Ancilla:** 2n+2 is the original input (2n for a and b + 2 for carry-in), the rest is initialized to 0 or 1, so 11n+1 - 2n-2 = 9n-1.\n",
    "\n",
    "The paper states that ancilla are 3n-1, given by the 2n numbers of 0s and 1s given to each Peres gate, plus the n-1 0s given as input to the buffers. But here are considered as ancilla also the bits initialized to 0 in order to copy and/or negate the copies of addends, which are in total 6n. These, as seen also for Design-1, are not considered by the two authors.\n",
    "\n",
    "**Garbage:** n+1 is the length of the output needed to represent the sum, the rest can be discarded, so 11n+1 - n-1 = 10n."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QUBITS\n",
    "\n",
    "**CSA-2:**            11n+1\n",
    "\n",
    "**CSA-1:**            9n-3      \n",
    "\n",
    "**CSA-1 w/ opt:**     8n+2      \n",
    "\n",
    "**RCA:**              2n+2      \n",
    "\n",
    "----------------------------------\n",
    "\n",
    "ANCILLA\n",
    "\n",
    "**CSA-2:**            9n-1\n",
    "\n",
    "**CSA-1:**            7n-1\n",
    "\n",
    "**CSA-1 w/ opt:**     6n\n",
    "\n",
    "**RCA:**              0 or 1\n",
    "\n",
    "----------------------------------\n",
    "\n",
    "GARBAGE\n",
    "\n",
    "**CSA-2:**            10n\n",
    "\n",
    "**CSA-1:**            8n-4\n",
    "\n",
    "**CSA-1 w/ opt:**     7n+1\n",
    "\n",
    "**RCA:**              n+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusions\n",
    "The quantum implementation of the two RCA designs are not as efficient as the Ripple Carry Adder: the second design is preferable in terms of depth because it removes a constant depth of 6 and in terms of quantum cost because it is way cheaper (21n-1 vs. 27n-1), but the total number of qubit used by the second design is bigger (11n+1 vs. 9n-3).\n",
    "\n",
    "The smaller depth however does not justify the bigger quantum cost and number of qubits used if they are compared to the Ripple Carry Adder implementation of Cuccaro et al."
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49"
  },
  "kernelspec": {
   "display_name": "Python 3.8.2 64-bit",
   "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.13"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}