1-Basic_Quantum_Concepts/2-Gates.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.2 Gates\n ",
    "\n",
    "* [Unitary matrix](./1-Basic_Quantum_Concepts/2-Gates.ipynb#unitarymatrix)\n",
    "* [The Control-NOT Gate (CNOT)](./1-Basic_Quantum_Concepts/2-Gates.ipynb#cnot)\n",
    "    * [Q# exercise: CNOT gate](./1-Basic_Quantum_Concepts/2-Gates.ipynb#qcnot)\n",
    "* [Circuit Representation](./1-Basic_Quantum_Concepts/2-Gates.ipynb#circuit)\n",
    "* [Hadamard Gate](./1-Basic_Quantum_Concepts/2-Gates.ipynb#hadamard)\n",
    "    * [Q# exercise: H gate](./1-Basic_Quantum_Concepts/2-Gates.ipynb#qh)\n",
    "* [Bloch Sphere](./1-Basic_Quantum_Concepts/2-Gates.ipynb#boch)\n",
    "* [Pauli Gates](./1-Basic_Quantum_Concepts/2-Gates.ipynb#pauli)\n",
    "    * [Q# exercise: Pauli gates](./1-Basic_Quantum_Concepts/2-Gates.ipynb#qpauli)\n",
    "* [Measurement](./1-Basic_Quantum_Concepts/2-Gates.ipynb#measurement)\n",
    "    * [Q# exercise: Measurement using M operation](./1-Basic_Quantum_Concepts/2-Gates.ipynb#qmeasurement)\n",
    "* [Interference](./1-Basic_Quantum_Concepts/2-Gates.ipynb#interference)\n",
    "\n",
    "### Unitary matrix\n <a id='#unitarymatrix'></a>",
    "\n",
    "Since qubit states are represented with vectors, the way to manipulate them is through matrix multiplications, which transforms a vector into a different vector. Such matrix operations applied onto the states are called \"gates\". In quantum mechanics, matrices representing gates are required to be unitary (see _Math insert - unitary, adjoint or Hermitian conjugate_ ). This is to ensure normalization condition, i.e. probabilities add up to 1, mentioned in Section 1.1. Unitarity also constraints the operation to be reversible. This is intuitive as one can find an operation that reverts the gate and returns a system back to its original state.\n",
    "\n",
    "![Figure 1.2 Gate](media/gate.png)\n",
    "\n",
    "_Math insert – unitary, adjoint or Hermitian conjugate_ --------------------------------------------\n",
    "\n",
    ">A matrix $U$ is unitary if $U^{\\dagger}U=I$, where $I$ is the identity matrix and the \"$\\dagger$\" symbol (reads\n",
    ">\"dagger\") means adjoint or Hermitian conjugate of matrix $U$. It can be further written as\n",
    ">$U^{\\dagger}=(U*)^{T}=(U^{T})*$, where \"$T$\" denotes transpose and \"*\" complex conjugate:\n",
    ">\n",
    ">$\\begin{pmatrix} U_1 \\\\ U_2 \\\\...\\\\U_N \\end{pmatrix}^T = \\begin{pmatrix} U_1 & U_2 & ... & U_N \\end{pmatrix}$\n",
    ">and if $a=a_0+ia_1$, then $a*=a_0-ia_1$ by definition. Therefore, \n",
    ">$\\begin{pmatrix} a & b \\\\c & d \\end{pmatrix}^{\\dagger}=\\begin{pmatrix} a* & b* \\\\c* & d* \\end{pmatrix}$.\n",
    ">\n",
    ">Let's take a complex number $c=a+ib$; its complex conjugate will be $c*=a-ib$. Multiplying them:\n",
    ">$c*c=a^2+b^2=|c|^2$.\n",
    ">\n",
    ">Now, let's take a matrix $x$ as follows:\n",
    ">\n",
    "$x=\\begin{bmatrix} a_1+ib_1 \\\\a_2+ib_2 \\\\a_3+ib_3 \\\\a_4+ib_4 \\end{bmatrix}$.\n",
    ">\n",
    ">The adjoint $x^{\\dagger}$ will be:\n",
    ">$x^{\\dagger}=\\begin{bmatrix} a_1-ib_1 & a_2-ib_2 & a_3-ib_3 & a_4-ib_4 \\end{bmatrix}$.\n",
    ">\n",
    ">Multiplying them:\n",
    ">$x^{\\dagger}x=\\begin{bmatrix} a_1-ib_1 & a_2-ib_2 & a_3-ib_3 & a_4-ib_4 \\end{bmatrix}*\\begin{bmatrix} a_1+ib_1 \\\\a_2+ib_2 \\\\a_3+ib_3 \\\\a_4+ib_4 \\end{bmatrix}$.\n",
    ">$=[a_1^2+b_1^2+a_2^2+b_2^2+a_3^2+b_3^2+a_4^2+b_4^2]$.\n",
    "> \n",
    ">If $x$ represents an amplitude matrix in a 2-qubit system, then from the concepts you\n",
    ">have learned from the previous sessions, we can conclude the following:\n",
    ">$Pr(|00\\rangle)=|a_1+ib_1|^2=a_1^2+b_1^2$\n",
    ">$Pr(|01\\rangle)=|a_2+ib_2|^2=a_2^2+b_2^2$\n",
    ">$Pr(|10\\rangle)=|a_3+ib_3|^2=a_3^2+b_3^2$\n",
    ">$Pr(|11\\rangle)=|a_4+ib_4|^2=a_4^2+b_4^2$.\n",
    ">And $x^{\\dagger}x= sum of probablities of all basis states = 1$.\n",
    ">\n",
    ">Now, let's say we apply a gate whose matrix is $U$ on $x$ and the resultant state is\n",
    ">$y$ as follows:\n",
    ">$y=Ux$\n",
    ">Applying conjugate transpose on both sides:\n",
    ">$y^{\\dagger}y=(Ux)^{\\dagger}$\n",
    ">After multiplication:\n",
    ">$y^{\\dagger}y=(Ux)^{\\dagger}Ux$\n",
    ">$=x^{\\dagger}U^{\\dagger}Ux$ (because $(AB)^{\\dagger}=B^{\\dagger}A{\\dagger}$; you can easily find the proog for this online).\n",
    ">\n",
    ">Now, if $U$ is unitary, then by definition $U^{\\dagger}=U^{-1}$. It implies:\n",
    ">$y^{\\dagger}y=x^{\\dagger}A^{-1}Ax$,\n",
    ">$y^{\\dagger}y=x^{\\dagger}Ix$,\n",
    ">$y^{\\dagger}y=x^{\\dagger}x$,\n",
    ">$y^{\\dagger}y=1$.\n",
    ">\n",
    ">It implies that $y$ is also a valid quantum state. This is possible only because we assume\n",
    ">that $U^{\\dagger}=U^{-1}$ ($U$ is unitary). The bottom line here is that all the matrices (gates) we\n",
    ">use in quantum computing must be unitary.\n",
    "\n",
    "### The Control-NOT Gate (CNOT)\n <a id='#cnot'></a>",
    "\n",
    "Let's introduce a commonly used gate, CNOT. One may know that NOT gate in classical computing is an operation that flips 0s and 1s. The CNOT gate acts on a two-qubit state. The two-qubit states is represented by a four-element vector, with the first qubit represented by the first two elements of the vector, and the second qubit by the last two elements. A CNOT gate flips the second qubit based on the state of the first qubit. Thus, the first qubit is called the \"control\" qubit, while the second one is called the \"target\" qubit. The CNOT gate takes the form of a 4 x 4 matrix.\n",
    "\n",
    "$CNOT=\\begin{bmatrix} 1 & 0 & 0 & 0\\\\0 & 1 & 0 & 0\\\\ 0 & 0 & 0 & 1\\\\ 0 & 0 & 1 & 0 \\end{bmatrix}$.\n",
    "One can see that the first quadrant is a 2 x 2 identity matrix. It keeps the control qubit intact after\n",
    "multiplication. The fourth quadrant is the 2 x 2 NOT gate. It flips the target qubit from \"0\" to be \"1\" and\n",
    "from \"1\" to be \"0\" if the control qubit is \"1\" but does nothing if the control qubit is \"0\". Here's an example\n",
    "to examine this behavior.\n",
    "\n",
    "$CNOT|10\\rangle = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\0 & 1 & 0 & 0 \\\\0 & 0 & 0 & 1 \\\\0 & 0 & 1 & 0 \\end{bmatrix} \\begin{pmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{pmatrix}$\n",
    "$=\\begin{pmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{pmatrix} = |11\\rangle$. eq. (1.2.1)\n",
    "\n",
    "Similarly, $C|00\\rangle=|00\\rangle$, $C|01\\rangle=|01\\rangle$ and $C|11\\rangle=|10\\rangle$. Use _Math insert – matrix multiplication_ to show\n",
    "these equations.\n",
    "\n",
    "_Math insert - matrix multiplication_ -------------------------------------------------------------------\n",
    ">\n",
    ">Gates are N by N matrices that multiply to state with $2^N$ vector elements. They follow\n",
    ">the rules such that\n",
    ">$\\begin{bmatrix} a & b \\\\c & d \\end{bmatrix}\\begin{pmatrix} x \\\\y \\end{pmatrix}=\\begin{pmatrix} ax+by \\\\ cx+dy \\end{pmatrix}$,\n",
    ">$\\begin{bmatrix} a & b & c \\\\d & e & f \\\\g & h & i \\end{bmatrix}\\begin{pmatrix} x \\\\ y \\\\ z \\end{pmatrix} = \\begin{pmatrix} ax+by+cs \\\\dx+ey+fz \\\\gx+hy+iz \\end{pmatrix}$,\n",
    ">and so on.\n",
    "\n",
    "### Q# exercise: CNOT gate\n<a id='#qcnot'></a>",
    "\n",
    "Local:\n",
    "1. Go to Quantum Katas: https://github.com/Microsoft/QuantumKatas Download or clone.\n",
    "\n",
    "2. In Visual Studio (Code) open folder \"BasicGates\". The CNOT exercise is in Tasks.qs\n",
    "\n",
    "3. Read about CNOT in Microsoft.Quantum.Intrinsic Reference Documentation\n",
    "**Link:** https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic\n",
    "\n",
    "4. The command for CNOT is\n",
    "\n",
    "operation CNOT (control : Qubit, target : Qubit) : ()\n",
    "\n",
    "5. Don't change anything and run dotnet test in the integrated terminal. This should automatically build the kata project and run all unit tests; initially, all unit tests should fail. You should get\n",
    "\n",
    "![Figure CNOT Gate1](media/CNOTgate_excercise.png)\n",
    "\n",
    "6. Open Tasks.qs file. I n \"Task 2.1. Two-qubit gate – 1\" in the body, add the appropriate command inside the operation and run dotnet test again.\n",
    "\n",
    "![Figure CNOT Gate1](media/CNOTgate_excercise2.png)\n",
    "\n",
    "7. If your answer is correct, you should get\n",
    "\n",
    "![Figure CNOT Gate1](media/CNOTgate_excercise3.png)\n",
    "\n",
    "8. The Katas has many projects in this exercise. Feel free to try out the other ones. As you answer more questions correctly, the number of passed tests will increase accordingly.\n",
    "\n",
    "Jupyter Notebook:\n",
    "\n",
    "1. Go to https://github.com/microsoft/QuantumKatas/tree/master/BasicGates and follow link to Jupyter Notebook to the BasicGates exercise.\n",
    "\n",
    "2. Run the package and jump to Task 2.1. It is the same exercise as above.\n",
    "\n",
    "### Circuit Representation\n<a id='#circuit'></a>",
    "\n",
    "Matrix calculations can sometimes get messy. To make quantum operations easier to follow, a graphic representation below is used to illustrate quantum operations. Because the diagram looks like a circuit, it is called a circuit representation. A qubit is denoted by a horizontal line:\n",
    "\n",
    "![Figure Circuit Representation of Qubits](media/circuitrepresentationqubit.png)\n",
    "\n",
    "Figure 1.2.1 Circuit representation of qubits.\n",
    "\n",
    "The purpose of using horizontal lines is to provide a visualization of qubits' evolution over time. Individual qubits are placed in parallel so that gates can connect them vertically in the diagram. What happens to each qubit is apparent. For example, CNOT introduced above can be captured in the following circuit diagram:\n",
    "\n",
    "![Figure Circuit Representation of CNOT Gate](media/circuitrepresentationcnot.png)\n",
    "\n",
    "Figure 1.2.2 Circuit representation of CNOT gate.\n",
    "\n",
    "Control qubit |$A$⟩ is unchanged after CNOT but target qubit |$B$⟩ becomes |$B$⊕$A$⟩ based on the control.\n",
    "\n",
    "### Hadamard Gate\n<a id='#hadamard'></a>",
    "\n",
    "Another frequently used gate is the Hadamard gate, H. Its matrix form is written as\n",
    "\n",
    "$H = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} {-\\frac{1}{\\sqrt{2}}} \\end{bmatrix}$\n",
    "\n",
    "The Hadamard gate puts states |0⟩ and |1⟩ into a superposition of the two with equal probability, i.e.\n",
    "\n",
    "$H|0⟩ = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} {-\\frac{1}{\\sqrt{2}}} \\end{bmatrix} \\begin{pmatrix} 1 \\\\ 0 \\end{pmatrix}$\n",
    "\n",
    "$= \\begin{pmatrix} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} \\end{pmatrix} = \\frac{1}{\\sqrt{2}} \\begin{pmatrix} 1 \\\\ 0 \\end{pmatrix} + \\frac{1}{\\sqrt{2}} \\begin{pmatrix} 0 \\\\ 1 \\end{pmatrix}$\n",
    "\n",
    "$= \\frac{1}{\\sqrt{2}} \\begin{pmatrix} |0⟩ + |1⟩ \\end{pmatrix} ≡ |+⟩ $, eq. (1.2.2)\n",
    "\n",
    "and\n",
    "\n",
    "$H|1⟩ = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} {-\\frac{1}{\\sqrt{2}}} \\end{bmatrix} \\begin{pmatrix} 0 \\\\ 1 \\end{pmatrix}$\n",
    "\n",
    "$= \\frac{1}{\\sqrt{2}} \\begin{pmatrix} |0⟩ + |1⟩ \\end{pmatrix} ≡ |-⟩ $, eq. (1.2.3)\n",
    "\n",
    "The symbol \"≡\" here means \"defined as\" or \"equivalent to\". In other words, the Hadamard gate converts classical states, i.e. |0⟩ and |1⟩, into quantum states |+⟩ and |−⟩. It also converts quantum states quantum states |+⟩ and |−⟩ back to classical states |0⟩ and |1⟩. Readers should prove $H$|+⟩= |0⟩ and $H$|−⟩= |1⟩ as an exercise. The negative sign in the fourth element in the $H$ matrix highlighted in eq. (1.2.3) has the significance. It makes the operation reversible. Without it, applying $H$ to the states |+⟩ and |−⟩ would give indistinguishable results. The circuit representation of a Hadamard gate is:\n",
    "\n",
    "![Figure Circuit Representation of Hadamard Gate](media/circuitrepresentationhadamard.png)\n",
    "\n",
    "Figure 1.2.3 Circuit representation of the Hadamard gate.\n",
    "\n",
    "It acts on a single qubit.\n",
    "\n",
    "### Q# exercise: H gate\n<a id='#qh'></a>",
    "\n",
    "1. In Quantum Katas Basic Gate is designed to implement H gate. Try the exercise on Jupiter Notebook.\n",
    "\n",
    "2. To further your familiarity, let's do another exercise in QuantumComputingViaQSharpSolution introduced in session 1.1.\n",
    "\n",
    "3. Open 07_Demo H Operation.qs in Visual Studio (Code) and run dotnet run.\n",
    "\n",
    "4. \"M\" here is a measurement operation. We will talk about it at the end of the session. \n",
    "\n",
    "M(qubits$[0]$)\n",
    "\n",
    "5. If the measured result is 0, it'll output \"False\"; if \"1\", it'll output \"true\". Run the script several times, you'll see the output changes randomly because H puts the qubit into a state with equal probability of getting \"0\" and \"1\".\n",
    "\n",
    "6. Also run 07_Demo H count-mutable-set-for-ToStringI. Half of the time, you will measure the state to be in |0⟩ and half of the time in |1⟩.\n",
    "\n",
    "### Bloch Sphere\n<a id='#bloch'></a>",
    "\n",
    "There is yet another graphic representation to visualize a qubit. It gives more information about a qubit than the circuit representation. It is called a Bloch sphere - a 3D sphere drawn in 2D with the North and South poles representing states |0⟩ and |1⟩, respectively.\n",
    "\n",
    "![Figure Bloch Sphere States Zero and One](media/blochspherezeroone.png)\n",
    "\n",
    "Figure 1.2.4 Bloch sphere with states |0⟩ and |1⟩ labelled by red dots.\n",
    "\n",
    "A Hadamard gate applied to the state |0⟩ or |1⟩ moves the state to |+⟩ or |−⟩ which is a superposition\n",
    "\n",
    "of |0⟩ and |1⟩ with the same amplitude $\\frac{1}{\\sqrt{2}}$. This means the state |+⟩ or |−⟩ is on the equator on the Bloch sphere.\n",
    "\n",
    "![Figure Bloch Sphere States Plus Minus](media/blochsphereplusminus.png)\n",
    "\n",
    "Figure 1.2.5 Bloch sphere with states |0⟩ and |1⟩ labelled by red dots and states |+⟩ and |−⟩ by blue\n",
    "dots.\n",
    "\n",
    "This is illustrating eq. (1.2.2 and 1.2.3) graphically on a Bloch sphere. It looks as if the states are rotated along\n",
    "the sphere about the y-axis by 90 degrees. But it is actually not a one-step rotation. This will be explained\n",
    "later in Pauli Gates.\n",
    "\n",
    "In general, an arbitrary one-qubit state $|\\psi⟩$ can be represented by a point anywhere on a Bloch sphere. $|\\psi⟩$ is on the sphere with angle $\\phi$ away from the x-axis and angle $\\theta$ away from the z-axis. Thus it can be written as |$\\psi⟩=\\cos\\frac{\\theta}{2}|0⟩+e^{-i\\phi}\\sin\\frac{\\theta}{2}|1⟩$, which is a superposition of states |0⟩ and |1⟩ with the angles defining the amplitudes. This further makes it clear that the states |0⟩ and |1⟩ are just two special cases with $\\theta$ = 0° and 180°, respectively.\n",
    "\n",
    "![Figure Bloch Sphere Arbitrary](media/blochspherearbitrary.png)\n",
    "\n",
    "Figure 1.2.6 Bloch sphere with an arbitrary state $|\\psi⟩$ labelled by a red dot.\n",
    "\n",
    "### Pauli Gates\n<a id='#pauli'></a>",
    "\n",
    "Since a general one-qubit state can be represented on a Bloch sphere with relative angles to the axes,\n",
    "what the gates do is to changes the angles, altering the position on the sphere that represents the state.\n",
    "We introduce three special rotational gates below named after physicist Wolfgang Pauli.\n",
    "\n",
    "Pauli X gate is the NOT gate that rotates the state about the x-axis by 180 degrees.\n",
    "\n",
    "$X = \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix}$, \n",
    "\n",
    "so that\n",
    "\n",
    "$X\\begin{pmatrix} \\alpha \\\\ \\beta \\end{pmatrix} = \\begin{pmatrix} \\beta \\\\ \\alpha \\end{pmatrix}$.\n",
    "\n",
    "It has the effect of swapping the coefficients, $\\alpha$ and $\\beta$ (Figure 1.2.7). Thus, a |0⟩ state \"flips\" to a |1⟩ and a\n",
    "|1⟩ state \"flips\" to a |0⟩.\n",
    "\n",
    "Pauli Y gate is a rotation about the y-axis by 180°. Not only does it flip 0s and 1s, the complex numbers $i$ and $-i$ change the phase of the vector (Figure 1.7).\n",
    "\n",
    "$Y = \\begin{bmatrix} 0 & -i \\\\ i & 0 \\end{bmatrix}$,\n",
    "\n",
    "so that\n",
    "\n",
    "$Y\\begin{pmatrix} \\alpha \\\\ \\beta \\end{pmatrix} = i\\begin{pmatrix} -\\beta \\\\ \\alpha \\end{pmatrix}$.\n",
    "\n",
    "Pauli Z gate rotates about the z-axis by 180°. Without the minus sign in the fourth element, it\n",
    "would be an identity matrix, but the minus sign provides a phase shift to |1⟩ (Figure 1.2.7).\n",
    "\n",
    "$Z = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}$,\n",
    "\n",
    "so that\n",
    "\n",
    "$Z\\begin{pmatrix} \\alpha \\\\ \\beta \\end{pmatrix} = \\begin{pmatrix} \\alpha \\\\ -\\beta \\end{pmatrix}$.\n",
    "\n",
    "![Figure Bloch Sphere Pauli Interactions](media/blochspherepauli.png)\n",
    "\n",
    "Figure 1.2.7 Bloch sphere representation of the Pauli gate interactions. Graph copied from Microsoft quantum computing.\n",
    "\n",
    "In general, rotation gates, R, about an axis can be described by the angles $\\phi$ and $\\theta$ in Figure 1.2.6:\n",
    "\n",
    "$R_z(\\phi)=\\begin{pmatrix} e^{i\\phi/2} & 0 \\\\ 0 & e^{-i\\phi/2} \\end{pmatrix}$,\n",
    "\n",
    "$R_y(\\theta)=\\begin{pmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{pmatrix}$,\n",
    "\n",
    "and\n",
    "\n",
    "$R_x(\\theta)=\\begin{pmatrix} \\cos\\frac{\\theta}{2} & -i\\sin\\frac{\\theta}{2} \\\\ -i\\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{pmatrix}$\n",
    "\n",
    "$= R_z(\\frac{\\pi}{2})R_y(\\theta)R_z(-\\frac{\\pi}{2})$ \n",
    "\n",
    "In fact, any arbitrary single quantum logic gate can be decomposed into a series of rotation matrices:\n",
    "\n",
    "$U=e^{i\\gamma} \\begin{bmatrix} e^{-i\\phi/2} & 0 \\\\ 0 & e^{i\\phi/2} \\end{bmatrix} \\begin{bmatrix} \\cos(\\frac{\\theta}{2}) & -\\sin(\\frac{\\theta}{2}) \\\\ \\sin(\\frac{\\theta}{2}) & \\cos(\\frac{\\theta}{2}) \\end{bmatrix}$\n",
    "\n",
    "with the only constraint on the gate being unitary. Here, $e^{i\\gamma}$ is a global phase shift that can be added without affecting the behavior.\n",
    "\n",
    "Now, if we revisit the Hadamard gate, it can be decomposed as a rotation about the x-axis by 180° followed by a clockwise rotation about the y-axis by 90°. The negative sign in the Hadamard gate determines the direction of rotation. |+⟩ and |−⟩ have opposite signs that put them on opposite sides of the Bloch sphere.\n",
    "\n",
    "![Figure Bloch Sphere Hadamard](media/blochspherehadamard.png)\n",
    "\n",
    "Figure 1.2.8 Hadamard gate on Block sphere using |0⟩ as the initial state as an example. Graph copied from Microsoft quantum computing.\n",
    "\n",
    "The circuit representation of the Pauli gates and general rotation gates are\n",
    "\n",
    "![Figure Bloch Sphere Hadamard](media/circuitrepresentationpauli.png)\n",
    "\n",
    "Figure 1.2.9 Circuit representation of the Pauli X, Y, Z and R gates. Pauli X gate is the same as a NOT gate.\n",
    "\n",
    "### Q# exercise: Pauli gates\n<a id='#qpauli'></a>",
    "\n",
    "1. Go to Quantum Katas: https://github.com/Microsoft/QuantumKatas introduced earlier in the CNOT excercise.\n",
    "\n",
    "2. In Visual Studio (Code) open folder \"BasicGates\" and then Tasks.qs. Or go to Basic Gates in Quantum Katas Jupiter Notebook.\n",
    "\n",
    "3. Try Task 1.1, 1.3, 1.4 and 1.6.\n",
    "\n",
    "4. Read more about other gates:\n",
    "\n",
    "    https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview\n",
    "\n",
    "### Measurement – not a gate\n<a id='#measurement'></a>",
    "\n",
    "Measurements are different from gates. Gates are unitary which makes operations reversible. Gates acting upon a quantum system do not destroy the system or make connections between the system and the outside world. Applying a gate does not lose information. However, when we in the outside world want to obtain information from the system, we need to measure it. Measuring a system brings it into contact with the outside world, irrevocably destroying information. Thus, measurement is, in general, not reversible – the system cannot be brought back to its state before the measurement. One consequence of this difference is that a measurement cannot be executed by a gate. It is an interaction between the system and its environment. A parameter or physical variable measured from a quantum system is called an \"observable\" (because we can observe it). Momentum, mass, velocity and energy are all observables.\n",
    "\n",
    "![Figure Measurement](media/measurement.png)\n",
    "\n",
    ">_Physics insert – measurement_ -------------------------------------------------------------------------\n",
    ">\n",
    ">If we use the wavefunction approach (session 1.1), we can derive the value we would expect to measure for a large number of measurements of a given observable, $M$. The expectation >value can be obtained as\n",
    ">\n",
    ">$〈M〉=〈\\psi|M|\\psi〉=\\sum_jm_j|c_j|^2$,\n",
    ">\n",
    ">for state $|M⟩=\\sum_jc_j|\\psi_j〉$,\n",
    ">\n",
    ">where $m_j$ is each measurement result of $M$, and $|c_j|^2$ = $P(m_j)$ is the probability of getting result $m_j$. Obtaining $m_j$ leaves the system in the state $|\\psi_j〉$. This >unavoidable disturbance of the system caused by the measurement process is often described as a \"collapse,\" a \"projection\" or a \"reduction\" of the wavefunction.\n",
    ">\n",
    "In our qubit system, recall that with two qubits (eq. (1.1.7) ), a state is described by a superposition of four basis states, i.e.\n",
    "\n",
    "$|\\psi⟩=c_{00}|00⟩+c_{01}|01⟩+c_{10}|10⟩+c_{11}|11⟩$\n",
    "\n",
    "with coefficients, $c_{ij}$. Now, what happens if we do a measurement on the system – say, if we measure the first qubit and find it to be 0? There are two possible states with the first qubit being 0. The probability of getting a 0 in the first qubit is\n",
    "\n",
    "$P=|c_{00}|^2 + |c_{01}|^2$.\n",
    "\n",
    "After such a measurement, there are only two possible states that can exist in the system. The state becomes\n",
    "\n",
    "$|\\psi'⟩=\\frac{c_{00}|00}{\\sqrt{P}}$. eq. (1.2.8)\n",
    "\n",
    "The denominator is there to keep the probability normalized (try the math yourself). A measurement projects a state $|\\psi⟩$ into a basis state with a definite value of the observable (or \"operator\") being measured.\n",
    "\n",
    ">_Math insert – Hermitian operator_ -----------------------------------------------------\n",
    ">\n",
    ">Recall that a gate is a unitary matrix, $U$, such that $U^\\dagger U$=I or U^\\dagger=U^{−1}. A measurement is not a unitary matrix. An observable corresponds to a Hermitian matrix, >$M$, such that $M^\\dagger=M$. (Technically, the basis states that have a definite value of the observable $M$ are the \"eigenstates\" of $M$, and the observed values of the operator >are the \"eigenvalues.\") Operating with the matrix $M$ on an eigenstate yields a number $m$ times the eigenstate: \n",
    ">$M|\\psi⟩=m|\\psi⟩$.\n",
    ">\n",
    ">This number, $m$, is the value of the observable $M$ that one would measure if the\n",
    ">system were in state $|\\psi〉$.\n",
    ">The operator corresponding to an observable is required to be Hermitian, because measurement results or observables need to be real numbers. Here's the proof that the measurement >operator must be Hermitian:\n",
    ">$〈M〉=〈\\psi|M|\\psi〉$\n",
    ">If 〈$M$〉 is real, then $〈M〉^\\dagger=〈M〉$. Therefore,\n",
    ">$〈M〉^\\dagger=〈\\psi|M^\\dagger|\\psi〉=〈\\psi|M|\\psi〉$.\n",
    ">This must hold for any state |$\\psi$〉. Thus, $M^\\dagger=M$.\n",
    "\n",
    "### Q# exercise: Measurement using M operation\n<a id='#qmeasurement'></a>",
    "\n",
    "1. Go to Quantum Katas: https://github.com/Microsoft/QuantumKatas introduced earlier in the CNOT exercise.\n",
    "2. In Visual Studio (Code) open folder \"Measurements\" and then Tasks.qs. Or use the Measurements exercise in Quantum Katas Jupyter Notebook.\n",
    "3. Look at Task 1.1. It only needs an operation M(q) to measure the state of the qubit q.\n",
    "\n",
    "![Figure Task 1.1](media/measurement_exercise.png)\n",
    "\n",
    "4. Now use M(q) to finish as many tasks as you can. These tasks need other gates you learned in this session to put the qubits into the states you can measure. Tasks 1.1-1.4 all follow the same process. Task 1.4 is also an interesting exercise as one can use the Bloch Sphere to visualize where the arbitrary state is relative to the |0⟩ state. Then use the rotation gate to move it back to the |0⟩ basis. The later tasks require additional concepts that we have not covered. You can skip them or read further on your own.\n",
    "\n",
    "### Interference\n<a id='#interference'></a>",
    "\n",
    "In the end of session 1.1, we introduced a generalized probability theory. The key is that probability is equal to the _square of magnitude of amplitude_, so the square of amplitude must be a positive number between 0 and 1. Here, we're going to look at the idea of interference between different possibilities, which is something that is typical of quantum mechanics, but not of classical probability theory. Interference occurs because we use amplitudes, rather than probabilities, and amplitudes can be negative or complex. Let's use a metaphorical example to illustrate this abstract idea.\n",
    "\n",
    "Say Bob is someone who may like sports and/or computer games. He has a 70% chance of liking\n",
    "sports ($S$) and a 30% chance of not liking sports ($\\overline{S}$). If he likes sports, there is an 80% chance that he likes\n",
    "computer games ($C$) and a 20% chance that he does not like computer games ($\\overline{C}$). If he does not like sports,\n",
    "there is a 10% chance he likes computer games, and a 90% chance that he doesn't. This situation is\n",
    "depicted as a tree on the left of Figure 1.2.9.\n",
    "\n",
    "What is the chance that Bob likes computer games? We can compute this by aid of the probability tree. There are two paths we can go down the tree to end up at $C:S \\to C$ and $\\overline{S} \\to C$. We can multiply the branching probabilities down each path, and then add the paths together. In this case, the probability of $C$ is given by\n",
    "\n",
    "$P(C) = 0.7 \\times 0.8 + 0.3 \\times 0.1 = 0. 59$, or 59%.\n",
    "\n",
    "But what if Bob were a quantum system? In that case, we would work with amplitudes. The tree\n",
    "on the right of Figure 1.2.9 shows one possible set of amplitudes, which give the same branching possibilities.\n",
    "Instead of calculating the probability of Bob liking computer games, we'll first calculate the amplitude. If\n",
    "we switch the word \"probability\" to \"amplitude\" in the above calculation, then everything is the same.\n",
    "Because in a quantum system, the amplitude could be a positive, negative or a complex number, let's\n",
    "assign a negative amplitude to one of the branches in Figure 1.2.9 to prove our point next. We find all the\n",
    "paths to get to $C$, and multiply the amplitudes along the path, and then sum the amplitudes of the paths:\n",
    "\n",
    "$a_c = \\sqrt{0.7} \\times \\sqrt{0.8} - \\sqrt{0.3} \\times \\sqrt{0.1}$.\n",
    "\n",
    "To get the probability, we take the modulus squared of the amplitude:\n",
    "\n",
    "$P(C) = |a_c|^2 \\approx$ 0.548, or 54.8%.\n",
    "\n",
    "The second path actually subtracts from the first path, causing the overall probability to decrease. Very\n",
    "strangely, the fact that there's a second way for Bob to like computer games _decreases_ the probability\n",
    "that he likes them! This is because the amplitude of the second path has the opposite sign from the\n",
    "amplitude for the first path. We call this \"destructive interference.\" If the amplitudes had the same sign,\n",
    "the second path would reinforce the first, and we would get \"constructive interference.\" Interference is\n",
    "fundamentally caused by the fact that amplitudes can be negative, or even complex, allowing them to\n",
    "cancel one another out. Interference is at the heart of much of the \"strangeness\" of quantum mechanics.\n",
    "Conceptually, however, it's rather simple, as we can see from the trees in Figure 1.2.9.\n",
    "\n",
    "![Figure Measurement](media/probabilitytrees.png)\n",
    "\n",
    "Figure 1.2.9. Probability trees in classical probability theory according to 1-norm (left) and in quantum\n",
    "mechanics according to 2-norm (right). We begin at the top of the tree, and ask, \"Does Bob like sports ($S$)\n",
    "or not like sports ($\\overline{S}$)?\" Then we get to the next bifurcation, and ask, \"Does Bob like computer games ($C$).\n",
    "or not like computer games ($\\overline{C}$).?\" On the left, we show the probabilities for each option. On the right, we\n",
    "show the amplitudes.\n",
    "\n",
    "![Figure Measurement](media/constructiveinterference.png)\n",
    "\n",
    "In quantum mechanics, why do we multiply the amplitudes, rather than the probabilities? Let's\n",
    "check with an arbitrary qubit state, $|psi⟩=c_0|0⟩+c_1|1⟩$. It has amplitude $c_0$ of being in |0⟩ and $c_1$ of being\n",
    "in |1⟩. If we then want to measure the presence of |+⟩ and |−⟩ in $|\\psi⟩$, what probably will be measured?\n",
    "Knowing $c_j=〈\\phi_j|\\psi〉$ from _Physics insert – Superposition_ in session 1.1, we would do an overlap integral\n",
    "$〈+|\\psi〉$ and $〈−|\\psi〉$ to get the corresponding amplitudes and square them to get the probabilities.\n",
    "\n",
    "$c_{\\pm}=〈\\pm|\\psi〉$\n",
    "\n",
    "$c_0〈\\pm|0〉 + c_1〈\\pm|1〉$\n",
    "\n",
    "$P(|\\pm〉) = |c_{\\pm}|^2$.\n",
    "\n",
    "($\\pm$ means + or −) The square happens after the amplitudes add up. This turns out to be equivalent to\n",
    "multiplying down a 2-norm probability tree in Figure 1.2.10, consistent with our metaphorical example for\n",
    "Bob above. Quantum states are intrinsically described with amplitudes.\n",
    "\n",
    "![Figure Multiplying Amplitudes](media/multiplyingamplitudes.png)\n",
    "\n",
    "Figure 1.2.10 Multiplying amplitudes down the 2-norm probability tress is equivalent to calculating the overlap integrals.\n",
    "\n",
    "The 2-norm in quantum mechanics can reduce to 1-norm in classical probability theory when constructive interference (paths with amplitudes of the same complex phase) dominates and destructive interference (paths with amplitudes of different complex phases) eliminate each other. This is explained very nicely in Richard Feynman's lecture on quantum electrodynamics. We are more likely to get a particular measurement if there are many paths to it that constructively interfere.\n",
    "\n",
    "Interference can also be seen in a gate operation (unitary matrix). As Scott Aaronson showed in his lecture (https://www.scottaaronson.com/democritus/lec9.html ), a randomizing matrix\n",
    "\n",
    "$\\begin{bmatrix} \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\end{bmatrix}$.\n",
    "\n",
    "can give equal probability of getting |0⟩ and |1⟩. But if the starting point is |0⟩, applying the matrix twice would give positive amplitudes to both |1⟩ states in either path, but a negative amplitude to one of the |0⟩ states. Thus, states |1⟩ constructively interfere, contributing to the outcome, while the states |0⟩ destructively interfere and cancel each other out (Figure 1.2.11).\n",
    "\n",
    "![Figure Applying Randomizing Matrix](media/applyingrandomizingmatrix.png)\n",
    "\n",
    "Figure 1.2.11 The outcome of applying randomizing matrix to the states twice depends on the interference between the paths.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython2",
  "version": 2,
  "kernelspec": {
   "name": "python38332bit225b1603132a4a1f9abff16033481403",
   "display_name": "Python 3.8.3 32-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}