notebooks/exercises/05_grovers_algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grover's algorithm\n",
    "\n",
    "\n",
    "In this notebook, we'll have a look at Grover's famous unstructured search algorithm. The problem is quite straightforward: we have some function $f(|x\\rangle) \\to \\{0,1\\}$ and we know that for a unique $|\\omega\\rangle$, $f(|\\omega\\rangle)=1$, in all other cases $|x\\rangle \\neq |\\omega\\rangle \\iff f(|x\\rangle)=0$. The goal is to find $|\\omega\\rangle$ given access to $f$. This is a very general and common problem: we are looking for a single item in a list, and the item is identified by the function $f$. The surprising advantage of Grover's algoritm is that it finds $|\\omega\\rangle$ with high probability in $O(\\sqrt{N})$, (where $N=2^n$, and $n$ the number of qubits). \n",
    "\n",
    "Classically, you would expect that, in a list of $N$ elements, you need, in the worst case, to check the $N$ elements to find the desired item with certainty. Even if we expand this to probabilistic search, the quantum algorithm performs better: in the classical case, if we look at $N/2$ items, we have a $50\\%$ chance of finding the item. In no classical scenario could we have $>50\\%$ chance of finding our item by checking $\\sqrt{N} \\leq N/2$ items ($N\\geq 4$), if you don't know anything about the properties of $f$. \n",
    "\n",
    "Grover's algorithm also does not hinge on the Quantum Fourier Transform, which sets it apart from Quantum Phase Estimation based algorithm, such as Shor's and the like. That's another reason why it's a very nice algorithm to study.\n",
    "\n",
    "Habitual incantations inbound:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install qiskit[visualization] --quiet\n",
    "%pip install matplotlib --quiet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay, let's see how Grover's search functions. \n",
    "\n",
    "We are given the _oracle_ for $f$, $U_\\omega$, whereas $f$ returns $1$ for the right item, in this case we have\n",
    "\n",
    "$$\\begin{cases}U_\\omega |x\\rangle = -|x\\rangle & \\mathrm{if}\\,  |x\\rangle = |\\omega\\rangle \\\\ U_\\omega |x\\rangle = |x\\rangle & \\mathrm{else} \\end{cases}$$\n",
    "\n",
    "which is qualitatively similar: $U_\\omega$, like $f$, can be used to check whether our current state is the solution.\n",
    "\n",
    "You saw in last week's exercises that the operator $R$, called the _diffuser_, defined as \n",
    "\n",
    "$$R = 2H^{\\otimes n} |0...0\\rangle\\langle 0...0| H^{\\otimes n} - \\mathbf{I}$$\n",
    "\n",
    "performs a flip of the state's amplitudes about the mean of all amplitudes. \n",
    "\n",
    "Let's take a look at a two qubit case for simplicity, and assume $|01\\rangle$ is the item we're looking for:\n",
    "\n",
    "- We apply Hadamards on all qubit and get $\\frac12 (|00\\rangle+|01\\rangle+|10\\rangle+|11\\rangle)$\n",
    "- Applying $U_{|01\\rangle}$ nets us $\\frac12 (|00\\rangle-|01\\rangle+|10\\rangle+|11\\rangle)$\n",
    "- The mean of all amplitudes is then $\\frac14(\\frac12 -\\frac12 +\\frac12 +\\frac12) = \\frac14$\n",
    "- If we apply $R$, we flip amplitudes about $\\frac14$: for $\\frac12$ we have $\\frac14 + (\\frac14-\\frac12)=0$, and $-\\frac12$ we have $ \\frac14 + (\\frac14-(-\\frac12))=1$ \n",
    "- In the end, the only remaining bitstring is $|01\\rangle$\n",
    "\n",
    "We see that in that case the solution $|01\\rangle$ has been picked out among all items.\n",
    "\n",
    "Let's implement Grover's algorithm.\n",
    "\n",
    "In this case, we work with the index of the bitstring, since every bitstring is also the binary representation of some integer. For example, $|10\\rangle = 0 \\cdot 2^0 + 1 \\cdot 2^1 = 2$ (don't forget the right-to-left ordering.) I've already written the function to get from an `int` to a bitstring, and vice-versa. \n",
    "\n",
    "We start with the two main blocks: $U_\\omega$ and $R$. Of course, you must implement them yourself. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from qiskit import QuantumCircuit\n",
    "from qiskit.circuit.library import UnitaryGate\n",
    "\n",
    "\n",
    "def from_bitstring(n_qubits:int,bitstring:str)->int:\n",
    "    if isinstance(bitstring,str):\n",
    "        ind=np.sum([2**(n_qubits-1-int(b)) for b in bitstring])\n",
    "        return ind\n",
    "    else:\n",
    "        return bitstring\n",
    "    \n",
    "\n",
    "def to_bitstring(n_qubits:int,ind:str)->int:\n",
    "    return format(ind, \"0{lp}b\".format(lp=n_qubits))\n",
    "    \n",
    "    \n",
    "# this is U_omega, the oracle\n",
    "# HINT: It's really easy to flip the phase of a bitstring if you know its index\n",
    "# which is why the argument is the index itself.\n",
    "def oracle(n_qubits:int,target_bitstring_ind:int):\n",
    "    # WRITE U_omega!\n",
    "    U_om = ...\n",
    "    return UnitaryGate(U_om,label=\"oracle\")\n",
    "\n",
    "    \n",
    "# this is R, the diffuser\n",
    "# this one doesn't take any index\n",
    "# HINT: you can use the oracle to implement the identity matrix\n",
    "# HINT 2: this is a circuit rather than a single gate because you need \n",
    "# more than a single UnitaryGate in this case\n",
    "def diffuser(n_qubits:int):\n",
    "    # WRITE R!\n",
    "    circ = QuantumCircuit(n_qubits, name='diffuser')\n",
    "\n",
    "    return circ\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have the two most important tools for our algorithm, we can simply run the algorithm.\n",
    "\n",
    "We know the optimal number of times we should run the oracle-diffuser pair; it is\n",
    "\n",
    "$$r=\\left\\lfloor \\frac{\\pi}{4} \\sqrt{N}\\right\\rfloor$$\n",
    "\n",
    "(read Nielsen-Chuang 6.1.4 for a derivation of this bound.)\n",
    "\n",
    "Let's get everything together and see if it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.quantum_info import Statevector\n",
    "\n",
    "def get_most_sampled_bitstring(circ):\n",
    "    statevector = Statevector.from_instruction(circ)\n",
    "    counts=statevector.sample_counts(1000)\n",
    "    bitstring =counts.most_frequent()\n",
    "    return bitstring\n",
    "\n",
    "\n",
    "def grovers_algorithm(n_qubits, target_bitstring:int|str):\n",
    "    \n",
    "    circ = QuantumCircuit(n_qubits, n_qubits)\n",
    "    bitstring_ind = from_bitstring(n_qubits,target_bitstring)\n",
    "\n",
    "    r = int(np.floor(np.pi/4*np.sqrt(2**n_qubits)))\n",
    "    circ.h(range(n_qubits))\n",
    "    \n",
    "    for _ in range(r):\n",
    "        circ.append(oracle(n_qubits, bitstring_ind), range(n_qubits)) #U\n",
    "        circ.append(diffuser(n_qubits), range(n_qubits)) # R\n",
    "  \n",
    "    return circ\n",
    "\n",
    "n_qubits = 6\n",
    "\n",
    "for trial in range(10):\n",
    "    random_bitstring_ind=np.random.randint(0,2**n_qubits)\n",
    "    solution=to_bitstring(n_qubits,random_bitstring_ind)\n",
    "    circ = grovers_algorithm(n_qubits, random_bitstring_ind)\n",
    "    guess = get_most_sampled_bitstring(circ)\n",
    "    print(f\"trial {trial}: solution: {solution}, guess: {guess} match: {guess==solution}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that you can also expand Grover's algorithm to the case where you look for multiple items. You only need minor changes: the oracle flips all the solutions, and the number of repeats is reduced by a factor $\\frac{1}{\\sqrt{k}}$ where $k$ is the number of items you're looking for."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "language": "python",
   "name": "python3"
  },
  "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}