PhaseEstimation/PhaseEstimation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Phase Estimation\n",
    "\n",
    "The **\"Phase Estimation\"** quantum kata is a series of exercises designed\n",
    "to teach you the basics of using phase estimation algorithms.\n",
    "\n",
    "It covers the following topics:\n",
    "* quantum phase estimation,\n",
    "* iterative phase estimation,\n",
    "* preparing necessary inputs to phase estimation routines and applying them.\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. Quantum Phase Estimation (QPE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Inputs to QPE: eigenstates of Z/S/T gates.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "  2. An integer `state` indicating which eigenstate to prepare.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Prepare one of the eigenstates of Z gate (which are the same as eigenstates of S or T gates): \n",
    "eigenstate $|0\\rangle$ if `state = 0`, or eigenstate $|1\\rangle$ if `state = 1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_Eigenstates_ZST \n",
    "\n",
    "operation Eigenstates_ZST (q : Qubit, state : Int) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Inputs to QPE: powers of Z/S/T gates.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A single-qubit unitary U.\n",
    "\n",
    "  2. A positive integer `power`.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "A single-qubit unitary equal to U raised to the given power.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Remember that you can define auxiliary operations. To do that, you'll need to create an extra code cell for each new operation and execute it before returning to this cell. \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_UnitaryPower \n",
    "\n",
    "function UnitaryPower (U : (Qubit => Unit is Adj + Ctl), power : Int) : (Qubit => Unit is Adj + Ctl) {\n",
    "    // ...\n",
    "    return ...;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Validate inputs to QPE.\n",
    "\n",
    "<span style=\"color:red\"><b>This task is temporarily not available in Notebook format; please use Q# project version of the PhaseEstimation kata to complete it.</b></span>\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. A single-qubit unitary U.\n",
    "\n",
    "  2. A single-qubit state $|\\psi\\rangle$ represented by a unitary P such that $|\\psi\\rangle = P|0\\rangle$\n",
    "(i.e., applying the unitary P to state $|0\\rangle$ prepares state $|\\psi\\rangle$).\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Assert that the given state is an eigenstate of the given unitary, \n",
    "i.e., do nothing if it is, and throw an exception if it is not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. QPE for single-qubit unitaries.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A single-qubit unitary U.\n",
    "\n",
    "  2. A single-qubit state $|\\psi\\rangle$ represented by a unitary P such that $|\\psi\\rangle = P|0\\rangle$\n",
    "(i.e., applying the unitary P to state $|0\\rangle$ prepares state $|\\psi\\rangle$).\n",
    "\n",
    "  3. An integer `n`.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "The phase of the eigenvalue that corresponds to the eigenstate $|\\psi\\rangle$, with `n` bits of precision.\n",
    "The phase should be between 0.0 and 1.0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_QPE \n",
    "\n",
    "operation QPE (U : (Qubit => Unit is Adj + Ctl), P : (Qubit => Unit is Adj), n : Int) : Double {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. Test your QPE implementation.\n",
    "\n",
    "**Goal:**\n",
    "Use your QPE implementation from task 1.4 to run quantum phase estimation \n",
    "on several simple unitaries and their eigenstates.\n",
    "This task is not covered by a test and allows you to experiment with running the algorithm.\n",
    "\n",
    "> This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_QPE` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_QPE`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_QPE () : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_QPE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Iterative Phase Estimation\n",
    "\n",
    "Unlike quantum phase estimation, which is a single algorithm, \n",
    "iterative phase estimation is a whole class of algorithms based on the same idea:\n",
    "treating phase estimation as a classical algorithm which learns the phase via a sequence of measurements\n",
    "(the measurement performed on each iteration can depend on the outcomes of previous iterations).\n",
    "\n",
    "A typical circuit for one iteration has the following structure:\n",
    "\n",
    "![Iterative Phase Estimation Circuit Diagram](./img/IPE_Circuit.PNG)\n",
    "\n",
    "($\\psi$ is the procedure to prepare the eigenstate $|\\psi\\rangle$, R is a rotation gate, and M is a power of the unitary U;\n",
    "both depend on the current information about the phase).\n",
    "\n",
    "The result of the measurement performed on the top qubit defines the next iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Single-bit phase estimation.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. A single-qubit unitary U that is guaranteed to have an eigenvalue $+1$ or $-1$ \n",
    "(with eigenphases $0.0$ or $0.5$, respectively).\n",
    "\n",
    "  2. A single-qubit state $|\\psi\\rangle$ represented by a unitary P such that $|\\psi\\rangle = P|0\\rangle$\n",
    "(i.e., applying the unitary P to state $|0\\rangle$ prepares state $|\\psi\\rangle$).\n",
    "\n",
    "**Output:** \n",
    "\n",
    "The eigenvalue which corresponds to the eigenstate $|\\psi\\rangle$ ($+1$ or $-1$).\n",
    "\n",
    "You are allowed to allocate exactly two qubits and call `Controlled U` exactly once.\n",
    "\n",
    "> It is possible to use the QPE implementation from task 1.4 to solve this task,\n",
    "  but we suggest you implement the circuit by hand for the sake of learning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_SingleBitPE \n",
    "\n",
    "operation SingleBitPE (U : (Qubit => Unit is Adj + Ctl), P : (Qubit => Unit is Adj)) : Int {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Two bit phase estimation.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. A single-qubit unitary U that is guaranteed to have an eigenvalue $+1$, $i$, $-1$ or $-i$\n",
    "(with eigenphases $0.0$, $0.25$, $0.5$ or $0.75$, respectively).\n",
    "\n",
    "  2. A single-qubit state $|\\psi\\rangle$ represented by a unitary P such that $|\\psi\\rangle = P|0\\rangle$\n",
    "(i.e., applying the unitary P to state $|0\\rangle$ prepares state $|\\psi\\rangle$).\n",
    "\n",
    "**Output:**\n",
    "\n",
    "The eigenphase which corresponds to the eigenstate $|\\psi\\rangle$ ($0.0$, $0.25$, $0.5$ or $0.75$).\n",
    "The returned value has to be accurate within the absolute error of 0.001.\n",
    "\n",
    "You are allowed to allocate exactly two qubits and call `Controlled U` multiple times.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Start by applying the same circuit as in task 2.1.  \n",
    "  What are the possible outcomes for each eigenvalue?  \n",
    "  What eigenvalues you can and can not distinguish using this circuit?\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need another hint? Click here</b></summary>\n",
    "  What eigenvalues you can and can not distinguish using this circuit?\n",
    "  What circuit you can apply to distinguish them?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_TwoBitPE \n",
    "\n",
    "operation TwoBitPE (U : (Qubit => Unit is Adj + Ctl), P : (Qubit => Unit is Adj)) : Double {\n",
    "    // ...\n",
    "    return -1.0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be continued..."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}