tutorials/RandomNumberGeneration/RandomNumberGenerationTutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Random Number Generation Tutorial\n",
    "\n",
    "True random number generation is a notoriously difficult problem. Many \"random\" generators today are actually pseudo-random, using a starting seed to spawning seemingly-random numbers that are actually a repeatable function of that seed. Most true random number generations are based on measurements of some natural phenomenon, such as atmospheric noise or atomic decay. \n",
    "(You can read more about it [here]( https://en.wikipedia.org/wiki/Random_number_generation).) \n",
    "\n",
    "Quantum random number generators (QRNGs) are truly random. Of course, this only applies to the case when they're running on a real quantum device, relying on the randomness of the quantum state collapse during measurement to produce the random numbers. When QRNGs run on a simulator, the source of randomness is the same as for other classical programs, so the generated numbers are pseudo-random. The quantum algorithm for random number generation is one of the simplest applications of quantum computing principles, requiring very few qubits to run.\n",
    "\n",
    "In this tutorial you will:\n",
    "* learn about quantum random number generation and the principles behind it,\n",
    "* implement a variety of QRNGs with equal probability of any given number,\n",
    "* implement a single-bit QRNG with weighted probabilities of generated bits.\n",
    "\n",
    "Let's go!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Recall from the [Qubit](../Qubit/Qubit.ipynb) tutorial that a qubit state $|\\psi\\rangle$ is defined via the basis states $|0\\rangle$ and $|1\\rangle$ as:\n",
    "\n",
    "$$|\\psi\\rangle = \\begin{bmatrix} \\alpha \\\\ \\beta \\end{bmatrix} = \\alpha|0\\rangle + \\beta|1\\rangle\\text{, where }|\\alpha|^2 + |\\beta|^2 = 1$$\n",
    "\n",
    "We call $\\alpha$ and $\\beta$ the **amplitudes** of states $|0\\rangle$ and $|1\\rangle$, respectively. \n",
    "When $|\\psi\\rangle$ is measured in the $\\{|0\\rangle, |1\\rangle\\}$ basis (the computational basis), the probabilities of the outcomes are defined based on the state amplitudes: there is a $|\\alpha|^2$ probability that the measurement result will be $0$, and a $|\\beta|^2$ probability that the measurement result will be $1$.\n",
    "\n",
    "> For example, a qubit in state $\\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} \\end{bmatrix}$ will yield measurement results $0$ or $1$ with equal probability, while a qubit in state $\\begin{bmatrix} \\frac{1}{2} \\\\ \\frac{\\sqrt3}{2} \\end{bmatrix}$ will yield measurement result $0$ only 25% of the time, and $1$ 75% of the time.\n",
    "\n",
    "This is sufficient to implement a simple random number generator!\n",
    "\n",
    "> Remember that you can refer to the [Single Qubit Gates tutorial](../SingleQubitGates/SingleQubitGates.ipynb) if you need a refresher on the various quantum gates and their usage in Q#."
   ]
  },
  {
   "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",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    Use the allocated qubit, apply a quantum gate to it, measure it and use the result to return a $0$ or $1$.\n",
    "</details>\n",
    "\n",
    "**Stretch goal:** Can you find a different way to implement this operation?\n",
    "\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "    What are the different quantum states that produce $0$ and $1$ measurement results with the same probability? How would measuring the qubit in a different basis change the result? \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_RandomBit\n",
    "\n",
    "operation RandomBit () : Int {\n",
    "    use q = Qubit();\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Quantum Random Number Generation Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T2_RandomTwoBits\n",
    "\n",
    "operation RandomTwoBits () : Int {\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Quantum Random Number Generation Workbook](./Workbook_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",
    "Let's take it a step further and generate an $N$-bit number. \n",
    "\n",
    "> Remember that you can use previously defined operations in your solution.\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.\n",
    "\n",
    "> Useful Q# documentation: \n",
    "> * [`for` loops](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/iterations), \n",
    "> * [mutable variables](https://docs.microsoft.com/azure/quantum/user-guide/language/typesystem/immutability), \n",
    "> * [exponents](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.math.powi)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T3_RandomNBits \n",
    "\n",
    "operation RandomNBits (N : Int) : Int {\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Quantum Random Number Generation Workbook](./Workbook_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$.\n",
    "\n",
    "> Useful Q# documentation: \n",
    "> * [`Math` namespace](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.math)\n",
    "> * [`ArcCos` function](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.math.arccos)\n",
    "> * [`Sqrt` function](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.math.sqrt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_WeightedRandomBit\n",
    "\n",
    "operation WeightedRandomBit (x : Double) : Int {\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Quantum Random Number Generation Workbook](./Workbook_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.\n",
    "\n",
    "> Useful Q# documentation: \n",
    "> * [`BitSizeI` function](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.math.bitsizei)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_RandomNumberInRange\n",
    "\n",
    "operation RandomNumberInRange (min : Int, max : Int) : Int {\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Quantum Random Number Generation Workbook](./Workbook_RandomNumberGenerationTutorial.ipynb#Exercise-5:-Generate-a-random-number-between-min-and-max).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What's Next?\n",
    "We hope you enjoyed this tutorial on quantum random number generation! If you're looking to learn more about quantum computing and Q#, here are some suggestions:\n",
    "* The [Quantum Katas](https://github.com/microsoft/QuantumKatas/) are sets of programming exercises on quantum computing that can be solved using Q#. They cover a variety of topics, from the basics like the concepts of superposition and measurements to more interesting algorithms like Grover's search.\n",
    "* For another look at quantum random number generation, you can check out the [Microsoft Learn module \"Create your first Q# program by using the Quantum Development Kit\"](https://docs.microsoft.com/learn/modules/qsharp-create-first-quantum-development-kit/1-introduction)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.27"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}