algorithms/deutsch_josza/deutsch_jozsa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d822b35c-f93f-4899-b7eb-2de8b8e43ad2",
   "metadata": {},
   "source": [
    "# Exponential speedup with the 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 fundamental and first quantum algorithms showing exponential speedup over their classical counterpart$^*$. While it has no practical applicative usage, it serves as a toy model for quantum computing, demonstrating how the concepts of super-position and interference enable quantum algorithms to overperform classical ones.\n",
    "\n",
    "$^*$ The exponential speedup is in the oracle complexity setting. In addition, it only refers to deterministic classical machines (see comment below)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf77d30a-7ca4-453c-9afd-ae7cc66c69b4",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "The algorithm treats the following problem:\n",
    "* Consider a black-box boolean function $f(x)$ that acts on the integers in the range $[0, 2^{n}-1]$.\n",
    "* It is guaranteed that the function is either constant or balanced (for half of the values it is 1 and for the other half it is 0).\n",
    "* The goal is to find, in a deterministic way, whether the function is constant or balanced.\n",
    "\n",
    "A brief mathematical explanation of the algorithm appears in Section 5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31b51fca-db54-4251-b96b-b26cdee134a3",
   "metadata": {},
   "source": [
    "## 1. Implementing the Deutsch-Jozsa algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12c83926-aa58-4030-be55-cc75e17766ff",
   "metadata": {},
   "source": [
    "Start with defining 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 is composed of three quantum blocks (see Figure 1): a Hadamard transform, an arithmetic oracle for the black-box function, and another Hadamard transform. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "91df521e-d0fb-4f3f-9d2d-badf11af9a32",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-03-12T12:52:14.761896Z",
     "iopub.status.busy": "2024-03-12T12:52:14.761389Z",
     "iopub.status.idle": "2024-03-12T12:52:18.296239Z",
     "shell.execute_reply": "2024-03-12T12:52:18.295292Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import (\n",
    "    H,\n",
    "    Output,\n",
    "    QBit,\n",
    "    QCallable,\n",
    "    QNum,\n",
    "    X,\n",
    "    allocate,\n",
    "    hadamard_transform,\n",
    "    qfunc,\n",
    "    within_apply,\n",
    "    write_qmod,\n",
    ")\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(compute=lambda: prep_minus(aux), action=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 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",
    "Define a classical function that gets the execution results from running 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-03-12T12:52:18.300448Z",
     "iopub.status.busy": "2024-03-12T12:52:18.299824Z",
     "iopub.status.idle": "2024-03-12T12:52:18.304663Z",
     "shell.execute_reply": "2024-03-12T12:52:18.303777Z"
    }
   },
   "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": [
    "## 2. Applying the algorithm on a simple oracle"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e7861d4-df77-4ef5-aa2a-bd9a3aa1a062",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Start with a simple example on $n=4$ qubits, and $f(x)= x >7$. Classicaly, 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": [
    "Build a predicate for the specific use case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "283141cf-08f1-482a-a742-e5ee56f9c0f1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-03-12T12:52:18.309433Z",
     "iopub.status.busy": "2024-03-12T12:52:18.308641Z",
     "iopub.status.idle": "2024-03-12T12:52:18.313655Z",
     "shell.execute_reply": "2024-03-12T12:52:18.312945Z"
    }
   },
   "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": [
    "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-03-12T12:52:18.316984Z",
     "iopub.status.busy": "2024-03-12T12:52:18.316577Z",
     "iopub.status.idle": "2024-03-12T12:52:20.978333Z",
     "shell.execute_reply": "2024-03-12T12:52:20.977486Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import create_model, show, synthesize\n",
    "\n",
    "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)\n",
    "qprog = synthesize(qmod)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee250190-ba84-4a08-a9fa-067ea448d2f6",
   "metadata": {},
   "source": [
    "Execute and call the classical post process:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6399ee7e-29c5-4442-9c6b-81dcf6817592",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-03-12T12:52:20.982441Z",
     "iopub.status.busy": "2024-03-12T12:52:20.981926Z",
     "iopub.status.idle": "2024-03-12T12:52:22.468013Z",
     "shell.execute_reply": "2024-03-12T12:52:22.467153Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The function is balanced\n"
     ]
    }
   ],
   "source": [
    "from classiq import execute\n",
    "\n",
    "results = execute(qprog).result()\n",
    "results_list = [sample.state[\"x\"] for sample in results[0].value.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-03-12T12:52:22.471832Z",
     "iopub.status.busy": "2024-03-12T12:52:22.471530Z",
     "iopub.status.idle": "2024-03-12T12:52:22.621369Z",
     "shell.execute_reply": "2024-03-12T12:52:22.620540Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/a60c066f-d366-4508-8ee6-531a8b13c164?version=0.38.0.dev42%2Bfd36e2c41c\n"
     ]
    }
   ],
   "source": [
    "write_qmod(qmod, \"simple_deutsch_jozsa\")\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ea0b055-e459-4e0a-a572-ba9fcfa7027d",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://classiq-docs-images.s3.amazonaws.com/deutsch_josza_closed.png\" style=\"width:100%\">\n",
    "<figcaption align = \"middle\"> Figure 1. The Deutsch-Jozsa algorithm </figcaption>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdbb09b9-966f-4753-bb19-827522116325",
   "metadata": {},
   "source": [
    "## 3. Applying the algorithm on a more complex oracle"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66e01d1f-0fb5-4a18-b44d-25b5cfe05bf2",
   "metadata": {},
   "source": [
    "Generalizing to more complex scenarios makes no difference for modeling. 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 provide a width bound to the Synthesis engine.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cd231fa-330b-460a-9f76-987d370b8952",
   "metadata": {},
   "source": [
    "Follow the three steps as before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "93045ada-8a49-44ad-8a41-b19938ef6c4c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-03-12T12:52:22.625427Z",
     "iopub.status.busy": "2024-03-12T12:52:22.625173Z",
     "iopub.status.idle": "2024-03-12T12:52:30.742074Z",
     "shell.execute_reply": "2024-03-12T12:52:30.741218Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The function is balanced\n"
     ]
    }
   ],
   "source": [
    "from classiq import Input, QArray, set_constraints\n",
    "from classiq.model import Constraints\n",
    "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)\n",
    "qmod = set_constraints(qmod, constraints=Constraints(max_width=19))\n",
    "qprog = synthesize(qmod)\n",
    "\n",
    "results = execute(qprog).result()\n",
    "results_list = [sample.state[\"x\"] for sample in results[0].value.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://classiq-docs-images.s3.amazonaws.com/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": [
    "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-03-12T12:52:30.746266Z",
     "iopub.status.busy": "2024-03-12T12:52:30.745818Z",
     "iopub.status.idle": "2024-03-12T12:52:30.914603Z",
     "shell.execute_reply": "2024-03-12T12:52:30.913854Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/f18bf944-ddd6-4477-9d6f-75b8832b12ca?version=0.38.0.dev42%2Bfd36e2c41c\n"
     ]
    }
   ],
   "source": [
    "show(qprog)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8f3ff458-7f41-47d7-924e-8929744e8af3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-03-12T12:52:30.918230Z",
     "iopub.status.busy": "2024-03-12T12:52:30.917804Z",
     "iopub.status.idle": "2024-03-12T12:52:30.937810Z",
     "shell.execute_reply": "2024-03-12T12:52:30.937074Z"
    }
   },
   "outputs": [],
   "source": [
    "write_qmod(qmod, \"complex_deutsch_jozsa\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9eb85d2e-87d0-4fb4-8bb7-a6d27afdd9cd",
   "metadata": {},
   "source": [
    "## 4. Mathematical explanation\n",
    "\n",
    "A brief summary of the linear algebra behind the Deutsch-Jozsa algorithm. The first Hadamard transformation generates an equal super-position 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",
    "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, application of 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": "e38d6052-ef88-4ba1-94a3-5ec847973462",
   "metadata": {},
   "source": [
    "## 5. Comments\n",
    "\n",
    "Without requiring deterministic determination, namely, allowing application of 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 $1-1/2^k$."
   ]
  },
  {
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}