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",
    "**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.\n",
    "\n",
    "> Note that since this task requires you to throw an exception in some cases, its test consists of two parts:\n",
    "> * The first part of the test, executed when you run the cell containing the solution code, checks that your solution _does not_ throw an exception if the given state _is_ an eigenstate of the given unitary.\n",
    "> * The second part of the test is provided in the second code cell (operation `TestAssertIsEigenstate_False`). This operation runs your solution on several pairs of unitaries and states that are _not_ the eigenstates of those unitaries, and thus it _should_ throw an exception on each pair. To test this, run this operation as is using the `%simulate` cell below it to test that your solution throws an exception for the first pair, then comment out the first line and run it again to test that your solution throws an exception for the second pair, and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata TestAssertIsEigenstate_True\n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation AssertIsEigenstate (U : Qubit => Unit, P : Qubit => Unit is Adj) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "operation TestAssertIsEigenstate_False () : Unit {\n",
    "    // Each of these lines runs your solution on a unitary and a state that is not its eigenstate.\n",
    "    // Run the code as is to test that your solution throws an exception for the first pair, \n",
    "    // then comment out the first line and run it again \n",
    "    // to test that your solution throws an exception for the second pair, \n",
    "    // and so on.\n",
    "    AssertIsEigenstate(Z, H);\n",
    "    AssertIsEigenstate(X, X);\n",
    "    AssertIsEigenstate(X, Z);\n",
    "    AssertIsEigenstate(Y, H);\n",
    "    AssertIsEigenstate(Y, X);\n",
    "    AssertIsEigenstate(Y, Z);\n",
    "    // Feel free to come up with your own tests as well!\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate TestAssertIsEigenstate_False"
   ]
  },
  {
   "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.24"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}