{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Grover's Algorithm\n", "\n", "The **Grover's Search** quantum kata is a series of exercises designed\n", "to get you familiar with Grover's search algorithm.\n", "\n", "It covers the following topics:\n", "\n", "* writing oracles for Grover's search,\n", "* performing steps of the algorithm, and\n", "* putting it all together: Grover's search algorithm.\n", "\n", "*Reading material:*\n", "\n", "* [The Oracles tutorial](../Oracles/Oracles.ipynb) is an introduction into quantum oracles.\n", "* [This Microsoft Learn module](https://docs.microsoft.com/learn/modules/solve-graph-coloring-problems-grovers-search/) offers a different, visual explanation of Grover's algorithm.\n", "* The tasks follow the explanation from *Quantum Computation and Quantum Information* by Nielsen and Chuang.\n", " In the 10th anniversary edition, this is section 6.1.2 on pages 248-251.\n", "* A different explanation of Grover's algorithm can be found in \n", " [this Wikipedia article](https://en.wikipedia.org/wiki/Grover%27s_algorithm).\n", "* [An Introduction to Quantum Algorithms](https://strubell.github.io/doc/quantum_tutorial.pdf) by Emma Strubell, pages 20-24.\n", "* [Lecture 4: Grover's Algorithm](https://www.cs.cmu.edu/~odonnell/quantum15/lecture04.pdf) by John Wright.\n", "* Lectures [12](https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.12.pdf) and [13](https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.13.pdf) by John Watrous.\n", "* [This page](http://davidbkemp.github.io/animated-qubits/grover.html) has an animated demonstration of Grover's algorithm for a simple case.\n", "\n", "Each task is wrapped in one operation preceded by the description of the task.\n", "Your goal is to fill in the blanks (marked with the `// ...` comments)\n", "with some Q# code that solves the task. To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS).\n", "\n", "Within each section, tasks are given in approximate order of increasing difficulty;\n", "harder ones are marked with asterisks." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part I. Oracles for Grover's Search\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 1.1. The $|11...1\\rangle$ Oracle\n", "**Inputs:** \n", "\n", " 1. N qubits in an arbitrary state $|x\\rangle$ (input/query register)\n", "\n", " 2. A qubit in an arbitrary state $|y\\rangle$ (target qubit)\n", "\n", "**Goal:**\n", "\n", "Flip the state of the target qubit (i.e., apply an X gate to it)\n", "if the query register is in the $|11...1\\rangle$ state,\n", "and leave it unchanged if the query register is in any other state.\n", "Leave the query register in the same state it started in.\n", "\n", "**Examples:**\n", "\n", "* If the query register is in state $|00...0\\rangle$, leave the target qubit unchanged.\n", "\n", "* If the query register is in state $|10...0\\rangle$, leave the target qubit unchanged.\n", "\n", "* If the query register is in state $|11...1\\rangle$, flip the target qubit.\n", "\n", "* If the query register is in state $\\frac{1}{\\sqrt{2}} \\big(|00...0\\rangle + |11...1\\rangle \\big)$, and the target is in state $|0\\rangle$,\n", "the joint state of the query register and the target qubit should be $\\frac{1}{\\sqrt{2}} \\big(|00...00\\rangle + |11...11\\rangle \\big)$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T11_Oracle_AllOnes \n", "\n", "operation Oracle_AllOnes (queryRegister : Qubit[], target : Qubit) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 1.2. The $|1010...\\rangle$ Oracle\n", "\n", "**Inputs:**\n", "\n", " 1. N qubits in an arbitrary state $|x\\rangle$ (input/query register)\n", "\n", " 2. A qubit in an arbitrary state $|y\\rangle$ (target qubit)\n", "\n", "**Goal:**\n", "\n", " Flip the state of the target qubit if the query register is in the $|1010...\\rangle$ state;\n", "that is, the state with alternating 1 and 0 values, with any number of qubits in the register.\n", "Leave the state of the target qubit unchanged if the query register is in any other state.\n", "Leave the query register in the same state it started in.\n", "\n", "**Examples:**\n", "\n", " * If the register is in state $|0000000\\rangle$, leave the target qubit unchanged.\n", " * If the register is in state $|10101\\rangle$, flip the target qubit." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T12_Oracle_AlternatingBits \n", "\n", "operation Oracle_AlternatingBits (queryRegister : Qubit[], target : Qubit) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 1.3. Arbitrary Bit Pattern Oracle\n", "\n", "**Inputs:**\n", "\n", " 1. N qubits in an arbitrary state $|x\\rangle$ (input/query register)\n", "\n", " 2. A qubit in an arbitrary state $|y\\rangle$ (target qubit)\n", "\n", " 3. A bit pattern of length N represented as `Bool[]`\n", "\n", "**Goal:**\n", "\n", " Flip the state of the target qubit if the query register is in the state described by the given bit pattern\n", "(`true` represents qubit state One, and `false` represents Zero).\n", "Leave the state of the target qubit unchanged if the query register is in any other state.\n", "Leave the query register in the same state it started in.\n", "\n", "**Example:**\n", "\n", " If the bit pattern is `[true, false]`, you need to flip the target qubit if and only if the qubits are in the $|10\\rangle$ state." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T13_Oracle_ArbitraryPattern \n", "\n", "operation Oracle_ArbitraryPattern (queryRegister : Qubit[], target : Qubit, pattern : Bool[]) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 1.4. Oracle Converter\n", "\n", "**Input:**\n", "\n", "A marking oracle: an oracle that takes a register and a target qubit and\n", "flips the target qubit if the register satisfies a certain condition.\n", "\n", "**Output:**\n", "\n", "A phase-flipping oracle: an oracle that takes a register and\n", "flips the phase of the register if it satisfies this condition.\n", "\n", "> Grover's algorithm relies on the search condition implemented as a phase-flipping oracle,\n", "but it is often easier to write a marking oracle for a given condition. This transformation\n", "allows to convert one type of oracle into the other. The transformation is described in the \n", "[Wikipedia article on Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm), in the section \"Description of ${U_\\omega}$\".\n", "\n", "
\n", "
\n", " Need a hint? Click here\n", " Remember that you can define auxiliary operations. To do that, you'll need to create an extra code cell for each new operation and execute it before returning to this cell.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T14_OracleConverter \n", "\n", "function OracleConverter (markingOracle : ((Qubit[], Qubit) => Unit is Adj)) : (Qubit[] => Unit is Adj) {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part II. The Grover Iteration" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 2.1. The Hadamard Transform\n", "\n", "**Input:** A register of N qubits in an arbitrary state\n", "\n", "**Goal:** Apply the Hadamard transform to each of the qubits in the register.\n", "\n", "> If the register started in the $|0...0\\rangle$ state, this operation\n", "will prepare an equal superposition of all $2^{N}$ basis states." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T21_HadamardTransform \n", "\n", "operation HadamardTransform (register : Qubit[]) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 2.2. Conditional Phase Flip\n", "\n", "**Input:** A register of N qubits in an arbitrary state.\n", "\n", "**Goal:** Flip the sign of the state of the register if it is not in the $|0...0\\rangle$ state.\n", "\n", "**Examples:**\n", "\n", " * If the register is in state $|0...0\\rangle$, leave it unchanged.\n", "\n", " * If the register is in any other basis state, multiply its phase by -1.\n", "\n", "> This operation implements operator $2|0...0\\rangle\\langle0...0| - I$ $ = \\left(\\begin{matrix}1&0&...&0\\\\0&-1&...&0\\\\\\vdots&\\vdots&\\ddots&\\vdots\\\\0&0&...&-1\\end{matrix}\\right) $\n", "\n", "
\n", "
\n", " Hint #1\n", " Note that quantum states are defined up to a global phase.\n", " Thus the state obtained as a result of this operation is equivalent to the state obtained by flipping the sign of only the $|0...0\\rangle$ basis state (those states differ by a global phase $-1$).
\n", " $$-\\big(2|0...0\\rangle\\langle0...0| - I\\big) = I - 2|0...0\\rangle\\langle0...0| = \\left(\\begin{matrix}-1&0&...&0\\\\0&1&...&0\\\\\\vdots&\\vdots&\\ddots&\\vdots\\\\0&0&...&1\\end{matrix}\\right) $$
\n", " \n", "It doesn't matter for Grover's search algorithm itself, since the global phase is not observable, but can have side effects when used as part of other algorithms.\n", "> See the extended discussion in this [Quantum Computing SE question](https://quantumcomputing.stackexchange.com/questions/5973/counting-in-q-number-of-solutions/6446#6446)
\n", "
\n", "
\n", "\n", "
\n", " Hint #2\n", " Consider the Controlled Z gate, applied with most of the qubits as control and the last qubit as target:\n", " $\\text{Controlled Z}(|s_0 s_1 \\ldots s_{n-2}\\rangle, |s_{n-1}\\rangle)$ leaves all basis states except $|1...11\\rangle$ unchanged, and adds a $-1$ phase to that state: $|1...11\\rangle \\rightarrow -|1...11\\rangle$ (remember that $Z|0\\rangle = |0\\rangle$ and $Z|1\\rangle = -|1\\rangle$). \n", " You need to modify it to add the $-1$ phase to only the $|0...00\\rangle$ state instead.\n", "

\n", " Alternatively, you can use the same trick as in the oracle converter task.
\n", "
\n", "
\n", "\n", "
\n", " Hint #3\n", " You can use the R gate to correct the global phase.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T22_ConditionalPhaseFlip \n", "\n", "operation ConditionalPhaseFlip (register : Qubit[]) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 2.3. The Grover Iteration\n", "\n", "**Inputs:**\n", "\n", " 1. N qubits in an arbitrary state $|x\\rangle$ (input/query register)\n", "\n", " 2. A phase-flipping oracle that takes an N-qubit register and flips\n", " the phase of the state if the register is in the desired state.\n", "\n", "**Goal:** Perform one Grover iteration.\n", "\n", "
\n", "
\n", " Need a hint? Click here\n", " A Grover iteration consists of 4 steps:\n", "
    \n", "
  1. Apply the Oracle
    2. \n", "
  2. Apply the Hadamard transform
    3. \n", "
  3. Perform a conditional phase shift
    4. \n", "
  4. Apply the Hadamard transform again
    5. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T23_GroverIteration \n", "\n", "operation GroverIteration (register : Qubit[], oracle : (Qubit[] => Unit is Adj)) : Unit is Adj {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part III. Putting It All Together: Grover's Search Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 3.1. Grover's Search\n", "\n", "**Inputs:**\n", "\n", " 1. N qubits in the $|0...0\\rangle$ state.\n", "\n", " 2. A marking oracle.\n", "\n", " 3. The number of Grover iterations to perform.\n", "\n", "**Goal:** Use Grover's algorithm to leave the register in the state that is marked by the oracle as the answer (with high probability).\n", "\n", "> The number of iterations is passed as a parameter because it is defined by the nature of the problem\n", "and is easier to configure/calculate outside the search algorithm itself (for example, in the classical driver)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%kata T31_GroversSearch \n", "\n", "operation GroversSearch (register : Qubit[], oracle : ((Qubit[], Qubit) => Unit is Adj), iterations : Int) : Unit {\n", " // ...\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Task 3.2. Using Grover's Search\n", "\n", "**Goal:** Use your implementation of Grover's Algorithm from Task 3.1 and the oracles from part 1\n", " to find the marked elements of the search space. This task is not covered by a test and allows you to experiment with running the algorithm.\n", " \n", "> This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_GroversSearch_Algorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_GroversSearch_Algorithm`).\n", "\n", "> Note that this task relies on your implementations of the previous tasks. If you are getting the \"No variable with that name exists.\" error, you might have to execute previous code cells before retrying this task.\n", "\n", "
\n", " Hint #1\n", " To check whether the algorithm found the correct answer (i.e., an answer marked as 1 by the oracle),\n", " you can apply the oracle once more to the register after you've measured it and an ancilla qubit,\n", " which will calculate the function of the answer found by the algorithm.\n", "
\n", "
\n", "
\n", " Hint #2\n", " Experiment with the number of iterations to see how it affects\n", " the probability of the algorithm finding the correct answer.\n", "
\n", "
\n", "
\n", " Hint #3\n", " You can use the Message function to output the results.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "operation Run_GroversSearch_Algorithm () : Unit {\n", " // ...\n", "}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%simulate Run_GroversSearch_Algorithm" ] } ], "metadata": { "kernelspec": { "display_name": "Q#", "language": "qsharp", "name": "iqsharp" }, "language_info": { "file_extension": ".qs", "mimetype": "text/x-qsharp", "name": "qsharp", "version": "0.14" } }, "nbformat": 4, "nbformat_minor": 2 }