RippleCarryAdder/RippleCarryAdder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ripple Carry Adder Kata\n",
    "\n",
    "The **Ripple Carry Adder** quantum kata is a series of exercises designed\n",
    "to get you familiar with ripple carry addition on a quantum computer.\n",
    "\n",
    "* The simplest quantum adder, covered in part I, closely mirrors its classical counterpart,\n",
    "using the same basic components and the same algorithm.\n",
    "* Part II explores building an in-place adder.\n",
    "* A more complex version of an in-place adder covered in part III of the kata uses a different algorithm\n",
    "to reduce the number of ancillary qubits needed.\n",
    "* Part IV covers building an in-place quantum subtractor.\n",
    "* Part V covers addition and subtraction modulo $2^N$.\n",
    "\n",
    "It is recommended to complete the [BasicGates kata](./../BasicGates/BasicGates.ipynb) before this one to get familiar with the basic gates used in quantum computing. The list of basic gates available in Q# can be found at [Microsoft.Quantum.Intrinsic](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic). For the syntax of flow control statements in Q#, see [Q# iterations](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/iterations) and [Q# conditional branching](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conditionalbranching) documentation.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with // ... comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_LowestBitSum\n",
    "\n",
    "operation LowestBitSum (a : Qubit, b : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_LowestBitCarry\n",
    "\n",
    "operation LowestBitCarry (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Ripple Carry Adder Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Ripple Carry Adder Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Don't forget that you can allocate extra qubits.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_LowestBitSumInPlace\n",
    "\n",
    "operation LowestBitSumInPlace (a : Qubit, b : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Can we re-use one of the input bits to calculate the carry in-place as well? Why or why not?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Think very carefully about the order in which you apply the operations.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_HighBitSumInPlace\n",
    "\n",
    "operation HighBitSumInPlace (a : Qubit, b : Qubit, carryin : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_TwoBitAdderInPlace\n",
    "\n",
    "operation TwoBitAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_ArbitraryAdderInPlace\n",
    "\n",
    "operation ArbitraryAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in [Ripple Carry Adder Workbook](./Workbook_RippleCarryAdder.ipynb#Task-2.5.-In-place-N-bit-adder)*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III*. Improved In-place Adder\n",
    "\n",
    "The in-place adder doesn't require quite as many qubits for the inputs and outputs, but it still requires an array of extra (\"ancillary\") qubits to perform the calculation.\n",
    "\n",
    "A relatively recent algorithm allows you to perform the same calculation using only one additional qubit.\n",
    "\n",
    "### Theory\n",
    "\n",
    "* [Paper on improved ripple carry addition](https://arxiv.org/pdf/quant-ph/0410184.pdf) by Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Majority gate\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 `c` in an arbitrary state $|\\omega\\rangle$.\n",
    "\n",
    "**Goal:** Construct the \"in-place majority\" gate:\n",
    "\n",
    "* Transform qubit `a` into the carry bit from the sum $\\phi + \\psi + \\omega$.\n",
    "* Transform qubit `b` into $|\\phi + \\psi\\rangle$.\n",
    "* Transform qubit `c` into $|\\phi + \\omega\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_Majority\n",
    "\n",
    "operation Majority (a : Qubit, b : Qubit, c : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. UnMajority and Add gate\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. qubit `a` storing the carry bit from the sum $\\phi + \\psi + \\omega$,\n",
    "  2. qubit `b` in state $|\\phi + \\psi\\rangle$,\n",
    "  3. qubit `c` in state $|\\phi + \\omega\\rangle$.\n",
    "\n",
    "**Goal:** Construct the \"un-majority and add\", or \"UMA\" gate:\n",
    "\n",
    "* Restore qubit `a` into state $|\\phi\\rangle$.\n",
    "* Transform qubit `b` into state $|\\phi + \\psi + \\omega\\rangle$.\n",
    "* Restore qubit `c` into state $|\\omega\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_UnMajorityAdd\n",
    "\n",
    "operation UnMajorityAdd (a : Qubit, b : Qubit, c : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.3. One-bit Majority-UMA 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",
    "**Goal:** Construct a one-bit binary adder from task 2.2 using Majority and UMA gates.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Allocate an extra qubit to hold the carry bit used in Majority and UMA gates during the computation. It's less efficient here, but it will be helpful for the next tasks.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T33_OneBitMajUmaAdder\n",
    "\n",
    "operation OneBitMajUmaAdder (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.4. Two-bit Majority-UMA 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",
    "**Goal:** Construct a two-bit binary adder from task 2.4 using Majority and UMA gates.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Think carefully about which qubits you need to pass to the two gates.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T34_TwoBitMajUmaAdder\n",
    "\n",
    "operation TwoBitMajUmaAdder (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.5. N-bit Majority-UMA 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",
    "**Goal:** Construct an N-bit binary adder from task 2.5 using only one ancillary qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T35_ArbitraryMajUmaAdder\n",
    "\n",
    "operation ArbitraryMajUmaAdder (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part IV*. In-place Subtractor\n",
    "\n",
    "Subtracting a number is the same operation as adding a negative number.\n",
    "As such, it's pretty easy to adapt the adder we just built to act as a subtractor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.1. N-bit Subtractor\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 `borrowBit` in state $|0\\rangle$.\n",
    "\n",
    "**Goal:** Construct an N-bit binary subtractor.\n",
    "\n",
    "* Transform register `b` into the state $|\\psi - \\phi\\rangle$.\n",
    "* Set qubit `borrowBit` to $|1\\rangle$ if that subtraction requires a borrow.\n",
    "* Leave register `a` unchanged.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Use the adder you already built. Experiment with inverting registers before and after the addition.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T41_Subtractor\n",
    "\n",
    "operation Subtractor (a : Qubit[], b : Qubit[], borrowBit : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part V*. Addition and subtraction modulo $2^N$\n",
    "\n",
    "In the previous parts we considered \"normal\" arithmetic, in which \n",
    "the sum of two numbers can have more bits than each of the summands.\n",
    "In these tasks we have used an extra qubit to store the \"carry\" or \"borrow\" bit (the most significant bit). \n",
    "If we want to perform our computation modulo $2^N$ instead, in classical computing \n",
    "we can easily discard this \"carry\" qubit and get the result modulo $2^N$ automatically. \n",
    "However, in quantum computing information cannot be erased that easily:\n",
    "this extra qubit is changed after the operation, and \"discarding\" it can affect the state of the other qubits. \n",
    "We need to modify the computation itself so that the last carry qubit is not involved at all.\n",
    "In this part we will learn to implement operations modulo $2^N$ which do either not use this extra qubit or uncompute it after use."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5.1. Adder modulo $2^N$\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 the state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "Transform the register `sum` into the state $|(\\phi + \\psi) \\mod 2^N\\rangle$.\n",
    "Leave registers `a` and `b` unchanged.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Consider task 1.7; can you reuse the same logic here? Which parts of that computation you don't need in this case?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T51_AdderModuloN\n",
    "\n",
    "operation AdderModuloN (a : Qubit[], b : Qubit[], sum : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5.2. Two's Complement\n",
    "\n",
    "**Input:**\n",
    "$N$-qubit register `a` in an arbitrary state $|\\phi\\rangle$.\n",
    "  \n",
    "**Goal:** Transform the register `a` into [two's complement](https://en.wikipedia.org/wiki/Two's_complement) of $\\phi$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T52_TwosComplement\n",
    "\n",
    "operation TwosComplement (a : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5.3. Subtractor modulo $2^N$\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 `diff` in the state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:** transform the register `diff` into the state $|(\\psi - \\phi) \\mod 2^N\\rangle$.\n",
    "Leave registers `a` and `b` unchanged.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    Can you use the previous two tasks as building blocks for this one?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T53_SubtractorModuloN\n",
    "\n",
    "operation SubtractorModuloN (a : Qubit[], b : Qubit[], diff : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5.4.  In-place adder modulo $2^N$\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",
    "\n",
    "**Goal:** Transform the register `b` into the state $|(\\phi + \\psi) \\mod 2^N\\rangle$.\n",
    "Leave register `a` unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T54_InPlaceAdderModuloN\n",
    "\n",
    "operation InPlaceAdderModuloN (a : Qubit[], b : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5.5  In-place subtractor modulo $2^N$\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",
    "\n",
    "**Goal:** Transform the register `b` into the state $|(\\psi - \\phi) \\mod 2^N\\rangle$.\n",
    "Leave register `a` unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T55_InPlaceSubtractorModuloN\n",
    "\n",
    "operation InPlaceSubtractorModuloN (a : Qubit[], b : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  }
 ],
 "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
}