KeyDistribution_BB84/KeyDistribution_BB84.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Key Distribution Kata\n",
    "\n",
    "The **Quantum Key Distribution** kata is a series of exercises designed to teach you about a neat quantum technology where you can use qubits to exchange secure cryptographic keys. In particular, you will work through implementing and testing a quantum key distribution protocol called [BB84](https://en.wikipedia.org/wiki/BB84). \n",
    "\n",
    "### Background\n",
    "\n",
    "What does a key distribution protocol look like in general? Normally there are two parties, commonly referred to as Alice and Bob, who want to share a random, secret string of bits called a _key_. This key can then be used for a variety of different [cryptographic protocols](https://en.wikipedia.org/wiki/Cryptographic_protocol) like encryption or authentication. Quantum versions of key exchange protocols look very similar, and utilize qubits as a way to securely transmit the bit string. \n",
    "\n",
    "<img src=\"./img/qkd-concept.png\" alt=\"General schematic for QKD protocol\" width=\"60%\"/>\n",
    "\n",
    "You can see in the figure above that Alice and Bob have two connections, one quantum channel and one bidirectional classical channel. In this kata you will simulate what happens on the quantum channel by preparing and measuring a sequence of qubits and then perform classical operations to transform the measurement results to a usable, binary key.\n",
    "\n",
    "There are a variety of different quantum key distribution protocols, however the most common is called [BB84](https://en.wikipedia.org/wiki/BB84) after the initials of the authors and the year it was published. It is used in many existing commercial quantum key distribution devices that implement BB84 with single photons as the qubits. \n",
    "\n",
    "#### For more information:\n",
    "* [Introduction to quantum cryptography and BB84](https://www.youtube.com/watch?v=UiJiXNEm-Go).\n",
    "* [QKD summer school lecture on quantum key distribution](https://www.youtube.com/watch?v=oEJOtu0joXk).\n",
    "* [Key Distribution Wikipedia article](https://en.wikipedia.org/wiki/Quantum_key_distribution).\n",
    "* [BB84 protocol Wikipedia article](https://en.wikipedia.org/wiki/BB84).\n",
    "* [Short animated video introducing BB84 protocol](https://www.youtube.com/watch?v=UVzRbU6y7Ks).\n",
    "* [Updated version of the BB84 paper](https://www.sciencedirect.com/science/article/pii/S0304397514004241?via%3Dihub).\n",
    "\n",
    "---\n",
    "### Instructions\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "\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.\n",
    "\n",
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.12.20070124"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BB84 protocol loops through the two main steps until Alice and Bob have as much key as they want.\n",
    "The first step is to use the quantum channel, where Alice prepares individual qubits and then sends them to Bob to be measured.\n",
    "The second step is entirely classical post-processing and communication that takes the measurement results from the quantum step and extracts a classical, random bit string Alice and Bob can use.\n",
    "Let's start by looking at how Alice will prepare her qubits for sending to Bob as a part of the quantum phase of the BB84 protocol.\n",
    "\n",
    "Alice has two choices for each qubit, which basis to prepare it in, and what bit value she wants to encode.\n",
    "This leads to four possible states each qubit can be in that Alice sends out.\n",
    "The bases she has to choose from are selected such that if an eavesdropper tries to measure a qubit in transit and chooses the wrong basis, then they just get a 0 or 1 with equal probability.\n",
    "\n",
    "In the first basis, called the computational basis, Alice prepares the states $|0\\rangle$ and $|1\\rangle$ where $|0\\rangle$ represents the key bit value `0` and $|1\\rangle$ represents the key bit value `1`.\n",
    "The second basis (sometimes called the diagonal or Hadamard basis) uses the states $|+\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$ to represent the key bit value `0`, and $|-\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$ to represent the key bit value `1`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Diagonal Basis\n",
    "\n",
    "Try your hand at converting qubits from the computational basis to the diagonal basis.\n",
    "\n",
    "**Input:** $N$ qubits (stored in an array of length $N$). Each qubit is either in $|0\\rangle$ or in $|1\\rangle$ state.\n",
    "\n",
    "**Goal:**  Convert the qubits to the diagonal basis: \n",
    "* if `qs[i]` was in state $|0\\rangle$, it should be transformed to $|+\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$,\n",
    "* if `qs[i]` was in state $|1\\rangle$, it should be transformed to $|-\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_DiagonalBasis_Test\n",
    "\n",
    "operation DiagonalBasis (qs : Qubit[]) : Unit {    \n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Equal superposition\n",
    "\n",
    " \n",
    "**Input**: A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal**:  Change the qubit state to a superposition state that has equal probabilities of measuring 0 and 1. \n",
    "\n",
    "> Note that this is not the same as keeping the qubit in the $|0\\rangle$ state with 50% probability and converting it to the $|1\\rangle$ state with 50% probability!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_EqualSuperposition_Test \n",
    "\n",
    "operation EqualSuperposition (q : Qubit) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. BB84 Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you have seen some of the steps that Alice will use to prepare here qubits, it's time to add in the rest of the steps of the BB84 protocol."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Generate random array\n",
    "\n",
    "You saw in part I that Alice has to make two random choices per qubit she prepares, one for which basis to prepare in, and the other for what bit value she wants to send.\n",
    "Bob will also need one random bit value to decide what basis he will be measuring each qubit in.\n",
    "To make this easier for later steps, you will need a way of generating random boolean values for both Alice and Bob to use.\n",
    "\n",
    "**Input:** An integer $N$.\n",
    "\n",
    "**Output** :  A `Bool` array of length N, where each element is chosen at random. \n",
    "\n",
    "> This will be used by both Alice and Bob to choose either the sequence of bits to send or the sequence of bases (`false` indicates $|0\\rangle$ / $|1\\rangle$ basis, and `true` indicates $|+\\rangle$ / $|-\\rangle$ basis) to use when encoding/measuring the bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_RandomArray_Test \n",
    "\n",
    "operation RandomArray (N : Int) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[N];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Prepare Alice's qubits\n",
    "\n",
    "Now that you have a way of generating the random inputs needed for Alice and Bob, it's time for Alice to use the random bits to prepare her sequence of qubits to send to Bob.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. `qs`: an array of $N$ qubits in the $|0\\rangle$ states,\n",
    "2. `bases`: a `Bool` array of length $N$; \n",
    "    `bases[i]` indicates the basis to prepare the i-th qubit in:  \n",
    "    * `false`: use $|0\\rangle$ / $|1\\rangle$ (computational) basis,\n",
    "    * `true`: use $|+\\rangle$ / $|-\\rangle$ (Hadamard/diagonal) basis.\n",
    "3. `bits`: a `Bool` array of length $N$;\n",
    "    `bits[i]` indicates the bit to encode in the i-th qubit: `false` = 0, `true` = 1.\n",
    "\n",
    "**Goal:**  Prepare the qubits in the described state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_PrepareAlicesQubits_Test\n",
    "\n",
    "operation PrepareAlicesQubits (qs : Qubit[], bases : Bool[], bits : Bool[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Measure Bob's qubits\n",
    "\n",
    "Bob now has an incoming stream of qubits that he needs to measure by randomly choosing a basis to measure in for each qubit.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `qs`: an array of $N$ qubits;  \n",
    "   each qubit is in one of the following states: $|0\\rangle$, $|1\\rangle$, $|+\\rangle$, $|-\\rangle$. \n",
    "2. `bases`: a `Bool` array of length $N$; \n",
    "   `bases[i]` indicates the basis used to prepare the i-th qubit:\n",
    "   * `false`: $|0\\rangle$ / $|1\\rangle$ (computational) basis,\n",
    "   * `true`: $|+\\rangle$ / $|-\\rangle$ (Hadamard/diagonal) basis.\n",
    "\n",
    "**Output:** Measure each qubit in the corresponding basis and return an array of results as boolean values, encoding measurement result `Zero` as `false` and `One` as `true`. \n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_MeasureBobsQubits_Test\n",
    "\n",
    "operation MeasureBobsQubits (qs : Qubit[], bases : Bool[]) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Generate the shared key!\n",
    "\n",
    "Now, Alice has a list of the bit values she sent as well as what basis she prepared each qubit in, and Bob has a list of bases he used to measure each qubit. To figure out the shared key, they need to figure out when they both used the same basis, and toss the data from qubits where they used different bases. If Alice and Bob did not use the same basis to prepare and measure the qubits in, the measurement results Bob got will be just random with 50% probability for both the `Zero` and `One` outcomes.\n",
    "    \n",
    "**Inputs:**\n",
    "\n",
    "1. `basesAlice` and `basesBob`: `Bool` arrays of length $N$\n",
    "   describing Alice's and Bobs's choice of bases, respectively;\n",
    "2. `measurementsBob`: a `Bool` array of length $N$ describing Bob's measurement results.\n",
    "    \n",
    "**Output:** a `Bool` array representing the shared key generated by the protocol.\n",
    "\n",
    "> Note that you don't need to know both Alice's and Bob's bits to figure out the shared key!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_GenerateSharedKey_Test\n",
    "\n",
    "function GenerateSharedKey (basesAlice : Bool[], basesBob : Bool[], measurementsBob : Bool[]) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Check if error rate was low enough\n",
    "\n",
    "The main trace eavesdroppers can leave on a key exchange is to introduce more errors into the transmission. Alice and Bob should have characterized the error rate of their channel before launching the protocol, and need to make sure when exchanging the key that there were not more errors than they expected. The \"errorRate\" parameter represents their earlier characterization of their channel.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `keyAlice` and `keyBob`: `Bool` arrays of equal length $N$ describing \n",
    "   the versions of the shared key obtained by Alice and Bob, respectively.\n",
    "2. `errorRate`: an integer between 0 and 50 - the percentage of the bits that did not match in Alice's and Bob's channel characterization.\n",
    "    \n",
    "**Output:** `true` if the percentage of errors is less than or equal to the error rate, and `false` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_CheckKeysMatch_Test\n",
    "\n",
    "function CheckKeysMatch (keyAlice : Bool[], keyBob : Bool[], errorRate : Int) : Bool {\n",
    "    // ...\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.6. Putting it all together\n",
    "\n",
    "**Goal:** Implement the entire BB84 protocol using tasks 2.1 - 2.5 \n",
    "and following the comments in the operation template. \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_BB84Protocol` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_BB84Protocol`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84Protocol () : Unit {\n",
    "    // 1. Alice chooses a random set of bits to encode in her qubits \n",
    "    //    and a random set of bases to prepare her qubits in.\n",
    "    // ...\n",
    "\n",
    "    // 2. Alice allocates qubits, encodes them using her choices and sends them to Bob.\n",
    "    //    (Note that you can not reflect \"sending the qubits to Bob\" in Q#)\n",
    "    // ...\n",
    "\n",
    "    // 3. Bob chooses a random set of bases to measure Alice's qubits in.\n",
    "    // ...\n",
    "\n",
    "    // 4. Bob measures Alice's qubits in his chosen bases.\n",
    "    // ...\n",
    "\n",
    "    // 5. Alice and Bob compare their chosen bases and use the bits in the matching positions to create a shared key.\n",
    "    // ...\n",
    "\n",
    "    // 6. Alice and Bob check to make sure nobody eavesdropped by comparing a subset of their keys\n",
    "    //    and verifying that more than a certain percentage of the bits match.\n",
    "    // For this step, you can check the percentage of matching bits using the entire key \n",
    "    // (in practice only a subset of indices is chosen to minimize the number of discarded bits).\n",
    "    // ...\n",
    "\n",
    "    // If you've done everything correctly, the generated keys will always match, since there is no eavesdropping going on.\n",
    "    // In the next section you will explore the effects introduced by eavesdropping.\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_BB84Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Eavesdropping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Eavesdrop!\n",
    "\n",
    "In this task you will try to implement an eavesdropper, Eve. \n",
    "\n",
    "Eve will intercept a qubit from the quantum channel that Alice and Bob are using. \n",
    "She will measure it in either the $|0\\rangle$ / $|1\\rangle$ basis or the $|+\\rangle$ / $|-\\rangle$ basis, and prepare a new qubit in the state she measured. Then she will send the new qubit back to the channel. \n",
    "Eve hopes that if she got lucky with her measurement, that when Bob measures the qubit he doesn't get an error so she won't be caught!\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `q`: a qubit in one of the following states: $|0\\rangle$, $|1\\rangle$, $|+\\rangle$, $|-\\rangle$.\n",
    "2. `basis`: Eve's guess of the basis she should use for measuring.\n",
    "   Recall that `false` indicates $|0\\rangle$ / $|1\\rangle$ basis and `true` indicates $|+\\rangle$ / $|-\\rangle$ basis. \n",
    "\n",
    "**Output:** the bit encoded in the qubit (`false` for $|0\\rangle$ / $|+\\rangle$ states, `true` for $|1\\rangle$ / $|-\\rangle$ states).\n",
    "\n",
    "   > In this task you are guaranteed that the basis you're given matches the one in which the qubit is encoded, that is, if you are given a qubit in state $|0\\rangle$ or $|1\\rangle$, you will be given `basis = false`, and if you are given a qubit in state $|+\\rangle$ or $|-\\rangle$, you will be given `basis = true`. This is different from a real eavesdropping scenario, in which you have to guess the basis yourself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_Eavesdrop_Test\n",
    "\n",
    "operation Eavesdrop (q : Qubit, basis : Bool) : Bool {\n",
    "    // ...\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. Catch the eavesdropper\n",
    "\n",
    "Add an eavesdropper into the BB84 protocol from task 2.6. \n",
    "\n",
    "Note that now we should be able to detect Eve and therefore we have to discard some of our key bits!\n",
    "\n",
    "> Similar to task 2.6, 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_BB84ProtocolWithEavesdropper` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_BB84ProtocolWithEavesdropper`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84ProtocolWithEavesdropper () : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_BB84ProtocolWithEavesdropper"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}