challenge-2020.12-dec/challenge-2020.12-dec.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 02: Minimum Hamming Distance using a Quantum Algorithm\n",
    "\n",
    "The Hamming distance between two binary strings (with the same number of bits) is defined as the number positions where the bits differ from each other. For example, the Hamming distance between these $6$-bit strings <span style=\"color:red\">$0$</span>$01$<span style=\"color:red\">$0$</span>$0$<span style=\"color:red\">$1$</span> and <span style=\"color:red\">$1$</span>$01$<span style=\"color:red\">$1$</span>$0$<span style=\"color:red\">$0$</span> is $3$.\n",
    "\n",
    "A simple way to calculate the Hamming distance between two numbers is to perform a bitwise XOR between them, and count the number of ones in the resulting string:\n",
    "\n",
    "$$ 001001 \\oplus 101100 = 100101 \\xrightarrow[]{\\; \\text{count ones} \\;} 011 \\text{ (3 in base-2)} $$\n",
    "\n",
    "The purpose of this challenge is to develop a quantum algorithm that takes as an input an arbitrary number $m$ of $n$-bit strings, and outputs the two strings with the minimum Hamming distance between them with a resonably high probability. How high? the higher the better.\n",
    "\n",
    "For instance, for the following input of four 4-bit strings: $[0000,1001,1100,1101]$ the algorithm should return strings $[1100,1101]$ since they only differ by one bit.\n",
    "\n",
    "**Level 1:** Start by only considering the cases in which the answer is unique. In other words, assume that all inputs only have one pair of strings that gives the minimum Hamming distance. So inputs such as $[0000,0001,0010,0111]$ don't have to be considered because there are two solutions: $[0000,0001]$ and $[0000,0010]$.\n",
    "\n",
    "**Level 2:** Now consider the case where more than one solution can exist and make sure the algorithm returns each of the possible solutions with equal probability. So, for the example above, the probability of measuring $[0000,0001]$ or $[0000,0010]$ should be close to $50\\%$ (inputs with repeated strings should also be considered).\n",
    "\n",
    "**Hint:** Consider looking into some of the \"textbook\" quantum algorithms (like Deutch-Jozsa (DJ) [1], Bernstein-Vazirani (BV) [2], Grover [3], etc.) to see if this problem can be solved with variations of these. Take for instance this pre-print [4], where a modified version of DJ was used to compute Hamming distances between two strings. Now, keep in mind that in that approach, Hamming weights were calculated using probability distributions (which require multiple runs of the algorithm), and not by amplifying states, as required by this challenge.\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.\n",
    "\n",
    "[2] Bernstein, Ethan, and Umesh Vazirani. \"Quantum complexity theory.\" SIAM Journal on computing 26.5 (1997): 1411-1473.\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](https://arxiv.org/abs/quant-ph/9605043)\n",
    "\n",
    "[4] Bravo, José Manuel. \"Calculating Hamming distance with the IBM Q Experience.\" Preprints (2018)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}