Superposition/Workbook_Superposition_Part2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Superposition Kata Workbook, Part 2\n",
    "\n",
    "The [Superposition Kata Workbook, Part 1](./Workbook_Superposition.ipynb) includes the solutions of kata tasks 1.1 - 1.7.  Part 2 continues the explanations for the rest of the tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"greenberger-horne-zeilinger\"></a> Task 1.8. Greenberger-Horne-Zellinger state.\n",
    "\n",
    "**Input:** $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state (stored in an array of length $N$).\n",
    "\n",
    "**Goal:**  Change the state of the qubits to the GHZ state $\\frac{1}{\\sqrt{2}} \\big (|0\\dots0\\rangle + |1\\dots1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The single-qubit GHZ state is the plus state $\\frac{1}{\\sqrt{2}} \\big (|0\\rangle + |1\\rangle\\big)$ that we've discussed in [task 1.1](./Workbook_Superposition.ipynb#plus-state). As a reminder, that state is prepared by applying a Hadamard gate.\n",
    "\n",
    "The 2-qubit GHZ state is the Bell state $\\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$ that we've discussed in [task 1.6](./Workbook_Superposition.ipynb#bell-state). That state can been prepared using the following circuit:\n",
    "\n",
    "<img src=\"./img/Task6HadamardCNOTCircuit.png\"/>\n",
    "\n",
    "The next one is the 3-qubit GHZ state:\n",
    "$$|GHZ\\rangle = \\frac{1}{\\sqrt{2}} \\big (|000\\rangle + |111\\rangle\\big)$$\n",
    "\n",
    "Let's use the 2-qubit circuit as a building block to construct the circuit for 3 qubits. First, let's add a third qubit to the above circuit:\n",
    "\n",
    "<img src=\"./img/Task8HadamardAnd3rdqubitircuit.png\"/>\n",
    "\n",
    "Comparing the state prepared by this circuit with the desired end state, we see that they differ only in the third (rightmost) qubit:\n",
    "\n",
    "$$|\\Phi^+\\rangle |0\\rangle = \\frac{1}{\\sqrt{2}} \\big (|000\\rangle + |11\\color{red}0\\rangle\\big)$$\n",
    "$$|GHZ\\rangle = \\frac{1}{\\sqrt{2}} \\big (|000\\rangle + |11\\color{red}1\\rangle\\big)$$\n",
    "\n",
    "\n",
    "Applying a controlled NOT operation using the first (leftmost) qubit as the control bit and the third (rightmost) qubit as the target qubit allows us to fix this difference: \n",
    "\n",
    "<table style=\"background-color: white; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=30%>\n",
    "    <col width=70%>\n",
    "        <td style=\"text-align:center; background-color:white; border:0\"><img src=\"./img/Task8HadamardAndCNOTCircuit.png\"/></td>\n",
    "        <td style=\"text-align:left; background-color:white; border:0\"><img src=\"./img/Task8CNOTFlip.png\"/></td>       \n",
    "</table>\n",
    "\n",
    "Similarly, the following circuit will prepare the GHZ state on four qubits $\\frac{1}{\\sqrt2} (|0000\\rangle + |1111\\rangle$:\n",
    "<img src=\"./img/Task84QubitCircuit.png\"/>\n",
    "\n",
    "Thus we can come to the general solution: apply Hadamard gate to the first qubit and do a series of CNOT gates with the first qubit as control and each of the other qubits as targets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T108_GHZ_State\n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation GHZ_State (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    \n",
    "    // Library function Rest returns all array elements except for the first one\n",
    "    for q in Rest(qs) {\n",
    "        CNOT(qs[0], q);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.8 of the Superposition kata.](./Superposition.ipynb#greenberger-horne-zeilinger)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-all-basis-vectors\"></a>  Task 1.9. Superposition of all basis vectors.\n",
    "\n",
    "**Input:** $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to an equal superposition of all basis vectors $\\frac{1}{\\sqrt{2^N}} \\big (|0 \\dots 0\\rangle + \\dots + |1 \\dots 1\\rangle\\big)$. \n",
    "\n",
    "> For example, for $N = 2$ the final state should be  $\\frac{1}{2} \\big (|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "As we've seen in [task 1.3](./Workbook_Superposition.ipynb#superposition-of-all-basis-vectors-on-two-qubits), to prepare a superposition of all basis vectors on 2 qubits we need to apply a Hadamard gate to each of the qubits.\n",
    "\n",
    "It seems that the solution for the general case might be to apply a Hadamard gate to every qubit as well. Let's check the first few examples:\n",
    "\n",
    "\\begin{align*}\n",
    "   H|0\\rangle &= \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big)\\\\\n",
    "   H|0\\rangle \\otimes H|0\\rangle &= \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)\\\\   \n",
    "               &= \\frac{1}{\\sqrt{2^2}}\\big(|00\\rangle + |01\\rangle+ |10\\rangle+ |11\\rangle\\big)\\\\\n",
    "   H|0\\rangle \\otimes H|0\\rangle \\otimes H|0\\rangle &= \\frac{1}{\\sqrt{2^2}}\\big(|00\\rangle + |01\\rangle+ |10\\rangle+ |11\\rangle\\big) \\otimes \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big)\\\\\n",
    "               &= \\frac{1}{\\sqrt{2^3}}\\big(|000\\rangle + |001\\rangle + |010\\rangle+ |100\\rangle+ |110\\rangle + |101\\rangle+ |011\\rangle+ |111\\rangle\\big)\\\\\n",
    "    \\underset{N}{\\underbrace{H|0\\rangle \\otimes \\dots \\otimes H|0\\rangle}} \n",
    "               &= \\frac{1}{\\sqrt{2^{N-1}}}  \\big( |\\underset{N-1}{\\underbrace{0 \\cdots 0}}\\rangle + \\cdots + |\\underset{N-1}{\\underbrace{1 \\cdots 1}}\\rangle \\big) \\otimes \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big) = \\\\\n",
    "               &= \\frac{1}{\\sqrt{2^N}} \\big( |\\underset{N}{\\underbrace{0 \\cdots 0}}\\rangle + \\cdots + |\\underset{N}{\\underbrace{1 \\cdots 1}}\\rangle \\big)\\\\    \n",
    "\\end{align*}\n",
    "\n",
    "Thus, the solution requires us to iterate over the qubit array and to apply the Hadamard gate to each element as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T109_AllBasisVectorsSuperposition\n",
    "\n",
    "operation AllBasisVectorsSuperposition (qs : Qubit[]) : Unit {\n",
    "    for q in qs {\n",
    "        H(q);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.9 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-basis-vectors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-all-even-or-all-odd-numbers\"></a>Task 1.10. Superposition of all even or all odd numbers.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state (stored in an array of length $N$).\n",
    "2. A boolean `isEven`.\n",
    "\n",
    "**Goal:**  Prepare a superposition of all *even* numbers if `isEven` is `true`, or of all *odd* numbers if `isEven` is `false`.  \n",
    "A basis state encodes an integer number using [big-endian](https://en.wikipedia.org/wiki/Endianness) binary notation: state $|01\\rangle$ corresponds to the integer $1$, and state $|10 \\rangle$ - to the integer $2$.  \n",
    "\n",
    "> For example, for $N = 2$ and `isEven = false` you need to prepare superposition $\\frac{1}{\\sqrt{2}} \\big (|01\\rangle + |11\\rangle\\big )$,  \n",
    "and for $N = 2$ and `isEven = true` - superposition $\\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |10\\rangle\\big )$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let’s look at some examples of basis states to illustrate the binary numbering system. \n",
    "\n",
    "The 4 basis states on $N = 2$ qubits can be split in two columns, where the left column represents the basis states that form the required superposition state for `isEven = false` and the right column - the basis states that form the required superposition state for `isEven = true`:\n",
    "\n",
    "<img src=\"./img/Task10_1.png\" width=\"400\">\n",
    " \n",
    "If we do the same basis state split for $N = 3$ qubits, the pattern becomes more obvious:\n",
    " \n",
    "<img src=\"./img/Task10_2.png\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The two leftmost qubits go through all possible basis states for `isEven = false` and for `isEven = true`, and the rightmost qubit stays in the $|1\\rangle$ state for `isEven = false` and in the $|0\\rangle$ state for `isEven = true`. \n",
    "\n",
    "A quick sanity check for $N = 4$ qubits re-confirms the pattern:\n",
    " \n",
    "<img src=\"./img/Task10_3.png\" width=\"400\">\n",
    " \n",
    "Again, the three leftmost qubits go through all possible basis states in both columns, and the rightmost qubit stays in the same state in each column. \n",
    "\n",
    "The solution is to put all qubits except the rightmost one into an equal superposition (similar to what we did in Task 9) and to set the rightmost qubit to $|0\\rangle$ or $|1\\rangle$ depending on the `isEven` flag, using the X operator to convert $|0\\rangle$ to $|1\\rangle$ if `isEven = false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T110_EvenOddNumbersSuperposition\n",
    "\n",
    "operation EvenOddNumbersSuperposition (qs : Qubit[], isEven : Bool) : Unit is Adj {\n",
    "    let N = Length(qs);\n",
    "    for i in 0 .. N-2 {\n",
    "        H(qs[i]);\n",
    "    }\n",
    "    // for odd numbers, flip the last bit to 1\n",
    "    if not isEven {\n",
    "        X(qs[N-1]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.10 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-even-or-all-odd-numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"superposition-of-zero-and-given-bit-string\"></a>Task 1.11. Superposition of $|0 \\dots 0\\rangle$ and the given bit string.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "2. A bit string of length $N$ represented as `Bool[]`. Bit values `false` and `true` correspond to $|0\\rangle$ and $|1\\rangle$ states. You are guaranteed that the first bit of the bit string is `true`.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to an equal superposition of $|0 \\dots 0\\rangle$ and the basis state given by the bit string.\n",
    "\n",
    "> For example, for the bit string `[true, false]` the state required is $\\frac{1}{\\sqrt{2}}\\big(|00\\rangle + |10\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> A common strategy for preparing a superposition state in a qubit register is using an auxiliary qubit (or several, for more complicated states). The auxiliary qubit can be put into a superposition state through the usual means of applying a Hadamard gate (or a rotation about the Y axis for an uneven superposition). \n",
    "> Then the basis states of the desired superposition are prepared individually based on the auxiliary qubit state by using it as the control qubit for a CNOT gate. One of the basis states will be prepared controlled on the $|0\\rangle$ component of the auxiliary state, and the other - controlled on the $|1\\rangle$ component. \n",
    "> Finally, you have to return the auxiliary qubit to the $|0\\rangle$ state by uncomputing it, i.e., by using the basis state prepared from the $|1\\rangle$ component as the control qubits for a CNOT gate with the auxiliary qubit as the target. \n",
    ">\n",
    "> More details on using this approach can be found in the solution to tasks [15](#superposition-of-four-bit-strings) and [16](#wstate-on-2k-qubits). However, for this task we can come up with a simpler solution. \n",
    "> Instead of allocating a new qubit to use as the auxiliary, we can use the first qubit in the register for this purpose, because we are guaranteed that the first bit in the two basis vectors that comprise the required superposition is different.\n",
    "> This saves us the need to allocate a new qubit and lets us skip the uncomputing step, as the qubit acting as the control for the next preparation steps is part of the desired result.\n",
    "\n",
    "Consider the earlier tasks in this kata that asked to prepare Bell states and GHZ state; the structure of the superposition state in this task is a more general case of those scenarios: all of them ask to prepare an equal superposition of two different basis states.\n",
    "\n",
    "The first step of the solution is the same as in those tasks: put the first qubit in the register into an equal superposition of $|0\\rangle$ and $|1\\rangle$ using the H gate to get the following state:\n",
    "\n",
    "$$\\frac{1}{\\sqrt2} (|0\\rangle + |1\\rangle) \\otimes |0 \\dots 0\\rangle = \\frac{1}{\\sqrt2} (|00 \\dots 0\\rangle + |10 \\dots 0\\rangle)$$\n",
    "\n",
    "The first term of the superposition already matches the desired state, so we need to fix the second term.\n",
    "To do that, we will walk through the remaining qubits in the register, checking if the bit in the corresponding position of the bit string `bits` is `true`. \n",
    "If it is, that qubit's state needs to be adjusted from $0$ to $1$ in the second term of our superposition (and left unchanged in the first term). \n",
    "We can do this change using the CNOT gate with the first qubit as the control and the current qubit as the target.\n",
    "When we have finished walking through the register like this, the register will be in the desired superposition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T111_ZeroAndBitstringSuperposition\n",
    "\n",
    "operation ZeroAndBitstringSuperposition (qs : Qubit[], bits : Bool[]) : Unit {\n",
    "    H(qs[0]);\n",
    "\n",
    "    for i in 1 .. Length(qs) - 1 {\n",
    "        if bits[i] {\n",
    "            CNOT(qs[0], qs[i]);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.11 of the Superposition kata.](./Superposition.ipynb#superposition-of-zero-and-given-bit-string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"superposition-of-two-bit-strings\"></a> Task 1.12. Superposition of two bit strings.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "2. Two bit strings of length $N$ represented as `Bool[]`s. Bit values `false` and `true` correspond to $|0\\rangle$ and $|1\\rangle$ states. You are guaranteed that the two bit strings differ in at least one bit.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to an equal superposition of the basis states given by the bit strings.\n",
    "\n",
    "> For example, for bit strings `[false, true, false]` and `[false, false, true]` the state required is $\\frac{1}{\\sqrt{2}}\\big(|010\\rangle + |001\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The strategy of using an auxiliary qubit to control the preparation process described in the previous task can be applied to this task as well. \n",
    "\n",
    "We will start by allocating an auxiliary qubit and preparing it in the $\\frac{1}{\\sqrt2} (|0\\rangle + |1\\rangle)$ state using the H gate. The overall state of the system will be \n",
    "\n",
    "$$\\frac{1}{\\sqrt2} (|0\\rangle + |1\\rangle)_a \\otimes |0 \\dots 0\\rangle_r = \\frac{1}{\\sqrt2} (|0\\rangle_a \\otimes |0 \\dots 0\\rangle_r + |1\\rangle_a \\otimes |0 \\dots 0\\rangle_r)$$\n",
    "\n",
    "At this point, we can prepare the two basis states of the target state separately, bit by bit, controlling the preparation of one of them on the $|0\\rangle$ state of the auxiliary qubit and the preparation of the other one - on the $|1\\rangle$ state. \n",
    "If a bit in one of the bit strings is `true`, we will apply a controlled X gate with the auxiliary qubit as control, the qubit in the corresponding position of the register as target, and control it on the $|0\\rangle$ or the $|1\\rangle$ state depending on which bit string we are considering at the moment. \n",
    "Such controlled gate can be implemented using [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) library function.\n",
    "\n",
    "After this the state of the system will be \n",
    "$$\\frac{1}{\\sqrt2} (|0\\rangle_a \\otimes |bits_1\\rangle_r + |1\\rangle_a \\otimes |bits_2\\rangle_r)$$\n",
    "\n",
    "Finally, we will uncompute the auxiliary qubit by using [`ControlledOnBitString`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) library function with the second bit string and the `X` operation as arguments, the quantum register as the control, and the auxiliary qubit as the target. \n",
    "This will affect only the $|1\\rangle_a \\otimes |bits_2\\rangle_r$ term, flipping the state of the auxiliary qubit in it and bringing the system to its final state:\n",
    "\n",
    "$$|0\\rangle_a \\otimes \\frac{1}{\\sqrt2} (|bits_1\\rangle + |bits_2\\rangle)_r$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T112_TwoBitstringSuperposition\n",
    "\n",
    "operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Unit {\n",
    "    use q = Qubit();\n",
    "    H(q);\n",
    "\n",
    "    for i in 0 .. Length(qs) - 1 {\n",
    "        if bits1[i] {\n",
    "            (ControlledOnInt(0, X))([q], qs[i]);\n",
    "        }\n",
    "        if bits2[i] {\n",
    "            (ControlledOnInt(1, X))([q], qs[i]);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // uncompute the auxiliary qubit to release it\n",
    "    (ControlledOnBitString(bits2, X))(qs, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to solve the task without using an extra qubit, if instead we use one of the qubits in the register in this role. \n",
    "While walking through the register and bit strings, the first time the bit strings disagreed, the qubit in the corresponding position would take on the role of the auxiliary qubit; we would put it in superposition using the H gate and perform all subsequent bit flips using that qubit as the control. \n",
    "\n",
    "This saves us an additional qubit and allows to skip the uncomputing step, though the code becomes less elegant. \n",
    "We will move the classical logic of comparing two bit strings to find the first position in which they differ to a function `FindFirstDiff`; note that it has to be defined in a separate code cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function FindFirstDiff (bits1 : Bool[], bits2 : Bool[]) : Int {\n",
    "    for i in 0 .. Length(bits1) - 1 {\n",
    "        if bits1[i] != bits2[i] {\n",
    "            return i;\n",
    "        }\n",
    "    }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T112_TwoBitstringSuperposition\n",
    "\n",
    "operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Unit {\n",
    "    // find the index of the first bit at which the bit strings are different\n",
    "    let firstDiff = FindFirstDiff(bits1, bits2);\n",
    "\n",
    "    // Hadamard corresponding qubit to create superposition\n",
    "    H(qs[firstDiff]);\n",
    "\n",
    "    // iterate through the bit strings again setting the final state of qubits\n",
    "    for i in 0 .. Length(qs) - 1 {\n",
    "        if bits1[i] == bits2[i] {\n",
    "            // if two bits are the same, apply X or nothing\n",
    "            if bits1[i] {\n",
    "                X(qs[i]);\n",
    "            }\n",
    "        } else {\n",
    "            // if two bits are different, set their difference using CNOT\n",
    "            if i > firstDiff {\n",
    "                CNOT(qs[firstDiff], qs[i]);\n",
    "                if bits1[i] != bits1[firstDiff] {\n",
    "                    X(qs[i]);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.12 of the Superposition kata.](./Superposition.ipynb#superposition-of-two-bit-strings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"superposition-of-four-bit-strings\"></a>Task 1.13*. Superposition of four bit strings.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "2. Four bit strings of length $N$, represented as `Bool[][]` `bits`. `bits` is an $4 \\times N$ array which describes the bit strings as follows: `bits[i]` describes the `i`-th bit string and has $N$ elements. You are guaranteed that all four bit strings will be distinct.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to an equal superposition of the four basis states given by the bit strings.\n",
    "\n",
    "> For example, for $N = 3$ and `bits = [[false, true, false], [true, false, false], [false, false, true], [true, true, false]]` the state required is $\\frac{1}{2}\\big(|010\\rangle + |100\\rangle + |001\\rangle + |110\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solutions\n",
    "#### Solution 1\n",
    "\n",
    "We are going to use the same trick of auxiliary qubits that we used in [the previous task](#superposition-of-two-bit-strings). \n",
    "Since the desired superposition has 4 basis states with equal amplitudes, we are going to need two qubits to define a unique basis to control preparation of each of the basis states in the superposition. \n",
    "\n",
    "We start by allocating two extra qubits and preparing an equal superposition of all 2-qubit states on them by applying an H gate to each of them:\n",
    "\n",
    "$$\\frac12 (|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle)_a \\otimes |0 \\dots 0\\rangle_r$$\n",
    "\n",
    "Then, for each of the four given bit strings, we walk through it and prepare the matching basis state on the main register of qubits, using controlled X gates with the corresponding basis state of the auxiliary qubits as control. \n",
    "For example, when preparing the bit string `bits[0]`, we apply X gates controlled on the basis state $|00\\rangle$; when preparing the bit string `bits[1]`, we apply X gates controlled on $|10\\rangle$, and so on.\n",
    "\n",
    "> We can choose an arbitrary matching of the 2-qubit basis states used as controls and the bit strings prepared on the main register. \n",
    "> Since all amplitudes are the same, the result does not depend on which state controlled which bit string preparation.\n",
    "> It can be convenient to use indices of the bit strings, converted to little-endian, to control preparation of the bit strings.\n",
    "> Q# library function [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) does exactly that.\n",
    "\n",
    "After this the system will be in the state \n",
    "\n",
    "$$\\frac12 (|00\\rangle_a |bits_0\\rangle_r + |10\\rangle_a |bits_1\\rangle_r + |01\\rangle_a |bits_2\\rangle_r + |11\\rangle_a |bits_3\\rangle_r)$$\n",
    "\n",
    "As the last step, we must uncompute the auxiliary qubits, i.e., return them to the $|00\\rangle$ state to unentangle them from the main register. \n",
    "Same as we did in the previous task, we will use [`ControlledOnBitString`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) with the corresponding bit string and the X operation as arguments, the quantum register as the control, and the auxiliary qubits as the target. \n",
    "We will uncompute each of them separately, so one of the auxiliary qubits will be uncomputed with the `bits[1]` and `bits[3]` bit strings as controls, and the other - with the `bits[2]` and `bits[3]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T113_FourBitstringSuperposition\n",
    "\n",
    "operation FourBitstringSuperposition (qs : Qubit[], bits : Bool[][]) : Unit {\n",
    "    use anc = Qubit[2];\n",
    "    // Put two ancillas into equal superposition of 2-qubit basis states\n",
    "    ApplyToEachA(H, anc);\n",
    "\n",
    "    // Set up the right pattern on the main qubits with control on ancillas\n",
    "    for i in 0 .. 3 {\n",
    "        for j in 0 .. Length(qs) - 1 {\n",
    "            if bits[i][j] {\n",
    "                (ControlledOnInt(i, X))(anc, qs[j]);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // Uncompute the ancillas, using patterns on main qubits as control\n",
    "    for i in 0 .. 3 {\n",
    "        if i % 2 == 1 {\n",
    "            (ControlledOnBitString(bits[i], X))(qs, anc[0]);\n",
    "        }\n",
    "        if i / 2 == 1 {\n",
    "            (ControlledOnBitString(bits[i], X))(qs, anc[1]);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution 2\n",
    "\n",
    "We are going to leverage the recursion abilities of Q# to create a superposition of the four bit strings.  This solution also extends to an arbitrary number of bit strings with no code changes.\n",
    "\n",
    "For this process we will look at the first bits of each string and adjust the probability of measuring a $|0\\rangle$ or $|1\\rangle$ accordingly on the first qubit of our answer.  We will then recursively call (as needed) the process again to adjust the probabilities of measurement on the second bit depending on the first bit.  This process recurses until no more input bits are provided.\n",
    "\n",
    "Consider for example the following four bit strings on which to create a superposition: \n",
    "$|001\\rangle, |101\\rangle, |111\\rangle, |110\\rangle$.\n",
    "\n",
    "We can rewrite the superposition state we need to prepare as\n",
    "\n",
    "$$\\frac12 \\big(|001\\rangle + |101\\rangle + |111\\rangle + |110\\rangle \\big) = \\frac12 |0\\rangle \\otimes |01\\rangle + \\frac{\\sqrt3}{2} |1\\rangle \\otimes \\frac{1}{\\sqrt3} \\big(|10\\rangle + |11\\rangle + |10\\rangle \\big)$$\n",
    "\n",
    "As the first step of the solution, we need to prepare a state $\\frac12 |0\\rangle + \\frac{\\sqrt3}{2} |1\\rangle$ on the first qubit (to measure $|0\\rangle$ with $\\frac14$ probability and to measure $|1\\rangle$ with $\\frac34$ probability).  To do this, we will apply an [`Ry`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation to the first qubit.\n",
    "\n",
    "After this, we'll need to prepare the rest of the qubits in appropriate states depending on the state of the first qubit - state $|01\\rangle$ if the first qubit is in state $|0\\rangle$ and state $\\frac{1}{\\sqrt3} \\big(|10\\rangle + |11\\rangle + |10\\rangle \\big)$ if the first qubit is in state $|1\\rangle$. We can do this recursively using the same logic. Let's finish walking through this example in detail.\n",
    "\n",
    "The second qubit of the recursion follows similarly but depends on the first qubit.  If the first qubit measures $|0\\rangle$, then we want the second qubit to measure $|0\\rangle$ with 100% probability, but if it measures $|1\\rangle$, we want it to measure $|0\\rangle$ with $\\frac13$ probability and $|1\\rangle$ with $\\frac23$ probability.  For this, we can do a controlled [`Ry`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation on the second qubit with the first qubit as control.\n",
    "\n",
    "The third qubit in this example will have three cases because it depends on the first two qubits; this follows naturally from the recursion.\n",
    "\n",
    "1. If the first two qubits measure $|00\\rangle$, then we need the third qubit to measure $|0\\rangle$ with 100% probability.  \n",
    "2. If the first two qubits measure $|10\\rangle$, then we need the third qubit to measure $|1\\rangle$ with 100% probability.  \n",
    "3. If the first two qubits measure $|11\\rangle$, then we need the third qubit to measure $|0\\rangle$ with $\\frac12$ probability and $|1\\rangle$ with $\\frac12$ probability.  Just as with the second qubit, a controlled [`Ry`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation on the third qubit will accomplish this goal.  \n",
    "\n",
    "> We will use [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) operation to perform rotations depending on the state of several previous qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T113_FourBitstringSuperposition\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation FourBitstringSuperposition (qs : Qubit[], bits : Bool[][]) : Unit {\n",
    "    FourBitstringSuperposition_Recursive([], qs, bits);\n",
    "}\n",
    "\n",
    "operation FourBitstringSuperposition_Recursive (currentBitString : Bool[], qs : Qubit[], bits : Bool[][]) : Unit {\n",
    "    // an array of bit strings whose columns we are considering begin with |0⟩\n",
    "    mutable zeroLeads = [];\n",
    "    // an array of bit strings whose columns we are considering begin with |1⟩\n",
    "    mutable oneLeads = [];\n",
    "    // the number of bit strings we're considering\n",
    "    let rows = Length(bits);\n",
    "    // the current position we're considering\n",
    "    let currentIndex = Length(currentBitString);\n",
    "    \n",
    "    if rows >= 1 and currentIndex < Length(qs) {\n",
    "        // figure out what percentage of the bits should be |0⟩\n",
    "        for row in 0 .. rows - 1 {\n",
    "            if bits[row][currentIndex] {\n",
    "                set oneLeads = oneLeads + [bits[row]];\n",
    "            } else {\n",
    "                set zeroLeads = zeroLeads + [bits[row]];\n",
    "            }\n",
    "        }       \n",
    "        // rotate the qubit to adjust coefficients based on the previous bit string\n",
    "        // for the first path through, when the bit string has zero length, \n",
    "        // the Controlled version of the rotation will perform a regular rotation\n",
    "        let theta = ArcCos(Sqrt(IntAsDouble(Length(zeroLeads)) / IntAsDouble(rows)));\n",
    "        (ControlledOnBitString(currentBitString, Ry))(qs[0 .. currentIndex - 1], \n",
    "                                                      (2.0 * theta, qs[currentIndex]));\n",
    "        \n",
    "        // call state preparation recursively based on the bit strings so far\n",
    "        FourBitstringSuperposition_Recursive(currentBitString + [false], qs, zeroLeads);\n",
    "        FourBitstringSuperposition_Recursive(currentBitString + [true], qs, oneLeads);\n",
    "    } \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.13 of the Superposition kata.](./Superposition.ipynb#superposition-of-four-bit-strings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"superposition-of-all-strings-with-parity\"></a>Task 1.14. Superposition of all bit strings of the given parity.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ ($N \\ge 1$) qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "2. An `Int` `parity`.\n",
    "\n",
    "**Goal:**  change the state to an equal superposition of all basis states that have\n",
    "* an even number of 1s in them if `parity = 0`, or\n",
    "* an odd number of 1s in them if `parity = 1`.\n",
    "\n",
    "> For example, for $N = 2$ the required state is $\\frac{1}{\\sqrt{2}}\\big(|00\\rangle + |11\\rangle\\big)$ if `parity = 0`, or $\\frac{1}{\\sqrt{2}}\\big(|01\\rangle + |10\\rangle\\big)$ if `parity = 1`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We are going to use a recursive approach that was hinted at in the task.\n",
    "\n",
    "Let's denote the required state on $N$ qubits as $|P_{N,0}\\rangle$ for `parity = 0` and $|P_{N,1}\\rangle$ for `parity = 1`. We can group the $2^{N-1}$ basis states included in the state $|P_{N,0}\\rangle$ by their first bit ($0$ or $1$) and write the state as follows:\n",
    "\n",
    "$$|P_{N,0}\\rangle = \\frac{1}{\\sqrt{2^{N-1}}} \\sum_{k : k \\text{ has parity }0} |k\\rangle_N = \\\\\n",
    "= \\frac{1}{\\sqrt{2^{N-1}}} \\big( |0\\rangle \\otimes \\sum_{k' : k' \\text{ has parity }0} |k'\\rangle_{N-1} + |1\\rangle \\otimes \\sum_{k'' : k'' \\text{ has parity }1} |k''\\rangle_{N-1} \\big) = \\\\ \n",
    "= \\frac{1}{\\sqrt{2}} \\big( |0\\rangle \\otimes |P_{N-1,0}\\rangle + |1\\rangle \\otimes |P_{N-1,1}\\rangle \\big)$$\n",
    "\n",
    "We can consider the expression for $|P_{N,1}\\rangle$ in a similar manner, and get a unified expression for both states:\n",
    "\n",
    "$$|P_{N,p}\\rangle = \\frac{1}{\\sqrt{2}} \\big( |0\\rangle \\otimes |P_{N-1,p}\\rangle + |1\\rangle \\otimes |P_{N-1,1-p}\\rangle \\big)$$\n",
    "\n",
    "Now we can use this expression to prepare the state using a recursive approach we've seen before:\n",
    "\n",
    "1. Apply **H** gate to the first qubit to prepare state $\\frac{1}{\\sqrt{2}} ( |0\\rangle + |1\\rangle ) \\otimes |0\\rangle_{N-1}$.\n",
    "2. Apply the controlled variant of procedure of preparing $|P_{N-1,p}\\rangle$ on the last $N-1$ qubits, with the first qubit in the $|0\\rangle$ state as the control.\n",
    "3. Apply the controlled variant of procedure of preparing $|P_{N-1,1-p}\\rangle$ on the last $N-1$ qubits, with the first qubit in the $|1\\rangle$ state as the control.  \n",
    "> Q# library function [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) allows to do that easily; you'll need to modify the signature of the operation you're given to include `is Adj+Ctl`, so that adjoint and controlled variants of the operation are defined automatically.\n",
    "4. The base of recursion is preparing the states for $N = 1$:\n",
    "  * For `parity = 0`, there is one single-qubit state with this parity: $|0\\rangle$ (no action required to prepare).\n",
    "  * For `parity = 1`, there is one single-qubit state with this parity: $|1\\rangle$ (apply **X** gate to prepare)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T114_AllStatesWithParitySuperposition\n",
    "\n",
    "operation AllStatesWithParitySuperposition (qs : Qubit[], parity : Int) : Unit is Adj+Ctl {\n",
    "    // base of recursion: if N = 1, set the qubit to parity\n",
    "    let N = Length(qs);\n",
    "    if N == 1 {\n",
    "        if parity == 1 {\n",
    "            X(qs[0]);\n",
    "        }\n",
    "    } else {\n",
    "        // split the first qubit into 0 and 1 (with equal amplitudes!)\n",
    "        H(qs[0]);\n",
    "        // prep 0 ⊗ state with the same parity and 1 ⊗ state with the opposite parity\n",
    "        (ControlledOnInt(0, AllStatesWithParitySuperposition))(qs[0 .. 0], (qs[1 ...], parity));\n",
    "        (ControlledOnInt(1, AllStatesWithParitySuperposition))(qs[0 .. 0], (qs[1 ...], 1 - parity));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 2\n",
    "\n",
    "\n",
    "We start by preparing an equal superposition of all basis states and allocating an extra qubit.\n",
    "\n",
    "This time we use the extra qubit to calculate the parity of the input state: applying a series of CNOT gates, each one with one of the input qubits as control and the extra qubit as a target\n",
    "will compute the parity of the state. \n",
    "\n",
    "Now we measure the extra qubit: if the measurement result matches our parity, we're done — the input qubits collapsed to an equal superposition of all states that have this parity. \n",
    "If the measurement result is the opposite, we can retry the whole process.\n",
    "\n",
    "We can avoid retrying the state preparation if our measurement result doesn't match the required parity: \n",
    "notice that applying an X gate to any one of the qubits changes the parity of each basis state to the opposite one, and thus converts the state we got to the state we need."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T114_AllStatesWithParitySuperposition\n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation AllStatesWithParitySuperposition (qs : Qubit[], parity : Int) : Unit {\n",
    "    use aux = Qubit();\n",
    "    ApplyToEach(H, qs);\n",
    "    ApplyToEach(CNOT(_, aux), qs);\n",
    "    let res = M(aux);\n",
    "    if ((res == Zero ? 0 | 1) != parity) {\n",
    "        X(qs[0]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 3\n",
    "\n",
    "Yet another way of getting the desired superposition could be preparing the mix of all possible basis states for all qubits iteratively, keeping the parity on each step.\n",
    "\n",
    "We start by preparing a superposition of all basis states with parity $0$.\n",
    "To achieve that, we loop through all the qubits except the first one and prepare all of them in equal superposition.\n",
    "In order to maintain the parity of the basis states involved, we use the first qubit and conditionally flip its state using a CNOT gate with each next qubit as the control, so that every time there is a $|1\\rangle$ state in the chain,\n",
    "we get back to an even number of $|1\\rangle$ states in that basis state. \n",
    "\n",
    "For example, after the first loop iteration we get the state $\\frac12(|00\\rangle + |11\\rangle)$.\n",
    "After the second iteration we get the state \n",
    "\n",
    "$$CNOT_{2,0} \\frac1{\\sqrt2}(|00\\rangle + |11\\rangle) \\otimes \\frac1{\\sqrt2}(|0\\rangle + |1\\rangle) = \\\\\n",
    "= CNOT_{2,0} \\frac12(|000\\rangle + |\\color{red}00\\color{red}1\\rangle + |110\\rangle + |\\color{red}11\\color{red}1\\rangle) = \\\\\n",
    "= \\frac12(|000\\rangle + |101\\rangle + |110\\rangle + |011\\rangle)$$\n",
    "\n",
    "After the loop we will have a superposition of all possible basis states with even number of $|1\\rangle$s. \n",
    "Then, if `parity` is equal to 1 and we want an odd number of $|1\\rangle$s, we just flip the state of the first qubit again (or any qubit).\n",
    "\n",
    "For example, if the input has 3 qubits, after the for loop we will have a superposition of 4 basis states:\n",
    "\n",
    "$$\\frac12(|000\\rangle + |101\\rangle + |110\\rangle + |011\\rangle)$$\n",
    "\n",
    "If `parity = 0`, we are done, having even numbers of $|1\\rangle$s. If `parity = 1`, we flip the state of the first qubit, getting the desired result:\n",
    "\n",
    "$$\\frac12(|100\\rangle + |001\\rangle + |010\\rangle + |111\\rangle)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T114_AllStatesWithParitySuperposition\n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation AllStatesWithParitySuperposition (qs : Qubit[], parity : Int) : Unit {\n",
    "    for i in 1 .. Length(qs) - 1 {\n",
    "        H(qs[i]);\n",
    "        CNOT(qs[i], qs[0]);\n",
    "    }\n",
    "\n",
    "    if parity == 1 {\n",
    "        X(qs[0]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.14 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-strings-with-parity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part  II. Arbitrary rotations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"unequal-superposition\"></a>  Task 2.1. Unequal superposition.\n",
    "\n",
    "**Input:** \n",
    "\n",
    "1. A qubit in the $|0\\rangle$ state.\n",
    "2. Angle $\\alpha$, in radians, represented as `Double`.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $\\cos\\alpha|0\\rangle$ + $\\sin\\alpha|1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "<table style=\"background-color: white; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=130>\n",
    "    <col width=300>\n",
    "    <col width=130>\n",
    "    <col width=230>\n",
    "        <td style=\"text-align:center; font-bold; font-size: 14px; background-color:white; border:0\">We want to move from the starting state</td>\n",
    "        <td style=\"text-align:center; background-color:white; border:0\"><img src=\"./img/Task3UnitcircleStart.png\"/></td>\n",
    "        <td style=\"text-align:center; font-bold; font-size: 14px; background-color:white; border:0\">To the desired final state</td>\n",
    "        <td style=\"text-align:center; background-color:white; border:0\"><img src=\"./img/Task3UnitcircleFinal.png\"/></td>       \n",
    " </table>\n",
    "In other words, we are looking for some kind of a rotation operation. There are three special gates that implement rotations around various axis of the Bloch Sphere: \n",
    "\n",
    "<table style=\"background-color: white; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <col width=250>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_x(\\theta) = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -i\\sin\\frac{\\theta}{2} \\\\ -i\\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_y(\\theta) = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_z(\\theta) = \\begin{bmatrix} e^{-i\\theta/2} & 0 \\\\ 0 & e^{i\\theta/2} \\end{bmatrix}$</td>\n",
    "      </tr>    \n",
    "</table>\n",
    "\n",
    "If we were to apply the $R_x$ gate to a qubit in the $|0\\rangle$ state, we would introduce complex coefficients to the amplitudes, which is clearly not what we're looking for. Similarly, the $R_z$ gate introduces only a global phase when applied to $|0\\rangle$ state, so we can rule it out as well. This leaves only the $R_y$ as a starting point for the solution.\n",
    "\n",
    "Applying the $R_y$ gate to the $|0\\rangle$ state, we get:\n",
    "$$R_y(\\theta) |0\\rangle = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix} \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} \\cos\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} \\end{bmatrix} = \\cos\\frac{\\theta}{2}|0\\rangle + \\sin\\frac{\\theta}{2}|1\\rangle$$\n",
    "\n",
    "Therefore, applying the $R_y(2\\alpha$) gate to $|0\\rangle$ is the solution to our problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> <table style=\"background-color: white; font-size: 14px; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=600>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; background-color:white; border:0\">\n",
    "Let us have a look at the Bloch sphere to obtain a geometrical interpretation of the operation.\n",
    "<br/><br/>\n",
    "The X-Z plane has no complex numbers, i.e. for qubit states that fall on it the amplitudes for both $|0\\rangle$ and $|1\\rangle$ basis states will always be real. We can see that the $R_y$ gate, which rotates the qubit state around the Y axis, keeps it within the X-Z plane. \n",
    "<br/><br/> \n",
    "Looking at the other two gates, $R_x$ gate rotates the qubit state around the X axis and thus takes the qubit state out of the X-Z plane, introducing complex coefficients. $R_z$ gate rotates the qubit state around the Z axis, so it doesn't modify the $|0\\rangle$ state which lies on the Z axis.\n",
    "<br/><br/> \n",
    "In case you are surprised to see the $|0\\rangle$ and $|1\\rangle$ vectors 180 degrees apart from each other, the Bloch sphere represents orthogonal vectors as opposite points on the sphere.  \n",
    "You can learn more about the Bloch sphere in <a href=\"https://web.cecs.pdx.edu/~mperkows/june2007/bloch-sphere.pdf\">this presentation</a>.</td>\n",
    "        <td style=\"text-align:center; font-size: 14px; background-color:white; border:0\"><img src=\"./img/blochsphere.png\"/></td> \n",
    "      </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Q#, $R_y$ gate is represented as [Ry](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) operation. Note that you have to apply $R_y(2\\alpha)$, not $R_y(\\alpha)$; Q# does not have implicit type casting from `Int` to `Double`, so you have to calculate the angle parameter of the operation as `2.0 * alpha`, using a double constant 2.0 instead of an integer 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T201_UnequalSuperposition \n",
    "\n",
    "operation UnequalSuperposition (q : Qubit, alpha : Double) : Unit {\n",
    "    Ry(2.0 * alpha, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the Superposition kata.](./Superposition.ipynb#unequal-superposition)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"controlled-split\"></a>  Task 2.2. $\\frac{1}{\\sqrt{2}}|00\\rangle+\\frac{1}{2}|10\\rangle+\\frac{1}{2}|11\\rangle$ state. \n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state.\n",
    "\n",
    "**Goal**: Change the state of the qubits to $\\frac{1}{\\sqrt{2}}|00\\rangle+\\frac{1}{2}|10\\rangle+\\frac{1}{2}|11\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We will start by putting the first qubit in the state $\\alpha|0\\rangle + \\beta|1\\rangle$, where $\\alpha$ and $\\beta$ are the square roots of relative weights of all basis states which start with 0 and with 1, respectively.  \n",
    "\n",
    "In this case, our state can be represented as $\\frac{1}{\\sqrt{2}} \\big( |0\\rangle \\otimes |0\\rangle + |1\\rangle \\otimes \\frac{1}{\\sqrt2}(|0\\rangle+|1\\rangle) \\big)$.\n",
    "\n",
    "We see that the relative weights of $|0\\rangle$ and $|1\\rangle$ states of the first qubit are both $\\frac12$ (the squares of their amplitudes in the decomposition above). This means that we can do the first step by applying the $H$ gate to the first qubit, which gives the $\\frac{1}{\\sqrt{2}}|00\\rangle + \\frac{1}{\\sqrt{2}}|10\\rangle$ state. In matrix form this will look as follows:  \n",
    "\n",
    "$$ H \\otimes I = \\frac{1}{\\sqrt{2}} \\begin{bmatrix}1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & -1 & 0 \\\\ 0 & 1 & 0 & -1 \\end{bmatrix} \\cdot\n",
    "\\begin{bmatrix}1 \\\\ 0 \\\\0 \\\\ 0 \\end{bmatrix} = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 \\\\ 0 \\\\ 1 \\\\0 \\end{bmatrix} = \\frac{1}{\\sqrt{2}} \\big( |0\\rangle + |1\\rangle \\big) \\otimes |0\\rangle$$\n",
    "\n",
    "Now the first term of the state $\\frac{1}{\\sqrt2}|00\\rangle$ matches that of the goal state, and we need to convert the second term $\\frac{1}{\\sqrt2}|10\\rangle$ to $|1\\rangle \\otimes \\frac{1}{\\sqrt2}(|0\\rangle+|1\\rangle)$.\n",
    "\n",
    "To do this, we use the controlled $H$ gate. The matrix representation of the controlled H gate is similar to the $CNOT$ gate, however the bottom right quarter of the matrix is not an $X$ gate but the $H$ gate:\n",
    "\n",
    "$$\\text{Controlled } H = \\begin{bmatrix}1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ 0 & 0 & \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix}$$\n",
    "\n",
    "When this is applied to our current state, we get our goal state:\n",
    "\n",
    "$$\\text{Controlled } H \\cdot \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 \\\\ 0 \\\\ 1 \\\\0 \\end{bmatrix} = \\begin{bmatrix}\\frac{1}{\\sqrt{2}} \\\\ 0 \\\\ \\frac{1}{2} \\\\ \\frac{1}{2} \\end{bmatrix} = \\frac{1}{\\sqrt{2}}|00\\rangle+\\frac{1}{2}|10\\rangle+\\frac{1}{2}|11\\rangle  $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T202_ControlledRotation \n",
    "\n",
    "operation ControlledRotation (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    Controlled H ([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the Superposition kata.](./Superposition.ipynb#controlled-split)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"threestates-twoqubits\"></a>Task 2.3*. $\\frac{1}{\\sqrt{3}} \\big(|00\\rangle + |01\\rangle + |10\\rangle\\big)$ state.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to $\\frac{1}{\\sqrt{3}} \\big(|00\\rangle + |01\\rangle + |10\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "There are multiple ways to prepare this state; the solution described below will focus on preparing this state without using arbitrary rotation gates. \n",
    "\n",
    "Initially we will prepare an equal superposition of all basis states on the two starting qubits by applying the **H** gate to each of them: \n",
    "$$\\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$$\n",
    "\n",
    "This state is a superposition of the state we want to prepare, and the $|11\\rangle$ state that we would like to discard. \n",
    "We can do exactly that by performing the right measurement on the system. To do this, we allocate an extra qubit (sometimes referred to as an *ancilla* qubit). With this extra qubit the new state becomes: \n",
    "$$\\frac{1}{2} \\big(|00\\textbf{0}\\rangle + |01\\textbf{0}\\rangle + |10\\textbf{0}\\rangle + |11\\textbf{0}\\rangle\\big)$$\n",
    "\n",
    "Now, we want to separate the first three basis states from the last one and to store this separation in the extra qubit. \n",
    "For example, we can keep the state of the extra qubit $|0\\rangle$ for the basis states that we want to keep, and switch it to $|1\\rangle$ for the basis states that we would like to discard. \n",
    "A **CCNOT** gate can be used to accomplish this, with the first two qubits used as control qubits and the extra qubit as target. \n",
    "When the gate is applied, the state of the extra qubit will only change to $|1\\rangle$ if both control qubits are in the $|11\\rangle$ state, which marks exactly the state that we want to discard:\n",
    "\n",
    "$$\\text{CCNOT}\\frac{1}{2} \\big(|00\\textbf{0}\\rangle + |01\\textbf{0}\\rangle + |10\\textbf{0}\\rangle + |11\\textbf{0}\\rangle\\big) = \n",
    "\\frac{1}{2}\\big(|00\\rangle + |01\\rangle + |10\\rangle \\big) \\otimes |\\textbf{0}\\rangle + \\frac{1}{2}|11\\rangle \\otimes |\\textbf{1}\\rangle $$\n",
    "\n",
    "Finally we measure just the extra qubit; this causes a partial collapse of the system to the state defined by the measurement result:\n",
    "* If the result is $|0\\rangle$, the system collapses to a state that is a linear combination of basis states which had the extra qubit in state $|0\\rangle$, i.e., the two qubits end up in the target state $\\frac{1}{\\sqrt3}\\big(|00\\rangle + |01\\rangle + |10\\rangle\\big)$. \n",
    "* If the result is $|1\\rangle$, the system collapses to a state $|11\\rangle$, so our goal is not achieved. The good thing is, this only happens in 25% of the cases, and we can just reset our qubits to the $|00\\rangle$ state and try again.\n",
    "\n",
    "> Q# has a built-in [repeat-until-success (RUS) loop](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conditionalloops#repeat-statement), which comes in handy in this case. \n",
    "> * We will describe the main operations (applying **H** and **CCNOT** gates and the measurement) in the `repeat` part of the loop, which specifies its body.  \n",
    "> * `until` section specifies the condition which will break the loop. In this case the result of the measurement needs to be `Zero` to indicate our success.  \n",
    "> * Finally, the `fixup` section allows us to clean up the results of the loop body execution before trying again if the success criteria is not met. In this case we reset the first two qubits back to the $|00\\rangle$ state.\n",
    "\n",
    "This technique is sometimes called post-selection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%kata T203_ThreeStates_TwoQubits\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation ThreeStates_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    // Initialize the extra qubit\n",
    "    use anc = Qubit();\n",
    "    // Using the repeat-until-success pattern to prepare the right state\n",
    "    repeat {\n",
    "        ApplyToEach(H, qs);\n",
    "        Controlled X(qs, anc);\n",
    "        let res = MResetZ(anc);\n",
    "    } \n",
    "    until (res == Zero)\n",
    "    fixup {\n",
    "        ResetAll(qs);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, this state can be prepared using arbitrary rotations (the **Ry** gate). \n",
    "\n",
    "To start, we will try to find a decomposition of the target state that makes it easier to see how to prepare the state.  \n",
    "Knowing that $|+\\rangle = \\frac{1}{\\sqrt{2}}\\big(|0\\rangle+|1\\rangle\\big)$, we can represent the state as follows:\n",
    "\n",
    "$$ \\frac{1}{\\sqrt{3}} \\big(|00\\rangle + |01\\rangle + |10\\rangle\\big) = \\frac{\\sqrt{2}}{\\sqrt{3}}|0\\rangle \\otimes |+\\rangle + \\frac{1}{\\sqrt{3}}|1\\rangle \\otimes |0\\rangle $$ \n",
    "\n",
    "To prepare this state, we first want to prepare the first qubit in the state $ \\frac{\\sqrt{2}}{\\sqrt{3}}|0\\rangle + \\frac{1}{\\sqrt{3}}|1\\rangle $, while leaving the second qubit unchanged. \n",
    "To do this we can use the [$Ry$](../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates) gate which  will perform the following transformation:\n",
    "$$ Ry|0\\rangle = \\cos\\frac{\\theta}{2}|0\\rangle + \\sin\\frac{\\theta}{2}|1\\rangle $$\n",
    "We need to find a value of $\\theta$ which satisfies both: \n",
    "$$\\cos\\frac{\\theta}{2} = \\frac{\\sqrt{2}}{\\sqrt{3}} \\text{ and } \\sin\\frac{\\theta}{2} = \\frac{1}{\\sqrt{3}}$$\n",
    "\n",
    "Solving the last equation for $\\theta$ gives us $\\frac{\\theta}{2} = \\arcsin\\frac{1}{\\sqrt{3}}$, or $\\theta = 2 \\arcsin\\frac{1}{\\sqrt{3}}$.\n",
    "\n",
    "When we apply this to our first qubit, we will get our desired intermediary state:\n",
    "$$ \\big(Ry(2 \\arcsin\\frac{1}{\\sqrt{3}})|0\\rangle \\big) \\otimes |0\\rangle = \n",
    "\\big(\\frac{\\sqrt{2}}{\\sqrt{3}}|0\\rangle + \\frac{1}{\\sqrt{3}}|1\\rangle \\big) \\otimes |0\\rangle = \n",
    "\\frac{\\sqrt{2}}{\\sqrt{3}}|0\\rangle \\otimes |0\\rangle + \\frac{1}{\\sqrt{3}}|1\\rangle \\otimes |0\\rangle$$\n",
    "\n",
    "Now, the second term of this state already matches our final goal, so we need to adjust the first term: \n",
    "prepare the $|+\\rangle$ state on the second qubit only if the first qubit is in the $|0\\rangle$ state. \n",
    "To do this, we apply a conditional $H$ gate to the second qubit, if the first qubit is in the $|0\\rangle$ state, this will give our desired state:\n",
    "$$ \\frac{\\sqrt{2}}{\\sqrt{3}}|0\\rangle \\otimes |+\\rangle + \\frac{1}{\\sqrt{3}}|1\\rangle \\otimes |0\\rangle$$\n",
    "\n",
    "> In Q# we can apply a conditional gate with arbitrary controls using the [`ControlledOnInt` function](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint). \n",
    "> In this case we want the **H** gate to be applied if the control qubit is in the $|0\\rangle$ state, so we will use `ControlledOnInt(0, H)` gate.\n",
    "\n",
    "*This solution is based on [Niel's answer at QuantumComputing Stack Exchange](https://quantumcomputing.stackexchange.com/a/2313/).*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%kata T203_ThreeStates_TwoQubits\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation ThreeStates_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    // Rotate first qubit to (sqrt(2) |0⟩ + |1⟩) / sqrt(3) (task 1.4 from BasicGates kata)\n",
    "    let theta = ArcSin(1.0 / Sqrt(3.0));\n",
    "    Ry(2.0 * theta, qs[0]);\n",
    "\n",
    "    // Split the state sqrt(2) |0⟩ ⊗ |0⟩ into |00⟩ + |01⟩\n",
    "    (ControlledOnInt(0, H))([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the Superposition kata.](./Superposition.ipynb#threestates-twoqubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"three-states-two-qubits-phases\"></a>Task 2.4*. $\\frac{1}{\\sqrt{3}} \\big( |00\\rangle + \\omega |01\\rangle + \\omega^2 |10\\rangle \\big)$. \n",
    "\n",
    "**Input:** Two qubits in $|0\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Output:** Create the following state on these qubits:$\\frac{1}{\\sqrt{3}} \\big( |00\\rangle + \\omega |01\\rangle + \\omega^2 |10\\rangle \\big)$ where $\\omega = e^{2\\pi i/3}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "To start, we will prepare the $\\frac{1}{\\sqrt{3}} \\big( |00\\rangle +  |01\\rangle + |10\\rangle \\big)$ state using the [solution to task 2.3](#threestates-twoqubits). To get to the final state, we need to add the relative phases to both $|01\\rangle$ and $|10\\rangle$ basis states without changing the $|00\\rangle$ state.\n",
    "\n",
    "First, we want to transform the $|01\\rangle$ state to the $\\omega |01\\rangle = e^{2\\pi i/3} |01\\rangle$ state, while not changing the other states. \n",
    "Using the [$R_1$](../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates) gate, we can change a qubit state from $|1\\rangle$ to $e^{i\\theta}|1\\rangle$ without changing the $|0\\rangle$ state. \n",
    "Indeed, here is the effect of the $R_1$ gate on the $|0\\rangle$ and the $|1\\rangle$ states:\n",
    "\n",
    "$$ R_1 |0\\rangle = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i\\theta} \\end{bmatrix} \\cdot \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} = |0\\rangle $$\n",
    "\n",
    "$$ R_1 |1\\rangle = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i\\theta} \\end{bmatrix} \\cdot \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix} = \\begin{bmatrix} 0 \\\\ e^{i\\theta} \\end{bmatrix} = e^{i\\theta}|1\\rangle $$\n",
    " \n",
    "When we apply the $R_1$ gate to the second qubit, this will only affect the $|01\\rangle$ term, which is exactly what we want. Knowing this, we just need the right value for $\\theta$, which in this case is $\\frac{2\\pi}{3}$.  \n",
    "\n",
    "We use the same approach to change $|10\\rangle$ term to $\\omega^2 |10\\rangle$. By applying the $R_1$ gate to the first qubit we will only change the $|10\\rangle$ term. In this case the right $\\theta$ will be $\\frac{4\\pi}{3}$.\n",
    "\n",
    "> If you get the `No identifier with the name \"ThreeStates_TwoQubits\" exists` error, you need to run the code cell with the [solution to task 2.3](#threestates-twoqubits) first to make sure the `ThreeStates_TwoQubits` operation is defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T204_ThreeStates_TwoQubits_Phases\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation ThreeStates_TwoQubits_Phases (qs : Qubit[]) : Unit {\n",
    "    //create (|00⟩ + |01⟩ + |10⟩) / sqrt(3) state\n",
    "    ThreeStates_TwoQubits(qs);\n",
    "    \n",
    "    R1(2.0 * PI() / 3.0, qs[1]);\n",
    "    R1(4.0 * PI() / 3.0, qs[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.4 of the Superposition kata.](./Superposition.ipynb#three-states-two-qubits-phases)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"hardy-state\"></a>Task 2.5*. Hardy state.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state.\n",
    "\n",
    "**Goal:** Change the state of the qubits to $\\frac{1}{\\sqrt{12}} \\big(3|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle \\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> This solution is a detailed explanation of [this StackExchange answer](https://quantumcomputing.stackexchange.com/a/6844/2879).\n",
    "\n",
    "We start with the state $|\\psi_0\\rangle=|00\\rangle$.\n",
    "\n",
    "**Step 1:** Start by putting the first qubit in the state $\\alpha|0\\rangle + \\beta|1\\rangle$, where $\\alpha$ and $\\beta$ are the square roots of relative weights of all basis states which start with 0 and with 1, respectively.  \n",
    "\n",
    "In case of Hardy state, two basis states start with 0: $\\frac{1}{\\sqrt{12}} \\big (3|00\\rangle + |01\\rangle\\big )$ and two basis states start with 1: $\\frac{1}{\\sqrt{12}} \\big (|10\\rangle + |11\\rangle\\big )$.\n",
    "The relative weights of 0 and 1 are just the sums of squares of their amplitudes: \n",
    "$\\alpha^2 = \\frac{9}{12} + \\frac{1}{12} = \\frac{10}{12}$ and $\\beta^2 = \\frac{1}{12} + \\frac{1}{12} = \\frac{2}{12}$, respectively. \n",
    "So we'll need to put the first qubit in the state $\\sqrt{\\frac{10}{12}}|0\\rangle + \\sqrt{\\frac{2}{12}}|1\\rangle$ using the $R_y$ gate:\n",
    "\n",
    "$$|00\\rangle \\overset{R_{y_1}}\\rightarrow \\big (\\sqrt{\\frac{10}{12}}|0\\rangle + \\sqrt{\\frac{2}{12}}|1\\rangle \\big ) \\otimes |0\\rangle =: |\\psi_1\\rangle$$\n",
    "\n",
    "Here $R_{y_1} := R_y(2\\arccos \\sqrt{\\frac{10}{12}}) \\otimes I$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><b>Click here for the same computation in matrix representation</b></summary>\n",
    "$\\begin{equation}\n",
    "R_{y_1} := R_y(\\theta_1) \\otimes I = \n",
    "\\begin{bmatrix} \n",
    "\\cos\\frac{\\theta_1}{2} & 0 & -\\sin\\frac{\\theta_1}{2} & 0 \\\\ \n",
    "0 & \\cos\\frac{\\theta_1}{2} & 0 & -\\sin\\frac{\\theta_1}{2} \\\\ \n",
    "\\sin\\frac{\\theta_1}{2} & 0 & \\cos\\frac{\\theta_1}{2} & 0 \\\\ \n",
    "0 & \\sin\\frac{\\theta_1}{2} & 0 & \\cos\\frac{\\theta_1}{2}  \n",
    "\\end{bmatrix}\n",
    "\\text{, where } \\cos\\frac{\\theta_1}{2}=\\sqrt{\\frac{10}{12}} \\text{ and } \\sin\\frac{\\theta_1}{2}=\\sqrt{\\frac{2}{12}}\\end{equation}$.\n",
    "    \n",
    "$\\begin{equation}\n",
    "R_{y_1}|00\\rangle = \\frac{1}{\\sqrt{12}} \\begin{bmatrix} \n",
    "\\sqrt{10} & 0 & -\\sqrt{2} & 0 \\\\ \n",
    "0 & \\sqrt{10} & 0 & -\\sqrt{2} \\\\ \n",
    "\\sqrt{2} & 0 & \\sqrt{10} & 0 \\\\ \n",
    "0 & \\sqrt{2} & 0 & \\sqrt{10} \n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n",
    "= \\frac{1}{\\sqrt{12}} \\begin{bmatrix} \\sqrt{10} \\\\ 0 \\\\ \\sqrt{2} \\\\ 0 \\end{bmatrix}\n",
    "= \\big (\\sqrt{\\frac{10}{12}}|0\\rangle + \\sqrt{\\frac{2}{12}}|1\\rangle \\big ) \\otimes |0\\rangle =: |\\psi_1\\rangle\n",
    "\\end{equation}$    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 2:** Finish the preparation by putting the second qubit in the right state, applying controlled Ry gates with the first qubit as the control. \n",
    "To get the first two terms right, you need to convert the terms\n",
    "\n",
    "$$\\big (\\sqrt{\\frac{10}{12}}|0\\rangle \\big) \\otimes |0\\rangle \\overset{R_{y_2}}\\rightarrow \\frac{1}{\\sqrt{12}} \\big (3|00\\rangle + |01\\rangle \\big) \\text{  (2.a) }$$ \n",
    "and\n",
    "$$\\big (\\sqrt{\\frac{2}{12}}|1\\rangle \\big) \\otimes |0\\rangle \\overset{R_{y_3}}\\rightarrow \\frac{1}{\\sqrt{12}} \\big (|10\\rangle+|11\\rangle \\big) \\text{  (2.b) }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 2.a:** The transformation\n",
    "$$\\big (\\sqrt{\\frac{10}{12}}|0\\rangle \\big) \\otimes |0\\rangle \\overset{R_{y_2}}\\rightarrow \\frac{1}{\\sqrt{12}} \\big (3|00\\rangle + |01\\rangle \\big)$$\n",
    "\n",
    "is equivalent to the following transformation (to see this, just multiply both sides by $\\sqrt{\\frac{12}{10}}$):\n",
    "\n",
    "$$|0\\rangle \\otimes |0\\rangle \\overset{R_{y_2}}\\rightarrow \\frac{1}{\\sqrt{10}} \\big (3|00\\rangle + |01\\rangle \\big) = |0\\rangle \\otimes \\frac{1}{\\sqrt{10}} \\big (3|0\\rangle + |1\\rangle \\big)$$\n",
    "\n",
    "This rotation should only be applied if the first qubit is in state $|0\\rangle$, i.e., we need a conditional-on-zero rotation. The rotation angle can be determined by $\\cos\\frac{\\theta_2}{2} = \\frac{3}{\\sqrt{10}}$ and $\\sin\\frac{\\theta_2}{2} = \\frac{1}{\\sqrt{10}}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><b>Click here for the same computation in matrix representation</b></summary>\n",
    "A regular conditional-on-one rotation (controlled rotation or $CR_y$) is defined by \n",
    "\n",
    "$$C_1R_y := CR_y =\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0 \\\\ \n",
    "0 & 0 & \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \n",
    "0 & 0 & \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2}\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "To perform a conditional-on-zero rotation, we have to apply an $X$ gate to the first qubit to transform $|0\\rangle\\rightarrow|1\\rangle$ and $|1\\rangle\\rightarrow|0\\rangle$, perform the conditional-on-one rotation $CR_y$ and apply another $X$ gate to the first qubit to undo the first $X$.\n",
    "\n",
    "$$C_0R_y:=\\big (X\\otimes I \\big )CRy\\big (X\\otimes I \\big )=\n",
    "\\begin{bmatrix} \n",
    "0 & 0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\\\ \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0\n",
    "\\end{bmatrix} \\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0 \\\\ \n",
    "0 & 0 & \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \n",
    "0 & 0 & \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2}\n",
    "\\end{bmatrix} \\begin{bmatrix} \n",
    "0 & 0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\\\ \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0\n",
    "\\end{bmatrix} = \\\\ \n",
    "= \\begin{bmatrix} \n",
    "0 & 0 & \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \n",
    "0 & 0 & \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\\\ \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0 \n",
    "\\end{bmatrix} \\begin{bmatrix} \n",
    "0 & 0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\\\ \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0\n",
    "\\end{bmatrix} = \\begin{bmatrix} \n",
    "\\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} & 0 & 0 \\\\ \n",
    "\\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} & 0 & 0 \\\\ \n",
    "0 & 0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "Applying $C_0R_{y_2}$ (with angle parameter $\\theta_2$ defined by $\\cos\\frac{\\theta_2}{2} = \\frac{3}{\\sqrt{10}}$ and $\\sin\\frac{\\theta_2}{2} = \\frac{1}{\\sqrt{10}}$) to $|\\psi_1\\rangle$ leads to: \n",
    "\n",
    "$$|\\psi_2\\rangle:=C_0R_{y_2} |\\psi_1\\rangle = \n",
    "\\begin{bmatrix} \\frac{3}{\\sqrt{10}} & -\\frac{1}{\\sqrt{10}} & 0 & 0 \\\\ \\frac{1}{\\sqrt{10}} & \\frac{3}{\\sqrt{10}} & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix}\\frac{1}{\\sqrt{12}}\\begin{bmatrix} \\sqrt{10} \\\\ 0 \\\\ \\sqrt{2} \\\\ 0 \\end{bmatrix}=\\frac{1}{\\sqrt{12}}\\begin{bmatrix} 3 \\\\ 1 \\\\ \\sqrt{2} \\\\ 0 \\end{bmatrix}$$  \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Step 2.b:** Similarly, the transformation\n",
    "\n",
    "$$\\big (\\sqrt{\\frac{2}{12}}|1\\rangle \\big) \\otimes |0\\rangle \\overset{R_{y_3}}\\rightarrow \\frac{1}{\\sqrt{12}} \\big (|10\\rangle+|11\\rangle \\big)$$\n",
    "\n",
    "is equivalent to \n",
    "\n",
    "$$|1\\rangle \\otimes |0\\rangle \\overset{R_{y_3}}\\rightarrow \\frac{1}{\\sqrt{2}} \\big (|10\\rangle+|11\\rangle \\big)$$\n",
    "\n",
    "and can be done using a controlled rotation, applied if first qubit is $|1\\rangle$, i.e., a conditional-on-one rotation. The rotation angle can be determined by $\\cos\\frac{\\theta_3}{2} = \\frac{1}{\\sqrt{2}}$ and $\\sin\\frac{\\theta_3}{2} = \\frac{1}{\\sqrt{2}}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><b>Click here for the same computation in matrix representation</b></summary>\n",
    "\n",
    "Using the definition of $CR_{y_3}$ we've seen previously for $\\frac{\\theta_3}{2} = \\frac{\\pi}{4}$, we finally get our target state:\n",
    "\n",
    "$$|\\psi_3\\rangle := CR_{y_3}|\\psi_2\\rangle=\n",
    "\\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0 \\\\ \n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\\\ \n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}}\n",
    "\\end{bmatrix} \\frac{1}{\\sqrt{12}} \\begin{bmatrix} 3 \\\\ 1 \\\\ \\sqrt{2} \\\\ 0 \\end{bmatrix}=\n",
    "\\frac{1}{\\sqrt{12}}\\begin{bmatrix} 3 \\\\ 1 \\\\ 1 \\\\ 1 \\end{bmatrix}=\n",
    "\\frac{1}{\\sqrt{12}} \\big (3|00\\rangle+|01\\rangle+|10\\rangle+|11\\rangle\\big )$$    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T205_Hardy_State\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation Hardy_State (qs : Qubit[]) : Unit {\n",
    "    Ry(2.0 * ArcCos(Sqrt(10.0 / 12.0)), qs[0]);\n",
    "    (ControlledOnInt(0, Ry))([qs[0]], (2.0 * ArcCos(Sqrt(9.0 / 10.0)), qs[1]));\n",
    "    (ControlledOnInt(1, Ry))([qs[0]], (2.0 * PI()/4.0, qs[1]));\n",
    "    // In this special case the second Controlled Ry is equivalent to a Controlled H:\n",
    "    // Controlled H([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.5 of the Superposition kata.](./Superposition.ipynb#hardy-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"wstate-on-2k-qubits\"></a>Task 2.6**. W state on $2^k$ qubits.\n",
    "\n",
    "**Input:** $N = 2^k$ qubits in the $|0 \\dots 0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to the [W state](https://en.wikipedia.org/wiki/W_state) - an equal superposition of $N$ basis states on $N$ qubits which have Hamming weight of 1.\n",
    "\n",
    "> For example, for $N = 4$ the required state is $\\frac{1}{2}\\big(|1000\\rangle + |0100\\rangle + |0010\\rangle + |0001\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The problem becomes more manageable if broken down into the simplest cases and built up from there. \n",
    "\n",
    "1. The smallest instance of the problem, $N = 1$, requires preparing $|W_1\\rangle = |1\\rangle$; this can be done trivially using an X gate.\n",
    "\n",
    "2. The next instance, $N = 2$, requires preparing $|W_2\\rangle = \\frac{1}{\\sqrt2}\\big(|10\\rangle + |01\\rangle\\big)$. \n",
    "It matches one of the Bell states we've seen earlier, but preparing it will be more interesting (and more useful for the next steps!) if we think of it in recursive terms.\n",
    "Let see how to express $|W_2\\rangle$ in terms of $|W_1\\rangle$:\n",
    "\n",
    "$$|W_2\\rangle = \\frac{1}{\\sqrt2}\\big(|10\\rangle + |01\\rangle\\big) = \\frac{1}{\\sqrt2}\\big(|W_1\\rangle \\otimes |0\\rangle + |0\\rangle \\otimes |W_1\\rangle\\big)$$\n",
    "\n",
    "This representation suggests us a solution: \"split\" the starting state $|00\\rangle$ in two terms, prepare $|W_1\\rangle$ on the first qubit for the first term and on the second qubit - for the second term. \n",
    "To do this, we can again use an auxiliary qubit prepared in the $|+\\rangle$ state and control the preparation of $|W_1\\rangle$ state on the first or the second qubit based on the state of the auxiliary qubit:\n",
    "\n",
    "$$|0\\rangle_{aux} |00\\rangle_{reg} \\overset{H}{\\longrightarrow} \n",
    "\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)_{aux} \\otimes |00\\rangle_{reg} = \n",
    "\\frac{1}{\\sqrt2}(|0\\rangle_{aux} |00\\rangle_{reg} + |1\\rangle_{aux} |00\\rangle_{reg})\n",
    "\\overset{CNOT_0}{\\longrightarrow} \\\\ {\\longrightarrow}\n",
    "\\frac{1}{\\sqrt2}(|0\\rangle_{aux} |W_1\\rangle|0\\rangle_{reg} + |1\\rangle_{aux} |00\\rangle_{reg})\n",
    "\\overset{CNOT_1}{\\longrightarrow} \\\\ {\\longrightarrow}\n",
    "\\frac{1}{\\sqrt2}(|0\\rangle_{aux} |W_1\\rangle|0\\rangle_{reg} + |1\\rangle_{aux} |0\\rangle|W_1\\rangle_{reg})\n",
    "$$\n",
    "\n",
    "> The auxiliary qubit is now entangled with the rest of the qubits, so we can't simply reset it without it affecting the superposition we have prepared using it.\n",
    "\n",
    "The last step to bring the register to the desired state is to uncompute the auxiliary qubit for the term $|1\\rangle_{aux} |0\\rangle|W_1\\rangle_{reg}$ (the other term already has it in state $|0\\rangle$).\n",
    "\n",
    "To do this, we need to consider the explicit expression of the state $|0\\rangle|W_1\\rangle = |01\\rangle$.\n",
    "Similarly to the previous tasks, we'll uncompute the auxiliary qubit for this term by using a controlled X gate, with the auxiliary qubit as the target and the main register in the $|01\\rangle$ state as a control.\n",
    "This will make sure that the gate is applied only for this term and not for any others.\n",
    "\n",
    "The last step can be simplified to use fewer qubits as controls: we can use just the second qubit of the main register in state $|1\\rangle$ as control, since we know that if the second qubit is in state $|1\\rangle$, the first one has to be in state $|0\\rangle$ (we don't need to use both of them as the control pattern).\n",
    "\n",
    "3. If we take this one step further, to $N = 4$, we'll see that the same recursive logic can be applied to the larger and larger sizes of the problem. Indeed,\n",
    "\n",
    "$$|W_4\\rangle = \\frac{1}{2}\\big(|1000\\rangle + |0100\\rangle + |0010\\rangle + |0001\\rangle\\big) = \\\\\n",
    "= \\frac{1}{\\sqrt2} \\big(\\frac{1}{\\sqrt2}(|10\\rangle + |01\\rangle) \\otimes |00\\rangle + |00\\rangle \\otimes \\frac{1}{\\sqrt2}(|10\\rangle + |01\\rangle) \\big) = \\\\\n",
    "= \\frac{1}{\\sqrt2} \\big(|W_2\\rangle \\otimes |00\\rangle + |00\\rangle \\otimes |W_2\\rangle\\big)\n",
    "$$\n",
    "\n",
    "We can use the same approach for this case: prepare an auxiliary qubit in $|+\\rangle$ state and use it to control preparation of $W_2$ state on the first and the second half of the register. \n",
    "The last step will be uncomputing the $|1\\rangle$ state of the auxiliary qubit using two controlled X gates with each of the qubits of the second half of the register in state $|1\\rangle$ as controls. \n",
    "\n",
    "The same recursive approach can be generalized for arbitrary powers of 2 as the register size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T206_WState_PowerOfTwo\n",
    "\n",
    "operation WState_PowerOfTwo (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    let N = Length(qs);\n",
    "\n",
    "    if N == 1 {\n",
    "        // base of recursion: |1⟩\n",
    "        X(qs[0]);\n",
    "    } else {\n",
    "        let K = N / 2;\n",
    "        use anc = Qubit();\n",
    "        H(anc);\n",
    "\n",
    "        (ControlledOnInt(0, WState_PowerOfTwo))([anc], qs[0 .. K - 1]);\n",
    "        (ControlledOnInt(1, WState_PowerOfTwo))([anc], qs[K .. N - 1]);\n",
    "\n",
    "        for i in K .. N - 1 {\n",
    "            CNOT(qs[i], anc);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implementation of the recursion requires $\\log_2 N = k$ extra qubits allocated for controlling the preparation (one per level of recursion). \n",
    "We can modify our approach to use just one extra qubit at a time.\n",
    "\n",
    "To do this, let's notice that to prepare $|W_{N}\\rangle$ we need to prepare the $|W_{N-1}\\rangle$ state on half of the qubits for both states of the auxiliary qubit, the difference is just in which half of the register we're using. \n",
    "This means that we can prepare the $|W_{N-1}\\rangle$ state on the first half of the qubits, and use an auxiliary qubit in superposition to control SWAP-ing the first half of the register with the second half.\n",
    "The uncomputation of the auxiliary qubit happens in the same way as in the first approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T206_WState_PowerOfTwo\n",
    "\n",
    "operation WState_PowerOfTwo (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    let N = Length(qs);\n",
    "\n",
    "    if N == 1 {\n",
    "        // base of recursion: |1⟩\n",
    "        X(qs[0]);\n",
    "    } else {\n",
    "        let K = N / 2;\n",
    "        WState_PowerOfTwo(qs[0 .. K - 1]);\n",
    "\n",
    "        use anc = Qubit();\n",
    "        H(anc);\n",
    "\n",
    "        for i in 0 .. K - 1 {\n",
    "            Controlled SWAP([anc], (qs[i], qs[i + K]));\n",
    "        }\n",
    "        for i in K .. N - 1 {\n",
    "            CNOT(qs[i], anc);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.6 of the Superposition kata.](./Superposition.ipynb#wstate-on-2k-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"wstate-on-arbitray-number-of-qubits\"></a>Task 2.7**. W state on an arbitrary number of qubits.\n",
    "\n",
    "**Input:** $N$ qubits in the $|0 \\dots 0\\rangle$ state ($N$ is not necessarily a power of 2).\n",
    "\n",
    "**Goal:**  Change the state of the qubits to the [W state](https://en.wikipedia.org/wiki/W_state) - an equal superposition of $N$ basis states on $N$ qubits which have Hamming weight of 1.\n",
    "\n",
    "> For example, for $N = 3$ the required state is $\\frac{1}{\\sqrt{3}}\\big(|100\\rangle + |010\\rangle + |001\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This problem allows a variety of solutions that rely on techniques from arbitrary rotations to recursion to postselection. \n",
    "\n",
    "The first approach we will describe relies on performing a sequence of controlled rotations.\n",
    "\n",
    "To prepare a weighted superposition $\\cos \\theta |0\\rangle + \\sin \\theta |1\\rangle$ on a single qubit, we need to start with the $|0\\rangle$ state and apply the [Ry gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) to it with the angle parameter equal to $2 \\theta$. \n",
    "We'll apply the Ry gate with angle $2 \\theta_1 = 2\\arcsin \\frac{1}{\\sqrt{N}}$ to the first qubit of the register to prepare the following state:\n",
    "\n",
    "$$(\\cos \\theta_1 |0\\rangle + \\sin \\theta_1 |1\\rangle) \\otimes |0 \\dots 0\\rangle = \\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}}|00 \\dots 0\\rangle $$\n",
    "\n",
    "The first term $\\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle$ already matches the first term of the $|W_N\\rangle$ state; now we need to convert the second term $\\frac{\\sqrt{N-1}}{\\sqrt{N}}|00 \\dots 0\\rangle$ into the rest of the $|W_N\\rangle$ terms.\n",
    "\n",
    "To prepare a term that matches the second term of the $|W_N\\rangle$ state, we can apply another Ry gate to the term $|00 \\dots 0\\rangle$, this time to the second qubit, with an angle $2 \\theta_2 = 2\\arcsin \\frac{1}{\\sqrt{N-1}}$.\n",
    "To make sure it doesn't affect the term that we're already happy with, we will apply a controlled version of the Ry gate, with the first qubit of the register in state $|0\\rangle$ as control.\n",
    "This will change our state to\n",
    "\n",
    "$$\\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}} |0\\rangle \\otimes (\\cos \\theta_2 |0\\rangle + \\sin \\theta_2 |1\\rangle) \\otimes |0 \\dots 0\\rangle = \\\\ \n",
    "= \\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}} \\frac{1}{\\sqrt{N-1}} |010 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}} \\frac{\\sqrt{N-2}}{\\sqrt{N-1}} |000 \\dots 0\\rangle$$\n",
    "\n",
    "Now we have two terms that match the terms of the $|W_N\\rangle$ state, and need to convert the third term $\\frac{\\sqrt{N-2}}{\\sqrt{N}}|00 \\dots 0\\rangle$ into the rest of terms.\n",
    "\n",
    "We will keep going like this, preparing one term of the $|W_N\\rangle$ state at a time, until the rotation on the last qubit will be an X gate, controlled on all previous qubits being in the $|0 \\dots 0\\rangle$ state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T207_WState_Arbitrary\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation WState_Arbitrary (qs : Qubit[]) : Unit {\n",
    "    let N = Length(qs);\n",
    "    Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N))), qs[0]);\n",
    "    for i in 1 .. N - 1 {\n",
    "        (ControlledOnInt(0, Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N - i))), _)))(qs[0 .. i-1], qs[i]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can express the same sequence of gates using recursion, if we notice that \n",
    "\n",
    "$$|W_N\\rangle = \\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}}|0\\rangle \\otimes |W_{N-1}\\rangle$$\n",
    "\n",
    "The first step of the solution would still be applying the Ry gate with angle $2 \\theta_1 = 2\\arcsin \\frac{1}{\\sqrt{N}}$ to the first qubit of the register to prepare the following state:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{N}}|10 \\dots 0\\rangle + \\frac{\\sqrt{N-1}}{\\sqrt{N}}|00 \\dots 0\\rangle $$\n",
    "\n",
    "But we would express the rest of the controlled rotations as the operation that prepares the $|W_{N-1}\\rangle$ state, controlled on the $|0\\rangle$ state of the first qubit.\n",
    "\n",
    "> Note that you don't have to implement the controlled version of the gate yourself; it is sufficient to add `is Adj+Ctl` to the signature of the operation `WState_Arbitrary` to specify that controlled variant has to be generated automatically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T207_WState_Arbitrary\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation WState_Arbitrary (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    let N = Length(qs);\n",
    "    Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N))), qs[0]);\n",
    "    if N > 1 {\n",
    "        (ControlledOnInt(0, WState_Arbitrary))(qs[0 .. 0], qs[1 ...]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Post-selection\n",
    "\n",
    "This solution follows the similar approach to the one used to solve [task 2.3](#Task-2.3*.-$\\frac{1}{\\sqrt{3}}-\\big(|00\\rangle-+-|01\\rangle-+-|10\\rangle\\big)$-state.), which is called post-selection. \n",
    "\n",
    "Let's assume that we know how to prepare the $W$ state for $N = 2^k$ (we've discussed this in [task 2.6](#Task-2.6**.-W-state-on-$2^k$-qubits.)), and figure out how to use this knowledge as a building block for solving this task.\n",
    "\n",
    "Let's look at the smallest possible case for which $N \\neq 2^k$: $N = 3$ (we'll be able to generalize our solution for this case to an arbitrary number of qubits). The target $W$ state looks like this:  \n",
    "\n",
    "$$|W_3\\rangle = \\frac{1}{3}\\big(|100\\rangle + |010\\rangle + |001\\rangle\\big)$$\n",
    "\n",
    "We will start by finding the smallest power of 2 $P$ which is greater than or equal to $N$; for our case $N = 3$ this power will be $P = 4$. We will allocate an extra $P - N$ qubits and use the solution of [task 2.6](#Task-2.6**.-W-state-on-$2^k$-qubits.) to prepare the $W_P$ state that looks as follows (with the state of the extra qubit highlighted in bold):  \n",
    "\n",
    "$$|W_4\\rangle = \\frac{1}{2}\\big |100\\textbf{0}\\rangle + |010\\textbf{0}\\rangle + |001\\textbf{0}\\rangle + |000\\textbf{1}\\rangle \\big) = \\\\\n",
    "= \\frac{\\sqrt3}{2} \\cdot \\frac{1}{\\sqrt3}\\big(|100\\rangle + |010\\rangle + |001\\rangle \\big) \\otimes |\\textbf{0}\\rangle + \\frac{1}{2}|000\\rangle \\otimes |\\textbf{1}\\rangle = \\\\\n",
    "= \\frac{\\sqrt3}{2} |W_3\\rangle \\otimes |\\textbf{0}\\rangle + \\frac{1}{2}|000\\rangle \\otimes |\\textbf{1}\\rangle$$\n",
    "\n",
    "As we can see, if the extra qubit is in the $|0\\rangle$ state, the main 3 qubits that we are concerned about are in the right $|W_3\\rangle$ state. \n",
    "\n",
    "What happens if we measure just the extra qubit? This causes a partial collapse of the system to the state defined by the measurement result:\n",
    "* If the result is $|0\\rangle$, the system collapses to the $|W_3\\rangle$ state - which is exactly what we wanted to achieve.\n",
    "* If the result is $|1\\rangle$, the system collapses to a state $|000\\rangle$, so our goal is not achieved. The good thing is, this only happens in 25% of the cases, and we can just try again.\n",
    "\n",
    "If we generalize this approach to an arbitrary $N$, we'll have \n",
    "\n",
    "$$|W_P\\rangle = \\frac{\\sqrt{N}}{\\sqrt{P}} |W_N\\rangle \\otimes |\\textbf{0}\\rangle^{\\otimes P-N} + \\frac{\\sqrt{P-N}}{\\sqrt{P}} |0\\rangle^{\\otimes N} \\otimes |W_{P-N}\\rangle$$\n",
    "\n",
    "Measuring the extra $P-N$ qubits gives us two possibilities:\n",
    "* All the extra qubits are in the $|0\\rangle$ state; this means the main qubits collapse to the $|W_N\\rangle$ state. \n",
    "* One of the extra qubits is in the $|1\\rangle$ state; this means that the main qubits collapse to the $|0\\rangle^{\\otimes N}$ state, which is **not** the desired state. In this case we will reset and try again until all the extra qubits are in the $|0\\rangle$ state.\n",
    "\n",
    "> If you get the `No identifier with the name \"WState_PowerOfTwo\" exists` error, you need to run the code cell with the solution to [task 2.6](#Task-2.6**.-W-state-on-$2^k$-qubits.) first to make sure the `WState_PowerOfTwo` operation is defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T207_WState_Arbitrary\n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation WState_Arbitrary (qs : Qubit[]) : Unit {\n",
    "    let N = Length(qs);\n",
    "    if N == 1 {\n",
    "        // base case of recursion: |1⟩\n",
    "        X(qs[0]);\n",
    "    } else {\n",
    "        // find the smallest power of 2 which is greater than or equal to N\n",
    "        // as a hack, we know we're not doing it on more than 64 qubits\n",
    "        mutable P = 1;\n",
    "        for i in 1 .. 6 {\n",
    "            if P < N {\n",
    "                set P *= 2;\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // allocate extra qubits (might be 0 qubits if N is a power of 2)\n",
    "        use anc = Qubit[P - N];\n",
    "        repeat {\n",
    "            // prepare state W_P on original + ancilla qubits\n",
    "            WState_PowerOfTwo(qs + anc);\n",
    "\n",
    "            // measure extra qubits; if all of the results are Zero, we got the right state on main qubits\n",
    "            mutable allZeros = true;\n",
    "            for i in 0 .. (P - N) - 1 {\n",
    "                if MResetZ(anc[i]) == One {\n",
    "                    set allZeros = false;\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        until (allZeros);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.7 of the Superposition kata.](./Superposition.ipynb#wstate-on-arbitray-number-of-qubits)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.24"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}