{ "cells": [ { "cell_type": "markdown", "id": "5ef43d5f", "metadata": {}, "source": [ "---\n", "title: Grover's algorithm description\n", "description: A free IBM course on quantum information and computation\n", "---\n", "\n", "# Description of Grover's algorithm\n", "\n", "In this section, we'll describe Grover's algorithm.\n", "We'll begin by discussing *phase query gates* and how to build them, followed by the description of Grover's algorithm itself.\n", "Finally, we'll briefly discuss how this algorithm is naturally applied to searching.\n", "\n", "## Phase query gates\n", "\n", "Grover's algorithm makes use of operations known as *phase query gates*.\n", "In contrast to an ordinary query gate $U_f,$ defined for a given function $f$ in the usual way described previously, a phase query gate for the function $f$ is defined as\n", "\n", "$$\n", "Z_f \\vert x\\rangle = (-1)^{f(x)} \\vert x\\rangle\n", "$$\n", "\n", "for every string $x\\in\\Sigma^n.$\n", "\n", "The operation $Z_f$ can be implemented using one query gate $U_f$ as this diagram suggests:\n", "\n", "![A quantum circuit implementing a Z\\_f gate using one query gate together with the phase kickback phenomenon](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/Z_f.svg)\n", "\n", "This implementation makes use of the phase kickback phenomenon, and requires that one workspace qubit, initialized to a $\\vert -\\rangle$ state, is made available.\n", "This qubit remains in the $\\vert - \\rangle$ state after the implementation has completed, and can be reused (to implement subsequent $Z_f$ gates, for instance) or simply discarded.\n", "\n", "In addition to the operation $Z_f,$ we will also make use of a phase query gate for the $n$-bit OR function, which is defined as follows for each string $x\\in\\Sigma^n.$\n", "\n", "$$\n", "\\mathrm{OR}(x) =\n", "\\begin{cases}\n", " 0 & x = 0^n\\\\[0.5mm]\n", " 1 & x \\neq 0^n\n", "\\end{cases}\n", "$$\n", "\n", "Explicitly, the phase query gate for the $n$-bit OR function operates like this:\n", "\n", "$$\n", "Z_{\\mathrm{OR}} \\vert x\\rangle\n", "= \\begin{cases}\n", " \\vert x\\rangle & x = 0^n \\\\[0.5mm]\n", "- \\vert x\\rangle & x \\neq 0^n.\n", "\\end{cases}\n", "$$\n", "\n", "To be clear, this is how $Z_{\\mathrm{OR}}$ operates on standard basis states; its behavior on arbitrary states is determined from this expression by linearity.\n", "\n", "The operation $Z_{\\mathrm{OR}}$ can be implemented as a quantum circuit by beginning with a Boolean circuit for the OR function, then constructing a $U_{\\mathrm{OR}}$ operation (that is, a standard query gate for the $n$-bit OR function) using the procedure described in the *Quantum algorithmic foundations* lesson, and finally a $Z_{\\mathrm{OR}}$ operation using the phase kickback phenomenon as described above.\n", "Notice that the operation $Z_{\\mathrm{OR}}$ has no dependence on the function $f$ and can therefore be implemented by a quantum circuit having no query gates.\n", "\n", "## Description of the algorithm\n", "\n", "Now that we have the two operations $Z_f$ and $Z_{\\mathrm{OR}},$ we can describe Grover's algorithm.\n", "\n", "The algorithm refers to a number $t,$ which is the number of *iterations* it performs (and therefore the number of *queries* to the function $f$ it requires).\n", "This number $t$ isn't specified by Grover's algorithm as we're describing it, and we'll discuss later in the lesson how it can be chosen.\n", "\n", "
\n", " 1. Initialize an $n$ qubit register $\\mathsf{Q}$ to the all-zero state $\\vert 0^n \\rangle$ and then apply a Hadamard operation to each qubit of $\\mathsf{Q}.$\n", " 2. Apply $t$ times the unitary operation $G = H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n} Z_f$ to the register $\\mathsf{Q}$\n", " 3. Measure the qubits of $\\mathsf{Q}$ with respect to standard basis measurements and output the resulting string.\n", "
\n", "\n", "The operation $G = H^{\\otimes n} Z_{\\mathrm{OR}} H^{\\otimes n} Z_f$ iterated in step 2 will be called the *Grover operation* throughout the remainder of this lesson.\n", "Here is a quantum circuit representation of the Grover operation when $n=7\\!:$\n", "\n", "![A quantum circuit representation of the Grover operation](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/Grover_operation.svg)\n", "\n", "In this diagram, the $Z_f$ operation is depicted as being larger than $Z_{\\mathrm{OR}}$ as an informal visual clue to suggest that it is likely to be the more costly operation.\n", "In particular, when we're working within the query model, $Z_f$ requires one query while $Z_{\\mathrm{OR}}$ requires no queries.\n", "If instead we have a Boolean circuit for the function $f,$ and then convert it to a quantum circuit for $Z_f,$ we can reasonably expect that the resulting quantum circuit will be larger and more complicated than one for $Z_{\\mathrm{OR}}.$\n", "\n", "Here's a diagram of a quantum circuit for the entire algorithm when $n=7$ and $t=3.$\n", "For larger values of $t$ we can simply insert additional instances of the Grover operation immediately before the measurements.\n", "\n", "![A quantum circuit for Grover's algorithm when t=3](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/grover-algorithm/Grover_circuit.svg)\n", "\n", "## Application to search\n", "\n", "Grover's algorithm can be applied to the *Search* problem as follows:\n", "\n", "* Choose the number $t$ in step 2. (This is discussed later in the lesson.)\n", "* Run Grover's algorithm on the function $f,$ using whatever choice we made for $t,$ to obtain a string $x\\in\\Sigma^n.$\n", "* Query the function $f$ on the string $x$ to see if it's a valid solution:\n", " * If $f(x) = 1,$ then we have found a solution, so we can stop and output $x.$\n", " * Otherwise, if $f(x) = 0,$ then we can either run the procedure again, possibly with a different choice for $t,$ or we can decide to give up and output \"no solution.\"\n", "\n", "Once we've analyzed how Grover's algorithm works, we'll see that by taking $t = O(\\sqrt{N}),$ we obtain a solution to our search problem (if one exists) with high probability.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "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" } }, "nbformat": 4, "nbformat_minor": 5 }