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",
    "* Finally, part IV covers building an in-place quantum subtractor.\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 [the Q# documentation](https://docs.microsoft.com/quantum/language/statements#control-flow).\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.\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": [
    "To begin, first prepare this notebook for execution (if you skip the first step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells; if you skip the second step, you'll get \"Invalid kata name\" error):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.11.2004.2825"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%workspace reload"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation LowestBitSum (a : Qubit, b : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation LowestBitCarry (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation OneBitAdder (a : Qubit, b : Qubit, sum : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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 `carryout` 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_Test\n",
    "\n",
    "operation HighBitSum (a : Qubit, b : Qubit, carryin : Qubit, sum : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation HighBitCarry (a : Qubit, b : Qubit, carryin : Qubit, carryout : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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>Need a hint? Click here</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_Test\n",
    "\n",
    "operation TwoBitAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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-engian) 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_Test\n",
    "\n",
    "operation ArbitraryAdder (a : Qubit[], b : Qubit[], sum : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\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": [
    "### 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>Need a hint? Click here</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_Test\n",
    "\n",
    "operation OneBitAdderInPlace (a : Qubit, b : Qubit, carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation HighBitSumInPlace (a : Qubit, b : Qubit, carryin : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation TwoBitAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\n",
    "\n",
    "operation ArbitraryAdderInPlace (a : Qubit[], b : Qubit[], carry : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "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_Test\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_Test\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>Need a hint? Click here</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_Test\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>Need a hint? Click here</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_Test\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_Test\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 `borrow` 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 `borrow` to $|1\\rangle$ if that subtraction requires a borrow.\n",
    "* Leave register `a` unchanged.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary>Need a hint? Click here</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_Test\n",
    "\n",
    "operation Subtractor (a : Qubit[], b : Qubit[], borrow : 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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}