challenge-2022.04-apr/challenge-2022.04-apr.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "146fce69",
   "metadata": {},
   "source": [
    "# Challenge:Finding the way out of the maze\n",
    "\n",
    "For this challenge we have the following situation. There is a maze that can be divided into cells of a 4x4 matrix, and the goal is known to be at the other end of the input cell. Furthermore, it can only be moved vertically or horizontally to change cells, these cells can be interpreted as a qubit, and this can be seen in figure 1. \n",
    "\n",
    "![design_challenge_april_0.png](images/design_challenge_april_0.png)\n",
    "<center>Figure 1. Maze starting board.</center>\n",
    "\n",
    "The approach to the problem always starts in the qubit $q_0$ and the goal is the qubit $q_{15}$, we must arrive with the least number of steps, you must also consider that this maze can change according to certain probability, ie, there are certain cells that may be occupied and therefore are not valid cells to access, these are represented with the colour grey.\n",
    "\n",
    "## Part 1: Finding the path \n",
    "\n",
    "Following the diagram in figure 2, design and programming an quantum algorithm to find the shortest paths following the idea that some cells may or not be available, depending on the probability indicated in the figure.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4e065fca",
   "metadata": {},
   "source": [
    "![design_challenge_april_1.png](images/design_challenge_april_1.png)\n",
    "<center>Figure 2. Maze considering overlapping cells.</center>\n",
    "\n",
    "<div class=\"alert alert-block alert-info\"><b> Considerations </b> \n",
    "\n",
    "For the quantum algorithm considered the white cells with the state $\\vert 1 \\rangle$ and the grey cells with the state $\\vert 0 \\rangle$, and it should return a vector, a dict or a probability histogram, where the binary string indicates the shortest paths with the highest probability.  </div> "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "84831b12",
   "metadata": {},
   "outputs": [],
   "source": [
    "## exmaple that you need to consider for the part 1\n",
    "\n",
    "##### CODE HERE ######\n",
    "def solution_part1():\n",
    "    \"\"\"\n",
    "    Args: you can consider any parameters you want,\n",
    "    for example the number of qubits, the number of superpositions cells, \n",
    "    the overlap, among others.\n",
    "    \"\"\"\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \"\"\"\n",
    "    return vector or dict, or a histogram with the bitstring \n",
    "     with more probabilities\n",
    "    example: '1111000100010001':501,'1110001000100011':523\"\"\"\n",
    "    return \n",
    "##### CODE HERE ######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1fcb94e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "## if you added parameters indicate them here\n",
    "s1 = solution_part1() \n",
    "#print the solution#\n",
    "s1"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "53c42e98",
   "metadata": {},
   "source": [
    "\n",
    "## Part 2: Finding the path with 12  cells\n",
    "This second part requires using the same quantum algorithm, and adding the conditions where cells $q_2$,$q_3$,$q_{12}$ and $q_{13}$ are not available.This can be seen in figure 3\n",
    "\n",
    "\n",
    "![design_challenge_april_2.png](images/design_challenge_april_2.png)\n",
    "<center>Figure 3. Maze considering  only 12 cells, where 8 has a superposition.</center>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22c13c3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "## exmaple that you need to consider for the part 2\n",
    "## you can use the code for solution_part1 and only add the changes\n",
    "\n",
    "##### CODE HERE ######\n",
    "def solution_part2():\n",
    "    \"\"\"\n",
    "    Args: you can consider any parameters you want,\n",
    "    for example the number of qubits, the number of superpositions cells, \n",
    "    the overlap, among others.\n",
    "    \"\"\"\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \"\"\"\n",
    "    return vector or dict, or a histogram with the bitstring \n",
    "     with more probabilities\n",
    "    example: '1000100011100011':498,''1111000100010001'':526\"\"\"\n",
    "    return \n",
    "##### CODE HERE ######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b06a3232",
   "metadata": {},
   "outputs": [],
   "source": [
    "## if you added parameters indicate them here\n",
    "s2 = solution_part2() \n",
    "#print the solution#\n",
    "s2"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "08434e06",
   "metadata": {},
   "source": [
    "## Part 3: Finding the path with different probabilities\n",
    "\n",
    "In this part you have the change that not all cells have an equiprobable probability, try to find if the probability stays the same as in part 1 or differs, for these changes consider figure 4.\n",
    "\n",
    "![design_challenge_april_3.png](images/design_challenge_april_3.png)\n",
    "<center>Figure 4. Maze considering  8 cells with superposition with a different probabilities.</center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0afb7e15",
   "metadata": {},
   "outputs": [],
   "source": [
    "## exmaple that you need to consider for the part 3\n",
    "## you can use the code for solution_part1 and only add the changes\n",
    "\n",
    "##### CODE HERE ######\n",
    "def solution_part3():\n",
    "    \"\"\"\n",
    "    Args: you can consider any parameters you want,\n",
    "    for example the number of qubits, the number of superpositions cells, \n",
    "    the overlap, among others.\n",
    "    \"\"\"\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \"\"\"\n",
    "    return vector or dict, or a histogram with the bitstring \n",
    "     with more probabilities\n",
    "    example: '1000100010001111':530,''1111000100010001'':494\"\"\"\n",
    "    return \n",
    "##### CODE HERE ######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36af93fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "## if you added parameters indicate them here\n",
    "s3 = solution_part3() \n",
    "#print the solution#\n",
    "s3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d51b59e5",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
    "[1] Deutsch, David, and Richard Jozsa. \"Rapid solution of problems by quantum computation.\" Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439.1907 (1992): 553-558., https://www.isical.ac.in/~rcbose/internship/lectures2016/rt08deutschjozsa.pdf\n",
    "\n",
    "[2] Bernstein, Ethan, and Umesh Vazirani. \"Quantum complexity theory.\" SIAM Journal on computing 26.5 (1997): 1411-1473.https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.655.1186&rep=rep1&type=pdf\n",
    "\n",
    "[3] Grover, Lov K. , \"A fast quantum mechanical algorithm for database search\", Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (1996), arXiv:quant-ph/9605043\n",
    "\n",
    "[4] Stuart Andrew Hadfield,\"Quantum Algorithms for Scientific Computing and Approximate Optimization\", (2018), https://arxiv.org/pdf/1805.03265.pdf"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}