Deutsch-Josza.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ce625809",
   "metadata": {},
   "source": [
    "# Deutsch-Josza algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52f40d4c",
   "metadata": {},
   "source": [
    "The Deutsch-Josza algorithm solves a \"toy problem\" meant to be technically more difficult for \"classical\" computers than for quantum computers.\n",
    "\n",
    "We are given an \"oracle\" and promised that its outputs are either **constant** or **balanced**. In other words, a **constant** oracle always returns \"0,\" or, alternatively, it always returns \"1.\" A **balanced** oracle returns \"0\" for exactly half of inputs and \"1\" for exactly the other half of inputs. Our problem is to determine whether any given oracle is **constant** or else **balanced**.\n",
    "\n",
    "A classical computer, on average, needs to check (about) half the possible inputs to answer the question of whether the oracle is constant or balanced; a quantum computer needs **1** query of the oracle to determine the same answer deterministically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4d82a325",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyqrack import QrackSimulator\n",
    "import os\n",
    "\n",
    "# Tell Qrack that it can use as many stabilizer qubits as it wants,\n",
    "# without worrying about converting to ket for GPU:\n",
    "os.environ['QRACK_MAX_CPU_QB']='-1'\n",
    "\n",
    "# All these example oracles happen to be stabilizer, so we can easily do more than hundreds of qubits.\n",
    "oracle_qubits = [*range(100)]\n",
    "num_qubits = len(oracle_qubits) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1276aa50",
   "metadata": {},
   "source": [
    "## Constant oracles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38d1323a",
   "metadata": {},
   "source": [
    "This example oracle always returns 0. (Therefore, it can do literally just **nothing**, to fulfill its role as oracle.) We determine that it is a **constant** oracle with just one query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b97d9d0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zero_oracle(sim):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3f95c0b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oracle is constant!\n"
     ]
    }
   ],
   "source": [
    "# Prepare the initial register state:\n",
    "sim = QrackSimulator(num_qubits, isOpenCL=False)\n",
    "sim.x(num_qubits - 1)\n",
    "for i in range(num_qubits):\n",
    "    sim.h(i)\n",
    "\n",
    "# Make exactly one query to the oracle:\n",
    "zero_oracle(sim)\n",
    "\n",
    "# Finish the unitary portion of the algorithm, with the result from the oracle:\n",
    "for i in oracle_qubits:\n",
    "    sim.h(i)\n",
    "\n",
    "# Always, a constant oracle measurement result will be \"0\";\n",
    "# always, a balanced oracle measurement result will be anything besides \"0\":\n",
    "result = 0\n",
    "for i in oracle_qubits:\n",
    "    result |= sim.m(i) << i\n",
    "if result == 0:\n",
    "    print(\"Oracle is constant!\")\n",
    "else:\n",
    "    print(\"Oracle is balanced!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be5c727a",
   "metadata": {},
   "source": [
    "This example oracle always returns 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d2d56652",
   "metadata": {},
   "outputs": [],
   "source": [
    "def one_oracle(sim):\n",
    "    sim.x(num_qubits - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d54694a9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oracle is constant!\n"
     ]
    }
   ],
   "source": [
    "# Prepare the initial register state:\n",
    "sim = QrackSimulator(num_qubits, isOpenCL=False)\n",
    "sim.x(num_qubits - 1)\n",
    "for i in range(num_qubits):\n",
    "    sim.h(i)\n",
    "\n",
    "# Make exactly one query to the oracle:\n",
    "one_oracle(sim)\n",
    "\n",
    "# Finish the unitary portion of the algorithm, with the result from the oracle:\n",
    "for i in oracle_qubits:\n",
    "    sim.h(i)\n",
    "\n",
    "# Always, a constant oracle measurement result will be \"0\";\n",
    "# always, a balanced oracle measurement result will be anything besides \"0\":\n",
    "result = 0\n",
    "for i in oracle_qubits:\n",
    "    result |= sim.m(i) << i\n",
    "if result == 0:\n",
    "    print(\"Oracle is constant!\")\n",
    "else:\n",
    "    print(\"Oracle is balanced!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3c5ad6a",
   "metadata": {},
   "source": [
    "## Balanced oracles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87116351",
   "metadata": {},
   "source": [
    "This is an example of a balanced oracle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e18a2546",
   "metadata": {},
   "outputs": [],
   "source": [
    "def balanced_oracle(sim):\n",
    "    for i in oracle_qubits:\n",
    "        sim.mcx([i], num_qubits - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fc23bcbd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oracle is balanced!\n"
     ]
    }
   ],
   "source": [
    "# Prepare the initial register state:\n",
    "sim = QrackSimulator(num_qubits, isOpenCL=False)\n",
    "sim.x(num_qubits - 1)\n",
    "for i in range(num_qubits):\n",
    "    sim.h(i)\n",
    "\n",
    "# Make exactly one query to the oracle:\n",
    "balanced_oracle(sim)\n",
    "\n",
    "# Finish the unitary portion of the algorithm, with the result from the oracle:\n",
    "for i in oracle_qubits:\n",
    "    sim.h(i)\n",
    "\n",
    "# Always, a constant oracle measurement result will be \"0\";\n",
    "# always, a balanced oracle measurement result will be anything besides \"0\":\n",
    "result = 0\n",
    "for i in oracle_qubits:\n",
    "    result |= sim.m(i) << i\n",
    "if result == 0:\n",
    "    print(\"Oracle is constant!\")\n",
    "else:\n",
    "    print(\"Oracle is balanced!\")"
   ]
  }
 ],
 "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.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}