samples/algorithms/database-search/Database Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Oracle Definition ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implements the oracle $D |z\\rangle |k\\rangle = |z \\oplus x_k \\rangle |k\\rangle$ used in the Grover\n",
    "search algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation ApplyDatabaseOracle(\n",
    "    markedElement : Int,\n",
    "    markedQubit: Qubit,\n",
    "    databaseRegister: Qubit[]\n",
    ") : Unit is Adj + Ctl {\n",
    "    ControlledOnInt(markedElement, X)(databaseRegister, markedQubit);\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ControlledOnInt?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State Preparation ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implements an oracle $DU$ that prepares the start state\n",
    "$DU |0\\rangle|0\\rangle = 1 / \\sqrt{N} |1\\rangle|\\text{marked}\\rangle + \\sqrt{N - 1} / \\sqrt{N} |0\\rangle|\\text{unmarked}\\rangle$ where $N = 2^n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PrepareDatabaseRegister(\n",
    "    markedElement : Int,\n",
    "    idxMarkedQubit: Int,\n",
    "    startQubits: Qubit[]\n",
    ") : Unit is Adj + Ctl {\n",
    "    let flagQubit = startQubits[idxMarkedQubit];\n",
    "    let databaseRegister = Exclude([idxMarkedQubit], startQubits);\n",
    "\n",
    "    // Apply 𝑈.\n",
    "    ApplyToEachCA(H, databaseRegister);\n",
    "\n",
    "    // Apply 𝐷.\n",
    "    ApplyDatabaseOracle(markedElement, flagQubit, databaseRegister);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we wrap our state preparation in a *user-defined type* to indicate that it is a state preparation oracle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Oracles;\n",
    "\n",
    "function GroverStatePrepOracle(markedElement : Int) : StateOracle {\n",
    "    return StateOracle(PrepareDatabaseRegister(markedElement, _, _));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover's Algorithm ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.AmplitudeAmplification;\n",
    "\n",
    "function GroverSearch(\n",
    "    markedElement: Int,\n",
    "    nIterations: Int,\n",
    "    idxMarkedQubit: Int\n",
    ") : (Qubit[] => Unit is Adj + Ctl) {\n",
    "\n",
    "    return StandardAmplitudeAmplification(nIterations, GroverStatePrepOracle(markedElement), idxMarkedQubit);\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Measurement;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation ApplyQuantumSearch() : (Result, Int) {\n",
    "\n",
    "    let nIterations = 6;\n",
    "    let nDatabaseQubits = 6;\n",
    "    let markedElement = 3;\n",
    "\n",
    "    use markedQubit = Qubit();\n",
    "    use databaseRegister = Qubit[nDatabaseQubits];\n",
    "\n",
    "    // Implement the quantum search algorithm.\n",
    "    GroverSearch(markedElement, nIterations, 0)([markedQubit] + databaseRegister);\n",
    "\n",
    "    // Measure the marked qubit. On success, this should be One.\n",
    "    let resultSuccess = MResetZ(markedQubit);\n",
    "\n",
    "    // Measure the state of the database register post-selected on\n",
    "    // the state of the marked qubit.\n",
    "    let resultElement = ForEach(MResetZ, databaseRegister);\n",
    "    let numberElement = ResultArrayAsInt(resultElement);\n",
    "\n",
    "    // Returns the measurement results of the algorithm.\n",
    "    return (resultSuccess, numberElement);\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate ApplyQuantumSearch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Epilogue ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}