QFT/QFT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Fourier Transforms\n",
    "\n",
    "The **\"QFT (Quantum Fourier Transform)\"** quantum kata is a series of exercises designed\n",
    "to teach you the basics of quantum Fourier transform (QFT). It covers implementing QFT and using\n",
    "it to perform simple state transformations.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty; \n",
    "harder ones are marked with asterisks."
   ]
  },
  {
   "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."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_OneQubitQFT \n",
    "\n",
    "operation OneQubitQFT (q : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_Rotation \n",
    "\n",
    "operation Rotation (q : Qubit, k : Int) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_BinaryFractionClassical \n",
    "\n",
    "operation BinaryFractionClassical (q : Qubit, j : Int[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_BinaryFractionQuantum \n",
    "\n",
    "operation BinaryFractionQuantum (q : Qubit, jRegister : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  This task is very similar to task 1.4, but the digit $j_1$ is encoded in-place, using task 1.1.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_BinaryFractionQuantumInPlace \n",
    "\n",
    "operation BinaryFractionQuantumInPlace (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T16_ReverseRegister \n",
    "\n",
    "operation ReverseRegister (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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.\n",
    "\n",
    "> You can do this with a library call, but we recommend\n",
    "implementing the algorithm yourself for learning purposes, using the previous tasks.\n",
    "\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Consider preparing a different state first and transforming it to the goal state:\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",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_QuantumFourierTransform \n",
    "\n",
    "operation QuantumFourierTransform (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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$.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Inverse QFT is literally the inverse transformation of QFT.\n",
    "Do you know a quantum way to express this?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T18_InverseQFT \n",
    "\n",
    "operation InverseQFT (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_QFT.ipynb#Task-1.8.-Inverse-QFT).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Using the Quantum Fourier Transform\n",
    "\n",
    "This section offers you tasks on state preparation and state analysis \n",
    "that can be solved using QFT (or inverse QFT). It is possible to solve them \n",
    "without QFT, but we recommend that you to try and come up with a QFT-based solution."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_PrepareEqualSuperposition \n",
    "\n",
    "operation PrepareEqualSuperposition (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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)$.\n",
    "\n",
    "> If you're using `DumpMachine` to debug your solution, \n",
    "remember that this kata uses big endian encoding of states,\n",
    "while `DumpMachine` uses little endian encoding.\n",
    "You can use [`%config` magic command](https://docs.microsoft.com/en-us/qsharp/api/iqsharp-magic/config) \n",
    "to reconfigure `DumpMachine` to use big endian encoding or bit strings.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Which basis state can be mapped to this state using QFT?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_PreparePeriodicState \n",
    "\n",
    "operation PreparePeriodicState (register : Qubit[], F : Int) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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)$.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Which basis state can be mapped to this state using QFT?  Which frequency would allow you to use task 2.2 here?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_PrepareAlternatingState \n",
    "\n",
    "operation PrepareAlternatingState (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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)$.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Which superposition of two basis states can be mapped to this state using QFT?\n",
    "    Use the solutions to tasks 2.1 and 2.3 to figure out the answer.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_PrepareEqualSuperpositionOfEvenStates \n",
    "\n",
    "operation PrepareEqualSuperpositionOfEvenStates (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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)$$\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Which superposition of two basis states can be mapped to this state using QFT?\n",
    "    Remember that sum of two complex amplitudes can be a real number if their imaginary parts cancel out.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_PrepareSquareWaveSignal \n",
    "\n",
    "operation PrepareSquareWaveSignal (register : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T26_Frequency \n",
    "\n",
    "operation Frequency (register : Qubit[]) : Int {\n",
    "    // ...\n",
    "\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_QFTPower\n",
    "\n",
    "operation QFTPower (P : Int, inputRegister : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_QFTRoot\n",
    "\n",
    "operation QFTRoot (P : Int, inputRegister : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [QFT Workbook](./Workbook_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": 2
}