QFT/Workbook_QFT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QFT Kata Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [QFT kata](./QFT.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts before tackling the QFT kata (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. The concept of qubit and multi-qubit systems\n",
    "3. Single-qubit and multi-qubit quantum gates\n",
    "4. The discrete Fourier transform (DFT) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Implementing Quantum Fourier Transform\n",
    "\n",
    "This sequence of tasks uses the implementation of QFT described in Nielsen & Chuang.\n",
    "All numbers in this kata use big endian encoding: most significant bit of the number\n",
    " is stored in the first (leftmost) bit/qubit.\n",
    " \n",
    " What this means is that we can represent a state in reversed bit-string format: <br><br>\n",
    " $|x\\rangle = x_1x_2..x_n$ = $x_12^{n-1} + x_22^{n-2}+...x_n2^{0}$\n",
    " \n",
    " We can also make use of the notation for decimals in binary format: \n",
    " \n",
    " $0.x_1x_2...x_n = \\frac{x_1}{2^{-1}}+ \\frac{x_2}{2^{-2}}+...\\frac{x_n}{2^{n}}$\n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. 1-qubit QFT\n",
    "\n",
    "**Input:** \n",
    "\n",
    "  A qubit in state $|\\psi\\rangle = x_0 |0\\rangle + x_1 |1\\rangle$.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Apply QFT to this qubit, i.e., transform it to a state\n",
    "$\\frac{1}{\\sqrt{2}} \\big((x_0 + x_1) |0\\rangle + (x_0 - x_1) |1\\rangle\\big)$.\n",
    "\n",
    "In other words, transform a basis state $|j\\rangle$ into a state $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot \\frac{j}{2}}|1\\rangle\\big)$ .\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First, notice that we are dealing with a *single* qubit, which has $N = 2$ possible basis states. \n",
    "\n",
    "The transformation of a state $x_0 |0\\rangle + x_1 |1\\rangle$ to a state $\\frac{1}{\\sqrt{2}} \\big((x_0 + x_1) |0\\rangle + (x_0 - x_1) |1\\rangle\\big)$ is actually just the expression for the transformation of an arbitrary state in the Z basis (a.k.a. the computational basis) to one in the X basis. \n",
    "\n",
    "For a starting state $|0\\rangle$, $x_0=1$ and $x_1=0$, so the new state will be  $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle +|1\\rangle\\big) = |+\\rangle$.\n",
    "Similarly, for a starting state $|1\\rangle$, $x_0=0$ and $x_1=1$, so the new state will be  $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle -|1\\rangle\\big) = |-\\rangle$.\n",
    "\n",
    "We already know a gate that will do this: the Hadamard gate!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_OneQubitQFT \n",
    "\n",
    "operation OneQubitQFT (q : Qubit) : Unit is Adj+Ctl {\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the QFT kata.](./QFT.ipynb#Task-1.1.-1-qubit-QFT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Rotation gate\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "  2. An integer k $\\geq$ 0.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Change the state of the qubit to $\\alpha |0\\rangle + \\beta \\cdot e^{\\frac{2\\pi i}{2^{k}}} |1\\rangle$.\n",
    "\n",
    "> Be careful about not introducing an extra global phase! \n",
    "This is going to be important in the later tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's have a look at the gates available under the [Microsoft.Quantum.Intrinsic namespace](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic). \n",
    "\n",
    "To avoid adding the extra global phase, we have to use a gate that does not modify the $|0\\rangle$ state, and only impacts $|1\\rangle$: that is, $U|\\psi\\rangle = \\alpha|0\\rangle + \\beta \\cdot U|1\\rangle$.\n",
    "\n",
    "The [R1Frac gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.r1frac) does exactly that:\n",
    "\n",
    "$$R1Frac(n,k) = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i\\pi n/2^{k}} \\end{bmatrix} $$\n",
    "\n",
    "We specify $n=2$ to get the transformation required: \n",
    "\n",
    "$$R1Frac(2,k) = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{2\\pi i/2^{k}} \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T12_Rotation \n",
    "\n",
    "operation Rotation (q : Qubit, k : Int) : Unit is Adj+Ctl {\n",
    "    R1Frac(2, k, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the QFT kata.](./QFT.ipynb#Task-1.2.-Rotation-gate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Prepare binary fraction exponent (classical input)\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "  2. An array of $n$ bits $[j_1, j_2, ..., j_n]$, stored as `Int[]` ($ j_k \\in \\{0,1\\}$).\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Change the state of the qubit to $\\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0.j_1 j_2 ... j_n} |1\\rangle$,\n",
    "where $0.j_1 j_2 ... j_n$ is a binary fraction, similar to decimal fractions: \n",
    "\n",
    "$$0.j_1 j_2 ... j_n = j_1 \\cdot \\frac{1}{2^1} + j_2 \\cdot \\frac{1}{2^2} + ... j_n \\cdot \\frac{1}{2^n}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Since we can express the exponent of a sum as a product of exponents ($e^{a+b} = e^a \\cdot e^b$), we can implement the required transformation as a sequence of rotation gates from task 1.2 with increasing **k**. \n",
    "\n",
    "Each of the individual rotations will use the bit $j_k$ to decide whether to apply the rotation, and the index of that bit $k$ to define the rotation angle.\n",
    "Note that we only want to apply the rotation if the bit $j_k$ is not zero. \n",
    "This means that the gate we apply for each $k$ will be \n",
    "\n",
    "$$U_k = \\begin{cases}\n",
    "I, j_k=0 \\\\\n",
    "R1Frac(2,k), j_k=1\n",
    "\\end{cases}$$\n",
    "\n",
    "Recall that \n",
    "\n",
    "$$ R1Frac(2,k)\\big( \\alpha |0\\rangle + \\beta |1\\rangle\\big) = \\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i/2^{k}} |1\\rangle = \\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0. \\underset{k-1}{\\underbrace{0\\dots0}} 1} |1\\rangle $$\n",
    "\n",
    "This means that we can write the overall effect of the gate $U_k$ for each $k$ as \n",
    "\n",
    "$$U_k\\big( \\alpha |0\\rangle + \\beta |1\\rangle\\big) = \\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0. \\underset{k-1}{\\underbrace{0\\dots0}} j_k} |1\\rangle$$\n",
    "\n",
    "As we iterate, the resulting state will get closer and closer to the required one:\n",
    "\n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=100>\n",
    "    <col width=500>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Step $k$</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">State after step $k$</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$1$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$$ \\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0.j_1} |1\\rangle $$</td>\n",
    "    </tr>      \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$2$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$$\\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i j_1 \\cdot 2^{-1} + 2\\pi i j_2 \\cdot 2^{-2}} |1\\rangle = \\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0.j_1j_2} |1\\rangle $$</td>\n",
    "    </tr>      \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">...</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">...</td>\n",
    "    </tr>      \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$n$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$$\\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0.j_1j_2 \\dots j_n} |1\\rangle $$</td>\n",
    "    </tr>      \n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_BinaryFractionClassical \n",
    "\n",
    "operation BinaryFractionClassical (q : Qubit, j : Int[]) : Unit is Adj+Ctl {\n",
    "    for ind in 0 .. Length(j) - 1 {\n",
    "        if j[ind] == 1 {\n",
    "            Rotation(q, ind + 1);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the QFT kata.](./QFT.ipynb#Task-1.3.-Prepare-binary-fraction-exponent-(classical-input))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. Prepare binary fraction exponent (quantum input)\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "  2. A register of $n$ qubits in state $|j_1 j_2 ... j_n\\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Change the state of the input\n",
    "from $(\\alpha |0\\rangle + \\beta |1\\rangle) \\otimes |j_1 j_2 ... j_n\\rangle$\n",
    "to $(\\alpha |0\\rangle + \\beta \\cdot e^{2\\pi i \\cdot 0.j_1 j_2 ... j_n} |1\\rangle) \\otimes |j_1 j_2 ... j_n\\rangle$,\n",
    "\n",
    "where $0.j_1 j_2 ... j_n$ is a binary fraction corresponding to the basis state $j_1 j_2 ... j_n$ of the register.\n",
    "\n",
    "> The register of qubits can be in superposition as well;\n",
    "the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "From the goals section, you can see that the register of $n$ qubits has to remain unchanged, while the qubit should acquire a phase that depends on the value of the qubits in the register. \n",
    "\n",
    "Since the register is a quantum register and can be in a superposition of basis states, we cannot just measure the register and then conditionally apply the operation from task 1.3. So, we have to convert our solution to task 1.3 from using the `Rotation` operation with classical condition to using it as a controlled operation (with quantum control). We can do this with the [`Controlled` functor](https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/expressions/functorapplication#functor-application).\n",
    "\n",
    "The `Rotation` operation in task 1.2 was defined to be both adjointable (Adj) and controllable (Ctl), so we don't need to come up with a way to implement its controlled variant manually. All we need to do is go through the qubits in the register and apply the controlled variant of the `Rotation` operation, similarly to the previous task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_BinaryFractionQuantum \n",
    "\n",
    "operation BinaryFractionQuantum (q : Qubit, jRegister : Qubit[]) : Unit is Adj+Ctl {\n",
    "    for ind in 0 .. Length(jRegister) - 1 {\n",
    "        Controlled Rotation([jRegister[ind]], (q, ind + 1));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.4 of the QFT kata.](./QFT.ipynb#Task-1.4.-Prepare-binary-fraction-exponent-(quantum-input))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. Prepare binary fraction exponent in place (quantum input)\n",
    "\n",
    "**Input:** \n",
    "\n",
    " A register of $n$ qubits in state $|j_1 j_2 ... j_n \\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Change the state of the register\n",
    "from $|j_1\\rangle \\otimes |j_2 ... j_n\\rangle$\n",
    "to $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1 j_2 ... j_n} |1\\rangle \\big) \\otimes |j_2 ... j_n\\rangle$.\n",
    "\n",
    "> The register of qubits can be in superposition as well;\n",
    "the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First, let's recall task 1.1: a Hadamard gate applied to a single qubit,  $H|j_1\\rangle$, will give either\n",
    "$\\frac{1}{\\sqrt{2}}(|0\\rangle+|1\\rangle)$ or $\\frac{1}{\\sqrt{2}}(|0\\rangle-|1\\rangle)$ depending on the state of $|j_1\\rangle$. This operation can also be written as\n",
    "$$H|j_1\\rangle= \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot \\frac{j_1}{2}}|1\\rangle\\big)= \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1}|1\\rangle\\big)$$\n",
    "\n",
    "So if the starting register state is $|j_1 j_2 ... j_n \\rangle$, applying a Hadamard gate to the first qubit will result in:\n",
    "\n",
    "$$\\big(H_1\\otimes I_{n-1} \\big) \\big(|j_1\\rangle \\otimes |j_2 ... j_n\\rangle\\big)= \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1}|1\\rangle\\big) \\otimes |j_2 ... j_n\\rangle $$\n",
    "\n",
    "After this, we can repeat the loop we used in task 1.4 for qubits $|j_2 ... j_n\\rangle$ with the first qubit as the target to add the remaining phase terms via the controlled `Rotation` operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_BinaryFractionQuantumInPlace \n",
    "\n",
    "operation BinaryFractionQuantumInPlace (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    OneQubitQFT(register[0]);\n",
    "    \n",
    "    for ind in 1 .. Length(register) - 1 {\n",
    "        Controlled Rotation([register[ind]], (register[0] , ind + 1));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.5 of the QFT kata.](./QFT.ipynb#Task-1.5.-Prepare-binary-fraction-exponent-in-place-(quantum-input))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. Reverse the order of qubits\n",
    "\n",
    "**Input:** \n",
    "\n",
    " A register of $n$ qubits in state $|x_1 x_2 ... x_n \\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Reverse the order of qubits, i.e., convert the state of the register to $|x_n ... x_2 x_1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Have a look at what the register looks like drawn as a circuit:\n",
    "\n",
    "<img src=\"./images/1.PNG\" width=\"300\"/>\n",
    "\n",
    "This will read as $|x_1 x_2 ... x_n \\rangle$. To reverse the order of the qubits, you can use SWAP operations (denoted with double-X), to switch $x_1$ with $x_n$, $x_2$ with $x_{n-1}$, and so on:\n",
    "\n",
    "<img src=\"./images/2.PNG\" width=\"300\"/>\n",
    "\n",
    "After $N/2$ of these swaps, the states will now be: \n",
    "\n",
    "<img src=\"./images/3.PNG\" width=\"300\"/>\n",
    "\n",
    "And the state of the register will be $|x_n ... x_2 x_1\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T16_ReverseRegister \n",
    "\n",
    "operation ReverseRegister (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    let N = Length(register);\n",
    "    for ind in 0 .. N / 2 - 1 {\n",
    "        SWAP(register[ind], register[N - 1 - ind]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.6 of the QFT kata.](./QFT.ipynb#Task-1.6.-Reverse-the-order-of-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. Quantum Fourier transform\n",
    "\n",
    "**Input:** \n",
    "\n",
    " A register of $n$ qubits in state $|j_1 j_2 ... j_n \\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Apply quantum Fourier transform to the input register, i.e., transform it to a state\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} \\sum_{k=0}^{2^n-1} e^{2\\pi i \\cdot \\frac{jk}{2^{n}}} |k\\rangle = $$\n",
    "$$\\begin{align}= &\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_n} |1\\rangle\\big) \\otimes \\\\\n",
    "\\otimes &\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_{n-1} j_n} |1\\rangle\\big) \\otimes ... \\otimes\\\\\n",
    "\\otimes &\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\\rangle\\big)\\end{align}$$\n",
    "\n",
    "> The register of qubits can be in superposition as well;\n",
    "the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's use the hint and start by preparing the described state with the qubits reversed:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + exp(2\\pi i \\cdot 0.j_1 j_2 ... j_{n-1} j_n) |1\\rangle\\big) \\otimes ...\n",
    "\\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + exp(2\\pi i \\cdot 0.j_{n-1} j_n) |1\\rangle\\big)\n",
    "\\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + exp(2\\pi i \\cdot 0.j_n) |1\\rangle\\big)$$\n",
    "\n",
    "You've already found a way to prepare a binary fraction exponent in place in task 1.5: the state $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1 j_2 ... j_n} |1\\rangle\\big) \\otimes |j_2 ... j_n\\rangle$ can be created by first applying the Hadamard gate to qubit $|j_1\\rangle$, then applying a succession of controlled rotations using qubits $|j_k\\rangle$ with increasing values of $k$ as controls, so that an extra phase term all the way up to $e^{2\\pi i \\cdot j_n/2^{n}}$ is added with each rotation. \n",
    "\n",
    "This will prepare the first qubit in the right state. You'll see that $j_1$ doesn't appear in the rest of the expression for the target state, so we won't need to use it for the rest of the state preparation.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To prepare the remaining qubits in the right states, we can work backwards from this state.\n",
    "The second qubit in the sequence needs to be prepared in the state $\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_2 ... j_{n-1} j_n} |1\\rangle\\big)$. \n",
    "Similarly, we can do this by applying a Hadamard gate to the qubit $|j_2\\rangle$ and then using qubits $|j_3\\rangle$ to $|j_n\\rangle$ to apply $n-2$ controlled rotation gates with $k=2^2$ to $k=2^{n-1}$ to $|j_2\\rangle$. \n",
    "After this operation, the total system state will be: \n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\\rangle\\big)\\otimes\n",
    "\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_2 ... j_{n-1} j_n} |1\\rangle\\big) \\otimes |j_3 ... j_n\\rangle$$\n",
    "\n",
    "These two steps allow us to see a pattern: for each qubit $j_k, k = 1 .. n$ :\n",
    "\n",
    "1. Apply a Hadamard gate to $|j_k\\rangle$.\n",
    "2. Apply the controlled rotation operator $n-k$ times to the qubit $|j_k\\rangle$, using qubits $|j_{k+1}\\rangle$ through $|j_n\\rangle$ as the controls, with phase corresponding to $2^2$ through $2^{n-k+1}$.\n",
    "\n",
    "The effect of thse steps will be preparing the following state:  \n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\\rangle\\big)\\otimes \\\\ \n",
    "\\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_2 ... j_{n-1} j_n} |1\\rangle\\big)\\otimes \\\\ \n",
    "\\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_3 ... j_{n-1} j_n} |1\\rangle\\big)\\otimes ... \\otimes \\\\\n",
    "\\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_n} |1\\rangle\\big)\n",
    "$$\n",
    "\n",
    "The qubits of the system can then be reversed using the task 1.6.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_QuantumFourierTransform \n",
    "\n",
    "operation QuantumFourierTransform (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    let n = Length(register);\n",
    "    for i in 0 .. n - 1 {\n",
    "        BinaryFractionQuantumInPlace(register[i ...]);\n",
    "    }\n",
    "    ReverseRegister(register);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can simulate a circuit summary of this process using `%trace` magic command. Set the parameter **n** to the number of qubits you want to draw the QFT circuit for, then run the cells below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation DrawQFTCircuit(n : Int) : Unit {\n",
    "    use qs = Qubit[n];\n",
    "    QuantumFourierTransform(qs);\n",
    "    ResetAll(qs);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%config trace.defaultDepth=3\n",
    "%trace DrawQFTCircuit n=3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.7 of the QFT kata.](./QFT.ipynb#Task-1.7.-Quantum-Fourier-transform)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.8. Inverse QFT\n",
    "\n",
    "**Input:** \n",
    "\n",
    " A register of $n$ qubits in state $|j_1 j_2 ... j_n \\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Apply inverse QFT to the input register, i.e., transform it to a state \n",
    "$\\frac{1}{\\sqrt{2^{n}}} \\sum_{k=0}^{2^n-1} e^{-2\\pi i \\cdot \\frac{jk}{2^{n}}} |k\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Have a look at the documentation on the [Adjoint Functor](https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/expressions/functorapplication#functor-application).\n",
    "For an operation that implements a unitary transformation $U$ of the quantum state, Adjoint $U$ implements $U^{\\dagger}$ automatically.\n",
    "\n",
    "This means that you can just reuse your solution to task 1.7 with an Adjoint functor!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T18_InverseQFT \n",
    "\n",
    "operation InverseQFT (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    Adjoint QuantumFourierTransform(register);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.8 of the QFT kata.](./QFT.ipynb#Task-1.8.-Inverse-QFT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Using the Quantum Fourier Transform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Prepare an equal superposition of all basis states\n",
    "\n",
    "**Input:** \n",
    "\n",
    "A register of $n$ qubits in state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Prepare an equal superposition of all basis vectors from $|0...0\\rangle$ to $|1...1\\rangle$ \n",
    "(i.e., state $\\frac{1}{\\sqrt{2^{n}}} \\big(|0...0\\rangle + ... + |1...1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We can think of the required equal superposition of all basis states as the QFT of the state $|0...0\\rangle$. Indeed, if $j_1 = j_2 = ... = j_n = 0$, we get \n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} \\sum_{k=0}^{2^n-1} e^{2\\pi i \\cdot \\frac{jk}{2^{n}}} |k\\rangle = \\frac{1}{\\sqrt{2^{n}}} \\sum_{k=0}^{2^n-1} e^{0} |k\\rangle = \\frac{1}{\\sqrt{2^{n}}} \\sum_{k=0}^{2^n-1} |k\\rangle$$\n",
    "\n",
    "This means that we can solve this task by simply calling the QFT on the given register, either the implementation from task 1.7 or the [library function](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.qft).\n",
    "\n",
    "Note that the library function QFT operates on a big endian register (most significant bit of the number stored first), so the input qubit array has to be converted to a [BigEndian type](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arithmetic.bigendian) first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_PrepareEqualSuperposition \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation PrepareEqualSuperposition (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    QFT(BigEndian(register));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the QFT kata.](./QFT.ipynb#Task-2.1.-Prepare-an-equal-superposition-of-all-basis-states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Prepare a periodic state\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. A register of $n$ qubits in state $|0...0\\rangle$.\n",
    "\n",
    "  2. An integer frequency F ($0 \\leq F \\leq 2^{n}-1$).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Prepare a periodic state with frequency F on this register:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} \\sum_k e^{2\\pi i \\cdot \\frac{Fk}{2^{n}}} |k\\rangle$$\n",
    "\n",
    "> For example, for $n = 2$ and $F = 1$ the goal state is $\\frac{1}{2}\\big(|0\\rangle + i|1\\rangle - |2\\rangle - i|3\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Recall the definition of the QFT: \n",
    "for a basis state $|j\\rangle \\in \\{|0\\rangle, |1\\rangle...|2^n-1\\rangle\\}$, the QFT is defined as \n",
    "\n",
    "$$ QFT|j\\rangle= \\frac{1}{\\sqrt{2^n}} \\sum_{k=1}^{2^n-1} e^{2\\pi i \\cdot j k/2^{n}} |k\\rangle$$\n",
    "\n",
    "You can see that using $j = F$ will produce the required state. \n",
    "\n",
    "You can check that this is the case by going though the example $F=1$ given in the task, by writing $|F\\rangle = |j_1j_2\\rangle = |01\\rangle$ and working through the QFT operation to produce the state $\\frac{1}{2}\\big(|0\\rangle + i|1\\rangle - |2\\rangle - i|3\\rangle\\big)$.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Click to view the steps </b></summary>\n",
    "\n",
    "For $n=2$, $N=4$ and so: \n",
    "\n",
    " $$QFT |1\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_2} |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + e^{2\\pi i \\cdot 0.j_1j_2} |1\\rangle\\big) = \\\\\n",
    "= |00\\rangle+ |01\\rangle e^{2\\pi i \\cdot 0.j_1j_2}+ |10\\rangle e^{2\\pi i \\cdot 0.j_2}+ |11\\rangle e^{2\\pi i \\cdot (0.j_1j_2 + 0.j_2)}$$\n",
    " \n",
    " Evaluating for $j_1=0$ and $j_2=1$ will give $\\frac{1}{2}\\big(|0\\rangle + i|1\\rangle - |2\\rangle - i|3\\rangle\\big)$.\n",
    "    \n",
    "</details>\n",
    "\n",
    "To prepare the state $|F\\rangle$ on the input register, you need to convert the integer value $F$ into a binary representation and encode it in the register. \n",
    "When writing the code, make sure that you pay attention to whether library functions use little or big endian!  In particular, [IntAsBoolArray](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray) uses little endian encoding, so the result must be reversed before encoding it in the register. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_PreparePeriodicState \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation PreparePeriodicState (register : Qubit[], F : Int) : Unit is Adj+Ctl {\n",
    "    let bitsBE = Reversed(IntAsBoolArray(F, Length(register)));\n",
    "    ApplyPauliFromBitString(PauliX, true, bitsBE, register);\n",
    "\n",
    "    QFT(BigEndian(register));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the QFT kata.](./QFT.ipynb#Task-2.2.-Prepare-a-periodic-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Prepare a periodic state with alternating $1$ and $-1$ amplitudes\n",
    "\n",
    "**Input:**\n",
    "\n",
    "A register of $n$ qubits in state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Prepare a periodic state with alternating $1$ and $-1$ amplitudes of basis states:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle - |1\\rangle + |2\\rangle - |3\\rangle + ... - |2^{n}-1\\rangle\\big)$$\n",
    "\n",
    "> For example, for $n = 2$ the goal state is $\\frac{1}{2} \\big(|0\\rangle - |1\\rangle + |2\\rangle - |3\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "Since the amplitudes of this state have no imaginary parts, it is clear that the value of exponents for an arbitrary amplitude $e^{2\\pi i \\cdot \\frac{Fk}{2^{n}}}$ must be either $2\\pi i$ for a coefficient of $1$ or $\\pi i$ for a coefficient of $-1$. \n",
    "This means that only $j_1$ can be 1: all other bits of $F$ must be $0$. \n",
    "Indeed, you can check that using $F = 1$ (in terms of task 2.2) yields the required state.\n",
    "\n",
    "You can simplify preparing this state: instead of using the general encoding of $F$ in the register, you can apply an X gate to the first qubit of the register, either as X(qubit[0]) or as X(Head(register)). The [Head function](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays.head) returns the first element of an array. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_PrepareAlternatingState \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PrepareAlternatingState (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    X(Head(register));\n",
    "\n",
    "    QFT(BigEndian(register));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the QFT kata.](./QFT.ipynb#Task-2.3.-Prepare-a-periodic-state-with-alternating-$1$-and-$-1$-amplitudes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Prepare an equal superposition of all even basis states\n",
    "\n",
    "**Input:** \n",
    "\n",
    "A register of $n$ qubits in state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Prepare an equal superposition of all even basis vectors:\n",
    "$\\frac{1}{\\sqrt{2^{n-1}}} \\big(|0\\rangle + |2\\rangle + ... + |2^{n}-2\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "You can see that the superposition of two states from tasks 2.1 and 2.3 will give this result. Indeed,\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n-1}}} \\big(|0\\rangle + |2\\rangle + ... + |2^{n}-2\\rangle\\big)= \n",
    "\\frac{1}{\\sqrt{2}} \\bigg( \\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle - |1\\rangle + |2\\rangle - |3\\rangle + ... - |2^{n}-1\\rangle\\big) + \\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle +|1\\rangle + |2\\rangle + |3\\rangle + ... + |2^{n}-1\\rangle\\big)\\bigg)$$\n",
    "\n",
    "Now, we can use the fact that QFT is a linear transformation.\n",
    "The periodic state from task 2.3 is created by applying the QFT to the $|100...0\\rangle$ state, while the state from task 2.1 is created by applying the QFT to the $|000...0\\rangle$ state. \n",
    "To prepare an equal superposition of these two states, we can create a superposition by applying a Hadamard gate to the first qubit in the register:\n",
    "\n",
    "$$ \\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle + |1\\rangle\\big) \\otimes |00...0\\rangle $$\n",
    "\n",
    "And then applying the QFT to the register: \n",
    "\n",
    "$$ QFT\\big(\\frac{1}{\\sqrt{2}} (|0\\rangle + |1\\rangle) \\otimes |00...0\\rangle\\big)= \\frac{1}{\\sqrt{2}} \\bigg( QFT\\big(|000...0\\rangle\\big)+ QFT\\big(|100...0\\rangle\\big)\\bigg)$$\n",
    "\n",
    "This results in the desired end state. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_PrepareEqualSuperpositionOfEvenStates \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PrepareEqualSuperpositionOfEvenStates (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    H(Head(register));\n",
    "    QFT(BigEndian(register));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.4 of the QFT kata.](./QFT.ipynb#Task-2.4.-Prepare-an-equal-superposition-of-all-even-basis-states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Prepare a square-wave signal\n",
    "\n",
    "**Input:** \n",
    "\n",
    "A register of $n\\geq2$ qubits in state $|0...0\\rangle$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Prepare a periodic state with alternating $1, 1, -1, -1$ amplitudes of basis states:\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle + |1\\rangle - |2\\rangle - |3\\rangle + ... - |2^{n}-2\\rangle - |2^{n}-1\\rangle\\big)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Writing out the state that we want to get gives us:\n",
    "\n",
    "$$ |0...00\\rangle + |0...01\\rangle - |0...10\\rangle - |0...11\\rangle $$\n",
    "\n",
    "The states which have 1 as their second-least significant bit have the -1 phase. Written as a tensor product of single-qubit states, this gives:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^{n}}} (|0\\rangle + |1\\rangle) \\otimes (|0\\rangle + |1\\rangle) ... \\otimes (|0\\rangle - |1\\rangle) \\otimes (|0\\rangle + |1\\rangle)$$\n",
    "\n",
    "We could try to prepare this state by setting only $j_2$ to 1 and the rest of bits to 0, then applying the QFT. This will add the required phase of -1 on the second-to-last bit, but will also add a phase term of $i$ on the last bit:\n",
    "$$QFT(|010...0\\rangle) = \\frac{1}{\\sqrt{2^{n}}}  \\big(|0\\rangle + |1\\rangle) \\otimes (|0\\rangle + |1\\rangle) ... \\otimes (|0\\rangle - |1\\rangle) \\otimes (|0\\rangle + i|1\\rangle)$$\n",
    "\n",
    "To fix this last phase term, we need cancel out that last $i$ phase in some form. This can be achieved by using the following state as the start:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}} \\big(e^{-i\\pi/4} |010...0\\rangle + e^{i\\pi/4} |110...0\\rangle\\big)$$\n",
    "\n",
    "Then,\n",
    "\n",
    "$$ QFT\\bigg(\\frac{1}{\\sqrt{2}} \\big(e^{-i\\pi/4} |010...0\\rangle + e^{i\\pi/4} |110...0\\rangle\\big)\\bigg) = \\\\\n",
    "= \\frac{1}{\\sqrt{2}}\\bigg( \\frac{1-i}{\\sqrt2}QFT|010...0\\rangle + \\frac{1+i}{\\sqrt2}QFT|110...0\\rangle \\bigg) = \\\\\n",
    "= \\frac{(1-i)}{2\\sqrt{2^{n}}} \\big( |0\\rangle + |1\\rangle) \\otimes (|0\\rangle + |1\\rangle)... |0\\rangle - |1\\rangle) \\otimes (|0\\rangle + i|1\\rangle)  \\big) + \\\\\n",
    "+ \\frac{(1+i)}{2\\sqrt{2^{n}}} \\big( |0\\rangle + |1\\rangle) \\otimes (|0\\rangle + |1\\rangle)... |0\\rangle - |1\\rangle) \\otimes (|0\\rangle - i|1\\rangle)  \\big) = \\\\\n",
    "= \\frac{1}{\\sqrt{2^{n}}} \\big(|0\\rangle + |1\\rangle) \\otimes (|0\\rangle + |1\\rangle) ... \\otimes (|0\\rangle - |1\\rangle) \\otimes (|0\\rangle + |1\\rangle)$$\n",
    " \n",
    "Creating the required superposition state is fairly easy; it can be done using the [T gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.t) and its adjoint. \n",
    "You can use the within...apply statements to avoid writing down the X gate twice. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_PrepareSquareWaveSignal \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation PrepareSquareWaveSignal (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    X(register[1]);\n",
    "    // |010...0⟩\n",
    "    H(register[0]);\n",
    "    // |010...0⟩ + |110...0⟩\n",
    "    T(register[0]);\n",
    "    within { X(register[0]); }\n",
    "    apply { Adjoint T(register[0]); }\n",
    "\n",
    "    QFT(BigEndian(register));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.5 of the QFT kata.](./QFT.ipynb#Task-2.5.-Prepare-a-square-wave-signal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.6. Get the frequency of a signal\n",
    "\n",
    "**Input:** \n",
    "\n",
    "A register of $n\\geq2$ qubits in state \n",
    "$\\frac{1}{\\sqrt{2^{n}}} \\sum_k e^{2\\pi i \\cdot \\frac{Fk}{2^{n}}} |k\\rangle$, $0\\leq F\\leq 2^{n}-1$.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Return the frequency F of the \"signal\" encoded in this state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "The original Fourier transform will give a time-domain signal's decomposition in the frequency domain, and the inverse Fourier transform will give a frequency-domain signal's time-domain representation.\n",
    "\n",
    "Keeping this in mind, if we already have the QFT of a state *F* in standard format, the value of *F* can be found by applying the inverse QFT to this register and then measuring the qubits. Since the [QFT](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.qft) operation is adjointable, this is very easy to do. \n",
    "\n",
    "Note that the iQFT takes a big endian register as input, but the [ResultArrayAsInt](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.resultarrayasint) function assumes little endian format of the bit string representation, so you'll need to reverse the array before converting it to an integer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T26_Frequency \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation Frequency (register : Qubit[]) : Int {\n",
    "    Adjoint QFT(BigEndian(register));\n",
    "    let bitsBE = MultiM(register);\n",
    "    return ResultArrayAsInt(Reversed(bitsBE));\n",
    "}       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.6 of the QFT kata.](./QFT.ipynb#Task-2.6.-Get-the-frequency-of-a-signal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Powers and roots of the QFT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1 Implement powers of the QFT\n",
    "    \n",
    "**Inputs:** \n",
    "\n",
    "  1. A register of $n$ qubits in an arbitrary state.\n",
    "\n",
    "  2. An integer $P$ ($ 0 \\leq P \\leq 2^{20} - 1 $).\n",
    "    \n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Transform state $|x\\rangle$ into state $ QFT^{P} |x\\rangle$, where $QFT$ is the quantum Fourier transform implemented in part I.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "Your solution has to run fast for any $P$ in the given range!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "Let $QFT_{2^n} = \\frac{1}{\\sqrt{2^n}}[\\omega_{2^n}^{k \\ell}]_{k,\\ell=0,\\ldots,2^n -1 }$, where $\\omega_{2^n}=\\exp(2\\pi i /2^n)$ is a primitive $2^n$ complex root of unity.\n",
    "\n",
    "We will first show that the operator $QFT_{2^n}$ has a small multiplicative order, namely $QFT_{2^n}^4 = \\mathbb{1}_{2^n}$. To see this, denote $M=[m_{\\ell,\\ell^\\prime}]=\\big( QFT_{2^n} \\big)^2$. We compute the coefficients of $M$ as $m_{\\ell,\\ell^\\prime} = \\sum_{k = 0}^{2^n-1} \\omega_{2^n}^{k(\\ell+\\ell^\\prime)} = \\delta_{\\ell,2^n-\\ell^\\prime}$. This means that $M$ is a permutation matrix  that looks like this: \n",
    "\n",
    "$$M=\\left[ \\begin{array}{cccc} 1 & 0 & \\cdots & 0 \\\\ 0 & 0 & \\cdots & 1 \\\\ \\vdots & & \\ddots & \\\\ 0 & 1 & & 0 \\end{array}\\right]$$\n",
    "\n",
    "Note that $M$ is an involution, i.e., $M^2=\\mathbb{1}_{2^n}$, which means that $QFT_{2^n}^4=\\mathbb{1}_{2^n}$. Therefore, for a given positive power $P$, we only have to compute the residue $p = P \\; {\\rm mod} \\; 4$ and apply $QFT_{2^n}^p$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_QFTPower\n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation QFTPower (P : Int, inputRegister : Qubit[]) : Unit is Adj+Ctl {\n",
    "    for _ in 1 .. (P % 4) {\n",
    "        QFT(BigEndian(inputRegister));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.1 of the QFT kata.](./QFT.ipynb#Task-3.1-Implement-powers-of-the-QFT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. Implement roots of the QFT\n",
    "**Inputs:** \n",
    "\n",
    "  1. A register of $n$ qubits in an arbitrary state.\n",
    "\n",
    "  2. An integer $P$ ($ 2 \\leq P \\leq 8 $).\n",
    "    \n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Transform state $|x\\rangle$ into state $V |x\\rangle$, where $V^{P} = QFT$. In other words, implement a $P^{th}$ root of the $QFT$. You can implement the required unitary up to a global phase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "A matrix $A$ having the property $A^\\alpha = B$ with a real $\\alpha$\n",
    "is called an $\\alpha$-th root of $B$ (in general this root is\n",
    "not uniquely determined). In case of the discrete Fourier transform\n",
    "$B=QFT$ we can define an\n",
    "$\\alpha$-th root of $QFT_{2^n}$ via an ansatz\n",
    "\n",
    "\\begin{equation}\n",
    "QFT_{2^n, \\alpha} := a_0(\\alpha) \\cdot \\mathbb{1}_{2^n} + a_1(\\alpha) F_{2^n} + a_2(\\alpha) F_{2^n}^2 +\n",
    "a_3(\\alpha) F_{2^n}^3,\n",
    "\\end{equation}\n",
    "where $F_{2^n}=QFT_{2^n}$, as any function that is defined on the eigenvalue of an operator can be expressed as a Taylor series of the operator. \n",
    "Since the order of $F_{2^n}$ is four (as shown in task 3.1), the series can be re-arranged into the form given above. \n",
    "\n",
    "Explicitly, we find that the coefficients $a_i(\\alpha)$ for $i=0,\\ldots,3$ are given by\n",
    "\n",
    "\\begin{equation}\n",
    "\\begin{array}{l@{,\\;\\;}l}\n",
    "a_0(\\alpha) := \\frac{1}{2} (\\phantom{{-}}1 {+} e^{i \\alpha}) \\cos{\\alpha} \\\\\n",
    "a_1(\\alpha) := \\frac{1}{2} (\\phantom{{-}}1 {-} i e^{i \\alpha})\\sin{\\alpha} \\\\\n",
    "a_2(\\alpha) := \\frac{1}{2} ({-}1 {+} e^{i \\alpha}) \\cos{\\alpha} \\\\\n",
    "a_3(\\alpha) := \\frac{1}{2} ({-}1 {-} i e^{i \\alpha}) \\sin{\\alpha} \\\\\n",
    "\\end{array}\n",
    "\\end{equation}\n",
    "\n",
    "It is possible to show that the one-parameter family\n",
    "$\\{ QFT_{2^n, \\alpha} \\;|\\; \\alpha \\in \\mathbb{R}\\} \\subset {\\mathbb{C}}^{N\\times N}$ has the\n",
    "following properties:\n",
    "\n",
    "1. $QFT_{2^n, \\alpha}$ is a unitary matrix for $\\alpha \\in \\mathbb{R}$.\n",
    "2. $QFT_{2^n, 0} = \\mathbb{1}_{2^n}$ and $QFT_{2^n, \\pi/2} = QFT_{2^n}$. \n",
    "3. $(QFT_{2^n,\\alpha})^{\\pi/(2\\alpha)} = QFT_{2^n}$ for $\\alpha \\in \\mathbb{R}$.\n",
    "\n",
    "We will use property 3 for $\\alpha=\\pi/(2P)$ to obtain a unitary operator $R = QFT_{2^n,\\pi/(2P)}$ such that $R^P = QFT_{2^n}$, i.e., $R$ is the required $P$-th root of the Fourier transform $QFT_{2^n}$. \n",
    "\n",
    "The remaining question is how to find an implementation of $QFT_{2^n, \\alpha}$. To derive a circuit, we note that the additive decomposition above can be used to implement $QFT_{2^n, \\alpha}$ as shown in the circuit below. \n",
    "\n",
    "<img src=\"./images/fractional-qft.PNG\"/>\n",
    "\n",
    "In this circuit there is a circulant matrix $C_\\alpha :=\n",
    "{\\rm circ}(a_0(\\alpha),\\ldots,a_3(\\alpha))$. \n",
    "Recall that a circulant matrix ${\\rm circ}_G(a_0, \\ldots, a_{n-1}) := (a_{j-i \\; {\\rm mod}\\; n})_{i, j=0, \\ldots n-1}$ can be diagonalized by the Fourier transform. In our case, we find that \n",
    "$$C_\\alpha = {\\rm circ}(a_0(\\alpha), \\ldots, a_3(\\alpha)) = QFT_4^{-1} \\cdot\n",
    "{\\rm diag}(1, e^{-i \\alpha}, e^{2 i \\alpha}, e^{-i \\alpha}) \\cdot QFT_4$$.\n",
    "\n",
    "For more information about this decomposition, which is a special case of a linear combinations of unitaries (LCU) method for the case in which the operator has finite order, see [A. Klappenecker and M. Roetteler.  Quantum software reusability](https://arxiv.org/abs/quant-ph/0309121).\n",
    "\n",
    "The cell below implements the helper operation for $C_\\alpha$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Circ (qs : LittleEndian, alpha : Double) : Unit is Adj + Ctl {\n",
    "    within {\n",
    "        Adjoint QFTLE(qs);\n",
    "    } apply {\n",
    "        ApplyDiagonalUnitary(\n",
    "            [0.0, -alpha, -2.0 * alpha, alpha],\n",
    "            qs\n",
    "        );\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_QFTRoot\n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation QFTRoot (P : Int, inputRegister : Qubit[]) : Unit is Adj + Ctl {\n",
    "    use aux = Qubit[2];\n",
    "    let Q = QFT;\n",
    "    let Q2 = OperationPowCA(Q, 2);\n",
    "    within {\n",
    "        ApplyToEachCA(H, aux);\n",
    "        Controlled Adjoint Q([aux[0]], BigEndian(inputRegister));\n",
    "        Controlled Adjoint Q2([aux[1]], BigEndian(inputRegister));\n",
    "    } apply {\n",
    "        Circ(LittleEndian(aux), PI() / (2.0 * IntAsDouble(P))); \n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.2 of the QFT kata.](./QFT.ipynb#Task-3.2.-Implement-roots-of-the-QFT)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}