JointMeasurements/Workbook_JointMeasurements.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Joint Measurement 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 [Joint Measurements kata](./JointMeasurements.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 Joint Measurements kata (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. The concept of qubit and multi-qubit systems\n",
    "3. Single-qubit and multi-qubit quantum gates and using them to manipulate the state of the system\n",
    "4. The concept of measurements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Single-qubit measurement\n",
    "\n",
    "**Input:** Two qubits (stored in an array) which are guaranteed to be either in superposition of states $|00\\rangle$ and $|11\\rangle$ or in superposition of states $|01\\rangle$ and $|10\\rangle$.\n",
    "\n",
    "**Output:**  0 if qubits were in the first superposition, 1 if they were in the second superposition.  \n",
    "*The state of the qubits at the end of the operation does not matter.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This task is a special case of the [task 1.9 of Measurements kata](./../Measurements/Measurements.ipynb#Task-1.9.-Distinguish-two-superposition-states-given-by-two-arrays-of-bit-strings), so we can use the same approach here (although much simpler, since we need to distinguish two specific superpositions of bit strings).\n",
    "\n",
    "When we measure all qubits of a certain superposition state, it collapses to one of the basis vectors that comprised the superposition. \n",
    "We can do exactly that: measure both qubits and see whether the measurement results are the same; if they are, the state was a superposition of $|00\\rangle$ and $|11\\rangle$, otherwise the state was a superposition of $|01\\rangle$ and $|10\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_SingleQubitMeasurement\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation SingleQubitMeasurement (qs : Qubit[]) : Int {\n",
    "    return M(qs[0]) == M(qs[1]) ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1 of the Joint Measurements kata.](./JointMeasurements.ipynb#Task-1.-Single-qubit-measurement)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. Parity measurement\n",
    "\n",
    "**Inputs**: Two qubits (stored in an array) which are guaranteed to be either in superposition of states $|00\\rangle$ and $|11\\rangle$ or in superposition of states $|01\\rangle$ and $|10\\rangle$.\n",
    "\n",
    "**Output**: 0 if qubits were in the first superposition, 1 if they were in the second superposition.  \n",
    "*The state of the qubits at the end of the operation should be the same as the starting state.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "This task is the same as the previous task, except that we are asked to revert back to the initial state after measurement. However, if we try to measure both qubits again, we'll lose the information about the original superposition states: a state $\\alpha |00\\rangle + \\beta |11\\rangle$ will collapse to either $|00\\rangle$ or $|11\\rangle$, and we won't be able to recover the information about the coefficients $\\alpha$ and $\\beta$.\n",
    "\n",
    "We need to measure *parity* of the state without collapsing it all the way to the basis states. [Pauli measurements](https://docs.microsoft.com/azure/quantum/concepts-pauli-measurements) can be used for joint measurements involving multiple qubits. For this task we apply the `PauliZ` matrix on both qubits.\n",
    "\n",
    "A joint measurement using `PauliZ` can be thought as projecting the measured state to one of the two eigenspaces of `PauliZ` with $+1$ and $-1$ as the corresponding eigenvalues. The measurement returns `Zero` if the measured state is projected to the space with an eigenvalue of $+1$, and a result of `One` if projected to the space with an eigenvalue of $-1$.\n",
    "\n",
    "To solidify this intuition, let us see what happens to various two-qubit states after joint measurement. The `PauliZ` matrix for two qubits is denoted by $Z \\otimes Z$: \n",
    "\n",
    "$$Z \\otimes Z = \\begin{bmatrix}\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & -1 & 0 & 0 \\\\\n",
    "    0 & 0 & -1 & 0 \\\\\n",
    "    0 & 0 & 0 & 1 \\\\\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "\n",
    "When this transformation is applied to a basis state $|00\\rangle$, we get\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & -1 & 0 & 0 \\\\\n",
    "    0 & 0 & -1 & 0 \\\\\n",
    "    0 & 0 & 0 & 1 \\\\\n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ \\end{bmatrix} = \n",
    "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ \\end{bmatrix}$$\n",
    "\n",
    "Comparing this to the characteristic equation for eigenvectors of $Z \\otimes Z$ given by\n",
    "$ Z \\otimes Z |\\psi\\rangle = \\lambda |\\psi\\rangle$,\n",
    "it is easy to see that $|00\\rangle$ belongs to the $+1$ eigenspace, hence the $Z \\otimes Z$ measurement will return `Zero` and leave the state unchanged.\n",
    "\n",
    "Similarly, it can easily be verified that $|11\\rangle$ also belongs to $+1$ eigenspace, while $|01\\rangle$ and $|10\\rangle$ belong to the $-1$ eigenspace.\n",
    "\n",
    "Now, what happens if we apply a $Z \\otimes Z$ measurement to a superposition state $\\alpha |00\\rangle + \\beta |11\\rangle$? We can see that \n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & -1 & 0 & 0 \\\\\n",
    "    0 & 0 & -1 & 0 \\\\\n",
    "    0 & 0 & 0 & 1 \\\\\n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} \\alpha \\\\ 0 \\\\ 0 \\\\ \\beta \\\\ \\end{bmatrix} = \n",
    "\\begin{bmatrix} \\alpha \\\\ 0 \\\\ 0 \\\\ \\beta \\\\ \\end{bmatrix}$$\n",
    "\n",
    "So this state also belongs to the $+1$ eigenspace, and measuring it will return `Zero` and leave the state unchanged. Similarly, we can verify that an $\\alpha |01\\rangle + \\beta |10\\rangle$ state belongs to the $-1$ eigenspace, and measuring it will return `One` without changing the state.\n",
    "\n",
    "Hence, based on the return value from a `PauliZ` joint measurement, we can recognize which of the superposition states we were given while preserving the initial superposition state.\n",
    "\n",
    "In Q#, the operation [`Measure`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) can be used to measure multiple qubits using an array of [Pauli](https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/typesystem/) constants that define the basis for measurement.\n",
    "\n",
    "(This solution can also be used in task 1.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_ParityMeasurement\n",
    "\n",
    "operation ParityMeasurement (qs : Qubit[]) : Int {\n",
    "    return Measure([PauliZ, PauliZ], qs) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2 of the Joint Measurements kata.](./JointMeasurements.ipynb#Task-2.-Parity-measurement)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. $|0000\\rangle + |1111\\rangle$ or $|0011\\rangle + |1100\\rangle$  ?\n",
    "**Inputs**: Four qubits (stored in an array) which are guaranteed to be either in superposition of states $|0000\\rangle$ and $|1111\\rangle$ or in superposition of states $|0011\\rangle$ and $|1100\\rangle$.\n",
    "\n",
    "**Output** : 0 if qubits were in the first superposition, 1 if they were in the second superposition.  \n",
    "*The state of the qubits at the end of the operation should be the same as the starting state.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "If we measure the parity of all the qubits (using `PauliZ` joint measurement, similar to the previous task), we'll get the same measurement of `Zero` for both states. Notice, however, that the **2nd** and **3rd** qubits are the same in the first superposition ($|00\\rangle$ or $|11\\rangle$), while they are different in  the second superposition ($|01\\rangle$ and $|10\\rangle$).\n",
    "\n",
    "Hence, measuring the parity of those two qubits in `PauliZ`, as before, helps us distinguish between the two superpositions without collapsing them. The operation [`Measure`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) will handle the task of measuring the parity of a subset of qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_GHZOrGHZWithX \n",
    "\n",
    "operation GHZOrGHZWithX (qs : Qubit[]) : Int {\n",
    "    return Measure([PauliZ, PauliZ], qs[1 .. 2]) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3 of the Joint Measurements kata.](./JointMeasurements.ipynb#Task-3.-$|0000\\rangle-+-|1111\\rangle$-or-$|0011\\rangle-+-|1100\\rangle$--?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. GHZ state or W state ?\n",
    "\n",
    "**Inputs:** An **even** number of qubits (stored in an array) which are guaranteed to be either in a superposition of states  $|0..0\\rangle$ and $|1..1\\rangle$ (the [GHZ state](https://en.wikipedia.org/wiki/Greenberger%E2%80%93Horne%E2%80%93Zeilinger_state)) or in the [W state](https://en.wikipedia.org/wiki/W_state).\n",
    "\n",
    "**Output:** 0 if qubits were in the first superposition, 1 if they were in the second superposition. \n",
    "*The state of the qubits at the end of the operation should be the same as the starting state.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's consider a measurement in $Z^{\\otimes N}$ basis, i.e., a parity measurement on all $N$ qubits.\n",
    "\n",
    "Since it is given that there is an **even** number of qubits, both basis states the first superposition have parity $0$ and belong to the $+1$ eigenspace of this operator, and measuring them will return `Zero`. Each basis state of the second superposition always has a single qubit in the $|1\\rangle$ state, and thus has parity $1$ and is guaranteed to be projected to the $-1$ eigenspace, returning `One`.\n",
    "\n",
    "Q# operation [MeasureAllZ](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.measureallz) is a convenient shorthand for operation `Measure` with an argument that consists of all `PauliZ` bases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_GHZOrWState\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation GHZOrWState (qs : Qubit[]) : Int {\n",
    "    return MeasureAllZ(qs) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Joint Measurements kata.](./JointMeasurements.ipynb#Task-4.-GHZ-state-or-W-state-?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"parity-x\"></a> Task 5*. Parity measurement in different basis\n",
    "\n",
    "**Inputs:** Two qubits (stored in an array) which are guaranteed to be\n",
    "* either in superposition $\\alpha |00\\rangle + \\beta |01\\rangle + \\beta |10\\rangle + \\alpha |11\\rangle$\n",
    "* or in superposition $\\alpha |00\\rangle - \\beta |01\\rangle + \\beta |10\\rangle - \\alpha |11\\rangle$\n",
    "\n",
    "**Output:** 0 if qubits were in the first superposition, 1 if they were in the second superposition.  \n",
    "*The state of the qubits at the end of the operation should be the same as the starting state.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Measuring the parity of these states in `PauliZ` basis is not going to help, since each state has all four basis states represented in it, the difference is only in the relative phases. \n",
    "Let's follow the hint given by the title and try to rewrite these states in a different basis - the Hadamard basis $\\{|+\\rangle, |-\\rangle\\}$.\n",
    "\n",
    "The gives states could be regrouped as follows:\n",
    "\n",
    "$$|\\psi_1\\rangle = \\alpha (|00\\rangle + |11\\rangle) + \\beta (|01\\rangle + |10\\rangle) \\\\\n",
    "|\\psi_2\\rangle = \\alpha (|00\\rangle - |11\\rangle) + \\beta (- |01\\rangle + |10\\rangle)$$\n",
    "\n",
    "The two-qubit basis states in the Hadamard basis are the following:\n",
    "\n",
    "$$\n",
    "|++\\rangle = \\frac12(|00\\rangle + |11\\rangle + |01\\rangle + |10\\rangle)\\\\\n",
    "|--\\rangle = \\frac12(|00\\rangle + |11\\rangle - |01\\rangle - |10\\rangle)\\\\\n",
    "|+-\\rangle = \\frac12(|00\\rangle - |11\\rangle - |01\\rangle + |10\\rangle)\\\\\n",
    "|-+\\rangle = \\frac12(|00\\rangle - |11\\rangle + |01\\rangle - |10\\rangle)$$\n",
    "\n",
    "Now it's easy to see how to represent the terms of our given states in the Hadamard basis:\n",
    "\n",
    "$$\n",
    "|00\\rangle + |11\\rangle = |++\\rangle + |--\\rangle\\\\\n",
    "|01\\rangle + |10\\rangle = |++\\rangle - |--\\rangle\\\\\n",
    "|00\\rangle - |11\\rangle = |+-\\rangle + |-+\\rangle\\\\\n",
    "|10\\rangle - |01\\rangle = |+-\\rangle - |-+\\rangle$$\n",
    "\n",
    "You can switch between the computational basis and the Hadamard basis using the H gate: \n",
    "\n",
    "$$|00\\rangle + |11\\rangle = |++\\rangle + |--\\rangle = H^{\\otimes 2} (|00\\rangle + |11\\rangle)$$\n",
    "\n",
    "and so on, where $H^{\\otimes 2} = H \\otimes H$ means applying the Hadamard operator to both qubits.\n",
    "\n",
    "Therefore, we can represent our starting states as \n",
    "\n",
    "$$|\\psi_1\\rangle = \\alpha H^{\\otimes 2} (|00\\rangle + |11\\rangle) + \\beta H^{\\otimes 2} (|00\\rangle - |11\\rangle) = (\\alpha + \\beta) H^{\\otimes 2} |00\\rangle + (\\alpha - \\beta) H^{\\otimes 2}|11\\rangle$$\n",
    "\n",
    "and, similarly,\n",
    "\n",
    "$$|\\psi_2\\rangle = (\\alpha + \\beta) H^{\\otimes 2} |01\\rangle + (\\alpha - \\beta) H^{\\otimes 2}|10\\rangle$$\n",
    "\n",
    "We now have a familiar format where the first superposition $|\\psi_1\\rangle$ has a parity of 0 and the second superposition $|\\psi_2\\rangle$ has a parity of 1, when considered in Hadamard basis.\n",
    "\n",
    "We can implement the necessary measurement manually, by applying the H gate to each of the qubits, measuring the parity of the state similarly to [task 2](#Task-2.-Parity-measurement) and applying the H gate to each of the qubits again. \n",
    "\n",
    "It is easier and more neat to use the `Measure` operation with [PauliX](https://docs.microsoft.com/azure/quantum/concepts-pauli-measurements) basis which performs an equivalent measurement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_DifferentBasis\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DifferentBasis (qs : Qubit[]) : Int {\n",
    "    return Measure([PauliX, PauliX], qs) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 5 of the Joint Measurements kata.](./JointMeasurements.ipynb#parity-x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"controlled-x-0\"></a> Task 6*. Controlled X gate with $|0\\rangle$ target\n",
    "\n",
    "**Input:** Two unentangled qubits (stored in an array of length 2). The first qubit (`qs[0]`) will be in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$ , the second (`qs[1]`) - in state $|0\\rangle$ (this can be written as two-qubit state $\\big(\\alpha |0\\rangle + \\beta |1\\rangle\\big) \\otimes |0\\rangle$). \n",
    "\n",
    "**Output:** Change the two-qubit state to $\\alpha |00\\rangle + \\beta |11\\rangle$ using only single-qubit gates and joint measurements. Do not use two-qubit gates. You do not need to allocate extra qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Lets apply $H$ to the second qubit. This results in\n",
    "\n",
    "$$\\big(\\alpha |0\\rangle + \\beta |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$$\n",
    "\n",
    "A key point to note is that at this point the two qubits are **unentangled**. However, a joint measurement in `PauliZ` basis causes the qubits to become entangled and collapse into one of the following states:\n",
    "\n",
    "* $ \\alpha |00\\rangle +  \\beta |11\\rangle$ if the measurement result was `Zero`\n",
    "* or $\\alpha |01\\rangle + \\beta |10\\rangle$ if the measurement result was `One`.\n",
    "\n",
    "If the qubits end up collapsing to the second state (given by the value of the measurement), applying the $X$ gate on the second qubit allows to fix the outcome to produce the desired result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_ControlledX\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation ControlledX (qs : Qubit[]) : Unit {\n",
    "    H(qs[1]);\n",
    "    let m = Measure([PauliZ, PauliZ], qs);\n",
    "    \n",
    "    if m == One {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 6 of the Joint Measurements kata.](./JointMeasurements.ipynb#controlled-x-0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"controlled-x\"></a> Task 7**. Controlled X gate with arbitrary target\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) in an arbitrary two-qubit state $\\alpha |00\\rangle + \\beta |01\\rangle + \\color{blue}\\gamma |10\\rangle  + \\color{blue}\\delta |11\\rangle$.\n",
    "\n",
    "**Goal:** Change the two-qubit state to $\\alpha |00\\rangle + \\beta |01\\rangle + \\color{red}\\delta |10\\rangle  + \\color{red}\\gamma |11\\rangle$ using only single-qubit gates and joint measurements.  Do not use two-qubit gates.\n",
    "\n",
    "> A general-case implementation of CNOT gate via joint measurements is described in [this paper](https://arxiv.org/pdf/1201.5734.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "The implementation of the circuit in page 3 as presented in the paper mentioned above is fairly straightforward. The table in page 4 describes the actions to perform on the control and target qubit depending on the measurements $P_{1}$, $P_{2}$ and $M$. $P_{1}$ and $P_{2}$ are joint measurements in `PauliZ` and $M$ is a single qubit `PauliZ` measurement.\n",
    "\n",
    "For this task, it is necessary to allocate an ancillary qubit denoted by `anc`.\n",
    "\n",
    "Initially, the input qubits are in superposition and the ancillary qubit is unentangled with the input qubits. Applying a Hadamard gate on the ancillary qubit gives,\n",
    "$$(\\alpha |00\\rangle + \\beta |01\\rangle + \\gamma |10\\rangle + \\delta |11\\rangle) \\otimes \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle) $$\n",
    "Note that even at this point, the ancillary and input qubits are **unentangled**.\n",
    "\n",
    "Now the measurement $P_{1}$ is made. This causes the ancillary bit to become **entangled** with the input qubits.\n",
    "\n",
    "$$\\frac{1}{\\sqrt2} \\big(\\alpha |\\color{red}00\\color{red}0\\rangle + \\alpha |\\color{blue}00\\color{blue}1\\rangle + \\beta |\\color{red}01\\color{red}0\\rangle + \\beta |\\color{blue}01\\color{blue}1\\rangle + \\gamma |\\color{blue}10\\color{blue}0\\rangle  + \\gamma |\\color{red}10\\color{red}1\\rangle + \\delta |\\color{blue}11\\color{blue}0\\rangle + \\delta |\\color{red}11\\color{red}1\\rangle \\big)$$\n",
    "\n",
    "After a joint measurement $P_{1}$ in `PauliZ` between **qubit 1** and the **ancillary qubit**, the above state is projected to one of the $+1$ and $-1$ eigenstates.\n",
    "\n",
    "* If the state is projected to the $+1$ eigenstate (measured as `Zero`), the resulting superposition is $\\alpha |\\color{red}00\\color{red}0\\rangle + \\beta |\\color{red}01\\color{red}0\\rangle + \\gamma |\\color{red}10\\color{red}1\\rangle + \\delta |\\color{red}11\\color{red}1\\rangle$\n",
    "\n",
    "* If the state is projected to the $-1$ eigenstate (measured as `One`), the resulting superposition is $\\alpha |\\color{blue}00\\color{blue}1\\rangle + \\beta |\\color{blue}01\\color{blue}1\\rangle + \\gamma |\\color{blue}10\\color{blue}0\\rangle  + \\delta |\\color{blue}11\\color{blue}0\\rangle$ (note that in both cases the $\\frac{1}{\\sqrt2}$ coefficient is removed, since the resulting state must be normalized)\n",
    "\n",
    "Let us assume $P_{1}$ was measured as `Zero`.\n",
    "\n",
    "> The measurement in the paper follows a different convention: `Zero` would be `1` and `One` would be `0` in the paper. You have to keep this in mind when translating the paper into Q# code.\n",
    "\n",
    "Now apply the Hadamard gate on the **second qubit** and the **ancillary qubit**. This yields the state,\n",
    "\n",
    "$$\\frac12 (\\alpha |0\\color{red}0\\color{red}0\\rangle + \\alpha |0\\color{blue}0\\color{blue}1\\rangle + \\alpha |0\\color{blue}1\\color{blue}0\\rangle + \\alpha |0\\color{red}1\\color{red}1\\rangle) + \\\\\n",
    "\\frac12 (\\beta |0\\color{red}0\\color{red}0\\rangle + \\beta |0\\color{blue}0\\color{blue}1\\rangle - \\beta |0\\color{blue}1\\color{blue}0\\rangle - \\beta |0\\color{red}1\\color{red}1\\rangle) + \\\\\n",
    "\\frac12 (\\gamma |1\\color{red}0\\color{red}0\\rangle - \\gamma |1\\color{blue}0\\color{blue}1\\rangle + \\gamma |1\\color{blue}1\\color{blue}0\\rangle - \\gamma |1\\color{red}1\\color{red}1\\rangle) + \\\\\n",
    "\\frac12 (\\delta |1\\color{red}0\\color{red}0\\rangle - \\delta |1\\color{blue}0\\color{blue}1\\rangle - \\delta |1\\color{blue}1\\color{blue}0\\rangle + \\delta |1\\color{red}1\\color{red}1\\rangle)$$\n",
    "\n",
    "Now a joint measurement $P_{2}$ in `PauliZ` is applied between **qubit 2** and the **ancillary qubit**\n",
    "\n",
    "* If the state is projected to the $+1$ eigenstate (measured as `Zero`), the resulting superposition is  \n",
    "  $\\big[(\\alpha + \\beta) |0\\color{red}0\\color{red}0\\rangle + (\\alpha - \\beta) |0\\color{red}1\\color{red}1\\rangle \\big] + \n",
    "  \\big[(\\delta + \\gamma) |1\\color{red}0\\color{red}0\\rangle + (\\delta - \\gamma) |1\\color{red}1\\color{red}1\\rangle\\big]$\n",
    "\n",
    "* If the state is projected to the $-1$ eigenstate (measured as `One`), the resulting superposition is  \n",
    "  $\\big[(\\alpha + \\beta) |0\\color{blue}0\\color{blue}1\\rangle + (\\alpha - \\beta) |0\\color{blue}1\\color{blue}0\\rangle\\big] - \n",
    "  \\big[(\\delta + \\gamma) |1\\color{blue}0\\color{blue}1\\rangle + (\\delta - \\gamma) |1\\color{blue}1\\color{blue}0\\rangle\\big]$\n",
    "\n",
    "\n",
    "Let us assume $P_{2}$ was measured as `Zero`. After applying the Hadamard gate to **qubit 2** and the **ancillary qubit**, we get\n",
    "\n",
    "$$(\\alpha + \\beta) \\frac12 (|000\\rangle + |001\\rangle + |010\\rangle + |011\\rangle) + \\\\\n",
    "(\\alpha - \\beta) \\frac12 (|000\\rangle - |001\\rangle - |010\\rangle + |011\\rangle) + \\\\\n",
    "(\\delta + \\gamma)\\frac12 (|100\\rangle + |101\\rangle + |110\\rangle + |111\\rangle) + \\\\\n",
    "(\\delta - \\gamma)\\frac12 (|100\\rangle - |101\\rangle - |110\\rangle + |111\\rangle)$$\n",
    "\n",
    "After simplifying, it becomes\n",
    "\n",
    "$$\\big[\\alpha|00\\color{red}0\\rangle + \\beta|01\\color{red}0\\rangle + \\delta|10\\color{red}0\\rangle + \\gamma|11\\color{red}0\\rangle\\big] + \n",
    "\\big[\\alpha|01\\color{blue}1\\rangle + \\beta|00\\color{blue}1\\rangle + \\delta|11\\color{blue}1\\rangle + \\gamma|10\\color{blue}1\\rangle\\big]$$\n",
    "\n",
    "Finally, after measuring the **ancillary qubit** as $M$,\n",
    "\n",
    "* If the measurement is `Zero`, we get $\\alpha|00\\color{red}0\\rangle + \\beta|01\\color{red}0\\rangle + \\delta|10\\color{red}0\\rangle + \\gamma|11\\color{red}0\\rangle$\n",
    "  \n",
    "  Hence if the three measured states are (`Zero`, `Zero`, `Zero`), we don't need to do anything further as the output is already in the desired state. Note that this would correspond to the first row (1, 1, 1) in the table in the paper.\n",
    "\n",
    "* If the measurement is `One`, we get $\\alpha|01\\color{blue}1\\rangle + \\beta|00\\color{blue}1\\rangle + \\delta|11\\color{blue}1\\rangle + \\gamma|10\\color{blue}1\\rangle$\n",
    "  \n",
    "  Hence if the three measured states are (`Zero`, `Zero`, `One`), we don't need to do anything to the **first qubit** and apply the `X` gate to the **second** qubit to obtain the desired state. Note that this would correspond to the second row (1, 1, 0) in the table in the paper.\n",
    "\n",
    "The rest of the table can be filled by a similar procedure, assuming different outcomes of the first two measurements and analyzing the further steps. Note that we need apply `Z` to the **first qubit** if $P_{2}$ is `One` and `X` to the **second qubit** if $P_{1}$ is not equal to $M$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_ControlledX_General\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation ControlledX_General (qs : Qubit[]) : Unit {\n",
    "    use anc = Qubit();\n",
    "    H(anc);\n",
    "\n",
    "    let c = qs[0];\n",
    "    let t = qs[1];\n",
    "\n",
    "    let p1 = MeasureAllZ([c, anc]);\n",
    "\n",
    "    H(anc);\n",
    "    H(t);\n",
    "\n",
    "    let p2 = MeasureAllZ([anc, t]);\n",
    "\n",
    "    H(anc);\n",
    "    H(t);\n",
    "\n",
    "    let m = MResetZ(anc);\n",
    "\n",
    "    if p2 == One {\n",
    "        Z(c);\n",
    "    }\n",
    "\n",
    "    if p1 != m {\n",
    "        X(t);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 7 of the Joint Measurements kata.](./JointMeasurements.ipynb#controlled-x)"
   ]
  }
 ],
 "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
}