KeyDistribution_BB84/Workbook_KeyDistribution_BB84.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Key Distribution - BB84 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 [Key Distribution BB84 kata](./KeyDistribution_BB84.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 Key Distribution - BB84 Kata (and this workbook):\n",
    "1. Basic single-qubit gates\n",
    "2. The concept of measurement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"diagonal_basis\"></a>  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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This task is similar to the one mentioned in [task 1.9 of Superposition kata](./../Superposition/Superposition.ipynb#superposition-of-all-basis-vectors). \n",
    "This task can be solved by applying a Hadamard gate to every qubit, resulting in $|+\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$ and $|-\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$ states depending on whether the starting state of each qubit was $|0\\rangle$ or $|1\\rangle$, respectively. \n",
    "\n",
    "To get the desired result, we will iterate over the given array of qubits using a foreach-style loop and apply a Hadamard gate to each qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_DiagonalBasis\n",
    "\n",
    "operation DiagonalBasis (qs : Qubit[]) : Unit {    \n",
    "    for q in qs {\n",
    "        H(q);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternative, we can use the [ApplyToEach](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.applytoeach) library function from Microsoft.Quantum.Canon namespace to apply the given gate to each element of the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_DiagonalBasis\n",
    "\n",
    "operation DiagonalBasis (qs : Qubit[]) : Unit {    \n",
    "    // Use the library function of Q#.\n",
    "    ApplyToEachA(H, qs);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the KeyDistribution_BB84 kata.](./KeyDistribution_BB84.ipynb#Task-1.1-diagonal-basis)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"equal_superposition\"></a> 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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "This task is similar to [Task 1.1](./../Superposition/Superposition.ipynb#plus-state) and [Task 1.2](./../Superposition/Superposition.ipynb#minus-state) of the Superposition kata. \n",
    "This can also be thought as a specific case of the previous task with $N = 1$.\n",
    "\n",
    "For a qubit state to have equal probabilities of producing 0 and 1 when measured, both basis states in the superposition need to have absolute values of amplitudes equal to $\\frac{1}{\\sqrt2}$.\n",
    "This means that any state of the following form will provide the desired results, as the relative phase will not affect the measurement probabilities\n",
    "\n",
    "$$|\\psi\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + e^{i\\phi}|1\\rangle)$$\n",
    "\n",
    "There are multiple ways to prepare one of these states using rotation gates.\n",
    "However, the simplest solution would be to reuse the previous task and to prepare a plus state $|+\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$ or a minus state $|-\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$ using the Hadamard gate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_EqualSuperposition \n",
    "\n",
    "operation EqualSuperposition (q : Qubit) : Unit {\n",
    "    // The most straightforward solution - preparing the plus state.\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-1.2-equal-superposition)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. BB84 Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"generate_random_array\"></a> Task 2.1. Generate random array\n",
    "\n",
    "**Input:** An integer $N$.\n",
    "\n",
    "**Output** :  A `Bool` array of length N, where each element is chosen at random. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "This is a very simple problem were we have to prepare a random bool array. We need to do three steps here.\n",
    "1. Create a mutable array of size $N$ with default value set to `false`.\n",
    "2. For each array index, choose one of the two random values (`true` or `false`) and assign that value to the array element at that index.\n",
    "3. Finally, return this array from the function.\n",
    "\n",
    "Steps 1 and 3 are quite straightforward, while step 2 is where our concentration should be. If we recall our Q# library operations, we will find the operation [DrawRandomBool](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.random.drawrandombool) which returns `true` or `false` based on the success probability provided. In our case, we require the success probability to be 50%, and thus the value we need to pass to `DrawRandomBool` operation should be `0.5`. This function needs to be called for each of the $N$ elements in the array, so we will iterate through all the indexes and set the value to each element of this array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_RandomArray\n",
    "\n",
    "// Required to use DrawRandomBool function\n",
    "open Microsoft.Quantum.Random;\n",
    "\n",
    "operation RandomArray (N : Int) : Bool[] {\n",
    "    \n",
    "    // Step 1: Create array of size N with default value false\n",
    "    mutable array = [false, size = N];\n",
    "\n",
    "    // Step 2: Iterate through all elements of the array and set the random value using DrawRandomBool function\n",
    "    for i in 0 .. N - 1 {\n",
    "        set array w/= i <- DrawRandomBool(0.5);\n",
    "    }\n",
    "\n",
    "    // Step 3: Return the random bool array\n",
    "    return array;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.1-generate-random-array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"prepare_alice_qubits\"></a> Task 2.2. Prepare Alice's qubits\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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "There are a total of 4 types of states that Alice can prepare before sending to Bob, each corresponds to the unique combination of bits and bases bool array. \n",
    "\n",
    "1. To send state $|0\\rangle$, bases[i] should be computational basis, i.e., `false`, and bits[i] should be 0, i.e., `false`.\n",
    "2. To send state $|1\\rangle$, bases[i] should be computational basis, i.e., `false`, and bits[i] should be 1, i.e., `true`.\n",
    "3. To send state $|+\\rangle$, bases[i] should be Hadamard/diagonal basis, i.e., `true`, and bits[i] should be 0, i.e., `false`.\n",
    "4. To send state $|-\\rangle$, bases[i] should be Hadamard/diagonal basis, i.e., `true` and bits[i] should be 1, i.e., `true`. \n",
    "\n",
    "So, in case `bits[i]` is set to `true`, we need to apply the $X$ gate to the i-th qubit, and then if `bases[i]` is set to `true`, the $H$ gate needs to be applied to the i-th qubit. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_PrepareAlicesQubits\n",
    "\n",
    "operation PrepareAlicesQubits (qs : Qubit[], bases : Bool[], bits : Bool[]) : Unit {\n",
    "    // Iterate over all the qubits to prepare each one\n",
    "    for i in 0 .. Length(qs) - 1 {\n",
    "        if bits[i] {\n",
    "            X(qs[i]);\n",
    "        }\n",
    "        if bases[i] {\n",
    "            H(qs[i]);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.2-prepare-alice-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"measure_bob_qubits\"></a>Task 2.3. Measure Bob's qubits\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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Now we have a random bool array, similar to what we created in [Task 2.1](#generate_random_array), and the qubit stream that we received from Alice. Bob is not aware of which bases Alice used for each qubit and thus can only randomly guess with 50% probability of being right.\n",
    "\n",
    "If the `bases[i]` array element is `true`, it means that we are choosing Hadamard/diagnoal basis for this qubit, and thus $H$ gate needs to be applied. Otherwise, we choose computational basis and don't need to apply the $H$ gate.\n",
    "\n",
    "Now the output is expected to be a bool array and thus we need to measure the each qubit and convert this measurement to a `Bool`. \n",
    "1. To measure each of the qubits in one operation call, we can use the [MultiM](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.multim) function from Q# libraries.\n",
    "2. Now to convert these measurement results into a Boolean array, we can use [ResultArrayAsBoolArray](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.resultarrayasboolarray) function. This takes array of `Result` type as an input and returns the required array of `Bool`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_MeasureBobsQubits\n",
    "\n",
    "// Required for MultiM function\n",
    "open Microsoft.Quantum.Measurement;\n",
    "// Required for ResultArrayAsBoolArray function\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation MeasureBobsQubits (qs : Qubit[], bases : Bool[]) : Bool[] {\n",
    "    \n",
    "    // Iterate over all the qubits\n",
    "    for i in 0 .. Length(qs) - 1 {\n",
    "        if bases[i] {\n",
    "            H(qs[i]);\n",
    "        }\n",
    "    }\n",
    "        \n",
    "    // MutliM(qs) produces Result[] which is taken by ResultArrayAsBoolArray as the input.\n",
    "    return ResultArrayAsBoolArray(MultiM(qs)); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.3-measure-bob-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"generate_the_shared_key\"></a>Task 2.4. Generate the shared key!\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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If Alice and Bob exchanged a qubit and used the same bases, the bit produced by Bob's measurement would be the same as the one Alice encoded. Thus, we do not require to share the actual bit sent by Alice over the communication channel. Sharing the bases used for each of the qubit is sufficient to understand if Bob measured each qubit correctly or not.\n",
    "\n",
    "To complete this task, we need to perform the following steps:\n",
    "1. Declare an empty mutable array, let's name it `key`.\n",
    "2. Decide which bit we can add to our key based on the comparison between bases used by Alice and Bob. All three arrays provided as input here are of same size and thus can be zipped together for iteration. Alternatively, you can iterate using an index value in range 0 to $N$ - 1 as well. \n",
    "3. Return the required `key`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_GenerateSharedKey\n",
    "\n",
    "// Required for Zipped3 Function\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "function GenerateSharedKey (basesAlice : Bool[], basesBob : Bool[], measurementsBob : Bool[]) : Bool[] {\n",
    "    \n",
    "    // Step 1: Declare empty array key for storing the required value of key\n",
    "    mutable key = [];\n",
    "    \n",
    "    // Iteration over all the qubit sending attempts\n",
    "    // Zipped3 function ensures we iterate over a tuple of 3 items.\n",
    "    for (a, b, bit) in Zipped3(basesAlice, basesBob, measurementsBob) {\n",
    "        if a == b {\n",
    "            set key += [bit]; // Step 2: Add bit to the key in case bases of both Alice and Bob matches\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // Step 3: Return the required key\n",
    "    return key;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.4 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.4-generate-shared-key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"check_error_rate\"></a> Task 2.5. Check if error rate was low enough\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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "When no eavesdropper is present, in an ideal setup, `keyAlice` should match `keyBob` exactly. But when an eavesdropper is present, some of the key bits might not match, indicating the presence of Eve in the communication system. \n",
    "\n",
    "To find the number of mismatched key values, we can iterate over the array and increament the counter whenever `keyAlice[i] != keyBob[i]`. If the percentage of mismatched key values is less than the acceptable errorRate, we return `true`, otherwise return `false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_CheckKeysMatch\n",
    "\n",
    "// Requried to use IntAsDouble Function\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "function CheckKeysMatch (keyAlice : Bool[], keyBob : Bool[], errorRate : Int) : Bool {\n",
    "    \n",
    "    let N = Length(keyAlice);\n",
    "    \n",
    "    // Declare a variable to count the number of mismatched bits\n",
    "    mutable mismatchCount = 0;\n",
    "    \n",
    "    for i in 0 .. N - 1 {\n",
    "        if keyAlice[i] != keyBob[i] {\n",
    "            set mismatchCount += 1; // Increament the counter whenever a mismatch is found\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // return true if probability of mismatched bits is less than the Error Rate provided\n",
    "    return IntAsDouble(mismatchCount) / IntAsDouble(N) <= IntAsDouble(errorRate) / 100.0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.5 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.5-check-error-rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"putting_it_all_together\"></a> 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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Now that all the pieces are in place, it is time for us to implement the entire protocol. We will need to utilize all the tasks we have completed so far in order to accomplish the goal.\n",
    "\n",
    "Just to revise, here are the steps we need to follow:\n",
    "1. Alice generates a random set of bits to encode her qubits, and a random array to decide which bases she would use. To achieve this, she can leverage our [Task 2.1. Generate random array](#generate_random_array), and define two variables `bitsAlice` and `basesAlice`.\n",
    "\n",
    "2. Now, Alice can prepare her qubits using the previously generated `bitsAlice` and `basesAlice`. For this, we need to declare an array of qubits `qs` and leverage [Task 2.2. Prepare Alice's qubits](#prepare_alice_qubits) to encode them: `PrepareAlicesQubits(qs, basesAlice, bitsAlice)`. Now Alice is ready to send her qubits to Bob, which is not reflected in the code.\n",
    "\n",
    "3. Next, Bob also needs to create a random set of bases which he would use to measure the qubits in. This again can be achieved using [Task 2.1. Generate random array](#generate_random_array). This would give us `basesBob`.\n",
    "\n",
    "4. Now Bob will use his array of random bases to measure Alice's qubits. For this, we can leverage our [Task 2.3. Measure Bob's qubits](#measure_bob_qubits): `MeasureBobsQubits(qs, basesBob)`.\n",
    "\n",
    "5. Alice and Bob prepare the shared key by comparing the bases used by them in their preparation/measurements. Referring to [Task 2.4. Generate the shared key!](#generate_the_shared_key), we can create shared keys as `GenerateSharedKey(basesAlice, basesBob, bitsAlice)` and `GenerateSharedKey(basesAlice, basesBob, bitsBob)`.\n",
    "\n",
    "6. Finally, we have to implement the key validation step to ensure there was no eavesdropper. We define a threshold value for the errorRate and use [Task 2.5. Check if error rate was low enough](#check_error_rate) to perform this operation: `CheckKeysMatch(keyAlice, keyBob, threshold)`.\n",
    "\n",
    "This completes our implementation of how Alice and Bob can generate a shared key using BB84 protocol. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84Protocol () : Unit {\n",
    "    // Require a nearly perfect match of the shared keys for success\n",
    "    // (1% of the characters are allowed to be different).\n",
    "    let threshold = 1;\n",
    "\n",
    "    use qs = Qubit[20];\n",
    "    // 1. Choose random basis and bits to encode\n",
    "    let basesAlice = RandomArray(Length(qs));\n",
    "    let bitsAlice = RandomArray(Length(qs));\n",
    "\n",
    "    // 2. Alice prepares her qubits\n",
    "    PrepareAlicesQubits(qs, basesAlice, bitsAlice);\n",
    "\n",
    "    // 3. Bob chooses random basis to measure in\n",
    "    let basesBob = RandomArray(Length(qs));\n",
    "\n",
    "    // 4. Bob measures Alice's qubits\n",
    "    let bitsBob = MeasureBobsQubits(qs, basesBob);\n",
    "\n",
    "    // 5. Generate shared key\n",
    "    let keyAlice = GenerateSharedKey(basesAlice, basesBob, bitsAlice);\n",
    "    let keyBob = GenerateSharedKey(basesAlice, basesBob, bitsBob);\n",
    "\n",
    "    // 6. Ensure at least the minimum percentage of bits match\n",
    "    if (CheckKeysMatch(keyAlice, keyBob, threshold)) {\n",
    "        Message($\"Successfully generated keys {keyAlice}/{keyBob}\");\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.6 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-2.6-putting-it-all-together)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Eavesdropping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"eavesdrop\"></a>Task 3.1. Eavesdrop!\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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The input `basis` is the reference of the basis in which the measurement needs to be made. If the basis is $|0\\rangle$ / $|1\\rangle$, the measurement is in the Pauli Z basis, and if the basis is $|+\\rangle$ / $|-\\rangle$, the measurement is in the Pauli X basis. \n",
    "\n",
    "Q# function [Measure](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) allows to measure an array of qubits based on the array of bases provided. Since we have only one qubit to be measured, array of a single element suffices. \n",
    "\n",
    "Finally, since the function needs to return `Bool` value, `Result` data type should be converted to `Bool` value before returning using [ResultAsBool](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.resultasbool)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_Eavesdrop\n",
    "\n",
    "// Required for ResultAsBool\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation Eavesdrop (q : Qubit, basis : Bool) : Bool {\n",
    "    \n",
    "    // Measurement along X axis if basis is diagonal basis and Z axis, otherwise.\n",
    "    return ResultAsBool(Measure([basis ? PauliX | PauliZ], [q]));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.1 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-3.1-eavesdrop)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"catch_the_eavesdropper\"></a>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 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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This task requires us to repeat the steps we followed in [Task 2.6. Putting it all together](#putting_it_all_together). The addition here is the intervention of an eavesdropper who will randomly guess the bases used by Alice for each qubit and measure them after step 2. The measurement made by the Eve is a repeated process that we designed in [Task 3.1. Eavesdrop!](#eavesdrop).\n",
    "\n",
    "Finally, when we check for the error rate, we will be able to detect Eve based on the errors encountered while comparing shared keys of Alice and Bob. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84ProtocolWithEavesdropper () : Unit {\n",
    "    let threshold = 1;\n",
    "\n",
    "    use qs = Qubit[20];\n",
    "    // 1. Choose random basis and bits to encode\n",
    "    let basesAlice = RandomArray(Length(qs));\n",
    "    let bitsAlice = RandomArray(Length(qs));\n",
    "\n",
    "    // 2. Alice prepares her qubits\n",
    "    PrepareAlicesQubits(qs, basesAlice, bitsAlice);\n",
    "\n",
    "    // Eve eavesdrops on all qubits, guessing the basis at random\n",
    "    for q in qs {\n",
    "        let n = Eavesdrop(q, DrawRandomBool(0.5));\n",
    "    }\n",
    "\n",
    "    // 3. Bob chooses random basis to measure in\n",
    "    let basesBob = RandomArray(Length(qs));\n",
    "\n",
    "    // 4. Bob measures Alice's qubits'\n",
    "    let bitsBob = MeasureBobsQubits(qs, basesBob);\n",
    "\n",
    "    // 5. Generate shared key\n",
    "    let keyAlice = GenerateSharedKey(basesAlice, basesBob, bitsAlice);\n",
    "    let keyBob = GenerateSharedKey(basesAlice, basesBob, bitsBob);\n",
    "\n",
    "    // 6. Ensure at least the minimum percentage of bits match\n",
    "    if (CheckKeysMatch(keyAlice, keyBob, threshold)) {\n",
    "        Message($\"Successfully generated keys {keyAlice}/{keyBob}\");\n",
    "    } else {\n",
    "        Message($\"Caught an eavesdropper, discarding the keys {keyAlice}/{keyBob}\");\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_BB84ProtocolWithEavesdropper"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.2 of the Key Distribution_BB84 kata.](././KeyDistribution_BB84.ipynb#Task-3.2-catch-the-eavesdropper)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}