DistinguishUnitaries/Workbook_DistinguishUnitaries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Distinguish Unitaries Kata 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 [Distinguish Unitaries kata](./DistinguishUnitaries.ipynb). 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 Distinguish Unitaries kata (and this workbook):\n",
    "\n",
    "1. [Basic linear algebra](./../tutorials/LinearAlgebra/LinearAlgebra.ipynb)).\n",
    "2. [The concept of qubit](./../tutorials/Qubit/Qubit.ipynb) and [multi-qubit systems](./../tutorials/MultiQubitSystems/MultiQubitSystems.ipynb).\n",
    "3. [Single-qubit](./../tutorials/SingleQubitGates/SingleQubitGates.ipynb) and [multi-qubit quantum gates](./../tutorials/MultiQubitGates/MultiQubitGates.ipynb) and using them to manipulate the state of the system.\n",
    "4. Measurements and using them to distinguish quantum states."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Single-Qubit Gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Identity or Pauli X?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the identity (**I** gate)\n",
    "or the Pauli X gate (**X** gate). \n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **I** gate, 1 if the given operation is the **X** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The only way to extract information out of a quantum system is measurement. \n",
    "Measurements give us information about the states of a system, so to get information about the gate, we need to find a way to convert it into information about a state.\n",
    "If we want to distinguish two gates, we need to figure out to prepare a state and perform a measurement on it that will give us a result that we can interpret.\n",
    "To do this, we’ll need to find a qubit state that, by applying to it I gate or X gate, will be transformed into states that can be distinguished using measurement, i.e., orthogonal states. \n",
    "Let's find such state.\n",
    "\n",
    "> As a reminder, here are the matrices that correspond to the given gates:\n",
    "> $$I = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}, X = \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix}$$\n",
    "\n",
    "Consider the effects of these gates on the basis states: \n",
    "\n",
    "$$I|0\\rangle = |0\\rangle, I|1\\rangle = |1\\rangle$$\n",
    "$$X|0\\rangle = |1\\rangle, X|1\\rangle = |0\\rangle$$\n",
    "\n",
    "We see that the **I** gate leaves the $|0\\rangle$ state unchanged, and the **X** gate transforms it into the $|1\\rangle$ state. \n",
    "So the easiest thing to do is to prepare a $|0\\rangle$ state, apply the given unitary to it and measure the resulting state in the computational basis:\n",
    "* If the measurement result is `Zero`, the measured state was $|0\\rangle$, and we know the unitary applied to it was the **I** gate.\n",
    "* If the measurement result is `One`, the measured state was $|1\\rangle$, and we know the unitary applied to it was the **X** gate.\n",
    "\n",
    "> In Q#, the freshly allocated qubits start in the $|0\\rangle$ state, so you don't need to do anything to prepare the necessary state before applying the unitary to it.\n",
    "> You also have to return the qubits you allocated to the $|0\\rangle$ state before releasing them. \n",
    "> You can do that by measuring the qubit using the `M` operation and applying the **X** gate if it was measured in the $|1\\rangle$ state, or you can use [`MResetZ`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.measurement.mresetz) operation that wraps this measurement and fixup into one operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T101_DistinguishIfromX_Test \n",
    "\n",
    "operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (q = Qubit()) {\n",
    "        unitary(q);\n",
    "        return M(q) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.1.-Identity-or-Pauli-X?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Identity or Pauli Z?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the identity (**I** gate)\n",
    "or the Pauli Z gate (**Z** gate). \n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **I** gate, 1 if the given operation is the **Z** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder, $Z = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}$\n",
    "\n",
    "We won't be able to distinguish **I** from **Z** by applying them to the basis states, since they both leave the $|0\\rangle$ state unchanged and add a phase to the $|1\\rangle$ state: \n",
    "\n",
    "$$I|0\\rangle = |0\\rangle, I|1\\rangle = |1\\rangle$$\n",
    "$$Z|0\\rangle = |0\\rangle, Z|1\\rangle = -|1\\rangle$$\n",
    "\n",
    "However, if we try applying these gates to a superposition of basis states, we'll start seeing a difference between the resulting states:\n",
    "\n",
    "$$I \\big(\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)\\big) = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$$\n",
    "$$Z \\big(\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)\\big) = \\frac{1}{\\sqrt2}(|0\\rangle \\color{blue}{-} |1\\rangle)$$\n",
    "\n",
    "These two states are orthogonal and can be distinguished by measuring them in the $\\{ |+\\rangle, |-\\rangle\\}$ basis using [`MResetX`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.measurement.mresetx) operation (which is equivalent to applying an **H** gate and measuring in the computational basis).\n",
    "\n",
    "> The task of distinguishing these two states is covered in more detail in the [Measurements kata](./..//Measurements/Measurements.ipynb#Task-1.3.-$|+\\rangle$-or-$|-\\rangle$?) and the corresponding workbook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T102_DistinguishIfromZ_Test \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishIfromZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (q = Qubit()) {\n",
    "        H(q);\n",
    "        unitary(q);\n",
    "        return MResetX(q) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.2.-Identity-or-Pauli-Z?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Z or S?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the **Z** gate\n",
    "or the **S** gate. \n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **Z** gate, 1 if the given operation is the **S** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants at most **twice**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder, $S = \\begin{bmatrix} 1 & 0 \\\\ 0 & i \\end{bmatrix}$\n",
    "\n",
    "This task differs from the previous two in that it allows you to apply the given unitary **twice**. \n",
    "Let's treat this as a hint that it is, and check how the given gates looks when applied twice. \n",
    "If you square the corresponding matrices (which is quite simple to do for diagonal matrices), you'll get\n",
    "\n",
    "$$Z^2 = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} = I, S^2 = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix} = Z$$\n",
    "\n",
    "This means that the task of identifying the *square* of the given unitary transformation is the same as distinguishing **I** from **Z** gates - and that's exactly the [task 1.2](#Task-1.2.-Identity-or-Pauli-Z?)!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T103_DistinguishZfromS_Test \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishZfromS (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (q = Qubit()) {\n",
    "        H(q);\n",
    "        unitary(q);\n",
    "        unitary(q);\n",
    "        return MResetX(q) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.3.-Z-or-S?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. Hadamard or X?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the Hadamard (**H**) gate\n",
    "or the **X** gate. \n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **H** gate, 1 if the given operation is the **X** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants at most **twice**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder, $H = \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}$\n",
    "\n",
    "The solution relies on the well-known identity $HXH = Z$ (i.e., Hadamard gate can be used to convert **X** to **Z** and vice versa). Applying a sequence of gates \"given unitary - **X** - unitary\" will be equivalent to $XXX = X$ gate if the unitary was **X**, and to $HXH = Z$ if the unitary was **H**. With this observation we need to distinguish **X** from **Z**, which can be done using the $|0\\rangle$ state: **X** gate will change it to $|1\\rangle$, and **Z** gate will leave it unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T104_DistinguishHfromX_Test \n",
    "\n",
    "operation DistinguishHfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (q = Qubit()) {\n",
    "        within {\n",
    "            unitary(q);\n",
    "        } apply {\n",
    "            X(q);\n",
    "        }\n",
    "        return M(q) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.4 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.4.-Hadamard-or-X?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. Z or $-$Z?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the **Z** gate\n",
    "or the minus **Z** gate (i.e., the gate $- |0\\rangle\\langle0| + |1\\rangle\\langle1|$). \n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **Z** gate, 1 if the given operation is the $-$**Z** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This task is more interesting: the given gates differ by a global phase they introduce (i.e., each of them is a multiple of the other), and the results of applying them to any single-qubit state are going to be indistinguishable by any measurement you can devise.\n",
    "\n",
    "Fortunately, we are given not just the unitary itself, but also its controlled variant, i.e., the gate which applies the given unitary if the control qubit or qubits are in the $|1\\rangle$ state, and does nothing if they are in the $|0\\rangle$ state.\n",
    "This allows us to use so called \"phase kickback\" trick, in which applying a controlled version of a gate allows us to observe the phase introduced by this gate on the control qubit. Indeed,\n",
    "\n",
    "| State | Controlled Z | Controlled $-$Z |\n",
    "|-------|---------------|------|\n",
    "| $|00\\rangle$ | $|00\\rangle$ | $|00\\rangle$ |\n",
    "| $|01\\rangle$ | $|01\\rangle$ | $|01\\rangle$ |\n",
    "| $|10\\rangle$ | $\\color{blue}{|10\\rangle}$  | $\\color{blue}{-|10\\rangle}$ |\n",
    "| $|11\\rangle$ | $\\color{blue}{-|11\\rangle}$ | $\\color{blue}{|11\\rangle}$  |\n",
    "\n",
    "We see that both controlled gates don't modify the states with the control qubit in the $|0\\rangle$ state, but if the control qubit is in the $|1\\rangle$ state, they introduce a $-1$ phase to different basis states. \n",
    "We can take advantage of this if we apply the controlled gate to a state in which the *control qubit* is in superposition, such as $\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle) \\otimes |0\\rangle$:\n",
    "\n",
    "$$\\text{Controlled Z}\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle) \\otimes |0\\rangle$$\n",
    "$$\\text{Controlled }-\\text{Z}\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle) \\otimes |0\\rangle$$\n",
    "\n",
    "After this we can measure the first qubit to distinguish $\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$ from $\\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$, like we did in [task 1.2](#Task-1.2.-Identity-or-Pauli-Z?).\n",
    "\n",
    "> In Q# we can express controlled version of a gate using [Controlled functor](https://docs.microsoft.com/en-us/quantum/user-guide/using-qsharp/operations-functions#controlled-functor): the first argument of the resulting gate will be an array of control qubits, and the second one - the arguments of the original gate (in this case just the target qubit)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T105_DistinguishZfromMinusZ_Test \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishZfromMinusZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        // prep (|0⟩ + |1⟩) ⊗ |0⟩\n",
    "        H(qs[0]);\n",
    "\n",
    "        Controlled unitary(qs[0..0], qs[1]);\n",
    "\n",
    "        return MResetX(qs[0]) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.5 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.5.-Z-or-$-$Z?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. Rz or R1 (arbitrary angle)?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the [**Rz** gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.rz)\n",
    "or the [**R1** gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.r1). \n",
    "\n",
    "This operation will take two parameters: the first parameter is the rotation angle, in radians, and the second parameter is the qubit to which the gate should be applied (matching normal **Rz** and **R1** gates in Q#).\n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **Rz** gate, 1 if the given operation is the **R1** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder, $$R_z(\\theta) = \\begin{bmatrix} e^{-i\\theta/2} & 0 \\\\ 0 & e^{i\\theta/2} \\end{bmatrix} \\text{, } \n",
    "R_1(\\theta) = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i\\theta} \\end{bmatrix} = e^{i\\theta/2} R_z(\\theta)$$\n",
    "\n",
    "We see that these two gates differ by a global phase $e^{i\\theta/2}$.\n",
    "In this problem we're free to choose the angle parameter which we'll pass to our gate, so we can choose an angle that make this global phase difference something easy to detect: for $\\theta = 2\\pi$ $e^{i\\theta/2} = -1$, so $R_z(\\theta) = -I$, and $R_1(\\theta) = I$.\n",
    "\n",
    "Now we need to distinguish **I** gate from $-$**I** gate, which can be done using controlled variant of the gate in exactly the same way as distinguishing **Z** gate from $-$**Z** gate in [task 1.6](#Task-1.5.-Z-or-$-$Z?)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T106_DistinguishRzFromR1_Test \n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation DistinguishRzFromR1 (unitary : ((Double, Qubit) => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        within {\n",
    "            H(qs[0]);\n",
    "        } apply {\n",
    "            Controlled unitary(qs[0..0], (2.0 * PI(), qs[1]));\n",
    "        }\n",
    "        return M(qs[0]) == Zero ? 1 | 0;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.6 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.6.-Rz-or-R1-(arbitrary-angle)?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. Y or XZ?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the **Y** gate\n",
    "or the sequence of Pauli **Z** and Pauli **X** gates (equivalent to applying the **Z** gate followed by the **X** gate).\n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **Y** gate, 1 if the given operation is the **XZ** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants at most **twice**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder, $$Y = \\begin{bmatrix} 0 & -i \\\\ i & 0 \\end{bmatrix} = iXZ$$\n",
    "\n",
    "We see that these two gates differ by a global phase $i = e^{i\\pi}$. Applying the gates twice will give us gates $Y^2 = I$ and $(XZ)^2 = XZXZ = -XXZZ = -I$, respectively.\n",
    "\n",
    "Now we need to distinguish **I** gate from $-$**I** gate, which is the same thing we did in the previous task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T107_DistinguishYfromXZ_Test \n",
    "\n",
    "operation DistinguishYfromXZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        // prep (|0⟩ + |1⟩) ⊗ |0⟩\n",
    "        within { H(qs[0]); }\n",
    "        apply {  \n",
    "            Controlled unitary(qs[0..0], qs[1]);\n",
    "            Controlled unitary(qs[0..0], qs[1]);\n",
    "        }\n",
    "\n",
    "        // 0 means it was Y\n",
    "        return M(qs[0]) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.7 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.7.-Y-or-XZ?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.8. Y, XZ, $-$Y or $-$XZ?\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the **Y** gate (possibly with an extra global phase of $-1$) or the sequence of Pauli **Z** and Pauli **X** gates (possibly with an extra global phase of $-1$).\n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:** \n",
    "* 0 if the given operation is the **Y** gate,\n",
    "* 1 if the given operation is the $-$**XZ** gate,\n",
    "* 2 if the given operation is the $-$**Y** gate,\n",
    "* 3 if the given operation is the **XZ** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants at most **three times**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 1\n",
    "\n",
    "In this task we have to distinguish 4 gates that were identical up to a global phase, i.e., gates $Y$, $iY$, $-Y$ and $-iY$ (in that order). \n",
    "\n",
    "One way to do this is \"by hand\", similar to the previous tasks. First we'll apply the controlled variant of the unitary twice and check whether the result is $I$ or $-I$ (which allows us to distinguish $\\pm Y$ and $\\pm iY$, since the first two gates squared will be equivalent to the $I$ gate, and the last two &mdash; to the $-I$ gate). Then we distinguish the gates in each group ($Y$ from $-Y$ or $iY$ from $-iY$) by applying the controlled variant of the unitary once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%kata T108_DistinguishYfromXZWithPhases_Test \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishYfromXZWithPhases (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using ((control, target) = (Qubit(), Qubit())) {\n",
    "        // Distinguish Y from iY\n",
    "        within {\n",
    "            H(control);\n",
    "        } apply {\n",
    "            Controlled unitary([control], target);\n",
    "            Controlled unitary([control], target);\n",
    "        }\n",
    "        Reset(target);\n",
    "        let isY = MResetZ(control) == Zero;\n",
    "        \n",
    "        // Distinguish Y from -Y and iY from -iY\n",
    "        within {\n",
    "            H(control);\n",
    "        } apply {\n",
    "            Controlled unitary([control], target);\n",
    "            // apply controlled variant of the gate we're expecting to compensate effect on target qubit\n",
    "            if (isY) {\n",
    "                CY(control, target);\n",
    "            } else {\n",
    "                CZ(control, target);\n",
    "                CX(control, target);\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        return (isY ? M(control) == Zero ? 0 | 2\n",
    "                    | M(control) == Zero ? 1 | 3);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 2\n",
    "\n",
    "An alternate solution takes advantage of [phase estimation](https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm) algorithm which, given a unitary and its eigenstate, allows to find its eigenvalue. If we prepare an eigenstate of the Y gate $\\frac{1}{\\sqrt2}(|0\\rangle + i|1\\rangle)$, it will be the eigenstate of all other gates as well, with eigenphases $0, \\pi/2, \\pi, 3\\pi/2$, respectively. You can convert the output of the phase estimation procedure into the return index directly.\n",
    "\n",
    "You can learn more about phase estimation in [this kata](../PhaseEstimation/PhaseEstimation.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "operation OraclePowerWrapper (U : (Qubit => Unit is Adj + Ctl), power : Int, target : Qubit[]) : Unit is Adj + Ctl {\n",
    "    for (_ in 1 .. power) {\n",
    "        U(target[0]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%kata T108_DistinguishYfromXZWithPhases_Test \n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Characterization;\n",
    "open Microsoft.Quantum.Oracles;\n",
    "\n",
    "operation DistinguishYfromXZWithPhases (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    // Run phase estimation on the unitary and the +1 eigenstate of the Y gate |0⟩ + i|1⟩\n",
    "\n",
    "    // Construct a phase estimation oracle from the unitary\n",
    "    let oracle = DiscreteOracle(OraclePowerWrapper(unitary, _, _));\n",
    "\n",
    "    // Allocate qubits to hold the eigenstate of U and the phase in a big endian register \n",
    "    mutable phaseInt = 0;\n",
    "    using ((eigenstate, phaseRegister) = (Qubit[1], Qubit[2])) {\n",
    "        let phaseRegisterBE = BigEndian(phaseRegister);\n",
    "        // Prepare the eigenstate of U\n",
    "        H(eigenstate[0]); \n",
    "        S(eigenstate[0]);\n",
    "        // Call library\n",
    "        QuantumPhaseEstimation(oracle, eigenstate, phaseRegisterBE);\n",
    "        // Read out the phase\n",
    "        set phaseInt = MeasureInteger(BigEndianAsLittleEndian(phaseRegisterBE));\n",
    "\n",
    "        ResetAll(eigenstate);\n",
    "        ResetAll(phaseRegister);\n",
    "    }\n",
    "\n",
    "    // Convert the measured phase into return value\n",
    "    return phaseInt;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.8 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.8.-Y,-XZ,-$-$Y-or-$-$XZ?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.9. Rz or Ry (fixed angle)?\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. An angle $\\theta \\in [0.01 \\pi; 0.99 \\pi]$.\n",
    "2. An operation that implements a single-qubit unitary transformation:\n",
    "either the [$R_z(\\theta)$ gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.rz)\n",
    "or the [$R_y(\\theta)$ gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry). \n",
    "\n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is the **Rz** gate, 1 if the given operation is the **Ry** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants **any number of times**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> As a reminder,\n",
    "> \n",
    "> $$R_z(\\theta) = \\begin{bmatrix} e^{-i\\theta/2} & 0 \\\\ 0 & e^{i\\theta/2} \\end{bmatrix} \\\\\n",
    "R_y(\\theta) = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$$\n",
    "\n",
    "The key observation here is that $R_z$ is a diagonal matrix and $R_y$ is not, so when applied to the $|0\\rangle$ state, the former will leave it unchanged (with an extra phase which is not observable), and the latter will convert it to a superposition $\\cos\\frac{\\theta}{2} |0\\rangle + \\sin\\frac{\\theta}{2} |1\\rangle$. The question is, how to distinguish those two states if they are not orthogonal (and for most values of $\\theta$ they will not be)?\n",
    "\n",
    "The task description gives you a big hint: it allows you to use the given unitary unlimited number of times, which points to a probabilistic solution (as opposed to deterministic solutions in all previous problems in this kata). Apply the unitary to the $|0\\rangle$ state and measure the result; if it is $|1\\rangle$, the unitary must be $R_y$, otherwise you can repeat the experiment again. After several iterations of measuring $|0\\rangle$ you can conclude that with high probability the unitary is $R_z$.\n",
    "\n",
    "To reduce the number of iterations after which you make the decision, you could apply the unitary several times to bring the overall rotation angle closer to $\\pi$: in case of $R_y$ gate this would allow you to rotate the state closer to the $|1\\rangle$ state, so that you'd detect it with higher probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "function ComputeRepetitions(angle : Double, offset : Int, accuracy : Double) : Int {\n",
    "    mutable pifactor = 0;\n",
    "    while (true) {\n",
    "        let pimultiple = PI() * IntAsDouble(2 * pifactor + offset);\n",
    "        let times = Round(pimultiple / angle);\n",
    "        if (AbsD(pimultiple - (IntAsDouble(times) * angle)) / PI() < accuracy) {\n",
    "            return times;\n",
    "        }\n",
    "        set pifactor += 1;\n",
    "    }\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%kata T109_DistinguishRzFromRy_Test \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishRzFromRy (theta : Double, unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    using (q = Qubit()) {\n",
    "        let times = ComputeRepetitions(theta, 1, 0.1);\n",
    "        mutable attempt = 1;\n",
    "        mutable measuredOne = false;\n",
    "        repeat {\n",
    "            for (_ in 1..times) {\n",
    "                unitary(q);\n",
    "            }\n",
    "            // for Rz, we'll never venture away from |0⟩ state, so as soon as we got |1⟩ we know it's not Rz\n",
    "            if (MResetZ(q) == One) {\n",
    "                set measuredOne = true;\n",
    "            }\n",
    "            // if we try several times and still only get |0⟩s, chances are that it is Rz\n",
    "        } until (attempt == 4 or measuredOne) \n",
    "        fixup {\n",
    "            set attempt += 1;\n",
    "        }\n",
    "        return measuredOne ? 1 | 0;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.9 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.9.-Rz-or-Ry-(fixed-angle)?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.11. Distinguish 4 Pauli unitaries\n",
    "\n",
    "**Input:** An operation that implements a single-qubit unitary transformation:\n",
    "either the identity (**I** gate) or one of the Pauli gates (**X**, **Y** or **Z** gate).\n",
    "The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:** \n",
    "* 0 if the given operation is the **I** gate,\n",
    "* 1 if the given operation is the **X** gate,\n",
    "* 2 if the given operation is the **Y** gate,\n",
    "* 3 if the given operation is the **Z** gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This task is quite different from the previous tasks in this section; \n",
    "at the first glance it might seem impossible to distinguish four different unitaries (i.e., get two bits of information) with just one unitary application! \n",
    "\n",
    "However, since the unitaries were chosen carefully (and you're not limited in the number of measurements you can do), it is possible. \n",
    "The solution uses the [Bell states](../Superposition/Superposition.ipynb#all-bell-states): the 4 orthogonal states which you can prepare by starting with the first of them $\\frac{1}{\\sqrt2}(|00\\rangle + |11\\rangle)$ and applying the gates **I**, **X**, **Z** and **Y**, respectively, to the first qubit. \n",
    "Thus the solution becomes: prepare the $\\frac{1}{\\sqrt2}(|00\\rangle + |11\\rangle)$ state, apply the unitary and measure the resulting state in Bell basis to figure out which of the Bell states it is \n",
    "(see the [Measurements kata](../Measurements/Measurements.ipynb#Task-1.12.-Distinguish-four-Bell-states.) for the details on how to do that)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T111_DistinguishPaulis_Test \n",
    "\n",
    "operation DistinguishPaulis (unitary : (Qubit => Unit is Adj+Ctl)) : Int {\n",
    "    // apply operation to the 1st qubit of a Bell state and measure in Bell basis\n",
    "    using (qs = Qubit[2]) {\n",
    "        within {\n",
    "            H(qs[0]);\n",
    "            CNOT(qs[0], qs[1]);\n",
    "        } apply {\n",
    "            unitary(qs[0]);\n",
    "        }\n",
    "\n",
    "        // after this I -> 00, X -> 01, Y -> 11, Z -> 10\n",
    "        let ind = MeasureInteger(LittleEndian(qs));\n",
    "        let returnValues = [0, 3, 1, 2];\n",
    "        return returnValues[ind];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.11 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-1.11.-Distinguish-4-Pauli-unitaries)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Multi-Qubit Gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. $I \\otimes X$ or $\\text{CNOT}$?\n",
    "\n",
    "**Input:** An operation that implements a two-qubit unitary transformation:\n",
    "either the $I \\otimes X$ (the **X** gate applied to the second qubit)\n",
    "or the $\\text{CNOT}$ gate with the first qubit as control and the second qubit as target.\n",
    "* The operation will accept an array of qubits as input, but it will fail if the array is empty or has one or more than two qubits.\n",
    "* The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is $I \\otimes X$, 1 if the given operation is the $\\text{CNOT}$ gate.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's consider the effect of these gates on the basis states:\n",
    "\n",
    "| State | $I \\otimes X$ | **CNOT** |\n",
    "|-------|---------------|------|\n",
    "| $|00\\rangle$ | $|01\\rangle$ | $|00\\rangle$ |\n",
    "| $|01\\rangle$ | $|00\\rangle$ | $|01\\rangle$ |\n",
    "| $|10\\rangle$ | $|11\\rangle$ | $|11\\rangle$ |\n",
    "| $|11\\rangle$ | $|10\\rangle$ | $|10\\rangle$ |\n",
    "\n",
    "We can see that applying these two gates to states with the first qubit in the $|1\\rangle$ state yields identical results, but applying them to states with the first qubit in the $|0\\rangle$ state produces states that differ in the second qubuit.\n",
    "This makes sense, since the **CNOT** gate is defined as \"apply **X** gate to the target qubit if the control qubit is in the $|1\\rangle$ state, and do nothing if it is in the $|0\\rangle$ state\".\n",
    "\n",
    "Thus, the easiest solution is: allocate two qubits in the $|00\\rangle$ state and apply the unitary to them, then measure the second qubit; if it is `One`, the gate is $I \\otimes X$, otherwise it's **CNOT**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T201_DistinguishIXfromCNOT_Test\n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation DistinguishIXfromCNOT (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        unitary(qs);\n",
    "        return MResetZ(qs[1]) == One ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-2.1.-$I-\\otimes-X$-or-$\\text{CNOT}$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Figure out the direction of $\\text{CNOT}$\n",
    "\n",
    "**Input:** An operation that implements a two-qubit unitary transformation:\n",
    "either the $\\text{CNOT}$ gate with the first qubit as control and the second qubit as target ($\\text{CNOT}_{12}$)\n",
    "or the $\\text{CNOT}$ gate with the second qubit as control and the first qubit as target ($\\text{CNOT}_{21}$).\n",
    "* The operation will accept an array of qubits as input, but it will fail if the array is empty or has one or more than two qubits.\n",
    "* The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is $\\text{CNOT}_{12}$, 1 if the given operation is $\\text{CNOT}_{21}$.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Again, let's consider the effect of these gates on the basis states:\n",
    "\n",
    "| State | $\\text{CNOT}_{12}$ | $\\text{CNOT}_{21}$ |\n",
    "|-------|---------------|------|\n",
    "| $|00\\rangle$ | $|00\\rangle$ | $|00\\rangle$ |\n",
    "| $|01\\rangle$ | $|01\\rangle$ | $|11\\rangle$ |\n",
    "| $|10\\rangle$ | $|11\\rangle$ | $|10\\rangle$ |\n",
    "| $|11\\rangle$ | $|10\\rangle$ | $|01\\rangle$ |\n",
    "\n",
    "We can see that applying these two gates to any basis state other than $|00\\rangle$ yields different results, and we can use any of these states to distinguish the unitaries.\n",
    "\n",
    "Thus, the easiest solution is: prepare two qubits in the $|01\\rangle$ state and apply the unitary to them, then measure the first qubit; if it is still `Zero`, the gate is $\\text{CNOT}_{12}$, otherwise it's $\\text{CNOT}_{21}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T202_CNOTDirection_Test\n",
    "\n",
    "operation CNOTDirection (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        within { X(qs[1]); }\n",
    "        apply { unitary(qs); }\n",
    "        return M(qs[0]) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-2.2.-Figure-out-the-direction-of-$\\text{CNOT}$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. $\\text{CNOT}_{12}$ or $\\text{SWAP}$?\n",
    "\n",
    "**Input:** An operation that implements a two-qubit unitary transformation:\n",
    "either the $\\text{CNOT}$ gate with the first qubit as control and the second qubit as target ($\\text{CNOT}_{12}$)\n",
    "or the $SWAP$ gate.\n",
    "* The operation will accept an array of qubits as input, but it will fail if the array is empty or has one or more than two qubits.\n",
    "* The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  0 if the given operation is $\\text{CNOT}_{12}$, 1 if the given operation is $\\text{SWAP}$.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants exactly **once**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Again, let's consider the effect of these gates on the basis states:\n",
    "\n",
    "| State | $\\text{CNOT}_{12}$ | $\\text{SWAP}$ |\n",
    "|-------|---------------|------|\n",
    "| $|00\\rangle$ | $|00\\rangle$ | $|00\\rangle$ |\n",
    "| $|01\\rangle$ | $|01\\rangle$ | $|10\\rangle$ |\n",
    "| $|10\\rangle$ | $|11\\rangle$ | $|01\\rangle$ |\n",
    "| $|11\\rangle$ | $|10\\rangle$ | $|11\\rangle$ |\n",
    "\n",
    "Same as in the previous task, applying these two gates to any basis state other than $|00\\rangle$ yields different results, and we can use any of these states to distinguish the unitaries.\n",
    "\n",
    "The easiest solution is: prepare two qubits in the $|01\\rangle$ state and apply the unitary to them, then measure the first qubit; if it is still `Zero`, the gate is $\\text{CNOT}_{12}$, otherwise it's $\\text{SWAP}$. Remember that this time the second qubit might end up in $|1\\rangle$ state, so it needs to be reset to $|0\\rangle$ before releasing it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T203_DistinguishCNOTfromSWAP_Test\n",
    "\n",
    "operation DistinguishCNOTfromSWAP (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {\n",
    "    using (qs = Qubit[2]) {\n",
    "        X(qs[1]);\n",
    "        unitary(qs);\n",
    "        Reset(qs[1]);\n",
    "        return M(qs[0]) == Zero ? 0 | 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-2.3.-$\\text{CNOT}_{12}$-or-$\\text{SWAP}$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Identity, $\\text{CNOT}$s or $\\text{SWAP}$?\n",
    "\n",
    "**Input:** An operation that implements a two-qubit unitary transformation:\n",
    "either the identity ($I \\otimes I$), the $\\text{CNOT}$ gate with one of the qubits as control and the other qubit as a target, \n",
    "or the $SWAP$ gate.\n",
    "* The operation will accept an array of qubits as input, but it will fail if the array is empty or has one or more than two qubits.\n",
    "* The operation will have Adjoint and Controlled variants defined.\n",
    "\n",
    "**Output:**  \n",
    "\n",
    "* 0 if the given operation is $I \\otimes I$, \n",
    "* 1 if the given operation is $\\text{CNOT}_{12}$,\n",
    "* 2 if the given operation is $\\text{CNOT}_{21}$,\n",
    "* 3 if the given operation is $\\text{SWAP}$.\n",
    "\n",
    "You are allowed to apply the given operation and its adjoint/controlled variants at most **twice**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "In this problem we are allowed to use the given unitary twice, so we can split our decision-making process in two phases:\n",
    "\n",
    "1. Apply the unitary to the $|11\\rangle$ state; $\\text{CNOT}_{12}$ will yield the $|10\\rangle$ state, $\\text{CNOT}_{21}$ &mdash; $|01\\rangle$, and both $I \\otimes I$ and $\\text{SWAP}$ gates will leave the state unchanged.\n",
    "2. Now to distinguish $I \\otimes I$ from $\\text{SWAP}$, we can use the $|01\\rangle$ state: $I \\otimes I$ gate will leave it unchanged, while $\\text{SWAP}$ will yield $|10\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T204_DistinguishTwoQubitUnitaries_Test\n",
    "\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation DistinguishTwoQubitUnitaries (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {\n",
    "    // first run: apply to |11⟩; CNOT₁₂ will give |10⟩, CNOT₂₁ will give |01⟩, II and SWAP will remain |11⟩\n",
    "    using (qs = Qubit[2]) {\n",
    "        ApplyToEach(X, qs);\n",
    "        unitary(qs);\n",
    "        let ind = MeasureInteger(LittleEndian(qs));\n",
    "        if (ind == 1 or ind == 2) {\n",
    "            // respective CNOT\n",
    "            return ind;\n",
    "        }\n",
    "    }\n",
    "    // second run: distinguish II from SWAP, apply to |01⟩: II will remain |01⟩, SWAP will become |10⟩\n",
    "    using (qs = Qubit[2]) {\n",
    "        X(qs[1]);\n",
    "        unitary(qs);\n",
    "        let ind = MeasureInteger(LittleEndian(qs));\n",
    "        return ind == 1 ? 3 | 0;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.4 of the Distinguish Unitaries kata.](./DistinguishUnitaries.ipynb#Task-2.4.-Identity,-$\\text{CNOT}$s-or-$\\text{SWAP}$?)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}