games/quantum_counterfeit_coin_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://raw.githubusercontent.com/Qiskit/qiskit-tutorials/master/images/qiskit-heading.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Quantum Counterfeit Coin Problem*_ \n",
    "\n",
    "The latest version of this notebook is available on https://github.com/qiskit/qiskit-tutorial.\n",
    "\n",
    "***\n",
    "### Contributors\n",
    "Rudy Raymond, Takashi Imamichi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "The counterfeit coin problem is a classic puzzle first proposed by E. D. Schell in the January 1945 edition of the *American Mathematical Monthly*:\n",
    "\n",
    ">You have eight similar coins and a beam balance. At most one coin is counterfeit and hence underweight. How can you detect whether there is an underweight coin, and if so, which one, using the balance only twice?\n",
    "\n",
    "The answer to the above puzzle is affirmative. What happens when we can use a quantum beam balance? \n",
    "\n",
    "Given a quantum beam balance and a counterfeit coin among $N$ coins, there is a quantum algorithm that can find the counterfeit coin by using the quantum balance only once (and independent of $N$, the number of coins!). On the other hand, any classical algorithm requires at least $\\Omega(\\log{N})$ uses of the beam balance. In general, for a given $k$ counterfeit coins of the same weight (but different from the majority of normal coins), there is [a quantum algorithm](https://arxiv.org/pdf/1009.0416.pdf) that queries the quantum beam balance for $O(k^{1/4})$ in contrast to any classical algorithm that requires $\\Omega(k\\log{(N/k)})$ queries to the beam balance. This is one of the wonders of quantum algorithms, in terms of query complexity that achieves quartic speed-up compared to its classical counterpart.\n",
    "\n",
    "## Quantum Procedure\n",
    "Hereafter we describe a step-by-step procedure to program the Quantum Counterfeit Coin Problem for $k=1$ counterfeit coin with the IBM Q Experience. [Terhal and Smolin](https://arxiv.org/pdf/quant-ph/9705041.pdf) were the first to show that it is possible to identify the false coin with a single query to the quantum beam balance.  \n",
    "\n",
    "### Preparing the environment\n",
    "First, we prepare the environment. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.931368Z",
     "start_time": "2018-09-26T16:51:57.520703Z"
    },
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# useful additional packages \n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "import numpy as np\n",
    "\n",
    "# useful math functions\n",
    "from math import pi, cos, acos, sqrt\n",
    "\n",
    "# importing Qiskit\n",
    "from qiskit import Aer, IBMQ, execute\n",
    "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister\n",
    "\n",
    "# import basic plot tools\n",
    "from qiskit.tools.visualization import plot_histogram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.937700Z",
     "start_time": "2018-09-26T16:51:58.932983Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qconfig loaded from /Users/alijavadi/Desktop/ajavadia-terra/Qconfig.py.\n"
     ]
    }
   ],
   "source": [
    "# Load saved IBMQ accounts\n",
    "IBMQ.load_account()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setting the number of coins and the index of false coin\n",
    "\n",
    "Next, we set the number of coins and the index of the counterfeit coin. The former determines the quantum superpositions used by the algorithm, while the latter determines the quantum beam balance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.942774Z",
     "start_time": "2018-09-26T16:51:58.939618Z"
    },
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "M = 16                   # Maximum number of physical qubits available\n",
    "numberOfCoins = 8        # This number should be up to M-1, where M is the number of qubits available\n",
    "indexOfFalseCoin = 6     # This should be 0, 1, ..., numberOfCoins - 1, where we use Python indexing\n",
    "\n",
    "if numberOfCoins < 4 or numberOfCoins >= M:\n",
    "    raise Exception(\"Please use numberOfCoins between 4 and \", M-1)\n",
    "if indexOfFalseCoin < 0 or indexOfFalseCoin >= numberOfCoins:\n",
    "    raise Exception(\"indexOfFalseCoin must be between 0 and \", numberOfCoins-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Querying the quantum beam balance\n",
    "\n",
    "As in a classical algorithm to find the false coin, we will use the balance by placing the same number of coins on the left and right pans of the beam. The difference is that in a quantum algorithm, we can query the beam balance in superposition. To query the quantum beam balance, we use a binary query string to encode coins placed on the pans; namely, the binary string `01101010` means to place coins whose indices are 1, 2, 4, and 6 on the pans, while the binary string `01110111` means to place all coins but those with indices 0 and 4 on the pans. Notice that we do not care how the selected coins are placed on the left and right pans, because their results are the same: it is balanced when no false coin is included, and tilted otherwise. \n",
    "\n",
    "In our example, because the number of coins is $8$ and the index of false coin is $3$, the query `01101010` will result in balanced (or, $0$), while the query `01110111` will result in tilted (or, $1$). Using two quantum registers to query the quantum balance, where the first register is for the query string and the second register for the result of the quantum balance, we can write the query to the quantum balance (omitting the normalization of the amplitudes): \n",
    "\n",
    "\\begin{eqnarray}\n",
    "|01101010\\rangle\\Big( |0\\rangle - |1\\rangle \\Big) &\\xrightarrow{\\mbox{Quantum Beam Balance}}& |01101010\\rangle\\Big( |0\\oplus 0\\rangle - |1 \\oplus 0\\rangle \\Big) = |01101010\\rangle\\Big( |0\\rangle - |1\\rangle \\Big)\\\\\n",
    "|01110111\\rangle\\Big( |0\\rangle - |1\\rangle \\Big) &\\xrightarrow{\\mbox{Quantum Beam Balance}}& |01110111\\rangle\\Big( |0 \\oplus 1\\rangle - |1 \\oplus 1\\rangle \\Big) = (-1) |01110111\\rangle\\Big( |0 \\rangle - |1 \\rangle \\Big)\n",
    "\\end{eqnarray}\n",
    "\n",
    "Notice that in the above equation, the phase is flipped if and only if the binary query string is $1$ at the index of the false coin. Let $x \\in \\left\\{0,1\\right\\}^N$ be the $N$-bit query string (that contains even number of $1$s), and let $e_k \\in \\left\\{0,1\\right\\}^N$ be the binary string which is $1$ at the index of the false coin and $0$ otherwise. Clearly, \n",
    "\n",
    "$$\n",
    "|x\\rangle\\Big(|0\\rangle - |1\\rangle \\Big) \\xrightarrow{\\mbox{Quantum Beam Balance}} \\left(-1\\right) ^{x\\cdot e_k} |x\\rangle\\Big(|0\\rangle - |1\\rangle \\Big), \n",
    "$$\n",
    "where $x\\cdot e_k$ denotes the inner product of $x$ and $e_k$. \n",
    "\n",
    "Here, we will prepare the superposition of all binary query strings with even number of $1$s. Namely, we want a circuit that produces the following transformation:\n",
    "\n",
    "$$\n",
    "|0\\rangle \\rightarrow \\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 0 \\mod 2} |x\\rangle,\n",
    "$$\n",
    "\n",
    "where $|x|$ denotes the Hamming weight of $x$.\n",
    "\n",
    "To obtain such superposition of states of even number of $1$s, we can perform Hadamard transformation on $|0\\rangle$ to obtain superposition of $\\sum_{x\\in\\left\\{0,1\\right\\}^N} |x\\rangle$, and check if the Hamming weight of $x$ is even. It can be shown that the Hamming weight of $x$ is even if and only if $x_1 \\oplus x_2 \\oplus \\ldots \\oplus x_N = 0$. Thus, we can transform:\n",
    "\n",
    "\\begin{equation}\n",
    "|0\\rangle|0\\rangle \\xrightarrow{H^{\\oplus N}} \\frac{1}{2^{N/2}}\\sum_x |x\\rangle |0\\rangle \\xrightarrow{\\mbox{XOR}(x)} \\frac{1}{2^{N/2}}\\sum_x |x\\rangle |0\\oplus x_1 \\oplus x_2 \\oplus \\ldots \\oplus x_N\\rangle \n",
    "\\end{equation}\n",
    "\n",
    "The right-hand side of the equation can be divided based on the result of the $\\mbox{XOR}(x) = x_1 \\oplus \\ldots \\oplus x_N$, namely, \n",
    "\n",
    "$$\n",
    "\\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 0 \\mod 2} |x\\rangle|0\\rangle + \\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 1 \\mod 2} |x\\rangle|1\\rangle.\n",
    "$$\n",
    "\n",
    "Thus, if we measure the second register and observe $|0\\rangle$, the first register is the superposition of all binary query strings we want. If we fail (observe $|1\\rangle$), we repeat the above procedure until we observe $|0\\rangle$. Each repetition is guaranteed to succeed with probability exactly half. Hence, after several repetitions we should be able to obtain the desired superposition state. *Notice that we can perform [quantum amplitude amplification](https://arxiv.org/abs/quant-ph/0005055) to obtain the desired superposition states with certainty and without measurement. The detail is left as an exercise*.\n",
    "\n",
    "Below is the procedure to obtain the desired superposition state with the classical `if` of the QuantumProgram. Here, when the second register is zero, we prepare it to record the answer to quantum beam balance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.949577Z",
     "start_time": "2018-09-26T16:51:58.944683Z"
    },
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Creating registers\n",
    "# numberOfCoins qubits for the binary query string and 1 qubit for working and recording the result of quantum balance\n",
    "qr = QuantumRegister(numberOfCoins+1)\n",
    "# for recording the measurement on qr\n",
    "cr = ClassicalRegister(numberOfCoins+1)\n",
    "\n",
    "circuitName = \"QueryStateCircuit\"\n",
    "queryStateCircuit = QuantumCircuit(qr, cr)\n",
    "\n",
    "N = numberOfCoins\n",
    "# Create uniform superposition of all strings of length N\n",
    "for i in range(N):\n",
    "    queryStateCircuit.h(qr[i])\n",
    "\n",
    "# Perform XOR(x) by applying CNOT gates sequentially from qr[0] to qr[N-1] and storing the result to qr[N]\n",
    "for i in range(N):\n",
    "    queryStateCircuit.cx(qr[i], qr[N])\n",
    "\n",
    "# Measure qr[N] and store the result to cr[N]. We continue if cr[N] is zero, or repeat otherwise\n",
    "queryStateCircuit.measure(qr[N], cr[N])\n",
    "\n",
    "# we proceed to query the quantum beam balance if the value of cr[0]...cr[N] is all zero\n",
    "# by preparing the Hadamard state of |1>, i.e., |0> - |1> at qr[N]\n",
    "queryStateCircuit.x(qr[N]).c_if(cr, 0)\n",
    "queryStateCircuit.h(qr[N]).c_if(cr, 0)\n",
    "\n",
    "# we rewind the computation when cr[N] is not zero\n",
    "for i in range(N):\n",
    "    queryStateCircuit.h(qr[i]).c_if(cr, 2**N)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Constructing the quantum beam balance\n",
    "\n",
    "The quantum beam balance returns $1$ when the binary query string contains the position of the false coin and $0$ otherwise, provided that the Hamming weight of the binary query string is even. Notice that previously, we constructed the superposition of all binary query strings whose Hamming weights are even. Let $k$ be the position of the false coin, then with regards to the binary query string $|x_1,x_2,\\ldots,x_N\\rangle|0\\rangle$, the quantum beam balance simply returns $|x_1,x_2,\\ldots,x_N\\rangle|0\\oplus x_k\\rangle$, that can be realized by a CNOT gate with $x_k$ as control and the second register as target. Namely, the quantum beam balance realizes\n",
    "\n",
    "$$\n",
    "|x_1,x_2,\\ldots,x_N\\rangle\\Big(|0\\rangle - |1\\rangle\\Big) \\xrightarrow{\\mbox{Quantum Beam Balance}} |x_1,x_2,\\ldots,x_N\\rangle\\Big(|0\\oplus x_k\\rangle - |1 \\oplus x_k\\rangle\\Big) = \\left(-1\\right)^{x\\cdot e_k} |x_1,x_2,\\ldots,x_N\\rangle\\Big(|0\\rangle - |1\\rangle\\Big)\n",
    "$$\n",
    "\n",
    "Below we apply the quantum beam balance on the desired superposition state. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.956692Z",
     "start_time": "2018-09-26T16:51:58.951205Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<qiskit.extensions.standard.cx.CnotGate at 0x119882470>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k = indexOfFalseCoin\n",
    "# Apply the quantum beam balance on the desired superposition state (marked by cr equal to zero)\n",
    "queryStateCircuit.cx(qr[k], qr[N]).c_if(cr, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Identifying the false coin\n",
    "\n",
    "In the above, we have queried the quantum beam balance once. How to identify the false coin after querying the balance? We simply perform a Hadamard transformation on the binary query string to identify the false coin. Notice that, under the assumption that we query the quantum beam balance with binary strings of even Hamming weight, the following equations hold.\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 0 \\mod 2} |x\\rangle &\\xrightarrow{\\mbox{Quantum Beam Balance}}& \\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 0 \\mod 2} \\left(-1\\right)^{x\\cdot e_k} |x\\rangle\\\\\n",
    "\\frac{1}{2^{(N-1)/2}}\\sum_{x\\in \\left\\{0,1\\right\\}^N~\\mbox{and}~|x|\\equiv 0 \\mod 2} \\left(-1\\right)^{x\\cdot e_k} |x\\rangle&\\xrightarrow{H^{\\otimes N}}&  \\frac{1}{\\sqrt{2}}\\Big(|e_k\\rangle+|\\hat{e_k}\\rangle\\Big)\n",
    "\\end{eqnarray}\n",
    "\n",
    "In the above, $e_k$ is the bitstring that is $1$ only at the position of the false coin, and $\\hat{e_k}$ is its inverse. Thus, by performing the measurement in the computational basis after the Hadamard transform, we should be able to identify the false coin because it is the one whose label is different from the majority: when $e_k$, the false coin is labelled $1$, and when $\\hat{e_k}$ the false coin is labelled $0$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:51:58.961517Z",
     "start_time": "2018-09-26T16:51:58.958216Z"
    },
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Apply Hadamard transform on qr[0] ... qr[N-1]\n",
    "for i in range(N):\n",
    "    queryStateCircuit.h(qr[i]).c_if(cr, 0)\n",
    "\n",
    "# Measure qr[0] ... qr[N-1]\n",
    "for i in range(N):\n",
    "    queryStateCircuit.measure(qr[i], cr[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we perform the experiment to see how we can identify the false coin by the above quantum circuit. Notice that when we use the `plot_histogram`, the numbering of the bits in the classical register is from right to left, namely, `0100` means the bit with index $2$ is one and the rest are zero. \n",
    "\n",
    "Because we use `cr[N]` to control the operation prior to and after the query to the quantum beam balance, we can detect that we succeed in identifying the false coin when the left-most bit is $0$. Otherwise, when the left-most bit is $1$, we fail to obtain the desired superposition of query bitstrings and must repeat from the beginning. *Notice that we have not queried the quantum beam oracle yet. This repetition is not neccesary when we feed the quantum beam balance with the superposition of all bitstrings of even Hamming weight, which can be done with probability one, thanks to the quantum amplitude amplification*. \n",
    "\n",
    "When the left-most bit is $0$, the index of the false coin can be determined by finding the one whose values are different from others. Namely, when $N=8$ and the index of the false coin is $3$, we should observe `011110111` or `000001000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-26T16:53:35.069745Z",
     "start_time": "2018-09-26T16:53:34.914672Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAE3CAYAAACw39aGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAGE5JREFUeJzt3Xu0X2V95/H3hwBaENBAuJiLQBOK\nCHRJj5SOVVFECNZQx2mHWEVQTGWV0qljHaettGg7reMMra1QjYgCjiKtt8wYLlpl0GKAIIpcRCKi\nSYgCGqCMIBe/88f+hf447JNzfsnvck54v9bKyt7Pfs75fc9akM959rOfZ6eqkCRpvO1GXYAkaXoy\nICRJrQwISVIrA0KS1MqAkCS1MiAkSa2GEhBJzktyV5IbJ7j+O0luSPKtJFcl+eVh1CVJmtiwRhAf\nBY7dzPXvAS+pqkOAdwPLh1GUJGli2w/jQ6rqyiT7bub6VV2nq4B5g65JkrR503EO4k3AJaMuQpKe\n6oYygpiqJC+lCYhf30yfZcAygJ133vlXDjzwwCFVJ0nbhuuuu+6eqpozWb9pExBJDgXOBRZX1Y8n\n6ldVy+nMUYyNjdXq1auHVKEkbRuSfH8q/abFLaYkC4BPA6+vqu+Muh5J0pBGEEk+ARwJ7JFkHfBn\nwA4AVfUB4Axgd+CcJACPVtXYMGqTJLUb1lNMSye5fgpwyjBqkSRNzbS4xSRJmn4MCElSKwNCktTK\ngJAktTIgJEmtDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiCkKXjjG9/InnvuycEH\nH9x6vao4/fTTWbhwIYceeihf//rXH792/vnns2jRIhYtWsT555//ePt1113HIYccwsKFCzn99NOp\nqoH/HFIvDAhpCk466SQuvfTSCa9fcskl3Hbbbdx2220sX76cU089FYCf/OQnnHnmmVx99dVcc801\nnHnmmWzcuBGAU089lQ996EOPf93mvr80CgaENAUvfvGLmT179oTXP/e5z3HiiSeShCOOOIJ7772X\nDRs2cNlll3H00Ucze/ZsnvWsZ3H00Udz6aWXsmHDBu6//36OOOIIknDiiSfy2c9+dog/kTQ5A0Lq\ng/Xr1zN//vzHz+fNm8f69es32z5v3rwntUvTiQEhSWplQEh9MHfuXNauXfv4+bp165g7d+5m29et\nW/ekdmk6MSCkPliyZAkXXHABVcWqVavYbbfd2GeffTjmmGO4/PLL2bhxIxs3buTyyy/nmGOOYZ99\n9mHXXXdl1apVVBUXXHABxx9//Kh/DOkJhvJOammmW7p0KVdccQX33HMP8+bN48wzz+SRRx4B4C1v\neQvHHXccK1euZOHChey000585CMfAWD27Nm8853v5AUveAEAZ5xxxuOT3eeccw4nnXQSDz74IIsX\nL2bx4sWj+eGkCWQmP3s9NjZWq1evHnUZkjSjJLmuqsYm6+ctJklSKwNCktTKgJAktTIgJEmtDAhJ\nUisDQpLUaigBkeS8JHcluXGC60nyd0nWJLkhyWHDqEuSNLFhjSA+Chy7meuLgUWdP8uAfxhCTZKk\nzRhKQFTVlcBPNtPleOCCaqwCnplkn2HUJklqN13mIOYCa7vO13XaJEkjMuP2YkqyjOY2FAsWLNji\n77PvOz7fr5Ikaeju+OtXDvwzpssIYj0wv+t8XqftSapqeVWNVdXYnDlzhlKcJD0VTZeAWAGc2Hma\n6QjgvqraMOqiJOmpbCi3mJJ8AjgS2CPJOuDPgB0AquoDwErgOGAN8FPg5GHUJUma2FACoqqWTnK9\ngN8bRi2SpKmZLreYJEnTjAEhSWplQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVgaEJKmVASFJ\namVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVgaEJKmVASFJ\namVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRWQwuIJMcmuTXJmiTvaLm+IMmXk1yf5IYkxw2r\nNknSkw0lIJLMAs4GFgMHAUuTHDSu258CF1fV84ETgHOGUZskqd2wRhCHA2uq6vaqehi4CDh+XJ8C\ndu0c7wbcOaTaJEkthhUQc4G1XefrOm3d/hx4XZJ1wErg99u+UZJlSVYnWX333XcPolZJEtNrknop\n8NGqmgccB1yY5En1VdXyqhqrqrE5c+YMvUhJeqoYVkCsB+Z3nc/rtHV7E3AxQFV9DXg6sMdQqpMk\nPcmUAyLJnCTP6BzPSnJykje0/Zbf4lpgUZL9kuxIMwm9YlyfHwBHdb7/c2kCwntIkjQivYwg/g+w\nqHP8l8DbgD8E/udkX1hVjwKnAZcBt9A8rXRTknclWdLp9p+BNyf5JvAJ4KSqqh7qkyT10fY99D0A\n+Ebn+HXAvwMeAG6iCYrNqqqVNJPP3W1ndB3fDLywh3okSQPUS0A8BuyY5ADgvqr6Qef20jMGU5ok\naZR6CYhLaCaRd6dZxwDNorfxk82SpG1ALwFxCvAG4BHgwk7bHjTrFyRJ25gpB0RV/QxY3rmttBew\noaquGFRhkqTR6uUx12cm+TjwELCm07YkyV8MqjhJ0uj08pjrB4D7gOcAD3favgb8x34XJUkavV7m\nII4Cnl1VjyQpgKq6O8megylNkjRKvYwg7mPc1hdJFgAb+lqRJGla6CUgzgU+leSlwHZJfg04n+bW\nkyRpG9PLLab3AA/SvPhnB+A84IPA+wZQlyRpxHp5zLVowsBAkKSngM0GRJIXV9WVneOXTdSvqr7U\n78IkSaM12QjiHODgzvGHJ+hTwP59q0iSNC1sNiCq6uCu4/0GX44kabroZSX15yZo/3T/ypEkTRe9\nPOb60gnaj+xDHZKkaWbSp5iSvKtzuGPX8Sb7A9/ve1WSpJGbymOu8zt/b9d1DM3k9Frc7luStkmT\nBkRVnQyQ5Kqq+tDgS5IkTQeTrYPYt6ru6Jz+c5LWx1mr6vZ+FyZJGq3JRhDfAnbpHK+hua2UcX0K\nmNXnuiRJIzbZOohduo57eeJJkjTD+Y++JKnVZHMQX6G5hbRZVfXivlUkSZoWJpuDOHcoVUiSpp3J\n5iDOH1YhkqTpZbJbTK+vqgs7x2+cqF9VndfvwiRJozXZLaalwIWd49dP0Kdo3i63WUmOpXnZ0Czg\n3Kr665Y+v02zMruAb1bVayf7vpKkwZjsFtNxXccTbdY3qSSzaF5VejSwDrg2yYqqurmrzyLgvwIv\nrKqNSfbc0s+TJG29Xt5JTZJnAq8Eng3cCXy+qu6dwpceDqzZtOI6yUXA8cDNXX3eDJxdVRsBququ\nXmqTJPVXL++DeBlwB3A68ALg94E7khw1hS+fS7Ox3ybrOm3dDgAOSPIvSVZ1bkm11bEsyeokq+++\n++6pli9J6lEvI4j3A8uq6uJNDUl+i+bW0YF9qmURzfsl5gFXJjlk/AilqpYDywHGxsYmXaMhSdoy\nvaykfjbwqXFtnwH2nsLXrueJW4XP67R1WwesqKpHqup7wHdoAkOSNAK9BMSFwO+NazsVuGAKX3st\nsCjJfkl2BE4AVozr81k6b6dLsgfNLSd3iZWkEellq43tgLckeTvNb/9zgb2AVZN9SFU9muQ04DKa\nx1zPq6qbOm+oW11VKzrXXpHkZuAx4I+q6sdb+HNJkrZSr1ttbPELg6pqJbByXNsZXccFvLXzR5I0\nYm61IUlq1es6iL1o1jTsQdeLg9xqQ5K2PVMOiCS/CXwMuA14HnATcDDwVaaw1YYkaWbp5SmmvwBO\nrqrnA/+v8/cy4LqBVCZJGqleAmJBVf3juLbzgRP7WI8kaZroJSDu6sxBQLPFxq8Bv0jz2KokaRvT\nS0B8CPj1zvHfAF8Gvgmc0++iJEmjN+VJ6qp6T9fxBUmuAHauqlsGUZgkabR6fcx1FnAE/7bd96Sr\nqCVJM1Mvj7keSrNf0tNpNtabBzyU5NVV9c0B1SdJGpFe5iDOo9nae25VHU6zF9P7cQ2EJG2TegmI\nA4C/7eyZtGnvpPfhltyStE3qJSBWAkvGtb0K+Hz/ypEkTReTbfd9If+23fcs4KIk19G8PnQ+8CvA\n5wZaoSRpJCabpF4z7vzGruObad7hIEnaBk223feZwypEkjS99LoO4kiavZfm0rxV7sKq+vIA6pIk\njdiUJ6mTnAJcDPwQ+DSwAfhEkjcPqDZJ0gj1MoJ4O3B096K4JJ8EPsVWvIpUkjQ99fKY6+40E9Pd\nbgVm968cSdJ00UtAfBU4K8lOAEl2Bt4LXDWIwiRJo9VLQLwFOBS4L8mPgHuBXwZ+dxCFSZJGa0pz\nEEkC/AJwFLA3nd1cq2rdAGuTJI3QlAKiqirJt4BdOqFgMEjSNq6XW0zX02zYJ0l6CujlMdcrgEuT\nfJRmL6ZNezRRVW75LUnbmF4C4oXA94CXjGsvfCeEJG1zJr3FlGSnJP8NeAC4Eji2ql7a9edlU/mg\nJMcmuTXJmiTv2Ey/1ySpJGNT/ikkSX03lTmIs2ne+3AL8Brgf/T6IZ13WZ8NLAYOApYmOail3y7A\nHwBX9/oZkqT+mkpAHAu8oqreTvMP/G9sweccDqypqtur6mHgIuD4ln7vBt4DPLQFnyFJ6qOpBMTO\nVbUBoKrWArttwefMpZnY3mRdp+1xSQ4D5leVb6iTpGlgKpPU2yd5KZAJzqmqL21NEUm2A84CTppC\n32XAMoAFCxZszcdKkjZjKgFxF098SunH484L2H+S77Ge5hWlm8zrtG2yC3AwcEWzaJu9gRVJllTV\n6u5vVFXLgeUAY2NjhSRpICYNiKratw+fcy2wKMl+NMFwAvDars+4D9hj03mSK4C3jQ8HSdLw9LKS\neotV1aPAaTTvsL4FuLiqbkryriRLhlGDJKk3Pb1ydGtU1Upg5bi2Myboe+QwapIkTWwoIwhJ0sxj\nQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVgaEJKmVASFJamVASJJaGRCSpFYGhCSplQEhSWpl\nQEiSWhkQkqRWBoQkqZUBIUlqZUBIkloZEJKkVgaEJKmVASFJamVASJJaGRCSpFYGhCSplQEhSWpl\nQEiSWhkQkqRWQwuIJMcmuTXJmiTvaLn+1iQ3J7khyT8nec6wapMkPdlQAiLJLOBsYDFwELA0yUHj\nul0PjFXVocA/Af99GLVJktoNawRxOLCmqm6vqoeBi4DjuztU1Zer6qed01XAvCHVJklqMayAmAus\n7Tpf12mbyJuASwZakSRps7YfdQHjJXkdMAa8ZILry4BlAAsWLBhiZZL01DKsEcR6YH7X+bxO2xMk\neTnwJ8CSqvpZ2zeqquVVNVZVY3PmzBlIsZKk4QXEtcCiJPsl2RE4AVjR3SHJ84EP0oTDXUOqS5I0\ngaEERFU9CpwGXAbcAlxcVTcleVeSJZ1u7wWeAfxjkm8kWTHBt5MkDcHQ5iCqaiWwclzbGV3HLx9W\nLZKkybmSWpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktTKgJAktTIgJEmt\nDAhJUisDQpLUyoCQJLUyICRJrQwISVIrA0KS1MqAkCS1MiAkSa0MCElSKwNCktTKgJAktTIgJEmt\nDAhJUisDQpLUyoCQJLUyICRJrQwISVKroQVEkmOT3JpkTZJ3tFx/WpJPdq5fnWTfYdUmSXqyoQRE\nklnA2cBi4CBgaZKDxnV7E7CxqhYCfwO8Zxi1SZLaDWsEcTiwpqpur6qHgYuA48f1OR44v3P8T8BR\nSTKk+iRJ42w/pM+ZC6ztOl8H/OpEfarq0ST3AbsD93R3SrIMWNY5fSDJrQOpWNp6ezDuv1+pX7J1\n91ieM5VOwwqIvqmq5cDyUdchTSbJ6qoaG3Ud0pYa1i2m9cD8rvN5nbbWPkm2B3YDfjyU6iRJTzKs\ngLgWWJRkvyQ7AicAK8b1WQG8oXP8H4AvVVUNqT5J0jhDucXUmVM4DbgMmAWcV1U3JXkXsLqqVgAf\nBi5Msgb4CU2ISDOZt0I1o8Vf0iVJbVxJLUlqZUBIkloZEJKkVgaEJKmVASGNgNvIaCYwIKQhSbJD\nkl0AXOOjmWDGbbUhzWCnAAck+QJwK7C+qh7adLGz6/HTquqnoypQ6uY6CGlIktwF3E2zEPRO4Grg\neuD2qvp+kjcCu1fVe0dYpvQ4RxDSECQ5BPgOzXtPdgReA7wSeDXwnSSXA38HnD6yIqVxHEFIQ5Bk\nDrAEuKaqvtXV/nLgWOAVwLyqmj2iEqUnMSCkEUgyq6oe6zo/F9itqn5rhGVJT+BTTNIQJNkxyeP/\nv20Kh87ENMBzgb8fRW3SRBxBSEPUWf+Qqvr5uPb5VbV2gi+TRsIRhDRASZ6Z5Pwkr0+yezV+3rm2\nfefvHapqrYvnNN0YENJgvRl4Fc1LsD6b5B+SHNcJhUc7fT6YZDcXz2m68RaTNEBJPkHzOt2LgecB\nhwO/1Ln8ReAZwAlVtf9oKpQm5joIaUA6r9ddCdxVVdcA1yS5DFgEHAYcAPwucNroqpQm5ghCGqDO\nU0rPqKr7Wq6NAdcAu1bVA0MvTpqEIwhpgDqPsz4eDpsmojvzDfsDVxoOmq4cQUgjkuRA4KdV9YNR\n1yK1MSCkAUiyBFhbVdePuhZpSxkQUp915h0e6Zx+G7gA+FhVrevqczJwbVXdOIISpSlxHYTUf68E\nVgH7AecCJwF3JLmys2Bue+DDwD6jK1GanAEh9d99wJeBh6vqrKo6kOaR1q8D7wEeBu6oqi+MsEZp\nUt5ikgYgyc7Ag0AB243bufUq4ItVdcao6pOmwoCQ+ixJxm+bsWmTvs7po8BBVfXtoRcn9cBbTFKf\nbQqH7s33Om2bNuo71nDQTOAIQuqTJHsALwK+UVXfG3dtu+4tvttGGdJ0Y0BIfZLkLOA3gS8A3wWu\nB26oqh91rm8PHAf8b8NBM4EBIfVJkuuArwL3AwfR3MK9k2YtxCXAKcBhVfWKkRUp9cC9mKQ+SLIP\nzYjhk1V1VZK9gSOBFwIvB8aA3wFeO7IipR45gpD6JMlewPZVtX5c+zzgVOD0qtplJMVJW8ARhNQn\nm+Ya4AmPtVZVrUtSNC8IkmYMA0Lqk84k9GOd904XzSK5TX4E/K/RVCZtGW8xSVspyQFV9Z2u89BM\nUP/cp5U0k7lQTtoKSfYEvp3km0n+KsmBnQHEY10L5l6SZOfuhXPSTGBASFtnKXAD8H7gecAlSb6a\n5D8lmd3p80ngWY4mNNN4i0naCkneBuwKnEUz53AgcBSwGNiL5pewR6rquSMrUtpCBoS0FZI8B9it\nqm7oatsB2BvYA/i/wFur6twRlShtMQNC6pPx+yslmUPz9NJuVfWvo6tM2jLOQUh90jLHsAfwZ4aD\nZipHENIWSLITsANw/0STz0m2o3lZ0KNDLU7qEwNC2gJJzgEW0Cx+uxq4s6oe6rr+NJpXjvo/mGYs\nA0LqUZJZwF3AKmAR8BhwBbACuLGq1iZZDtxdVX8yskKlreRWG1LvjgBuAU6pqg1JfgM4CVgO/DDJ\nCuANgNt6a0ZzBCH1qLPn0hE0t5Vu72rfFXgl8Oc0cw+LRlOh1B8GhLQVOttnPI1mk75HOm2fAn5Q\nVX840uKkreQtJqlHnQno/WmeYFoPPNRpnwXMollB/Uejq1DqD0cQUg+SLAPeDPwY2B14gGavpY9X\n1f2jrE3qNwNCmqIkYzRPKp0O/CvNaOEFNHsv/ZRmUdzVo6tQ6i8DQpqiJH8F7F1VJ3e1PY3mUddl\nwGHAq6vq7hGVKPWVW21IU/ct4KAkB29qqKqfVdWNwH8B7gdePqripH4zIKSp+xTwPeB9SV61qTHJ\ndlX1IPCLwCOjKk7qN28xSVPQCYGfd3Zo/VPgZOBhmjmJW4EXAXOr6vkjLFPqKwNC2gKdzfoWA78N\nPB24BLiiqr490sKkPjIgpB50dmilqn4+6lqkQXOhnDSJJH8L3AN8rKru6GrfYdPqaWlb5CS1tBlJ\n9qJZ93AS8N0kX0vypiTP6tpa4+NJXj3KOqVBMCCkzXsZ8AXgAOA5NNt6vxu4M8lnkiwBTgBuHFmF\n0oA4ByFtRpKFwK8CX6iqu7raj6AZVSwD/qWqXjSaCqXBMSCkSXQmpnfsfmNc17XVwEeq6uzhVyYN\nlgEhTSDJLwGnAHNobsfeDVwKfLGqKsnunbZdq+qB0VUqDYYBIU0gyS3AV4B7gfuAfWm2+b4DOKuq\nbkry9LaRhbQtMCCkFkmOAc6uqoWd81nAPjQb8v17YC5wclWtG12V0mD5FJPUbmfgR0nmA1TVY1W1\nrqpWAH8M/Bw4epQFSoNmQEjtPgP8EPj7JPt3X6iqO4Hv0ryXWtpmGRBSi2ruvf4xzW4D1yf5SpI/\nSHJIktOAJcBHRlqkNGDOQUiTSHIYcDzN3MM+wJeAS6vqvJEWJg2YASH1IMkv0KyJuG/UtUiDZkBI\nklo5ByFJamVASJJaGRCSpFYGhCSplQEhSWplQEiSWhkQkqRW/x9igRJhbF3rJgAAAABJRU5ErkJg\ngg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1199244e0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False coin index is:  6\n"
     ]
    }
   ],
   "source": [
    "backend = Aer.backends(\"qasm_simulator\")[0]\n",
    "shots = 1 # We perform a one-shot experiment\n",
    "success = 0 \n",
    "\n",
    "# Run until successful\n",
    "while not success:\n",
    "    results = execute(queryStateCircuit, backend=backend, shots=shots).result()\n",
    "    answer = results.get_counts()\n",
    "    for key, value in answer.items():\n",
    "        if key[0:1] != \"1\":\n",
    "            success = 1\n",
    "\n",
    "plot_histogram(answer)\n",
    "from collections import Counter\n",
    "for key in answer.keys():\n",
    "    normalFlag, _ = Counter(key[1:]).most_common(1)[0] #get most common label\n",
    "    for i in range(2,len(key)):\n",
    "        if key[i] != normalFlag:\n",
    "            print(\"False coin index is: \", len(key) - i - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## About Quantum Counterfeit Coin Problem\n",
    "\n",
    "The case when there is a single false coin, as presented in this notebook, is essentially [the Bernstein-Vazirani algorithm](http://epubs.siam.org/doi/abs/10.1137/S0097539796300921), and the single-query coin-weighing algorithm was first presented in 1997 by [Terhal and Smolin](https://arxiv.org/pdf/quant-ph/9705041.pdf). The Quantum Counterfeit Coin Problem for $k > 1$ in general is studied by [Iwama et al.](https://arxiv.org/pdf/1009.0416.pdf) Whether there exists a quantum algorithm that only needs $o(k^{1/4})$ queries to identify all the false coins remains an open question. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "keywords = {'Topics': ['Counterfeit coin problem'], 'Commands': ['`h`']}"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}