ipynb/1.4-The_Lazy_Colleague.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "eeef0cef",
   "metadata": {},
   "source": [
    "##### Office Hijinks\n",
    "\n",
    "# The Lazy Colleague (400 points)\n",
    "\n",
    "### Backstory\n",
    "\n",
    "It is very common to work in teams, but it is just as common to find a teammate who decides not to work. However, colleagues do not usually tell the boss, so this individual goes unnoticed. Zenda is supervising four employees, and it is known that one of them never works. But who is it?\n",
    "\n",
    "### Finding the lazy employee\n",
    "\n",
    "The project Zenda's team is working on can only be completed if **at least three people** in the team are working. Let's model this situation in a circuit:\n",
    "\n",
    "![project quantum circuit](../img/project_execution.jpeg)\n",
    "\n",
    "In this diagram, the qubit $e_i$ refers to the $i$-th employee, which will take the value 1 if this employee is chosen to work on the project. The output state labelled result will take the value 0 if the project was not completed and 1 if it was. Let us imagine that employee $e_1$ is the one who does not work. Then, if we apply the operator to the state $|1\\rangle |1\\rangle |0\\rangle |1\\rangle |0\\rangle$ (that is, we select $e_1$, $e_2$, and $e_4$ for the project), the output will be $|1\\rangle |1\\rangle |0\\rangle |1\\rangle |0\\rangle$. As we can see, the last qubit is still $|0\\rangle$, i.e. the project has not been carried out. This is because there are only two employees that actually work on the project, and a minimum of three is required.\n",
    "\n",
    "Zenda wants to know who the lazy worker is, executing as few projects as possible. For this reason, they ask you to help her with your quantum skills. You are asked to discover who the lazy employee is, using a single shot and a single call to the \"Project execution\" operator.\n",
    "\n",
    "## Challenge code\n",
    "\n",
    "On one hand, you are asked to complete `circuit` (you only need to apply gates). You can only call the `project_execution` operator once, which is already incorporated in the template. On the other hand, you must complete `process_output`, which will take the output of your circuit and will return who the lazy guy is.\n",
    "\n",
    "The `project_execution` function will be generated when testing the solution; if you want to experiment with the function output in the notebook, you can temporarily replace `project_execution` with an operator of the form `qml.MultiControlledX(wires=['e1', 'e2', 'e4', 'result'])`. In this case, the absence of \"e3\" on the wires means that in this project, \"e3\" will be the lazy employee. Just remember to switch it back to project_execution before submitting, so that your function uses the correct project_execution during testing!\n",
    "\n",
    "You may find it useful to do some tests in [Quirk](https://algassert.com/quirk) before you start coding.\n",
    "\n",
    "### Output\n",
    "\n",
    "To judge this challenge, we will arbitrarily generate 5000 different projects (`project_execution`), which we will send one by one to the circuit to check that your prediction is correct (\"e1\", \"e2\", \"e3\" or \"e4\"). Therefore, in this case, there will be no public and private test cases. Good luck!\n",
    "\n",
    "### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1a97c2b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "import pennylane as qml\n",
    "import pennylane.numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b94e73df",
   "metadata": {},
   "outputs": [],
   "source": [
    "dev = qml.device(\"default.qubit\", wires=[\"e1\", \"e2\", \"e3\", \"e4\", \"result\"], shots=100)\n",
    "dev.operations.add(\"op\")\n",
    "\n",
    "wires = [\"e1\", \"e2\", \"e3\", \"e4\", \"result\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c75f7eee",
   "metadata": {},
   "outputs": [],
   "source": [
    "@qml.qnode(dev)\n",
    "def circuit(project_execution):\n",
    "    \"\"\"This is the circuit we will use to detect which is the lazy worker. Remember \n",
    "    that we will only execute one shot.\n",
    "\n",
    "    Args:\n",
    "        project_execution (qml.ops): \n",
    "            The gate in charge of marking in the last qubit if the project has been finished\n",
    "            as indicated in the statement.\n",
    "\n",
    "    Returns:\n",
    "        (numpy.tensor): Measurement output in the 5 qubits after a shot.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Put your code here #\n",
    "    \n",
    "    ## This is Grover search over the reduced 4-dimensional subspace\n",
    "    # init |0111>|0> + |1011>|0> + |1101>|0> + |1110>|0>\n",
    "    n = len(wires) - 1\n",
    "    for i in range(n): # prep i-th qubit\n",
    "        if i == 0: # non-controlled RX\n",
    "            qml.RX(np.arcsin(1/np.sqrt(n-i)) * 2, wires=wires[i])\n",
    "        else: # multi-controlled RX\n",
    "            qml.ctrl(qml.RX, control=wires[:i])(\n",
    "                np.arcsin(1/np.sqrt(n-i)) * 2, wires[i]\n",
    "            )\n",
    "        qml.PauliX(wires=wires[i]) # rotate i-th qubit to 1\n",
    "\n",
    "    # phase flip the solution\n",
    "    # e.g. -|0111>|-> + |1011>|-> + |1101>|-> + |1110>|->\n",
    "    qml.PauliX(wires=\"result\")\n",
    "    qml.Hadamard(wires=\"result\")\n",
    "    project_execution(wires=wires)\n",
    "    \n",
    "    # reverse the initialisation\n",
    "    for i in range(n)[::-1]: # prep i-th qubit\n",
    "        qml.PauliX(wires=wires[i])\n",
    "        if i == 0: # non-controlled RX\n",
    "            qml.RX(-np.arcsin(1/np.sqrt(n-i)) * 2, wires=wires[i])\n",
    "        else: # multi-controlled RX\n",
    "            qml.ctrl(qml.RX, control=wires[:i])(\n",
    "                -np.arcsin(1/np.sqrt(n-i)) * 2, wires[i]\n",
    "            )\n",
    "    \n",
    "    # phase flip all the initial state |0000>\n",
    "    for i in wires[:-1]:\n",
    "        qml.PauliX(wires=i)\n",
    "    qml.ctrl(qml.PauliZ, control=wires[:-2])(wires=wires[-2])\n",
    "    for i in wires[:-1]:\n",
    "        qml.PauliX(wires=i)\n",
    "        \n",
    "    # redo the initialisation\n",
    "    for i in range(n): # prep i-th qubit\n",
    "        if i == 0: # non-controlled RX\n",
    "            qml.RX(np.arcsin(1/np.sqrt(n-i)) * 2, wires=wires[i])\n",
    "        else: # multi-controlled RX\n",
    "            qml.ctrl(qml.RX, control=wires[:i])(\n",
    "                np.arcsin(1/np.sqrt(n-i)) * 2, wires[i]\n",
    "            )\n",
    "        qml.PauliX(wires=wires[i])\n",
    "    \n",
    "    return qml.sample(wires=dev.wires[:-1])\n",
    "\n",
    "def process_output(measurement):\n",
    "    \"\"\"This function will take the circuit measurement and process it to determine who is the lazy worker.\n",
    "\n",
    "    Args:\n",
    "        measurement (numpy.tensor): Measurement output in the 5 qubits after a shot.\n",
    "\n",
    "    Returns:\n",
    "        (str): This function must return \"e1\", \"e2\", \"e3\", or \"e4\" - the lazy worker.\n",
    "    \"\"\"\n",
    "    if np.all(measurement == [0,1,1,1]):\n",
    "        return \"e1\"\n",
    "    elif np.all(measurement == [1,0,1,1]):\n",
    "        return \"e2\"\n",
    "    elif np.all(measurement == [1,1,0,1]):\n",
    "        return \"e3\"\n",
    "    else:\n",
    "        return \"e4\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8b6a1aa2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# These functions are responsible for testing the solution.\n",
    "\n",
    "def run(test_case_input: str) -> str:\n",
    "    return None\n",
    "\n",
    "def check(solution_output: str, expected_output: str) -> None:\n",
    "    samples = 5000\n",
    "\n",
    "    solutions = []\n",
    "    output = []\n",
    "\n",
    "    for s in range(samples):\n",
    "        lazy = np.random.randint(0, 4)\n",
    "        no_lazy = list(range(4))\n",
    "        no_lazy.pop(lazy)\n",
    "\n",
    "        def project_execution(wires):\n",
    "            class op(qml.operation.Operator):\n",
    "                num_wires = 5\n",
    "\n",
    "                def compute_decomposition(self, wires):\n",
    "                    raise ValueError(\"You cant descompose this gate\")\n",
    "\n",
    "                def matrix(self):\n",
    "                    m = np.zeros([32, 32])\n",
    "                    for i in range(32):\n",
    "                        b = [int(j) for j in bin(64 + i)[-5:]]\n",
    "                        if sum(np.array(b)[no_lazy]) == 3:\n",
    "                            if b[-1] == 0:\n",
    "                                m[i, i + 1] = 1\n",
    "                            else:\n",
    "                                m[i, i - 1] = 1\n",
    "                        else:\n",
    "                            m[i, i] = 1\n",
    "                    return m\n",
    "\n",
    "            op(wires=wires)\n",
    "            return None\n",
    "\n",
    "        out = circuit(project_execution)\n",
    "        solutions.append(lazy + 1)\n",
    "        output.append(int(process_output(out)[-1]))\n",
    "\n",
    "    assert np.allclose(\n",
    "        output, solutions, rtol=1e-4\n",
    "    ), \"Your circuit does not give the correct output.\"\n",
    "\n",
    "    ops = [op.name for op in circuit.tape.operations]\n",
    "    assert ops.count(\"op\") == 1, \"You have used the oracle more than one time.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ea29e182",
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = [['No input', 'No output']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ed1bb6bc",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running test case 0 with input 'No input'...\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
}