Bernstein-Vazirani.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fced567c",
   "metadata": {},
   "source": [
    "# Bernstein-Vazirani algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a9c1694",
   "metadata": {},
   "source": [
    "The Bernstein-Vazirani algorithm is closely related in principle to the Deutsch-Josza algorithm, (which is also explained in another notebook in this repository).\n",
    "\n",
    "We are given an \"oracle\" and promised that its output is \"0\" or \"1\" based on whether the bitwise product of the input state with a \"**hidden string**\" is **even** or **odd**. Our problem is to determine the \"hidden string\" encoded into the oracle.\n",
    "\n",
    "A classical computer, needs to check (at least) half the possible inputs to answer the question of what the hidden string is; a quantum computer needs **1** query of the oracle to determine the same answer deterministically."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4b7dc84f",
   "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",
    "# Not all cases necessarily are, but this is a stabilizer case.\n",
    "# (Note that exponential encoding overhead for the oracle would be problematic to complexity theory considerations.)\n",
    "oracle_qubits = [*range(100)]\n",
    "num_qubits = len(oracle_qubits) + 1\n",
    "hidden_bits = 1452"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3eeb0d1",
   "metadata": {},
   "source": [
    "You may change the `hidden_bits` above to be any value that can fit within the oracle register width. Your `hidden_bits` corresponds to the oracle below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9b41bb33",
   "metadata": {},
   "outputs": [],
   "source": [
    "def oracle(sim):\n",
    "    for i in oracle_qubits:\n",
    "        if ((hidden_bits >> i) & 1) > 0:\n",
    "            sim.mcx([i], num_qubits - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4262b07b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hidden string:  1452\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",
    "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",
    "# This measurement result is always the \"hidden_bits\" parameter of the oracle.\n",
    "result = 0\n",
    "for i in oracle_qubits:\n",
    "    result |= sim.m(i) << i\n",
    "print(\"Hidden string: \", result)"
   ]
  }
 ],
 "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
}