challenge-2022.07-jul/challenge-2022.07-jul.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c4923aae",
   "metadata": {},
   "source": [
    "# Challenge: Palindrome Integer\n",
    "\n",
    "The purpose of this challenge is to generate an application for the analysis and design of quantum algorithms. For this case it is to prove that it is a palindrome, being the particular case in integers, for this it is considered that a [palindrome](https://en.wikipedia.org/wiki/Palindrome) integer is an integer x for which reverse(x) = x where reverse(x) is x with its digit reversed. Negative numbers are not palindrome.\n",
    "\n",
    "To get a clearer idea of this, consider the following two cases:\n",
    "\n",
    "\n",
    "#### Case 1:\n",
    "\n",
    "Consider the a integer number in the variable $p_1$, as $12588521$.\n",
    "    \n",
    "If you change the reverse order of the number, there is \n",
    "    \n",
    "                           \n",
    "$$ \\text{reverdsed}(p_1) = 12588521 .$$\n",
    "\n",
    "\n",
    "Rename as $p_1'$, it can be verified that\n",
    "\n",
    "$$p_1 = p_1',$$\n",
    "\n",
    "hence $p_1$ is a palindrome.\n",
    "\n",
    "\n",
    "#### Case 2:\n",
    "\n",
    "Consider the a integer number in the variable $p_2$, as 12583621.\n",
    "    \n",
    "If you change the reverse order of the number, there is \n",
    "    \n",
    "                           \n",
    "$$ \\text{reverdsed}(p_2) = 125638521 .$$\n",
    "\n",
    "\n",
    "Rename as $p_2'$, it can be verified that\n",
    "\n",
    "$$p_2 \\neq p_2',$$\n",
    "\n",
    "hence $p_2$ is a palindrome.\n",
    "\n",
    "\n",
    "## Classical Code\n",
    "\n",
    "Python has an accessible way to achieve this algorithm in a classic way, for this you must pass the integer value in a string or it can be in a list and use the instruction `[::-1]` after the string, that generates the action of putting the string in reverse and with an if condition that both are equal will show us if it is a palindrome or not. \n",
    "\n",
    "You can check the next code with the previous case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d5353568",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(A):\n",
    "        if(str(A)==str(A)[::-1]):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72df7987",
   "metadata": {},
   "source": [
    "Solution of case 1 using the classic algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b781e325",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(12588521)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bfaa80e",
   "metadata": {},
   "source": [
    "Solution of case 1 using the classic algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6c8b695a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(12583621)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a37573e9",
   "metadata": {},
   "source": [
    "#### new proposal\n",
    "\n",
    "Some changes are made to the algorithm such as considering that it is a list of numbers for each digit of the number. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b0352a98",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(A):\n",
    "        A = [int(x) for x in str(A)]\n",
    "        len_pa = len(A)\n",
    "        for i in range(int(len_pa/2)):\n",
    "            if A[i] != A[len_pa-i-1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1edff640",
   "metadata": {},
   "source": [
    "Case 1, with the new proposal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "9252f2f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(12588521)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2323b6e",
   "metadata": {},
   "source": [
    "Case 2, with the new proposal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "99b4fbc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(12583621)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "713c7f09",
   "metadata": {},
   "source": [
    "## Quantum Proposal\n",
    "\n",
    "\n",
    "For this challenge, the idea of the second proposal will be used and generated in a quantum circuit. And consider the previous inputs of both cases:  12588521, 12583621.\n",
    "\n",
    "**Now the case 1 must be [1,2,5,8,8,5,2,1];**\n",
    "\n",
    "**and case 2 must be [1,2,5,8,3,6,2,1]**\n",
    "\n",
    "\n",
    "For this purpose, different blocks will be considered, such as :\n",
    "\n",
    "- Generate a vector of positive integers, \n",
    "- Inverse of the vector,\n",
    "- Condition of being equal the number of two vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5345206",
   "metadata": {},
   "source": [
    "#### Generate a vector of  positive integers\n",
    "\n",
    "\n",
    "Encoding to classical to quantum consider the encoding basis, where classical $N$-bit string can be representated as a basis state of a $N$-qubit system. For example, if the classical binary strins  is 101 ,  the quantum state must be $|101\\rangle$. \n",
    "\n",
    "\n",
    "The case of storing the values in a vector can be represented in a QRAM( some references https://arxiv.org/pdf/0708.1879.pdf, https://github.com/qsharp-community/qram/blob/master/docs/primer.pdf), for this address qubits and information qubits are needed.\n",
    "\n",
    "From the following vector example [1,5,7,8], for the example is important to use n qubits for the length of the vector and m qubits for the length of the maximum bits representation. The lenght of the vector is 2 and is possible this can be representante in only 2 qubits, because $n^2$, where n is the number of qubits that is $2^2= 4$, therefore n = 2 qubits, for the address, so the state $|00\\rangle$ represents the index 1; the state $|01\\rangle$ represents the index 1; the state $|10\\rangle$ represents the index 2; and the state $11\\rangle$ represents the index 3. And m = 4, because the number bigger is 8 in the vector and in the binary representation is $|1000\\rangle$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9cf0176b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Method to generate the vector in a quantum circuit, \n",
    "the quantum circuit depends of a qubit addres value, can select a binary string representation\n",
    "in the encoding data.\n",
    "\n",
    "input_vector: Integer value or a list of positive integer values, example 12588521 or [1,2,5,8,8,5,2,1]\n",
    "\n",
    "return: a quantum circuit that has a set of qubit address and a set of qubit values. \n",
    "\"\"\"\n",
    "\n",
    "def qc_vector(input_vector):\n",
    "    \n",
    "    \n",
    "    \n",
    "    return #return quantum circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa6a2dbb",
   "metadata": {},
   "source": [
    "#### Inverse of the vector\n",
    "\n",
    "generates a way to represent from the same vector but starting in reversed order, using the previous example [8,7,5,1]. Tip you can use the `qc_vector()` method with previous modification.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6d89e95",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Method to generate the vector in a quantum circuit, \n",
    "the quantum circuit depends of a qubit addres value, can select a binary string representation\n",
    "in the encoding data.\n",
    "\n",
    "input_vector: Integer value or a list of positive integer values, example 12588521 or [1,2,5,8,8,5,2,1]\n",
    "\n",
    "return: a quantum circuit that has a set of qubit address and a set of qubit values in a reverser order. \n",
    "\"\"\"\n",
    "\n",
    "def qc_vector_reverse(input_vector):\n",
    "    \n",
    "    \n",
    "    return #return quantum circuit "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfb56200",
   "metadata": {},
   "source": [
    "#### Condition of being equal the number of two vectors\n",
    "\n",
    "Design an oracle when two values in a quantum circuit when are different or equals, depend of your choice, activate a flag qubit with a specific state $|0\\rangle$ or $|1\\rangle$.\n",
    "\n",
    "\n",
    "Example consider the states $|101\\rangle $  and $|110\\rangle $, and choice if activate if are equals or different."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57c85bca",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Method to generate an oracle for a  quantum circuit, \n",
    "using m+1 qubits, and return a 0 or 1 that neabs different or equals. \n",
    "\n",
    "qubit_num: Integer value that representate the values qubits for the qram + 1 , that is the flag qubit. \n",
    "\n",
    "return: a quantum circuit that has a set of qubit values + 1 with the flag qubit. \n",
    "\"\"\"\n",
    "\n",
    "def quantum_oracle(qubit_number):\n",
    "    \n",
    "    \n",
    "    return #return quantum circuit "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "165e625f",
   "metadata": {},
   "source": [
    "#### Palindrome integer in a quantum circuit \n",
    "\n",
    "\n",
    "Using as base the previous functions and/or some auxiliary ones that you consider to be of support and that it returns 0 or1 to represent that it is not or it is a palindrome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89e1ef9d",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Method to check if a positive integer value  is a palindrome or not.\n",
    "\n",
    "input value: Integer value.\n",
    "\n",
    "return: a boolean value that indicates is a palindrome or not the input_vector\n",
    "\"\"\"\n",
    "\n",
    "def quantum_isPalindrome(input_value):\n",
    "\n",
    "\n",
    "    return #return 0 or 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b410751c",
   "metadata": {},
   "source": [
    "### Check your quantum algorithm\n",
    "\n",
    "\n",
    "Consider the values of case 1 and case 2 for your proposal:\n",
    "\n",
    "- 12588521\n",
    "\n",
    "- 12583621"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b6cd2d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "quantum_isPalindrome(12588521)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe356b42",
   "metadata": {},
   "outputs": [],
   "source": [
    "quantum_isPalindrome(12583621)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fca5e02",
   "metadata": {},
   "source": [
    "If you are here is because you do it, congrats 🥳 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dce383fa",
   "metadata": {},
   "source": [
    "## References\n",
    "\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"
   ]
  }
 ],
 "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}