ipynb/3.3-A_Pauli-Worded_Problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d141e234",
   "metadata": {},
   "source": [
    "##### A Tale of Timbits\n",
    "\n",
    "# A Pauli-Worded Problem (300 points)\n",
    "\n",
    "### Backstory\n",
    "\n",
    "Now Zenda and Reece know where Trine is in hyperjail, and how to evade the quantum guard who patrols the hypercube. The only question is how to get there! Doc Trine's journal explains that the portal to hyperjail is held open by exotic matter, and the quantum sensor not only helps avoid the guard, but can be used to detect this matter! But the galaxy is a big place. How do Zenda and Reece find the entrance to hyperjail?\n",
    "\n",
    "Thankfully, they stumble onto a section of Trine's journal entitled 'How to build a robot swarm'. This not only directs them to an old storage cupboard with hundreds of jetpack-equipped robots, but instructions for coordinating them using a special entangled state. Zenda and Reece need to search the office and see if this state can be found! There are several mysterious boxes which, at the push of a button, output a quantum state $\\rho$. Zenda and Reece would like to figure out if any of these states will do. Unfortunately, noise makes it harder to tell what the states are!\n",
    "\n",
    "### Blurry shadows\n",
    "\n",
    "Whenever Zenda and Reece push the button on a box and output a state in order to test it, it goes into a noisy circuit, where each qubit is subject to [depolarizing noise](https://docs.pennylane.ai/en/stable/code/api/pennylane.DepolarizingChannel.html), $\\Delta_{\\lambda}$. If $\\rho$ is a single-qubit density matrix, $\\Delta_{\\lambda}$ is defined by\n",
    "\n",
    "$$\\Delta_{\\lambda} [\\rho] = (1-\\lambda) \\rho + \\frac{\\lambda}{2} I$$\n",
    "\n",
    "and with probability $\\lambda$, the state is deleted and replaced with something random. Zenda and Reece suspect that noisy is making the states coming out of the box very hard to distinguish from random, and would like some way to test just how badly blurred they are.\n",
    "\n",
    "To explore this, we first note that any density matrix on $n$ qubits can be written as a linear combination of a special set of \"Pauli\" density matrices. These have the form\n",
    "\n",
    "$$\\rho_P = \\frac{1}{2^n} (I + P)$$\n",
    "\n",
    "where $P \\in \\{I,X,Y,Z\\}^{\\otimes n}$ is a tensor product of $n$ single-qubit Pauli operators, called a [Pauli word](https://docs.pennylane.ai/en/stable/code/qml_pauli.html). We'll let $\\rho_P(\\lambda) = \\Delta^{\\otimes n}_{\\lambda} [\\rho_P]$ label the result of applying a layer of depolarizing noise to the Pauli density $\\rho_P$.\n",
    "\n",
    "If adding noise makes a Pauli density matrix look random, a combination of Pauli densities — in other words, any matrix! — will look random. Here, \"looks random\" means \"*the expectation of any measurement is similar to the maximally mixed density matrix $\\rho_0 = I/2^n$*\". Remarkably, we can capture all expectations at once using something called trace distance between density matrices. This is defined as\n",
    "\n",
    "$$T(\\rho, \\sigma) = \\frac{1}{2} \\mathrm{Tr}|\\rho - \\sigma|$$\n",
    "\n",
    "where $|A| = \\sqrt{A^{\\dagger} A}$ for a generic matrix $A$ (to calculate $|\\rho - \\sigma|$ you will be provided with the function `abs_dist`). For any (projective) measurement $M$, the trace distance between two density matrices $\\rho$ and $\\sigma$ bounds the difference in expectations:\n",
    "\n",
    "$$\\langle M \\rangle_{\\rho} - \\langle M \\rangle_{\\sigma} = \\mathrm{Tr} [M(\\rho - \\sigma)] \\leq T(\\rho, \\sigma)$$\n",
    "\n",
    "If the trace distance is small, the two states are hard to tell apart with *any* measurement.\n",
    "\n",
    "Zenda and Reece suspect that the noise in their circuitry is blurring the states and making them hard to distinguish. Your goal is to write a function which verifies the bound\n",
    "\n",
    "$$T \\left( \\rho_P(\\lambda), \\rho_0 \\right) \\leq (1-\\lambda)^{|P|}$$\n",
    "\n",
    "by computing the difference between the right-hand side and left-hand side, where $|P|$ is the number of **non-identity** operators in the Pauli word $P$. You should find this is always positive! Since a Pauli density matrix gets exponentially blurry, and all states can be built from these Pauli densities, most states will be exponentially hard to distinguish.\n",
    "\n",
    "## Challenge code\n",
    "\n",
    "In the code below, you are given various functions:\n",
    "\n",
    "- `word_dist`: which counts the number of non-identity operators in a Pauli word.\n",
    "- `abs_dist`: which computes the distance $|\\rho - \\sigma|$ between density matrices (rho and sigma).\n",
    "- `noisy_Pauli_density`: a helper subcircuit which produces the density matrix $\\rho_P$ associated with a Pauli word $P$ (`word`) and applies depolarizing noise to each qubit with parameter `lmbda`. It is merely a collection of gates, and should not return anything. You must complete this function.\n",
    "- `maxmix_trace_dist`: a helper function which calculates the trace distance $T \\left( \\rho_P(\\lambda), \\rho_0 \\right)$, from the noisy $\\rho_Q$ (specified by `word` and `lmbda`) to the maximally mixed density $\\rho_0$. **You must complete this function**.\n",
    "- `bound_verifier`: a function which computes the difference $(1 - \\lambda)^{|P|} - T \\left( \\rho_P(\\lambda), \\rho_0 \\right)$, with both terms specified by lmbda and P. **You must complete this function**.\n",
    "\n",
    "### Inputs\n",
    "\n",
    "The functions `noisy_Pauli_density`, `maxmix_trace_dist` and `bound_verifier` take as input a Pauli word (`word` (`str`)) represented as a string of characters `I`, `X`, `Y` and `Z`, and a noise parameter `lmbda` (`float`) giving probability of erasing the state of a qubit.\n",
    "\n",
    "Note that, for `noisy_Pauli_density`, you are working with the `default.mixed` device and can create a density matrix using [`qml.QubitDensityMatrix`](https://docs.pennylane.ai/en/stable/code/api/pennylane.QubitDensityMatrix.html).\n",
    "\n",
    "### Output\n",
    "\n",
    "Your function `bound_verifier` must correctly compute the difference between the upper bound $(1 - \\lambda)^{|P|}$ and the trace distance $T \\left( \\rho_P(\\lambda), \\rho_0 \\right)$ on test cases.\n",
    "\n",
    "If your solution matches the correct one within the given tolerance specified in `check` (in this case it's a `1e-4` relative error tolerance), the output will be `\"Correct!\"` Otherwise, you will receive a `\"Wrong answer\"` prompt.\n",
    "\n",
    "### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e0b2151f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "import pennylane as qml\n",
    "import pennylane.numpy as np\n",
    "import scipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "428fccc3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def abs_dist(rho, sigma):\n",
    "    \"\"\"A function to compute the absolute value |rho - sigma|.\"\"\"\n",
    "    polar = scipy.linalg.polar(rho - sigma)\n",
    "    return polar[1]\n",
    "\n",
    "def word_dist(word):\n",
    "    \"\"\"A function which counts the non-identity operators in a Pauli word\"\"\"\n",
    "    return sum(word[i] != \"I\" for i in range(len(word)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6c9099c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Produce the Pauli density for a given Pauli word and apply noise\n",
    "\n",
    "def noisy_Pauli_density(word, lmbda):\n",
    "    \"\"\"\n",
    "       A subcircuit which prepares a density matrix (I + P)/2**n for a given Pauli\n",
    "       word P, and applies depolarizing noise to each qubit. Nothing is returned.\n",
    "\n",
    "    Args:\n",
    "            word (str): A Pauli word represented as a string with characters I,  X, Y and Z.\n",
    "            lmbda (float): The probability of replacing a qubit with something random.\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "    \n",
    "    # params\n",
    "    n = len(word)\n",
    "    wires = range(n)\n",
    "    wire_map = {i:i for i in wires}\n",
    "    \n",
    "    # create Pauli matrix & \"Pauli density matrix\"\n",
    "    pword = qml.pauli.string_to_pauli_word(word, wire_map=wire_map)\n",
    "    pmat = qml.pauli.pauli_word_to_matrix(pword, wire_map=wire_map)\n",
    "    dmat = (np.eye(2**n) + pmat) / 2**n\n",
    "    qml.QubitDensityMatrix(dmat, wires=wires)\n",
    "    \n",
    "    # add depolarising noise\n",
    "    for i in wires:\n",
    "        qml.DepolarizingChannel(lmbda, wires=i)\n",
    "\n",
    "noisy_Pauli_density(\"XXI\", 0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "11b22622",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.002222222222222316+0j)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Compute the trace distance from a noisy Pauli density to the maximally mixed density\n",
    "\n",
    "def maxmix_trace_dist(word, lmbda):\n",
    "    \"\"\"\n",
    "       A function compute the trace distance between a noisy density matrix, specified\n",
    "       by a Pauli word, and the maximally mixed matrix.\n",
    "\n",
    "    Args:\n",
    "            word (str): A Pauli word represented as a string with characters I, X, Y and Z.\n",
    "            lmbda (float): The probability of replacing a qubit with something random.\n",
    "\n",
    "    Returns:\n",
    "            float: The trace distance between two matrices encoding Pauli words.\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "\n",
    "    n = len(word)\n",
    "    \n",
    "    @qml.qnode(qml.device(\"default.mixed\", wires=n))\n",
    "    def circuit(word, lmbda):\n",
    "        noisy_Pauli_density(word, lmbda)\n",
    "        return qml.density_matrix(wires=range(n))\n",
    "    \n",
    "    pauli = circuit(word, lmbda)\n",
    "    mixed = 1/2**n * np.eye(2**n)\n",
    "    trdist = 1/2 * np.trace(abs_dist(pauli, mixed))\n",
    "    return trdist\n",
    "\n",
    "maxmix_trace_dist(\"XXI\", 0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "fc6990de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.0877777777777777+0j)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bound_verifier(word, lmbda):\n",
    "    \"\"\"\n",
    "       A simple check function which verifies the trace distance from a noisy Pauli density\n",
    "       to the maximally mixed matrix is bounded by (1 - lambda)^|P|.\n",
    "\n",
    "    Args:\n",
    "            word (str): A Pauli word represented as a string with characters I, X, Y and Z.\n",
    "            lmbda (float): The probability of replacing a qubit with something random.\n",
    "\n",
    "    Returns:\n",
    "            float: The difference between (1 - lambda)^|P| and T(rho_P(lambda), rho_0).\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "\n",
    "    trdist = maxmix_trace_dist(word, lmbda)\n",
    "    bound = (1 - lmbda)**word_dist(word)\n",
    "    return bound - trdist\n",
    "\n",
    "bound_verifier(\"XXI\", 0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "572f2090",
   "metadata": {},
   "outputs": [],
   "source": [
    "# These functions are responsible for testing the solution.\n",
    "def run(test_case_input: str) -> str:\n",
    "\n",
    "    word, lmbda = json.loads(test_case_input)\n",
    "    output = np.real(bound_verifier(word, lmbda))\n",
    "\n",
    "    return str(output)\n",
    "\n",
    "\n",
    "def check(solution_output: str, expected_output: str) -> None:\n",
    "\n",
    "    solution_output = json.loads(solution_output)\n",
    "    expected_output = json.loads(expected_output)\n",
    "    assert np.allclose(\n",
    "        solution_output, expected_output, rtol=1e-4\n",
    "    ), \"Your trace distance isn't quite right!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8d6d7343",
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = [['[\"XXI\", 0.7]', '0.0877777777777777'], ['[\"XXIZ\", 0.1]', '0.4035185185185055'], ['[\"YIZ\", 0.3]', '0.30999999999999284'], ['[\"ZZZZZZZXXX\", 0.1]', '0.22914458207245006']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0437c586",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running test case 0 with input '[\"XXI\", 0.7]'...\n",
      "Correct!\n",
      "Running test case 1 with input '[\"XXIZ\", 0.1]'...\n",
      "Correct!\n",
      "Running test case 2 with input '[\"YIZ\", 0.3]'...\n",
      "Correct!\n",
      "Running test case 3 with input '[\"ZZZZZZZXXX\", 0.1]'...\n",
      "Correct!\n"
     ]
    }
   ],
   "source": [
    "for i, (input_, expected_output) in enumerate(test_cases):\n",
    "    print(f\"Running test case {i} with input '{input_}'...\")\n",
    "\n",
    "    try:\n",
    "        output = run(input_)\n",
    "\n",
    "    except Exception as exc:\n",
    "        print(f\"Runtime Error. {exc}\")\n",
    "\n",
    "    else:\n",
    "        if message := check(output, expected_output):\n",
    "            print(f\"Wrong Answer. Have: '{output}'. Want: '{expected_output}'.\")\n",
    "\n",
    "        else:\n",
    "            print(\"Correct!\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pennylane",
   "language": "python",
   "name": "pennylane"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}