tutorials/RandomNumberGeneration/Workbook_RandomNumberGenerationTutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Random Number Generation 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 [Random Number Generation Tutorial](./RandomNumberGenerationTutorial.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 Quantum Random Number Generation Tutorial (and this workbook):\n",
    "\n",
    "1. The concept of qubit and measurement\n",
    "2. Single-qubit gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 1</span>: Generate a single random bit\n",
    "\n",
    "**Input:** None.\n",
    "\n",
    "**Goal:** Generate a $0$ or $1$ with equal probability.\n",
    "\n",
    "**Stretch goal:** Can you find a different way to implement this operation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The state of single qubit can be represented as a two-dimensional column vector $\\begin{bmatrix} \\alpha\\\\ \\beta \\end{bmatrix}$, where $\\alpha$ and $\\beta$ are complex numbers that satisfy $|\\alpha|^2 + |\\beta|^2 = 1$. When we measure the qubit, we get either 0 with probability $|\\alpha|^2$ or 1 with probability $|\\beta|^2$. Essentially we can control probablity of measurement outcome by setting the right amplitudes of basis states. \n",
    "\n",
    "When we allocate the qubit in Q#, amplitudes $\\alpha$ and $\\beta$ are 1 and 0, respectively. Now our goal is set equal amplitudes for $\\alpha$ and $\\beta$ for absolute randomness. We can achieve that by simply applying Hadamard gate to the initial state $|0\\rangle$:\n",
    "\n",
    "$$\n",
    "H|0\\rangle=\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1 & 1 \\\\\n",
    "   1 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   1\\\\\n",
    "   0\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1 \\cdot 1 + 1 \\cdot 0 \\\\\n",
    "   1 \\cdot 1 + (-1) \\cdot 0\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "  \\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   1\n",
    "  \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Now, both 0 and 1 measurement outcomes occur with equal probablity of $|\\frac{1}{\\sqrt{2}}|^2 = \\frac{1}{2}$.\n",
    "\n",
    "> Note: Since probablity is the square of the absolute value of amplitude, we will get the same randomness by applying Hadamard gate on base state $|1\\rangle$. Try it out as an exercise!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_RandomBit\n",
    "\n",
    "operation RandomBit () : Int {\n",
    "    // Allocate single qubit\n",
    "    use q = Qubit();\n",
    "    \n",
    "    // Set qubit in superposition state\n",
    "    H(q);\n",
    "    \n",
    "    // Measuring state of qubit and return integer value of result\n",
    "    return (M(q) == Zero) ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 1 of the Quantum Random Number Generation tutorial.](./RandomNumberGenerationTutorial.ipynb#Exercise-1:-Generate-a-single-random-bit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 2</span>: Generate a random two-bit number\n",
    "\n",
    "Now that you can generate a single random bit, you can use that logic to create random multi-bit numbers. Let's try first to make a two-bit number by combining two randomly generated bits.\n",
    "\n",
    "**Input:** None.\n",
    "\n",
    "**Goal:** Generate a random number in the range $[0, 3]$ with an equal probability of getting each of the four numbers.\n",
    "\n",
    "**Stretch goal:** Can you do this without allocating qubits in this operation?\n",
    "\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    Remember that you can use the previously defined operations.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's reuse `RandomBit` operation from [Exercise 1](#Exercise-1:-Generate-a-single-random-bit).\n",
    "We can generate two random bits by calling `RandomBit` operation twice, multiply the most significant bit by 2 and add the second random bit to generate a random two-bit number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T2_RandomTwoBits\n",
    "\n",
    "operation RandomTwoBits () : Int {\n",
    "    return 2 * RandomBit() + RandomBit();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 2 of the Quantum Random Number Generation tutorial.](./RandomNumberGenerationTutorial.ipynb#Exercise-2:-Generate-a-random-two-bit-number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 3</span>: Generate a number of arbitrary size\n",
    "\n",
    "**Input:** An integer $N$ ($1 \\le N \\le 10$).\n",
    "\n",
    "**Goal:** Generate a random number in the range $[0, 2^N - 1]$ with an equal probability of getting each of the numbers in this range."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's reuse `RandomBit` operation from [Exercise 1](#Exercise-1:-Generate-a-single-random-bit) again.\n",
    "We'll generate N random bits by calling `RandomBit` operation N times, and treat the result as a binary notation to convert it into an integer.\n",
    "Since the maximum value of the number written with N bits is $2^N - 1$, we don't need to do any extra checks to ensure that the result is within the given range."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T3_RandomNBits \n",
    "\n",
    "operation RandomNBits (N : Int) : Int {\n",
    "    mutable result = 0;\n",
    "    for i in 0 .. N - 1 {\n",
    "        set result = result * 2 + RandomBit();\n",
    "    }\n",
    "    return result;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 3 of the Quantum Random Number Generation tutorial.](./RandomNumberGenerationTutorial.ipynb#Exercise-3:-Generate-a-number-of-arbitrary-size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 4</span>: Generate a weighted bit!\n",
    "\n",
    "In each of the above exercises, all generated numbers were equally likely. Now let's create an operation that will return a random bit with different probabilities of outcomes. \n",
    "\n",
    "> Remember that by setting amplitudes of basis states $\\alpha$ and $\\beta$, we can control the probability of getting measurement outcomes $0$ and $1$ when the qubit is measured.\n",
    "\n",
    "**Input:** \n",
    "A floating-point number $x$, $0 \\le x \\le 1$. \n",
    "\n",
    "**Goal:** Generate $0$ or $1$ with probability of $0$ equal to $x$ and probability of $1$ equal to $1 - x$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We already learnt how to generate random bit with equal probability in exercise 1, in this exercise we need to generate random bit with weighted probability.\n",
    "\n",
    "An arbitrary single-qubit state can be written as:\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle =\n",
    "    \\cos \\frac{\\theta}{2} |0 \\rangle \\, + \\, e^{i\\phi}  \\sin \\frac{\\theta}{2} |1\\rangle\n",
    "$$\n",
    "\n",
    "Here $\\theta$ is angle between state vector and $Z$-axis, and $\\phi$ is longitude angle with respect to $X$-axis on the Bloch sphere.\n",
    "\n",
    "Our goal is to generate 0 or 1 with probability of 0 equal to $x$ and probability of 1 equal to $1 - x$, which means the qubit state should look like\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle =\n",
    "    \\sqrt x |0 \\rangle + \\sqrt{1 - x} |1\\rangle\n",
    "$$\n",
    "\n",
    "By comparing the amplitudes of the state $|0 \\rangle$ on both equations we get\n",
    "\n",
    "$$\n",
    "\\sqrt x = \\cos \\frac{\\theta}{2} \\Rightarrow \\theta = 2 \\arccos\\sqrt x\n",
    "$$\n",
    "\n",
    "Since $\\theta$ is angle between state vector and the $Z$-axis, we need to apply the [Ry](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) gate with caculated $\\theta$ to the starting state $|0 \\rangle$ to get the desired qubit state.\n",
    "\n",
    "Ry operation applies a given rotation about $Y$-axis (i.e., in the $ZX$-plane), hence $\\phi$ (longitude angle with respect to $X$-axis) is always equal to $0^{\\circ}$, which means that the relative phase $e^{i\\phi}$ doesn't have any impact on resulting qubit state.\n",
    "\n",
    "> We can also calculate ${\\theta}$ by comparing the amplitudes of the state $|1 \\rangle$ on both equations, which is $2 \\arcsin\\sqrt{1.0 - x}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_WeightedRandomBit\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation WeightedRandomBit (x : Double) : Int {\n",
    "    // Calculate theta value\n",
    "    let theta = 2.0 *  ArcCos(Sqrt(x));  // (or) 2.0 * ArcSin(Sqrt(1.0 - x));\n",
    "\n",
    "    // Allocate single qubit\n",
    "    use q = Qubit();\n",
    "\n",
    "    // Set qubit in superposition state which aligns with given probabilities\n",
    "    Ry(theta, q);\n",
    "\n",
    "    // Measuring state of qubit and return integer value of result\n",
    "    return M(q) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 4 of the Quantum Random Number Generation tutorial.](./RandomNumberGenerationTutorial.ipynb#Exercise-4:-Generate-a-weighted-bit!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 5</span>: Generate a random number between min and max\n",
    "\n",
    "In exercise 3, we generated numbers in the range $[0, 2^N-1]$ $(1 \\leq N \\leq 10)$. Now let's create an operation that will return a random number in the range $[min, max]$. \n",
    "\n",
    "**Input:** \n",
    "Two integers $min$ and $max$ ($0 \\leq min \\leq max \\leq 2^{10}-1$).\n",
    "\n",
    "**Goal:** Generate a random number in the range $[min, max]$ with an equal probability of getting each of the numbers in this range."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We can reuse `RandomNBits` operation from [Exercise 3](#Exercise-3:-Generate-a-number-of-arbitrary-size).\n",
    "\n",
    "We'll generate an N-bit random number by calling `RandomNBits` operation, where N is the bitsize of $max - min$. We can repeat this process until the result is less than or equal than $max - min$, and return that number plus $min$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_RandomNumberInRange\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation RandomNumberInRange (min : Int, max : Int) : Int {\n",
    "    // Set nBits as bitsize of (max - min)\n",
    "    let nBits = BitSizeI(max - min);\n",
    "\n",
    "    // Declare result variable with mutable binding\n",
    "    mutable result = 0;\n",
    "    \n",
    "    repeat {\n",
    "        set result = RandomNBits(nBits);\n",
    "    } until result <= max - min;\n",
    "\n",
    "    return result + min;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 5 of the Quantum Random Number Generation tutorial.](./RandomNumberGenerationTutorial.ipynb#Exercise-5:-Generate-a-random-number-between-min-and-max)"
   ]
  }
 ],
 "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": 4
}