{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "# Grover's Algorithm\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "---\n", "\n", "## Overview\n", "\n", "This notebook demonstrates Grover's algorithm applied to an example of searching for 2 marked items in a small unsorted database. Grover's algorithm illustrates patterns and structure that are also used in other quantum algorithms, such as:\n", "\n", "- [Deutsch-Jozsa algorithm](https://nvidia.github.io/cuda-quantum/latest/applications/python/deutsch_jozsa.html) (distinguishing constant from balanced functions)\n", "- Simon’s algorithm (finding hidden periodicity)\n", "- [Shor’s algorithm](https://nvidia.github.io/cuda-quantum/latest/applications/python/shors.html) (factoring via [quantum Fourier transform](https://nvidia.github.io/cuda-quantum/latest/applications/python/quantum_fourier_transform.html)).\n", "\n", "For a more thorough explanation of Grover's algorithm, check out the [CUDA-Q Academic repository](https://github.com/NVIDIA/cuda-q-academic/blob/main/qis-examples/grovers.ipynb).\n", "\n", "Before we get started, we will need to import a few libraries:\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import cudaq\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "\n", "#cudaq.set_target(\"nvidia\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "---\n", "\n", "## Problem\n", "\n", "We consider the problem of searching for a marked element or a set of marked elements in an unstructured database. We can make this explicit by considering a database made up of binary strings of length $n$. Let $\\mathbb{B}^n$ denote the set of binary strings of length $n$. A Boolean function\n", "$$f: \\mathbb{B}^n\n", "\\to \\{0,1\\}$$\n", "encodes the marked elements, where $f(x) =1$ if $x$ is a marked string. Our goal is to find all strings $x$ such that $f(x) = 1$.\n", "\n", "Classically, if we have no prior knowledge about $f$ (i.e., it is given as a black-box oracle), the best strategy requires $O(N)$ evaluations, where $N = 2^n$ is the total number of binary strings. However, there exists a quantum algorithm due to L. Grover that finds a solution using only $O(\\sqrt{N})$ oracle queries ([Grover, 1996](https://arxiv.org/abs/quant-ph/9605043)). \n", "\n", "We will use computational basis states on $n$ qubits to represent the $2^n$ elements in the database $B^n$. Our goal is to create a quantum kernel that separates the marked states from the non-marked states. That is, sampling from the kernel yields a marked state with high probability and a non-marked state with low probability. \n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "In this notebook, we will use a specific example to illustrate the steps and key concepts of Grover's algorithm. \n", "\n", "Let $n=4$ and mark the states `1001` and `1111`. \n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "## Structure of Grover's Algorithm\n", "\n", "Grover's Algorithm can be broken down into the following steps:\n", "\n", "1. Preparation: Initialize $n$ qubits in an equal superposition state. \n", "2. Oracle Application: Apply the oracle operator to flip the phase of the marked states (i.e., multiply them by $-1$).\n", "3. Amplitude Amplification: Use the diffusion operator to amplify the amplitudes of the marked states.\n", "4. Iteration: Repeat Steps 2 and 3 a specified number of times, which depends on the number of marked elements and $n$.\n", "5. Measurement: Measure the qubits. With high probability, the result will be one of the marked states.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "### Step 1: Preparation\n", "The first step of Grover's algorithm requires initializing $n$ qubits in a state of equal superposition:\n", "\n", "$$\n", "\\ket{\\xi}:= H^{\\otimes n} (|0\\rangle^{\\otimes n}) = \\frac{1}{\\sqrt{N}} \\sum\\limits_{i=0}^{N-1} |i\\rangle,\n", "$$\n", "where each binary string is identified with the integer it represents (e.g., $|5\\rangle = |0101\\rangle$).\n", "\n", "The kernel in the code block below places the $n$ qubits in an equal superposition state.\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Kernel to create an equal superposition state of qubits initialized to |0>\n", "@cudaq.kernel\n", "def equal_superposition(qubits_in_zero_state : cudaq.qview):\n", " h(qubits_in_zero_state)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "### Good and Bad States\n", "\n", "We can simplify our analysis of Grover's Algorithm by focusing on two useful quantum states, which we'll refer to as the \"good\" and \"bad\" states. The \"good\" state captures the marked bitstrings and the \"bad\" state is orthogonal to the \"good\" state.\n", "\n", "Suppose there are $t$ marked states, i.e., there are $t$ elements $x \\in \\mathbb{B}^n$ with $f(x) = 1$. Letting $N=2^n$, we introduce the following quantum states:\n", "\n", "$$\n", "|G\\rangle := \\frac{1}{\\sqrt{t}} \\sum\\limits_{i, f(i) = 1} |i\\rangle, \\quad |B\\rangle := \\frac{1}{\\sqrt{N - t}} \\sum\\limits_{i, f(i) = 0} |i\\rangle.\n", "$$\n", "\n", "These are the uniform superpositions of marked and unmarked states, referred to as the \"good\" and \"bad\" states, respectively. \n", "\n", "Rewriting the uniform superposition state $\\ket{\\xi}$ in terms of $|G\\rangle$ and $|B\\rangle$, we obtain:\n", "\n", "$$\n", "\\ket{\\xi} = \\frac{1}{\\sqrt{N}} \\sum\\limits_{i, f(i) = 1} |i\\rangle + \\frac{1}{\\sqrt{N}} \\sum\\limits_{i, f(i) = 0} |i\\rangle\n", "= \\frac{\\sqrt{t}}{\\sqrt{N}} |G\\rangle + \\frac{\\sqrt{N - t}}{\\sqrt{N}} |B\\rangle.\n", "$$\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "Let's see what this look likes for our example of $n=4$ and marked states `1001` and `1111`. Here $\\ket{\\xi} = \\frac{1}{16}\\sum_{k=0}^{15}\\ket{k}$ since there are 4 qubits and 16 computational basis states with $\\ket{0} = \\ket{0000}, \\ket{1} = \\ket{0001}, \\cdots \\ket{15} = \\ket{1111}$. The good state is a equal superposition of the states $\\ket{9} =\\ket{1001}$ and $\\ket{15} =\\ket{1111}$: \n", "$$\\ket{G} = \\frac{1}{\\sqrt{2}}(\\ket{9}+\\ket{15} )= \\frac{1}{\\sqrt{2}}(\\ket{1001}+\\ket{1111}).$$\n", "\n", "The bad state is an equal superposition of the remaining states:\n", "$$\\ket{B} = \\frac{1}{\\sqrt{14}}(\\ket{0}+\\ket{1}+\\ket{2}+\\cdots+\\ket{8}+\\ket{10}+\\cdots+\\ket{14}) = \\frac{1}{\\sqrt{14}}\\sum_{x\\in B^4}f(x)\\ket{x}. $$\n", "\n", "Notice that $\\ket{G}$ and $\\ket{B}$ are orthogonal. \n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "Next, we observe that the coefficients $\\frac{\\sqrt{t}}{\\sqrt{N}}$ and $\\frac{\\sqrt{N - t}}{\\sqrt{N}}$ are real numbers satisfying:\n", "\n", "$$\n", "\\left(\\frac{\\sqrt{t}}{\\sqrt{N}}\\right)^2 + \\left(\\frac{\\sqrt{N - t}}{\\sqrt{N}}\\right)^2 = 1.\n", "$$\n", "\n", "This naturally leads us to apply a trigonometry identity to define an angle $\\theta$ such that:\n", "\n", "$$\n", "\\theta = \\arcsin\\left(\\frac{\\sqrt{t}}{\\sqrt{N}}\\right).\n", "$$\n", "\n", "With this notation, we can rewrite $\\ket{\\xi}$ as:\n", "\n", "$$\n", "\\ket{\\xi} = \\sin(\\theta) |G\\rangle + \\cos(\\theta) |B\\rangle.\n", "$$\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "For our example, we have 2 marked states and 4 qubits, in other words $t =2$ and $ N = 2^4 = 16$.\n", "In this case, $\\theta = \\arcsin(\\frac{\\sqrt{2}}{\\sqrt{16}}) = \\arcsin(\\frac{1}{\\sqrt{8}}))\\approx 21^\\circ$. " ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Let us now examine the geometric picture behind our current discussion. We'll consider the ambient Hilbert space to be spanned by the standard basis vectors $|0\\rangle, |1\\rangle, \\dots, |N-1\\rangle$, where the full dimension is $N = 2^n$. Since the uniform superposition state $|\\xi\\rangle$ can be expressed as a linear combination of the states $|G\\rangle$ and $|B\\rangle$ with real coefficients, all three states $|\\xi\\rangle, |G\\rangle,$ and $|B\\rangle$ reside in a two-dimensional real subspace of the ambient Hilbert space, which we can visualize as a 2D plane as in the image below. Since, $|G\\rangle$ and $|B\\rangle$ are orthogonal, we can imagine them graphed as unit vectors in the positive $y$ and positive $x$ directions, respectively. From our previous expression, $\\ket{\\xi} = \\sin(\\theta) |G\\rangle + \\cos(\\theta) |B\\rangle,$ we see that the state $|\\xi\\rangle$ forms an angle $\\theta$ with $|B\\rangle$.\n", "\n", "