{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "import cirq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Add the specified number of input and output qubits.\"\"\"\n",
    "def set_io_qubits(qubit_count):\n",
    "  input_qubits = [cirq.GridQubit(i, 0) for i in range(qubit_count)]\n",
    "  output_qubit = cirq.GridQubit(qubit_count, 0)\n",
    "  return (input_qubits, output_qubit)\n",
    "\n",
    "\"\"\"For post-processing measurement outcomes.\"\"\"\n",
    "def bitstring(bits):\n",
    "  return ''.join(str(int(b)) for b in bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implement the Grover circuit.\n",
    "In the below code, two parts of the Grover circuit as missing.\n",
    "\n",
    "First, implement the bit-flip oracle that flips the output_qubit if and only if the input_qubits are in the state |11...1>.\n",
    "For this note that you can control a single qubit gate on multiple qubits using the function cirq.ControlledGate(gate to be controlled, control_qubits).on(target_qubit)\n",
    "\n",
    "Afterwards, implement the R gate which maps |00...0> to -|00...0> and does nothing on all other basis states |j>.\n",
    "This one is a bit harder, first think about how to decompose this gate yourself. If you do not manage to find a decomposition, please raise your hand and I will give you a hint!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Create circuit that implements Grover search for bitstring 11...1\"\"\"\n",
    "def make_grover_circuit(input_qubits, output_qubit, n_grover_iterates):\n",
    "    \n",
    "  # Initialize circuit and qubits.\n",
    "  c = cirq.Circuit()  \n",
    "  c.append([\n",
    "      # Turning flip-oracle into phase-oracle\n",
    "      cirq.X(output_qubit),\n",
    "      cirq.H(output_qubit),\n",
    "      # Appending first layer of Hadamard.\n",
    "      cirq.H.on_each(*input_qubits),\n",
    "  ])\n",
    "  \n",
    "  # Applying the Grover iterate the specified number of times.\n",
    "  for i in range(n_grover_iterates):  \n",
    "    # Query oracle.\n",
    "    # TODO: Implement oracle for the single marked bitstring 11...1\n",
    "\n",
    "    # Applying H gate on all qubits.\n",
    "    c.append(cirq.H.on_each(*input_qubits))\n",
    "\n",
    "    # The R operator.\n",
    "    # TODO: Implement the R operator.\n",
    "\n",
    "    # Applying H gate on all qubits.\n",
    "    c.append(cirq.H.on_each(*input_qubits))\n",
    "\n",
    "  # Measure the result.\n",
    "  c.append(cirq.measure(*input_qubits, key='result'))\n",
    "\n",
    "  return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test():\n",
    "  qubit_count = 6\n",
    "  circuit_sample_count = 100\n",
    "\n",
    "  # Set up input and output qubits.\n",
    "  (input_qubits, output_qubit) = set_io_qubits(qubit_count)\n",
    "\n",
    "  # Choose the x' and make an oracle which can recognize it.\n",
    "  marked_bitstring = [1 for i in range(qubit_count)]\n",
    "  print('Secret bit sequence: {}'.format(marked_bitstring))\n",
    "  \n",
    "  # Embed the oracle into a quantum circuit implementing Grover's algorithm.\n",
    "  n_grover_iterates = int((np.pi/4) * np.sqrt(2 ** qubit_count))\n",
    "  circuit = make_grover_circuit(input_qubits, output_qubit, n_grover_iterates)\n",
    "  \n",
    "  # Print the circuit.\n",
    "  print('Circuit:')\n",
    "  print(circuit)\n",
    "\n",
    "  # Sample from the circuit a couple times.\n",
    "  simulator = cirq.Simulator()\n",
    "  result = simulator.run(circuit, repetitions=circuit_sample_count)\n",
    "\n",
    "  # Collect frequences.\n",
    "  frequencies = result.histogram(key='result', fold_func=bitstring)\n",
    "  print('Sampled results:\\n{}'.format(frequencies))\n",
    "\n",
    "  # Check if we actually found the secret value.\n",
    "  most_common_bitstring = frequencies.most_common(1)[0][0]\n",
    "  print('Most common bitstring: {}'.format(most_common_bitstring))\n",
    "  print('Found a match: {}'.format(\n",
    "        most_common_bitstring == bitstring(marked_bitstring)))\n",
    "\n",
    "test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Running the Grover circuit and tracking amplitude of marked bitstring\n",
    "To analyse the phenomena of undercooking/overcooking we apply the Grover iterate a number of times and track what the amplitude of the marked bitstring 11...1 is. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_amplitude_marked_bitstring(qubit_count):\n",
    "  circuit_sample_count = 100\n",
    "  # Set up input and output qubits.\n",
    "  (input_qubits, output_qubit) = set_io_qubits(qubit_count)\n",
    "\n",
    "  amplitudes = [0] * (2**qubit_count)  \n",
    "  for i in range(2**qubit_count):\n",
    "    # Embed the oracle into a quantum circuit implementing Grover's algorithm.\n",
    "    n_grover_iterates = int(np.sqrt(2 ** qubit_count))\n",
    "    circuit = make_grover_circuit(input_qubits, output_qubit, i)\n",
    "    \n",
    "    # Sample from the circuit a couple times.\n",
    "    simulator = cirq.Simulator()\n",
    "    result = simulator.run(circuit, repetitions=circuit_sample_count)\n",
    "\n",
    "    # Collect frequences.\n",
    "    frequencies = result.histogram(key='result', fold_func=bitstring)\n",
    "    amplitudes[i] = frequencies[\"1\"*qubit_count]\n",
    "  \n",
    "  plt.plot(amplitudes)\n",
    "  plt.axvline(x=(np.pi / 4) * np.sqrt(2**qubit_count))\n",
    "\n",
    "plot_amplitude_marked_bitstring(6)"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}