RippleCarryAdder/Workbook_RippleCarryAdder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ripple Carry Adder Workbook\n",
    "**What is this workbook?** \n",
    "A workbook is a collection of problems, accompanied by solutions to them. The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required.\n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck or for reinforcement. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Ripple Carry Adder Kata](./RippleCarryAdder.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a novice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts and associated techniques **prior to** beginning work on the Basic Gates Quantum Kata.\n",
    "\n",
    "1. [Basic Gates Kata](../BasicGates/BasicGates.ipynb). \n",
    "2. [Single-qubit gates](../tutorials/SingleQubitGates/SingleQubitGates.ipynb).\n",
    "3. List of basic gates available in Q# can be found at [Microsoft.Quantum.Intrinsic](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic).\n",
    "4. [Syntax of flow control statements in Q#](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/iterations) \n",
    "5. [Q# conditional branching](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conditionalbranching) documentation.\n",
    "\n",
    "You can also consult the [complete Quantum Katas learning path](https://github.com/microsoft/QuantumKatas#learning-path)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Simple Adder Outputting to Empty Qubits\n",
    "\n",
    "\n",
    "### Theory\n",
    "\n",
    "* [Classical binary adder on Wikipedia](https://en.wikipedia.org/wiki/Adder_(electronics)).\n",
    "* Part 2 of the [paper on quantum binary addition](https://arxiv.org/pdf/quant-ph/0008033.pdf) by Thomas G. Draper explains how to adapt the classical adder to a quantum environment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Summation of two bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,  \n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,  \n",
    "  3. qubit `sum` in state $|0\\rangle$.\n",
    "\n",
    "**Goal:** Transform the `sum` qubit into the lowest bit of the binary sum of $\\phi$ and $\\psi$.\n",
    "\n",
    "* $|0\\rangle + |0\\rangle \\to |0\\rangle$\n",
    "* $|0\\rangle + |1\\rangle \\to |1\\rangle$\n",
    "* $|1\\rangle + |0\\rangle \\to |1\\rangle$\n",
    "* $|1\\rangle + |1\\rangle \\to |0\\rangle$\n",
    "\n",
    "Any superposition should map appropriately. \n",
    "\n",
    "**Example:** (Recall that $|+\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle + |1\\rangle)$, $|-\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)$)\n",
    "\n",
    "$|+\\rangle \\otimes |-\\rangle \\otimes |0\\rangle \\to \\frac{1}{2}(|000\\rangle + |101\\rangle - |011\\rangle - |110\\rangle)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> In this workbook we will reason about the computations acting on basis states, as opposed to arbitrary superposition states. \n",
    "> (Since all computations will be implemented using quantum gates, they'll be linear, and behave correctly on superpositions if they are correct on all basis states.) \n",
    "> This will allow us to use qubit states and the classical values stored in them interchangeably.\n",
    "\n",
    "Clearly, the expression we're looking for is $a \\oplus b$ - sum of bits $a$ and $b$ modulo 2.\n",
    "\n",
    "If we apply $CNOT(a,sum)$, then $a=a$, $b=b$, and $sum$ becomes $0 \\oplus a = a$.\n",
    "\n",
    "Again applying $CNOT(b,sum)$, we get $a=a$, $b=b$, and $sum$ becomes $sum \\oplus b = a \\oplus b$. That's exactly what we're looking for!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_LowestBitSum\n",
    "\n",
    "operation LowestBitSum (a : Qubit, b : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    CNOT(a, sum);\n",
    "    CNOT(b, sum);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative Solution\n",
    "\n",
    "If we apply $CNOT(a,b)$ , then $a = a$, $b = a \\oplus b$, and $sum = 0$.\n",
    "\n",
    "Again applying $CNOT(b,sum)$, we get $a = a$, $b = a \\oplus b$, and $sum = sum \\oplus b = a \\oplus b$.\n",
    "\n",
    "Now by applying $CNOT(a,b)$, we get $a = a$, $b = a \\oplus (a \\oplus b) = b$, $sum = a \\oplus b$, and thus we will restore the previous value of $b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_LowestBitSum\n",
    "\n",
    "operation LowestBitSum (a : Qubit, b : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    CNOT(a, b);\n",
    "    CNOT(b, sum);\n",
    "    CNOT(a, b);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.1 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.1.-Summation-of-two-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Carry of two bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goal:** Set the `carry` qubit to $|1\\rangle$ if the binary sum of $\\phi$ and $\\psi$ produces a carry.\n",
    "\n",
    "* $|0\\rangle$ and $|0\\rangle \\to |0\\rangle$\n",
    "* $|0\\rangle$ and $|1\\rangle \\to |0\\rangle$\n",
    "* $|1\\rangle$ and $|0\\rangle \\to |0\\rangle$\n",
    "* $|1\\rangle$ and $|1\\rangle \\to |1\\rangle$\n",
    "\n",
    "Any superposition should map appropriately. \n",
    "\n",
    "**Example:**\n",
    "\n",
    "$|+\\rangle \\otimes |-\\rangle \\otimes |0\\rangle \\to \\frac{1}{2}(|000\\rangle + |100\\rangle - |010\\rangle - |111\\rangle)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Clearly, $carry = a \\text{ AND } b$.\n",
    "\n",
    "If we apply $CCNOT(a, b, carry)$, then $a=a$, $b=b$, and $carry$ becomes $(a \\text{ AND } b) \\oplus carry = (a \\text{ AND } b) \\oplus 0 = (a \\text{ AND } b)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_LowestBitCarry\n",
    "\n",
    "operation LowestBitCarry (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    CCNOT(a, b, carry);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.2 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.2.-Carry-of-two-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. One-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. two qubits `sum` and `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform the `sum` qubit into the lowest bit of the binary sum of $\\phi$ and $\\psi$.\n",
    "* Transform the `carry` qubit into the carry bit produced by that sum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "This task is just a combination of the two previous ones. Using [task 1.1](#Task-1.1.-Summation-of-two-bits) and [task 1.2](#Task-1.2.-Carry-of-two-bits), \n",
    "we can get the solution below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_OneBitAdder\n",
    "\n",
    "operation OneBitAdder (a : Qubit, b : Qubit, sum : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    LowestBitSum(a, b, sum);\n",
    "    LowestBitCarry(a, b, carry);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.3 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.3.-One-bit-adder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. Summation of 3 bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carryin` in an arbitrary state $|\\omega\\rangle$,\n",
    "  4. qubit `sum` in state $|0\\rangle$.\n",
    "\n",
    "**Goal:** Transform the `sum` qubit into the lowest bit of the binary sum of $\\phi$, $\\psi$ and $\\omega$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Clearly, the expression we're looking for is $a \\oplus b \\oplus carryin$ - sum of bits $a$, $b$, and $carryin$ modulo 2.\n",
    "\n",
    "If we apply $CNOT(a,sum)$, the bits $a$, $b$, and $carryin$ remain unchanged, and $sum$ becomes $0 \\oplus a = a$.\n",
    "\n",
    "If we apply $CNOT(b,sum)$ after that, the bits $a$, $b$, and $carryin$ remain unchanged, and $sum$ becomes $sum \\oplus b = a \\oplus b$.\n",
    "\n",
    "Finally, if we apply $CNOT(carryin,sum)$, the bits $a$, $b$, and $carryin$ remain unchanged, and $sum$ becomes $sum \\oplus carryin = a \\oplus b \\oplus carryin$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_HighBitSum\n",
    "\n",
    "operation HighBitSum (a : Qubit, b : Qubit, carryin : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    CNOT(a, sum);\n",
    "    CNOT(b, sum);\n",
    "    CNOT(carryin, sum);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternative Solution\n",
    "\n",
    "Let's start by applying $CNOT(a,b)$: the bits $a$, $carryin$, and $sum$ remain unchanged, and $b$ becomes $a \\oplus b$.\n",
    "\n",
    "After that, we apply $CNOT(b,carryin)$: the bits $a$, $a \\oplus b$, and $sum$ remain unchanged, and $carryin$ becomes $carryin \\oplus (a \\oplus b)$.\n",
    "\n",
    "Now we apply $CNOT(carryin,sum)$: the bits $a$, $a \\oplus b$, and $carryin \\oplus a \\oplus b$ remain unchanged, and $sum$ becomes $sum \\oplus (a \\oplus b \\oplus carryin)$.\n",
    "\n",
    "Now that we have obtained the right value stored in the $sum$ variable, we need to restore the values in $b$ and $carryin$ to their original values. We can do that using uncomputation, implemented using the `within ... apply` construct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_HighBitSum\n",
    "\n",
    "operation HighBitSum (a : Qubit, b : Qubit, carryin : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    within {\n",
    "        CNOT(a, b);\n",
    "        CNOT(b, carryin);\n",
    "    } apply {\n",
    "        CNOT(carryin, sum);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.4 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.4.-Summation-of-3-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. Carry of 3 bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carryin` in an arbitrary state $|\\omega\\rangle$,\n",
    "  4. qubit `carryout` in state $|0\\rangle$.\n",
    "\n",
    "**Goal:** Transform the `carryout` qubit into the carry bit produced by the sum of $\\phi$, $\\psi$ and $\\omega$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The resulting value of `carryout` should be the majority of bits $\\phi$, $\\psi$ and $\\omega$, that is, 1 if two or three of them are 1, and 0 otherwise.\n",
    "\n",
    "The majority of three inputs $a$, $b$, and $carryin$ can be expressed as $(a \\text{ AND } b) \\oplus (b \\text{ AND } carryin) \\oplus (carryin \\text{ AND } a)$. Indeed, you can check that if one or none of the inputs are 1, each of the expressions in the brackets is 0, and their sum is 0 as well. If two inputs are 1, exactly one of the expressions in the brackets is 1, and if all three inputs are 1, all three expressions in the brackets are 1, and their sum modulo 2 is 1.\n",
    "\n",
    "Similarly to task 1.2, we can use the CCNOT gate with pairs of inputs as controls and `carryout` as the target to add pairwise $\\text{AND}$s of the inputs to the output qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_HighBitCarry\n",
    "\n",
    "operation HighBitCarry (a : Qubit, b : Qubit, carryin : Qubit, carryout : Qubit) : Unit is Adj {\n",
    "    CCNOT(a, b, carryout);\n",
    "    CCNOT(b, carryin, carryout);\n",
    "    CCNOT(carryin, a, carryout);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.5 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.5.-Carry-of-3-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. Two-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. two-qubit register `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. two-qubit register `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. two-qubit register `sum` in state $|00\\rangle$,\n",
    "  4. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform the `sum` register into the binary sum (little-endian) of $\\phi$ and $\\psi$.\n",
    "* Transform the `carry` qubit into the carry bit produced by that sum.\n",
    "\n",
    "> All registers in this kata are in **little-endian** order.\n",
    "> This means that they have the least significant bit first, followed by the next least significant, and so on.\n",
    ">\n",
    "> In this exercise, for example, $1$ would be represented as $|10\\rangle$, and $2$ as $|01\\rangle$.\n",
    ">\n",
    "> The sum of $|10\\rangle$ and $|11\\rangle$ would be $|001\\rangle$, with the last qubit being the carry qubit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First we will follow the hint and allocate a qubit to store the carry bit produced by the addition of the least significant bits (LSBs) that will be used as $carryin$ for the addition of the most significant bits (MSBs).\n",
    "\n",
    "Then we will perform addition bit by bit, first the LSBs and then the MSBs. \n",
    "\n",
    "1. We can add the LSBs with the `OneBitAdder` function from the [task 1.3](#Task-1.3.-One-bit-adder), using the LSBs `a[0]` and `b[0]` as the bits added by it, `sum[0]` as their sum, and the qubit `carryin` as the carry bit produced by them. \n",
    "2. Next we will add the MSBs using the operations `HighBitSum` from the [task 1.4](#Task-1.4.-Summation-of-3-bits) and `HighBitCarry` from the [task 1.5](#Task-1.5.-Carry-of-3-bits). We'll use the MSBs `a[1]` and `b[1]` and the qubit `carryin` as the bits added by it, `sum[1]` as their sum, and the qubit `carry` as the carry bit produced by them. \n",
    "\n",
    "At this point we have all the input qubits in the right states, but we need to uncompute the qubit `carryin` before releasing it. We can do it by applying `Adjoint LowestBitCarry(a[0], b[0], carryin)` - the adjoint of the operation we used to compute its state as part of the `OneBitAdder` operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T16_TwoBitAdder\n",
    "\n",
    "operation TwoBitAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    use carryin = Qubit();\n",
    "    \n",
    "    // Add the least significant bits\n",
    "    OneBitAdder(a[0], b[0], sum[0], carryin);\n",
    "\n",
    "    // Add the most significant bits\n",
    "    HighBitSum(a[1], b[1], carryin, sum[1]);\n",
    "    HighBitCarry(a[1], b[1], carryin, carry);\n",
    "    \n",
    "    // Uncompute the temporarily allocated carry bit \n",
    "    Adjoint LowestBitCarry(a[0], b[0], carryin);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.6 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.6.-Two-bit-adder|)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. N-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$-qubit register `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. $N$-qubit register `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. $N$-qubit register `sum` in state $|0...0\\rangle$,\n",
    "  4. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform the `sum` register into the binary sum (little-endian) of $\\phi$ and $\\psi$.\n",
    "* Transform the `carry` qubit into the carry bit produced by that sum.\n",
    "\n",
    "**Challenge:**\n",
    "\n",
    "Can you do this without allocating extra qubits?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First we will get the length of the adder inputs $N$ and allocate a qubit array of length $N$ for storing the carry bits.\n",
    "\n",
    "Then we will perform addition bit by bit, from the LSBs to the MSBs. \n",
    "\n",
    "1. We can add the LSBs with the `OneBitAdder` function from the [task 1.3](#Task-1.3.-One-bit-adder), using the LSBs `a[0]` and `b[0]` as the bits added by it, `sum[0]` as their sum, and the qubit `carryin` as the carry bit produced by them. \n",
    "2. Next we will add the more significant bits using the operations `HighBitSum` from the [task 1.4](#Task-1.4.-Summation-of-3-bits) and `HighBitCarry` from the [task 1.5](#Task-1.5.-Carry-of-3-bits). On each step we'll use the MSBs `a[i]` and `b[i]` and the qubit `carryin[i-1]` as the bits added by it, `sum[i]` as their sum, and `carryin[i]` as the carry bit produced by them. \n",
    "3. Once we've added all the bits, we use $CNOT(carryin[N-1], carry)$ to copy the most significant of the carry bits out to the qubit `carry`.\n",
    "\n",
    "Now that we have the required $sum$ and $carry$, we have to uncompute the qubits `carryin` by running a for loop in reverse order and applying `Adjoint HighBitCarry`, followed by the `Adjoint LowestBitCarry` - the adjoints of the operations used to compute these qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_ArbitraryAdder\n",
    "\n",
    "operation ArbitraryAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    let N = Length(a);\n",
    "    use carryin = Qubit[N];\n",
    "    \n",
    "    // Add the least significant bits\n",
    "    OneBitAdder(a[0], b[0], sum[0], carryin[0]);\n",
    "    \n",
    "    // Add the more significant bits\n",
    "    for i in 1 .. N - 1 {\n",
    "        HighBitSum(a[i], b[i], carryin[i - 1], sum[i]);\n",
    "        HighBitCarry(a[i], b[i], carryin[i - 1], carryin[i]);\n",
    "    }\n",
    "    \n",
    "    // Copy the most significant bit of the carryin into the carryout qubit\n",
    "    CNOT(carryin[N - 1], carry);\n",
    "    \n",
    "    // Uncompute the temporarily allocated carry bits \n",
    "    for i in N - 1 .. -1 .. 1 {\n",
    "        Adjoint HighBitCarry(a[i], b[i], carryin[i - 1], carryin[i]);\n",
    "    }\n",
    "    Adjoint LowestBitCarry(a[0], b[0], carryin[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge Solution\n",
    "\n",
    "As we are trying to solve this task without using additional qubits, let's notice that we compute sum bits and carry bits in parallel and then uncompute the carry bits; most of computation focuses on the carry bits, while the sum bits only store the results and are not involved in the carry bits computation. Now that we cannot allocate temporary qubits to store the carry bits, let's try to temporarily store them in the sum bits (which are initially empty).\n",
    "\n",
    "To do this, we'll reorder the computations we do:\n",
    "\n",
    "1. Start by computing all the carry bits (storing them in the sum) and copying out the most significant carry bit to get the `carry` qubit in the right state. We can do it using the same operations `LowestBitCarry` from the [task 1.2](#Task-1.2.-Carry-of-two-bits) and `HighBitCarry` from the [task 1.5](#Task-1.5.-Carry-of-3-bits) we used in the regular version of the solution, but with `sum[i]` used as the target of operations instead of `carryin[i]`.\n",
    "\n",
    "2. Now that we have obtained the required carry, we will work on uncomputing the carry bits and getting the sum bits instead. We cannot uncompute all of the carry bits before computing all the sum bits, though, because the more significant sum bits depend on the less significant carry bits. Instead, we'll iterate from the more significant bits to the less significant ones, and on each step uncompute the carry bit using `Adjoint HighBitCarry` on the inputs and the less significant carry, and immediately compute the sum bit using `HighBitSum` from the [task 1.4](#Task-1.4.-Summation-of-3-bits) on the same inputs. \n",
    "\n",
    "3. Finally, we uncompute the LSB of the carry using `Adjoint LowestBitCarry` and then use the operation `LowestBitSum` from the [task 1.1](#Task-1.1.-Summation-of-two-bits) to get the LSB of the sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_ArbitraryAdder\n",
    "\n",
    "operation ArbitraryAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    let N = Length(a);\n",
    "\n",
    "    // Compute all carry bits, storing them in sum\n",
    "    LowestBitCarry(a[0], b[0], sum[0]);\n",
    "    for i in 1 .. N -1  {\n",
    "        HighBitCarry(a[i], b[i], sum[i - 1], sum[i]);\n",
    "    }\n",
    "    // Copy the most significant bit of the carryin into the carryout qubit\n",
    "    CNOT(sum[N - 1], carry);\n",
    "\n",
    "    for i in N-1 .. -1 .. 1 {\n",
    "        // Uncompute the carry bit stored in the sum qubit\n",
    "        Adjoint HighBitCarry(a[i], b[i], sum[i - 1], sum[i]);\n",
    "        // And compute the sum bit to store there\n",
    "        HighBitSum(a[i], b[i], sum[i - 1], sum[i]);\n",
    "    }\n",
    "    // Uncompute the LSB of the carry\n",
    "    Adjoint LowestBitCarry(a[0], b[0], sum[0]);\n",
    "    // And compute the LSB of the sum\n",
    "    LowestBitSum(a[0], b[0], sum[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.7 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-1.7.-N-bit-adder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Simple In-place Adder\n",
    "\n",
    "The adder from the previous section requires empty qubits to accept the result.\n",
    "This section adapts the previous adder to calculate the sum in-place,\n",
    "that is, to reuse one of the numerical inputs for storing the output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. In-place summation of two bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform qubit `b` into the lowest bit of the sum of $\\phi$ and $\\psi$.\n",
    "* Leave qubit `a` unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Clearly, what we're looking is for $b$ to become $a \\oplus b$, i.e., the sum of bits $a$ and $b$ modulo 2. This would implement in-place summation of 2 bits.\n",
    "\n",
    "If we apply $CNOT(a,b)$, then $a$ remains unchanged, and $b$ becomes $a \\oplus b$. That's exactly what we're looking for!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_LowestBitSumInPlace\n",
    "\n",
    "operation LowestBitSumInPlace (a : Qubit, b : Qubit) : Unit is Adj {\n",
    "    CNOT(a, b);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.1 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-2.1.-In-place-summation-of-two-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. In-place one-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform the `carry` qubit into the carry bit from the addition of $\\phi$ and $\\psi$.\n",
    "* Transform qubit `b` into the lowest bit of $\\phi + \\psi$.\n",
    "* Leave qubit `a` unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If we apply `LowestBitCarry(a, b, carry)` defined in [task 1.2](#Task-1.2.-Carry-of-two-bits), it will compute the carry bit we need, so that the bits $a$ and $b$ remain unchanged and the bit $carry$ becomes $(a \\text{ AND } b) \\oplus carry = (a \\text{ AND } b) \\oplus 0 = (a \\text{ AND } b)$.\n",
    "Now by applying `LowestBitSumInPlace(a, b)` from [task 2.1](#Task-2.1.-In-place-summation-of-two-bits) we will compute the sum in place, so that the bit $a$ remains unchanged and the bit $b$ becomes $a \\oplus b$.\n",
    "\n",
    "> It is important to first find the carry and then the sum, as doing in-place summation of $a$ and $b$ changes the value of the qubit $b$ to $a \\oplus b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_OneBitAdderInPlace\n",
    "\n",
    "operation OneBitAdderInPlace (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    LowestBitCarry(a, b, carry);\n",
    "    LowestBitSumInPlace(a, b);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.2 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-2.2.-In-place-one-bit-adder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. In-place summation of three bits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. qubit `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carryin` in an arbitrary state $|\\omega\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform qubit `b` into the lowest bit from the sum $\\phi + \\psi + \\omega$.\n",
    "* Leave qubits `a` and `carryin` unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Clearly, what we're looking is for $b$ to become $a \\oplus b \\oplus carryin$, i.e., the sum of bits $a$, $b$, and $carryin$ modulo 2. This would implement in-place summation of 3 bits.\n",
    "\n",
    "So if we apply $CNOT(a, b)$, then bit $a$ remains unchanged and bit $b$ becomes $b \\oplus a$.\n",
    "\n",
    "Now if we apply $CNOT(carryin, b)$, the bits $a$ and $carryin$ remain unchanged, and $b$ becomes $b \\oplus carryin = a \\oplus b \\oplus carryin$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_HighBitSumInPlace\n",
    "\n",
    "operation HighBitSumInPlace (a : Qubit, b : Qubit, carryin : Qubit) : Unit is Adj {\n",
    "    CNOT(a, b);\n",
    "    CNOT(carryin, b);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.3 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-2.3.-In-place-summation-of-three-bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. In-place two-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. two-qubit register `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. two-qubit register `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform register `b` into the state $|\\phi + \\psi\\rangle$.\n",
    "* Transform the `carry` qubit into the carry bit from the addition.\n",
    "* Leave register `a` unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First, we will allocate a qubit to store the internal carry (the carry bit from adding two least significant bits). Now we know that any temporarily allocated qubits need to be restored to the $|0\\rangle$ state before being released. We can implement this uncomputation using the `within ... apply` construct. \n",
    "\n",
    "As we have to perform in-place addition, we will first have to figure out the internal carry and the final carry. We can get the internal carry and final carry using the operations `LowestBitCarry` from [task 1.2](#Task-1.2.-Carry-of-two-bits) and `HighBitCarry` from [task 1.5](#Task-1.5.-Carry-of-3-bits), respectively.\n",
    "\n",
    "> If we perform the addition instead of computing carry in the first step, it will change the values stored in the qubits, since we're doing addition in-place, and we may get the wrong carry.\n",
    "\n",
    "Now, once we have found the internal carry and final carry, we can start with the in-place addition of the qubits.\n",
    "First, we will add the MSBs in-place using `HighBitSumInPlace(a[1], b[1], internalCarry)`.\n",
    "Since we need to uncompute the qubit `internalCarry` before releasing it, we will use the operation `LowestBitCarry` in the within block. \n",
    "\n",
    "Now, we will simply use the operation `LowestBitSumInPlace` to add the LSBs in-place. \n",
    "\n",
    "> We are adding the LSBs outside the `within ... apply` construct so as to not change the value of $b[0]$ and affect the restoration of internalCarry."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_TwoBitAdderInPlace\n",
    "\n",
    "operation TwoBitAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    use internalCarry = Qubit();\n",
    "    \n",
    "    within {\n",
    "        LowestBitCarry(a[0], b[0], internalCarry);\n",
    "    } apply {\n",
    "        HighBitCarry(a[1], b[1], internalCarry, carry);\n",
    "        HighBitSumInPlace(a[1], b[1], internalCarry);\n",
    "    }\n",
    "    \n",
    "    LowestBitSumInPlace(a[0], b[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.4 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-2.4.-In-place-two-bit-adder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. In-place N-bit adder\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$-qubit register `a` in an arbitrary state $|\\phi\\rangle$,\n",
    "  2. $N$-qubit register `b` in an arbitrary state $|\\psi\\rangle$,\n",
    "  3. qubit `carry` in state $|0\\rangle$.\n",
    "\n",
    "**Goals:**\n",
    "\n",
    "* Transform register `b` into the state $|\\phi + \\psi\\rangle$.\n",
    "* Transform the `carry` qubit into the carry bit from the addition.\n",
    "* Leave register `a` unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First, we will allocate a qubit array of length $N$ to store the internal carry qubits. \n",
    "\n",
    "As we have to perform in-place addition, we will first have to figure out all the internal carries. We can get the least significant bit of the internal carries and the remaining bits using the operations `LowestBitCarry` from [task 1.2](#Task-1.2.-Carry-of-two-bits) and `HighBitCarry` from [task 1.5](#Task-1.5.-Carry-of-3-bits), respectively.\n",
    "\n",
    "> Note: If we add the qubits instead of computing carry in the first step, it will change the qubit states due to addition happening in-place, and we may get the wrong carry.\n",
    "\n",
    "So we first use the function `LowestBitCarry(a[0], b[0], internalCarries[0])` to get the internal carry of the LSBs (least significant bits). Next, we will use a loop from LSB to MSB to get the subsequent carries using the function `HighBitCarry(a[i], b[i], internalCarries[i - 1], internalCarries[i])`.\n",
    "\n",
    "Now, we have found all the internal carries. We will copy the most significant bit of the internal carry array in the $carry$ bit using `CNOT(internalCarries[N - 1], carry)`. \n",
    "\n",
    "The goal now is to perform the in-place addition and store it in the N-qubit register `b` and uncompute the `internalCarries` qubit array to release it at the end of the computation.\n",
    "For this, we will loop from the last to the first qubit, i.e., MSB to LSB, to restore the `internalCarries` array using `Adjoint` of the `HighBitCarry` operation and perform in-place addition using the `HighBitSumInPlace` operation from [task 2.3](#Task-2.3.-In-place-summation-of-three-bits), respectively.\n",
    "\n",
    "> Note: We are first restoring the `internalCarries` qubit for index i and then performing the in-place addition, as `internalCarries[i]` does not affects the addition for $a[i]$ and $b[i]$, and if we perform the addition first, then the qubit $b[i]$ will change which affects the restoration.\n",
    "\n",
    "Lastly, for the LSB, we will uncompute the `internalCarries[0]` qubit and get the sum of $a[0]$ and $b[0]$ in $b[0]$ using `Adjoint` on the `LowestBitCarry` operation and the `LowestBitSumInPlace` operation from [task 2.1](#Task-2.1.-In-place-summation-of-two-bits), respectively. \n",
    "\n",
    "> Note: While computing the internal carries, we go from index $1$ to $N-1$, as we require the previous carry to get the new carry. But for the in-place addition and restoration of internal carries, we go from the index $N-1$ to $1$, as we require the previous carry for the summation and on summation the qubits of $b$ change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_ArbitraryAdderInPlace\n",
    "\n",
    "operation ArbitraryAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    let N = Length(a);\n",
    "    use internalCarries = Qubit[N];\n",
    "    LowestBitCarry(a[0], b[0], internalCarries[0]);\n",
    "    for i in 1 .. N - 1 {\n",
    "        HighBitCarry(a[i], b[i], internalCarries[i - 1], internalCarries[i]);\n",
    "    }\n",
    "    CNOT(internalCarries[N - 1], carry);\n",
    "\n",
    "    for i in N - 1 .. -1 .. 1 {\n",
    "        Adjoint HighBitCarry(a[i], b[i], internalCarries[i - 1], internalCarries[i]);\n",
    "        HighBitSumInPlace(a[i], b[i], internalCarries[i - 1]);\n",
    "    }\n",
    "    Adjoint LowestBitCarry(a[0], b[0], internalCarries[0]);\n",
    "    LowestBitSumInPlace(a[0], b[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.5 of the Ripple Carry Adder kata.](./RippleCarryAdder.ipynb#Task-2.5.-In-place-N-bit-adder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More solutions coming soon.."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.26"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}