{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![(book cover)](https://covers.oreillystatic.com/images/0636920167433/cat.gif \"(book cover)\")\n",
    "# Programming Quantum Computers by O'Reilly Media -  [book info](http://shop.oreilly.com/product/0636920167433.do)  - [all code samples](https://oreilly-qc.github.io)\n",
    "\n",
    "## Code samples for Chapter 14\n",
    "These code samples were written by Mariia Mykhailova."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deutsch-Jozsa Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"ApplyConstantFunctionOracle\",\"ApplyBalancedFunctionOracle\",\"IsConstantFunction\",\"RunDeutschJozsaAlgorithm\"]",
      "text/html": [
       "<ul><li>ApplyConstantFunctionOracle</li><li>ApplyBalancedFunctionOracle</li><li>IsConstantFunction</li><li>RunDeutschJozsaAlgorithm</li></ul>"
      ],
      "text/plain": [
       "ApplyConstantFunctionOracle, ApplyBalancedFunctionOracle, IsConstantFunction, RunDeutschJozsaAlgorithm"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Deutsch-Jozsa algorithm\n",
    "\n",
    "operation ApplyConstantFunctionOracle (x : Qubit[]) : Unit {\n",
    "    // Do nothing... (or add a global phase of -1, which is effectively the same)\n",
    "}\n",
    "\n",
    "\n",
    "operation ApplyBalancedFunctionOracle (x : Qubit[]) : Unit {\n",
    "    // f(x) = 1 if qubit x[0] is equal to 1\n",
    "    Z(x[0]);\n",
    "}\n",
    "\n",
    "\n",
    "// Operation that implements Deutsch-Jozsa algorithm\n",
    "operation IsConstantFunction (N : Int, oracle : (Qubit[] => Unit)) : Bool {\n",
    "    mutable isConstant = true;\n",
    "\n",
    "    // Allocate an array of N qubits for the input register x.\n",
    "    use x = Qubit[N];\n",
    "    // Newly allocated qubits start in the |0⟩ state.\n",
    "    // The first step is to prepare the qubits in the required state before calling the oracle.\n",
    "    ApplyToEach(H, x);\n",
    "\n",
    "    // Apply the oracle to the input register.\n",
    "    oracle(x);\n",
    "\n",
    "    // Apply a Hadamard gate to each qubit of the input register again.\n",
    "    ApplyToEach(H, x);\n",
    "\n",
    "    // Measure each qubit of the input register in the computational basis using the M operation.\n",
    "    for q in x {\n",
    "        if (M(q) == One) {\n",
    "            set isConstant = false;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return isConstant;\n",
    "}\n",
    "\n",
    "\n",
    "operation RunDeutschJozsaAlgorithm () : Unit {\n",
    "    for (oracle, fStr) in [(ApplyConstantFunctionOracle, \"f(x) = 0\"), \n",
    "                           (ApplyBalancedFunctionOracle, \"f(x) = x[0]\")] {\n",
    "        let verdict = IsConstantFunction(2, oracle);\n",
    "        Message($\"Function {fStr} identified as {verdict ? \"constant\" | \"balanced\"}\");\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Function f(x) = 0 identified as constant\n",
      "Function f(x) = x[0] identified as balanced\n"
     ]
    },
    {
     "data": {
      "application/json": "{\"@type\":\"tuple\"}",
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate RunDeutschJozsaAlgorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bernstein-Vazirani Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"ApplyProductOracle\",\"RecoveredVector\",\"RunBernsteinVaziraniAlgorithm\"]",
      "text/html": [
       "<ul><li>ApplyProductOracle</li><li>RecoveredVector</li><li>RunBernsteinVaziraniAlgorithm</li></ul>"
      ],
      "text/plain": [
       "ApplyProductOracle, RecoveredVector, RunBernsteinVaziraniAlgorithm"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Bernstein-Vazirani algorithm\n",
    "\n",
    "operation ApplyProductOracle (x : Qubit[], r : Int[]) : Unit {\n",
    "    // f(x) = Σᵢ rᵢ xᵢ modulo 2 for a given bit vector r (scalar product function)\n",
    "    for i in 0 .. Length(x) - 1 {\n",
    "        if (r[i] == 1) {\n",
    "            Z(x[i]);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// Operation that implements Bernstein-Vazirani algorithm\n",
    "operation RecoveredVector (N : Int, oracle : (Qubit[] => Unit)) : Int[] {\n",
    "    mutable r = new Int[N];\n",
    "\n",
    "    // Allocate an array of N qubits for the input register x.\n",
    "    use x = Qubit[N];\n",
    "    // Newly allocated qubits start in the |0⟩ state.\n",
    "    // The first step is to prepare the qubits in the required state before calling the oracle.\n",
    "    ApplyToEach(H, x);\n",
    "\n",
    "    // Apply the oracle to the input register.\n",
    "    oracle(x);\n",
    "\n",
    "    // Apply a Hadamard gate to each qubit of the input register again.\n",
    "    ApplyToEach(H, x);\n",
    "\n",
    "    // Measure each qubit of the input register in the computational basis using the M operation.\n",
    "    for i in 0 .. Length(x) - 1 {\n",
    "        set r w/= i <- M(x[i]) == One ? 1 | 0;\n",
    "    }\n",
    "\n",
    "    return r;\n",
    "}\n",
    "\n",
    "\n",
    "operation RunBernsteinVaziraniAlgorithm () : Unit {\n",
    "    for r in [[0, 0], [1, 0], [0, 1], [1, 1]] {\n",
    "        let oracle = ApplyProductOracle(_, r);\n",
    "        let recoveredR = RecoveredVector(2, oracle);\n",
    "        Message($\"Bit vector {r} recovered as {recoveredR}\");\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bit vector [0,0] recovered as [0,0]\n",
      "Bit vector [1,0] recovered as [1,0]\n",
      "Bit vector [0,1] recovered as [0,1]\n",
      "Bit vector [1,1] recovered as [1,1]\n"
     ]
    },
    {
     "data": {
      "application/json": "{\"@type\":\"tuple\"}",
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate RunBernsteinVaziraniAlgorithm"
   ]
  }
 ],
 "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
}