algorithms/deutsch_jozsa/deutsch_jozsa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d822b35c-f93f-4899-b7eb-2de8b8e43ad2",
   "metadata": {},
   "source": [
    "# Deutsch-Jozsa Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "152ddf06-25a7-4724-a3fb-305dbb7bbc07",
   "metadata": {
    "editable": true,
    "jp-MarkdownHeadingCollapsed": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "The Deutsch-Jozsa algorithm [[1](#DJWiki)], named after David Deutsch and Richard Jozsa, is one of the first fundamental   quantum algorithms showing exponential speedup over its classical counterpart$^*$. While it has no practical applicative use, it serves as a toy model for quantum computing, demonstrating how the concepts of superposition and interference enable quantum algorithms to outperform classical ones."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf77d30a-7ca4-453c-9afd-ae7cc66c69b4",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "The algorithm treats the following problem:\n",
    "\n",
    "* **Input:** A black box Boolean function $f(x)$ that acts on the integers in the range $[0, 2^{n}-1]$.\n",
    "\n",
    "* **Promise:** The function is either constant or balanced (for half of the values it is 1 and for the other half it is 0).\n",
    "\n",
    "* **Output:** Whether the function is constant or balanced.\n",
    "\n",
    "\n",
    "$^*$ The exponential speedup is in the oracle complexity setting. It only refers to deterministic classical machines.\n",
    "\n",
    "***\n",
    "\n",
    "\n",
    "Problem hardness: If we require a deterministic answer to the problem, classically, we have to inquire of the oracle $2^{n-1}+1$ times in the worst case. **The quantum approach requires a single query, thus, introducing a clear exponential speedup**. (Without requiring deterministic determination, namely, allowing application of the classical probabilistic algorithm to get the result up to some error, then the exponential speedup is lost: taking $k$ classical evaluations of the function $f$ determines whether the function is constant or balanced, with a probability of $1-1/2^k$).\n",
    "\n",
    "\n",
    "We define the Deutsch-Jozsa algorithm, which has a [quantum part](#The-Quantum-Part) and a [classical postprocess part](#The-Classical-Postprocess). Then, we run the algorithm on two different examples, one with a [simple](#Example:-Simple-Arithmetic-Oracle) $f(x)$ and another that is [more complex](#Example:-Complex-Arithmetic-Oracle). A [mathematical explanation](#Technical-Notes) of the algorithm is provided at the end of this notebook.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5190bdfe-52f9-4992-9817-3dd3955208ec",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://docs.classiq.io/resources/deutsch_josza_closed.png\" style=\"width:100%\">\n",
    "<figcaption align = \"middle\"> Figure 1. The Deutsch-Jozsa algorithm </figcaption>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "109523bf-6e2b-4f86-a4ab-ae21423e1e19",
   "metadata": {},
   "source": [
    "## How to Build the Algorithm with Classiq"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12c83926-aa58-4030-be55-cc75e17766ff",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "We define a `deutsch_jozsa` quantum function whose arguments are a quantum function for the black box $f(x)$, and a quantum variable on which it acts, $x$. The Deutsch-Jozsa algorithm comprising three quantum blocks (see Figure 1): a Hadamard transform, an arithmetic oracle for the black box function, and another Hadamard transform. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cc14e03-5d2b-49c1-b588-ef6c042d83e3",
   "metadata": {},
   "source": [
    "### The Quantum Part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "91df521e-d0fb-4f3f-9d2d-badf11af9a32",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:11.427268Z",
     "iopub.status.busy": "2024-05-07T14:33:11.426789Z",
     "iopub.status.idle": "2024-05-07T14:33:14.260875Z",
     "shell.execute_reply": "2024-05-07T14:33:14.260110Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import *\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def prep_minus(out: Output[QBit]) -> None:\n",
    "    allocate(1, out)\n",
    "    X(out)\n",
    "    H(out)\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_oracle(predicate: QCallable[QNum, QBit], target: QNum) -> None:\n",
    "    aux = QBit(\"aux\")\n",
    "    within_apply(within=lambda: prep_minus(aux), apply=lambda: predicate(target, aux))\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def deutsch_jozsa(predicate: QCallable[QNum, QBit], x: QNum) -> None:\n",
    "    hadamard_transform(x)\n",
    "    my_oracle(predicate=lambda x, y: predicate(x, y), target=x)\n",
    "    hadamard_transform(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49fcd1ec-ad54-48aa-91a7-844b5ebd5586",
   "metadata": {},
   "source": [
    "### The Classical Postprocess\n",
    "\n",
    "The classical part of the algorithm reads: The probability of measuring the $|0\\rangle_n$ state is 1 if the function is constant and 0 if it is balanced. \n",
    "We define a classical function that gets the execution results from running the quantum part and returns whether the function is constant or balanced:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "953b77f9-6db0-4df1-8ac9-9c4f2f3be932",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:14.266379Z",
     "iopub.status.busy": "2024-05-07T14:33:14.264879Z",
     "iopub.status.idle": "2024-05-07T14:33:14.270955Z",
     "shell.execute_reply": "2024-05-07T14:33:14.270288Z"
    }
   },
   "outputs": [],
   "source": [
    "def post_process_deutsch_jozsa(parsed_results):\n",
    "    if len(parsed_results) == 1:\n",
    "        if 0 not in parsed_results:\n",
    "            print(\"The function is balanced\")\n",
    "        else:\n",
    "            print(\"The function is constant\")\n",
    "    else:\n",
    "        print(\n",
    "            \"cannot decide as more than one output was measured, the distribution is:\",\n",
    "            parsed_results,\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44bc3682-872b-4641-a356-459bfe8b218b",
   "metadata": {},
   "source": [
    "## Example: Simple Arithmetic Oracle"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e7861d4-df77-4ef5-aa2a-bd9a3aa1a062",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "We start with a simple example on $n=4$ qubits, and $f(x)= x >7$. Classically, in the worst case, the function should be evaluated $2^{n-1}+1=9$ times. However, with the Deutsch-Jozsa algorithm, this function is evaluated only once."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88600df9-cfb9-46a1-b710-c3706c8d99f9",
   "metadata": {},
   "source": [
    "We build a predicate for this specific use case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "283141cf-08f1-482a-a742-e5ee56f9c0f1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:14.275754Z",
     "iopub.status.busy": "2024-05-07T14:33:14.274384Z",
     "iopub.status.idle": "2024-05-07T14:33:14.279599Z",
     "shell.execute_reply": "2024-05-07T14:33:14.278926Z"
    }
   },
   "outputs": [],
   "source": [
    "@qfunc\n",
    "def simple_predicate(x: QNum, res: QBit) -> None:\n",
    "    res ^= x > 7"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87f5a868-db7c-4159-ba66-b5b86a8e15a2",
   "metadata": {},
   "source": [
    "Next, we define a model by inserting the predicate into the `deutsch_jozsa` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ff146265-e125-4bd8-92fa-5782c8ae5ec4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:14.283995Z",
     "iopub.status.busy": "2024-05-07T14:33:14.282901Z",
     "iopub.status.idle": "2024-05-07T14:33:17.988266Z",
     "shell.execute_reply": "2024-05-07T14:33:17.987607Z"
    }
   },
   "outputs": [],
   "source": [
    "NUM_QUBITS = 4\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QNum]):\n",
    "    allocate(NUM_QUBITS, x)\n",
    "    deutsch_jozsa(lambda x, y: simple_predicate(x, y), x)\n",
    "\n",
    "\n",
    "qmod = create_model(main, out_file=\"simple_deutsch_jozsa\")\n",
    "qprog = synthesize(qmod)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee250190-ba84-4a08-a9fa-067ea448d2f6",
   "metadata": {},
   "source": [
    "Finally, we execute and call the classical postprocess:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6399ee7e-29c5-4442-9c6b-81dcf6817592",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:17.992603Z",
     "iopub.status.busy": "2024-05-07T14:33:17.991365Z",
     "iopub.status.idle": "2024-05-07T14:33:19.431817Z",
     "shell.execute_reply": "2024-05-07T14:33:19.431128Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The function is balanced\n"
     ]
    }
   ],
   "source": [
    "result = execute(qprog).result_value()\n",
    "results_list = [sample.state[\"x\"] for sample in result.parsed_counts]\n",
    "post_process_deutsch_jozsa(results_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c39f9666-78c8-49ff-a0e8-1b5c57e43a12",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:19.434188Z",
     "iopub.status.busy": "2024-05-07T14:33:19.433975Z",
     "iopub.status.idle": "2024-05-07T14:33:19.521800Z",
     "shell.execute_reply": "2024-05-07T14:33:19.520900Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/5d59d5f5-4087-48c0-b873-a04a2b10bdb0?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdbb09b9-966f-4753-bb19-827522116325",
   "metadata": {},
   "source": [
    "## Example: Complex Arithmetic Oracle"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66e01d1f-0fb5-4a18-b44d-25b5cfe05bf2",
   "metadata": {},
   "source": [
    "*Generalizing to more complex scenarios makes no difference for modeling*. Let us take a complicated function, working with $n=3$: a function $f(x)$ that first takes the maximum between the input bitwise-xor with 4 and the input bitwise-and with 3, then checks whether the result is greater or equal to 4. Can you tell whether the function is balanced or constant?\n",
    "\n",
    "*This time we provide a width bound to the synthesis engine.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cd231fa-330b-460a-9f76-987d370b8952",
   "metadata": {},
   "source": [
    "We follow the three steps as before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "93045ada-8a49-44ad-8a41-b19938ef6c4c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:19.524166Z",
     "iopub.status.busy": "2024-05-07T14:33:19.523987Z",
     "iopub.status.idle": "2024-05-07T14:33:27.365817Z",
     "shell.execute_reply": "2024-05-07T14:33:27.365167Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The function is balanced\n"
     ]
    }
   ],
   "source": [
    "from classiq.qmod.symbolic import max\n",
    "\n",
    "NUM_QUBITS = 3\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def complex_predicate(x: QNum, res: QBit) -> None:\n",
    "    res ^= max(x ^ 4, x & 3) >= 4\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QNum]):\n",
    "    allocate(NUM_QUBITS, x)\n",
    "    deutsch_jozsa(lambda x, y: complex_predicate(x, y), x)\n",
    "\n",
    "\n",
    "qmod = create_model(main, out_file=\"complex_deutsch_jozsa\")\n",
    "qmod = set_constraints(qmod, constraints=Constraints(max_width=19))\n",
    "qprog = synthesize(qmod)\n",
    "\n",
    "result = execute(qprog).result_value()\n",
    "results_list = [sample.state[\"x\"] for sample in result.parsed_counts]\n",
    "post_process_deutsch_jozsa(results_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b4befb7-217d-4327-8f1e-cf56f9f12eea",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://docs.classiq.io/resources/deutsch_jozsa_opened.png\" style=\"width:100%\">\n",
    "<figcaption align = \"middle\"> Figure 2. The Deutsch-Jozsa algorithm for the complex example, focusing on oracle implementation </figcaption>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd43e848-54d2-4be5-911d-1ea4d661bc5a",
   "metadata": {},
   "source": [
    "We can visualize the circuit obtained from the synthesis engine. Figure 2 presents the complex structure of the oracle, generated automatically by the synthesis engine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4a9a9c0f-dd72-4228-8840-fc4b0090de1f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:33:27.369359Z",
     "iopub.status.busy": "2024-05-07T14:33:27.368915Z",
     "iopub.status.idle": "2024-05-07T14:33:27.544315Z",
     "shell.execute_reply": "2024-05-07T14:33:27.543490Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/1b14df30-4d91-4a5f-9749-73741ccaca38?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9eb85d2e-87d0-4fb4-8bb7-a6d27afdd9cd",
   "metadata": {},
   "source": [
    "## Technical Notes\n",
    "\n",
    "A brief summary of the linear algebra behind the Deutsch-Jozsa algorithm. The first Hadamard transformation generates an equal superposition over all the standard basis elements:\n",
    "$$\n",
    "|0\\rangle_n \\xrightarrow[H^{\\otimes n}]{} \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n.\n",
    "$$\n",
    "The arithmetic oracle gets a Boolean function and adds an $e^{\\pi i}=-1$ phase to all states for which the function returns true:\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n \\xrightarrow[\\text{Oracle}(f(j))]{}\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\\rangle_n.\n",
    "$$\n",
    "Finally, applying the Hadamard transform, which can be written as $H^{\\otimes n}\\equiv \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{k,l=0}(-1)^{k\\cdot l} |k\\rangle \\langle l| $, gives\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\\rangle  \\xrightarrow[H^{\\otimes n}]{} \n",
    "\\sum^{2^n-1}_{k=0} \\left(\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)+j\\cdot k} \\right) |k\\rangle.\n",
    "$$\n",
    "\n",
    "The probability of getting the state $|k\\rangle = |0\\rangle$ is\n",
    "$$\n",
    "P(0)=\\left|\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)} \\right|^2 =\n",
    "\\left\\{\n",
    "\\begin{array}{l l}\n",
    "1 & \\text{if } f(x) \\text{ is constant} \\\\\n",
    "0 & \\text{if } f(x) \\text{ is balanced.}\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "141bcbd4-f2f7-4bf5-89f2-823b627eafa4",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a id='DJWiki'>[1]</a>: [Deutsch Jozsa (Wikipedia)](https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}