deutsch_jozsa_algo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "82dfbb33-94a0-4e59-bca0-46caad0e9f68",
   "metadata": {},
   "source": [
    "First let's do our imports:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "973b14f2-2e37-4d1a-af90-59c4dfc3645e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialization\n",
    "import numpy as np\n",
    "\n",
    "# importing Qiskit\n",
    "from qiskit import IBMQ, Aer\n",
    "from qiskit.providers.ibmq import least_busy\n",
    "from qiskit import QuantumCircuit, assemble, transpile\n",
    "\n",
    "# import basic plot tools\n",
    "from qiskit.visualization import plot_histogram"
   ]
  },
  {
   "cell_type": "raw",
   "id": "0bf5fc23-6cb0-4977-b9f8-e2c3fe6435c8",
   "metadata": {},
   "source": [
    "Next, we set the size of the input register for our oracle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d31e2ed-4163-46e1-a74a-a8f2d48291ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the length of the n-bit input string. \n",
    "n = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eafbb6f5-2e10-4549-89e0-e3356ec93eac",
   "metadata": {},
   "source": [
    "Let's start by creating a constant oracle, in this case the input has no effect on the output so we just randomly set the output qubit to be 0 or 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9a6974c-b875-4907-b1dc-0d253aaf27e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the length of the n-bit input string. \n",
    "n = 3\n",
    "\n",
    "const_oracle = QuantumCircuit(n+1)\n",
    "\n",
    "output = np.random.randint(2)\n",
    "if output == 1:\n",
    "    const_oracle.x(n)\n",
    "\n",
    "const_oracle.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42b2efd1-72d5-406c-9f8a-46940fc966b6",
   "metadata": {},
   "source": [
    "Next, let's implement a balanced oracle. We can create a balanced oracle by performing CNOTs with each input qubit as a control and the output bit as the target. We can vary the input states that give 0 or 1 by wrapping some of the controls in X-gates. Let's first choose a binary string of length n (b_str) that dictates which controls to wrap. For each qubit in our circuit, we place an X-gate if the corresponding digit in b_str is 1, or do nothing if the digit is 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f264e1c6-7e29-4140-bd8d-d3a47547afc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "balanced_oracle = QuantumCircuit(n+1)\n",
    "b_str = \"101\"\n",
    "\n",
    "# Place X-gates at inputs\n",
    "for qubit in range(len(b_str)):\n",
    "    if b_str[qubit] == '1':\n",
    "        balanced_oracle.x(qubit)\n",
    "\n",
    "# Use barrier as divider\n",
    "balanced_oracle.barrier()\n",
    "\n",
    "# Controlled-NOT gates\n",
    "for qubit in range(n):\n",
    "    balanced_oracle.cx(qubit, n)\n",
    "\n",
    "# Use barrier as divider\n",
    "balanced_oracle.barrier()\n",
    "\n",
    "# Place X-gates at outputs\n",
    "for qubit in range(len(b_str)):\n",
    "    if b_str[qubit] == '1':\n",
    "        balanced_oracle.x(qubit)\n",
    "\n",
    "balanced_oracle.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13da4b0b-0e83-430c-9a8e-24dc844cc92d",
   "metadata": {},
   "source": [
    "Now, let's put everything together. This first step in the algorithm is to initialize the input qubits in the state |+⟩ and the output qubit in the state |−⟩:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a82be21-0fcd-4d66-a101-687a755c9c47",
   "metadata": {},
   "outputs": [],
   "source": [
    "dj_circuit = QuantumCircuit(n+1, n)\n",
    "\n",
    "# Apply H-gates\n",
    "for qubit in range(n):\n",
    "    dj_circuit.h(qubit)\n",
    "\n",
    "# Put qubit in state |->\n",
    "dj_circuit.x(n)\n",
    "dj_circuit.h(n)\n",
    "dj_circuit.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4de956b1-560d-44b0-8a98-88a608ecf0d3",
   "metadata": {},
   "source": [
    "Then, we apply the oracle. Let's assume we have a balanced oracle: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a06df83-6fce-4045-8f5c-22a1515fc1be",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add oracle\n",
    "dj_circuit += balanced_oracle\n",
    "dj_circuit.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9164bb5f-a165-497a-b4c6-fe2d50224eba",
   "metadata": {},
   "source": [
    "Finally, we perform H-gates on the n-input qubits, and measure our input register:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9bc6c683-b2d2-4cd1-a761-24cd5b31e2a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Repeat H-gates\n",
    "for qubit in range(n):\n",
    "    dj_circuit.h(qubit)\n",
    "dj_circuit.barrier()\n",
    "\n",
    "# Measure\n",
    "for i in range(n):\n",
    "    dj_circuit.measure(i, i)\n",
    "\n",
    "# Display circuit\n",
    "dj_circuit.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60c3edaf-8c99-49f9-92d8-f1e0461efa9f",
   "metadata": {},
   "source": [
    "Let's see the output: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aad85fc0-8483-40f4-9a08-7ade5625a424",
   "metadata": {},
   "outputs": [],
   "source": [
    "# use account specific quantum computer\n",
    "provider = IBMQ.load_account()\n",
    "quantum_sys = provider.get_backend('ibmq_manila')\n",
    "qobj = assemble(dj_circuit, quantum_sys)\n",
    "\n",
    "# use a quantum simulator\n",
    "#quantum_sys = Aer.get_backend('aer_simulator')\n",
    "#qobj = assemble(dj_circuit, quantum_sys)\n",
    "#results = quantum_sys.run(qobj).result()\n",
    "#answer = results.get_counts()\n",
    "#plot_histogram(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "461f5baa-12dd-44a5-a86d-29a3e6ffcd0a",
   "metadata": {},
   "source": [
    "We can see from the results above that we have a 0% chance of measuring 000. This correctly predicts the function is balanced!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d78c3c5-d57a-4f94-ba6a-13964331c1b8",
   "metadata": {},
   "source": [
    "Below is a generalised function that creates Deutsch-Jozsa oracles and turns them into quantum gates. It takes the case, (either 'balanced' or 'constant', and n, the size of the input register:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5e0bd40-cbe0-41c1-ae0c-625d51c75317",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dj_oracle(case, n):\n",
    "    # We need to make a QuantumCircuit object to return\n",
    "    # This circuit has n+1 qubits: the size of the input,\n",
    "    # plus one output qubit\n",
    "    oracle_qc = QuantumCircuit(n+1)\n",
    "    \n",
    "    # First, let's deal with the case in which oracle is balanced\n",
    "    if case == \"balanced\":\n",
    "        # First generate a random number that tells us which CNOTs to\n",
    "        # wrap in X-gates:\n",
    "        b = np.random.randint(1,2**n)\n",
    "        # Next, format 'b' as a binary string of length 'n', padded with zeros:\n",
    "        b_str = format(b, '0'+str(n)+'b')\n",
    "        # Next, we place the first X-gates. Each digit in our binary string \n",
    "        # corresponds to a qubit, if the digit is 0, we do nothing, if it's 1\n",
    "        # we apply an X-gate to that qubit:\n",
    "        for qubit in range(len(b_str)):\n",
    "            if b_str[qubit] == '1':\n",
    "                oracle_qc.x(qubit)\n",
    "        # Do the controlled-NOT gates for each qubit, using the output qubit \n",
    "        # as the target:\n",
    "        for qubit in range(n):\n",
    "            oracle_qc.cx(qubit, n)\n",
    "        # Next, place the final X-gates\n",
    "        for qubit in range(len(b_str)):\n",
    "            if b_str[qubit] == '1':\n",
    "                oracle_qc.x(qubit)\n",
    "\n",
    "    # Case in which oracle is constant\n",
    "    if case == \"constant\":\n",
    "        # First decide what the fixed output of the oracle will be\n",
    "        # (either always 0 or always 1)\n",
    "        output = np.random.randint(2)\n",
    "        if output == 1:\n",
    "            oracle_qc.x(n)\n",
    "    \n",
    "    oracle_gate = oracle_qc.to_gate()\n",
    "    oracle_gate.name = \"Oracle\" # To show when we display the circuit\n",
    "    return oracle_gate"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb75edb1-46e3-4970-87e0-9e5c65811cd7",
   "metadata": {},
   "source": [
    "Let's also create a function that takes this oracle gate and performs the Deutsch-Jozsa algorithm on it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a372b8b-cc2a-4ba4-904c-30c055ea27d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dj_algorithm(oracle, n):\n",
    "    dj_circuit = QuantumCircuit(n+1, n)\n",
    "    # Set up the output qubit:\n",
    "    dj_circuit.x(n)\n",
    "    dj_circuit.h(n)\n",
    "    # And set up the input register:\n",
    "    for qubit in range(n):\n",
    "        dj_circuit.h(qubit)\n",
    "    # Let's append the oracle gate to our circuit:\n",
    "    dj_circuit.append(oracle, range(n+1))\n",
    "    # Finally, perform the H-gates again and measure:\n",
    "    for qubit in range(n):\n",
    "        dj_circuit.h(qubit)\n",
    "    \n",
    "    for i in range(n):\n",
    "        dj_circuit.measure(i, i)\n",
    "    \n",
    "    return dj_circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5afc80de-07d9-45f3-bd24-08c12b94fe45",
   "metadata": {},
   "source": [
    "Finally, let's use these functions to play around with the algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe329ec6-eab2-4e5a-93b8-677d15be28d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 4\n",
    "oracle_gate = dj_oracle('balanced', n)\n",
    "dj_circuit = dj_algorithm(oracle_gate, n)\n",
    "dj_circuit.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11ac5b8e-4148-48a9-b680-94fb32c24d2e",
   "metadata": {},
   "source": [
    "And see the results of running this circuit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8495fcf5-b43d-4cc6-b1d9-0a4b1a8441b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "transpiled_dj_circuit = transpile(dj_circuit, quantum_sys)\n",
    "qobj = assemble(transpiled_dj_circuit)\n",
    "results = quantum_sys.run(transpiled_dj_circuit).result()\n",
    "answer = results.get_counts()\n",
    "plot_histogram(answer)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Qiskit v0.35.0 (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.8.13"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}