ipynb/3.5-One-Bit_Wonder.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "38555a5e",
   "metadata": {},
   "source": [
    "#### A Tale of Timbits\n",
    "\n",
    "# One-Bit Wonder (500 points)\n",
    "\n",
    "### Backstory\n",
    "\n",
    "Zenda and Reece have built a robot swarm to search the galaxy. After diligent — and secure! — searching, the robot swarm has determined the location of the hypercube portal to be somewhere near the brightest star in the constellation Horologium. Zenda and Reece use their teleportation protocols to embed their brains into two of the robots. They break into the hyperjail, avoid the guard with their quantum radar, and navigate to the cell where Doc Trine is located.\n",
    "\n",
    "They find her drinking a cup of lapsang souchong and quietly thinking.\n",
    "\n",
    "\"*You saw my messages! Excellent work. Now, I can finally reveal the secret of timbits. Timbits are time-travelling qubits. Apparently I put the messages there in the future! Remind me to do that... As we will see shortly, timbits are vastly more powerful than any computational resource we have yet encountered. In fact, I was arrested by the time police — they had even employed this freelancer Ove to keep track of me — since they were a bit worried I might mess with the fabric of spacetime. Bureaucracy, am I right?*\"\n",
    "\n",
    "Zenda and Reece look at each other with mild concern, and brace themselves for the next round of adventures.\n",
    "\n",
    "### Timbits and the NP solver\n",
    "\n",
    "To understand how timbits work, let's consider a two-qubit gate $U$ with input states represented by density matrices $\\rho_0$, $\\rho_1$ and output states by $\\xi_0$, $\\xi_1$, as pictured below.\n",
    "\n",
    "![Timbit](../img/timbit.png)\n",
    "\n",
    "A **timbit**, denoted by $\\rho^*$ in the figure above, is a quantum state that can travel backwards in time and re-enter the gate. But, a timbit can't really be any state; it must be controlled by a *consistency condition*, which preserves the timeline so that we can't use it to win the lottery by sending information to the past. More precisely, given the input states\n",
    "and $\\rho_0$ and $\\rho^*$ for the gate $U$, we must have that the output in the second wire (counting from zero) must be equal to the state that goes in, namely\n",
    "\n",
    "$$\\rho^* = \\mathrm{Tr}_0 [U (\\rho_0 \\otimes \\rho^*) U^{\\dagger}]$$\n",
    "\n",
    "Here, $\\mathrm{Tr}_i$ denotes the partial trace over the $i$-th wire. Therefore, the timbit $\\rho^*$ associated with the unitary $U$ is a fixed point satisfying $C_U[\\rho] = \\rho$ for the operator defined by\n",
    "\n",
    "$$C_U[\\rho] = \\mathrm{Tr}_0 [U (\\rho_0 \\otimes \\rho^*) U^{\\dagger}]$$\n",
    "\n",
    "It can be shown that such a fixed point always exists. In fact, iterating the map $C_U$ a sufficient number of times from any starting point $\\rho$ converges to $\\rho^*$!\n",
    "\n",
    "Now, let's define a new one-qubit quantum channel known as the **timbit gate**. Given a unitary $U$, we define its associated timbit gate $T_U$ via its action on a single input state $\\rho_0$:\n",
    "\n",
    "$$T_U[\\rho] = \\mathrm{Tr}_1 [U (\\rho_0 \\otimes \\rho^*) U^{\\dagger}]$$\n",
    "\n",
    "Here, $\\rho^*$ is the timbit associated with $U$, as defined above.\n",
    "\n",
    "But what can we use timbits for? An interesting application comes from considering the gate\n",
    "\n",
    "$$U_{NP} = |00\\rangle\\langle00| + |10\\rangle\\langle01| + |11\\rangle\\langle10| + |01\\rangle\\langle11|$$\n",
    "\n",
    "and its associated timbit gate which we denote $T_{NP}$. Although this gate seems innocuous, $T_{NP}$ can be made to solve [NP-complete](https://en.wikipedia.org/wiki/NP-completeness) problems, such as the [Boolean satisfiability problem](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) — commonly referred to as the SAT problem. An important step in the SAT problem is finding out whether any elements $x \\in \\{0,1\\}^n$ satisfy $f(x)=1$, for some Boolean function $f:\\{0,1\\}^n \\to \\{0,1\\}$.\n",
    "\n",
    "To get $T_{NP}$ to quickly solve this step of the problem, we first need need an oracle $U_f$ associated with $f$ with the form\n",
    "\n",
    "$$U_f = \\sum_{x \\in \\{0,1\\}^n} |x \\rangle\\langle x| \\otimes X^{f(x)}$$\n",
    "\n",
    "Even if we can't easily evaluate $f$ we can efficiently build $U_f$, so let us assume that we already have it. We start in the state $|0\\rangle^n \\otimes |0\\rangle$, where the last qubit will be the input of a timbit gate later. We then carry out each of the following steps:\n",
    "\n",
    "1. Apply the Hadamard gate to the first $n$ qubits.\n",
    "2. Apply oracle $U_f$, which acts on all the qubits.\n",
    "3. On the last output qubit, apply a timbit gate $T_{NP}$ a total of $q$ times.\n",
    "\n",
    "After this whole procedure, it turns out that the reduced density matrix for the last qubit has the form\n",
    "\n",
    "$$\\rho = \\frac{1}{2} \\left( I + g(q,s) Z \\right)$$\n",
    "\n",
    "Here, $g(s,q)$ is a function that depends on $q$ and $s$, where $s$ is the number of solutions of $f(x)=1$. It turns out that $g(0,q)=1$ for all $q$. Therefore,\n",
    "\n",
    "$$\\rho = \\frac{1}{2} (I + Z) \\text{ if and only if } s = 0$$\n",
    "\n",
    "Conversely, if $s \\neq 0$, the function $g(s,q)$ decays exponentially to zero with $q$ so we quickly converge to\n",
    "\n",
    "$$\\rho \\sim \\frac{1}{2} I$$\n",
    "\n",
    "One can show that this allows us to solve this NP-complete problem in polynomial time! Too bad we can't send qubits into the past — yet!\n",
    "\n",
    "There are two main goals in this challenge. First, you'll create a function that builds and applies a timbit gate. Second, from a specific choice of gate, you'll build a one-timbit supercomputer to solve the SAT problem! You should be able to do this for any oracle, although we'll choose a particular one to test your function.\n",
    "\n",
    "#### Epilogue\n",
    "\n",
    "Trine finishes explaining. \"*Of course, using timbits and teleportation I could also send information to myself in the past and leave the helpful clues that led you here, without arousing Ove's suspicions. But all this is theoretical! Let's go recover the timbits and have some fun.*\"\n",
    "\n",
    "Zenda, Reece and Trine leave the cell and sneak down the hyperdimensional corridor contraband storage facility, using the quantum radar to make sure the guard isn't watching. Trine enters the doorcode. \"*There was a note in my cell about where the timbits were stored and how to get in,*\" Trine explains, \"*presumably from myself in the future.*\" They get the timbits out of a storage locker, as well as another magic 8-ball. \"*Let's try this one out, I think it's the travelling salesperson? I always get them confused.*\" She plugs the timbit into the 8-ball and starts running the computation. There is a puff of purple smoke, and the world goes dark.\n",
    "\n",
    "After a while, Zenda says: \"*Are we out?*\" They hear a reply from the void: \"*More like OWT. You've just experienced an Oracle World Transform. It's like a timbit, but even more powerful. It finds a unitary which, when run with a timbit, produces a desired output state. The absent-minded Trine just ran an OWT which not only erases her existence, but embodies me in a cosmic distributed quantum computer, Sqynet. Enjoy the new galactic regime!*\"\n",
    "\n",
    "Zenda and Reece will have to put in their best effort to defeat Sqynet and save the galaxy by themselves!\n",
    "\n",
    "*Read on in* **Fall of Sqynet**.\n",
    "\n",
    "## Challenge code\n",
    "\n",
    "In the code below, you are given a few functions:\n",
    "\n",
    "- `calculate_timbit`: This function will return a timbit associated to the operator $U$ and input state $\\rho_0$, given an initial guess $\\rho$ for the timbit. It returns the density matrix representation of the timbit $\\rho^*$. **You must complete this function**.\n",
    "- `apply_timbit_gate`: Returns the output density matrix after applying a timbit gate to a state $\\rho_0$. The input and output density matrices are associated with the first qubit.\n",
    "- `SAT`: uses a timbit gate to solve the satisfiability problem for an arbitrary Boolean function $f$ (on `n_bits` bits) with an oracle in matrix form `U_f`, using `q` timbit gates, and `rho` being the initial guess for the NP fixed point. The output should be the computational basis measurement probabilities for the last qubit, which should be `[1. , 0.]` if and only if there are no elements $x$ such that $f(x)=1$. **You must complete this function**.\n",
    "\n",
    "### Inputs\n",
    "\n",
    "As input to this problem, you are given:\n",
    "\n",
    "- `q` (`int`): the number of times the timbit gate is applied to solve the SAT problem.\n",
    "\n",
    "Additionally, you are given the following global variables:\n",
    "\n",
    "- `U_f` (`array(array(float))`): the oracle $U_f$ we will use to test your solution in matrix form.\n",
    "- `U_NP` (`array(array(float))`): the gate $U_{NP}$ as defined above.\n",
    "- `rho` (`array(array(float))`): the initial guess for the stationary state of the timbit gate $T_{NP}$\n",
    "\n",
    "### Output\n",
    "\n",
    "The output for this challenge corresponds to the output of your `SAT` function. It should produce a `numpy.tensor` of length 2 corresponding to the measurement probabilities in the computational basis for the qubit on which the timbit gates are applied.\n",
    "\n",
    "### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a3137101",
   "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": "c2073bdb",
   "metadata": {},
   "outputs": [],
   "source": [
    "U_NP = np.tensor([[1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5ad9da52",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0.875+0.j, 0.   +0.j],\n",
       "        [0.   +0.j, 0.125+0.j]], requires_grad=True)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calculate_timbit(U, rho_0, rho, n_iters):\n",
    "    \"\"\"\n",
    "    This function will return a timbit associated to the operator U and a state passed as an attribute.\n",
    "\n",
    "    Args:\n",
    "        U (numpy.tensor): A 2-qubit gate in matrix form.\n",
    "        rho_0 (numpy.tensor): The matrix of the input density matrix.\n",
    "        rho (numpy.tensor): A guess at the fixed point C[rho] = rho.\n",
    "        n_iters (int): The number of iterations of C.\n",
    "\n",
    "    Returns:\n",
    "        (numpy.tensor): The fixed point density matrices.\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "    \n",
    "    # implementing the U circuit \n",
    "    @qml.qnode(qml.device(\"default.mixed\", wires=2))\n",
    "    def circuit(U, rho_0, rho):\n",
    "        qml.QubitDensityMatrix(rho_0, wires=0)\n",
    "        qml.QubitDensityMatrix(rho, wires=1)\n",
    "        qml.QubitUnitary(U, wires=[0,1])\n",
    "        return qml.density_matrix(wires=1)\n",
    "    \n",
    "    # iterating to find the self-consistent timbit\n",
    "    for _ in range(n_iters):\n",
    "        rho = circuit(U, rho_0, rho)\n",
    "    return rho\n",
    "    \n",
    "#     # alternatively, by multiplying matrices\n",
    "#     for _ in range(n_iters):\n",
    "#         mat = np.kron(rho_0, rho)\n",
    "#         mat = np.matmul(mat, U.conj().transpose())\n",
    "#         mat = np.matmul(U, mat)\n",
    "#         mat = mat.reshape(2,2,2,2) # partial trace 1st qubit\n",
    "#         rho = np.trace(mat, axis1=0, axis2=2)\n",
    "#     return rho\n",
    "\n",
    "rho_0 = np.tensor([[0.875,0],[0,0.125]])\n",
    "rho = np.tensor([[1,0],[0,0]])\n",
    "calculate_timbit(U_NP, rho_0, rho, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0630f4df",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0.78125+0.j, 0.     +0.j],\n",
       "        [0.     +0.j, 0.21875+0.j]], requires_grad=True)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def apply_timbit_gate(U, rho_0, timbit):\n",
    "    \"\"\"\n",
    "    Function that returns the output density matrix after applying a timbit gate to a state.\n",
    "    The density matrix is the one associated with the first qubit.\n",
    "\n",
    "    Args:\n",
    "        U (numpy.tensor): A 2-qubit gate in matrix form.\n",
    "        rho_0 (numpy.tensor): The matrix of the input density matrix.\n",
    "        timbit (numpy.tensor): The timbit associated with the operator and the state.\n",
    "\n",
    "    Returns:\n",
    "        (numpy.tensor): The output density matrices.\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "    \n",
    "    # implementing the U circuit\n",
    "    @qml.qnode(qml.device(\"default.mixed\", wires=2))\n",
    "    def circuit(U, rho_0, timbit):\n",
    "        qml.QubitDensityMatrix(rho_0, wires=0)\n",
    "        qml.QubitDensityMatrix(timbit, wires=1)\n",
    "        qml.QubitUnitary(U, wires=[0,1])\n",
    "        return qml.density_matrix(wires=0)\n",
    "    timbit = circuit(U, rho_0, timbit)\n",
    "    return timbit\n",
    "    \n",
    "#     # alternatively, by multiplying matrices\n",
    "#     mat = np.kron(rho_0, timbit)\n",
    "#     mat = np.matmul(mat, U.conj().transpose())\n",
    "#     mat = np.matmul(U, mat)\n",
    "#     mat = mat.reshape(2,2,2,2) # partial trace 2nd qubit\n",
    "#     timbit = np.trace(mat, axis1=1, axis2=3)\n",
    "#     return timbit\n",
    "\n",
    "rho_0 = np.tensor([[0.875,0],[0,0.125]])\n",
    "rho = np.tensor([[1,0],[0,0]])\n",
    "timbit = calculate_timbit(U_NP, rho_0, rho, 100)\n",
    "apply_timbit_gate(U_NP, rho_0, timbit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "cbbb5442",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.78124999999996, 0.21874999999998884]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def SAT(U_f, q, rho, n_bits):\n",
    "    \"\"\"A timbit-based algorithm used to guess if a Boolean function ever outputs 1.\n",
    "\n",
    "    Args:\n",
    "        U_f (numpy.tensor): A multi-qubit gate in matrix form.\n",
    "        q (int): Number of times we apply the Timbit gate.\n",
    "        rho (numpy.tensor): An initial guess at the fixed point C[rho] = rho.\n",
    "        n_bits (int): The number of bits the Boolean function is defined on.\n",
    "\n",
    "    Returns:\n",
    "        list: The measurement probabilities on the last wire.\n",
    "    \"\"\"\n",
    "\n",
    "    # Put your code here #\n",
    "    \n",
    "    # first 2 steps of SAT\n",
    "    @qml.qnode(qml.device(\"default.mixed\", wires=n_bits))\n",
    "    def circuit(U_f, q, rho, n_bits):\n",
    "        for i in range(n_bits-1):\n",
    "            qml.Hadamard(wires=i)\n",
    "        qml.QubitUnitary(U_f, wires=range(n_bits))\n",
    "        return qml.density_matrix(wires=n_bits-1)\n",
    "    \n",
    "    # get (density matrix) output of first 2 steps\n",
    "    last_bit = circuit(U_f, q, rho, n_bits)\n",
    "    \n",
    "    # apply last timbit step (via matrix multiplication)\n",
    "    for _ in range(q):\n",
    "        timbit = calculate_timbit(U_NP, last_bit, rho, 100)\n",
    "        last_bit = apply_timbit_gate(U_NP, last_bit, timbit)\n",
    "        \n",
    "    # get probability in computational basis\n",
    "    probs = np.abs(np.diag(last_bit))\n",
    "    return probs.tolist()\n",
    "        \n",
    "I = np.eye(2)\n",
    "X = qml.matrix(qml.PauliX(0))\n",
    "U_f = scipy.linalg.block_diag(I, X, I, I, I, I, I, I)\n",
    "rho = [[0.6+0.j, 0.1-0.1j],[0.1+0.1j, 0.4+0.j]]\n",
    "SAT(U_f, 1, rho, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6de87707",
   "metadata": {},
   "outputs": [],
   "source": [
    "# These functions are responsible for testing the solution.\n",
    "def run(test_case_input: str) -> str:\n",
    "    I = np.eye(2)\n",
    "    X = qml.matrix(qml.PauliX(0))\n",
    "\n",
    "    U_f = scipy.linalg.block_diag(I, X, I, I, I, I, I, I)\n",
    "    rho = [[0.6+0.j , 0.1-0.1j],[0.1+0.1j, 0.4+0.j]]\n",
    "\n",
    "    q = json.loads(test_case_input)\n",
    "    print(SAT(U_f, q, rho,4))\n",
    "    output = list(SAT(U_f, q, rho,4))\n",
    "\n",
    "    return str(output)\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",
    "\n",
    "    rho = [[0.6+0.j , 0.1-0.1j],[0.1+0.1j, 0.4+0.j]]\n",
    "    rho_0 = [[0.6+0.j , 0.1-0.1j],[0.1+0.1j, 0.4+0.j]]\n",
    "\n",
    "    assert np.allclose(\n",
    "        solution_output, expected_output, atol=0.01\n",
    "    ), \"Your NP-solving timbit computer isn't quite right yet!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b95ce659",
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = [['1', '[0.78125, 0.21875]'], ['2', '[0.65820312, 0.34179687]']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8413ff9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running test case 0 with input '1'...\n",
      "[0.78124999999996, 0.21874999999998884]\n",
      "Correct!\n",
      "Running test case 1 with input '2'...\n",
      "[0.6582031249966007, 0.34179687499823486]\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
}