challenge-2021.02-feb/challenge-2021.02-feb.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 04: QOSF MENTORSHIP PROGRAM SCREENING TASKS\n",
    "\n",
    "Since this month coincides with the application window for the QOSF mentorship program, we have decided to make the corresponding screening tasks as the challenge for this month.\n",
    "\n",
    "There are four separate tasks, so please feel free to try them all!\n",
    "\n",
    "### Acknowledgements\n",
    "\n",
    "[Dario Rosa](https://github.com/Dario-Rosa85) was responsible for developing tasks 1 and 2, with suggestions from \n",
    "[Anton Simen](https://github.com/AntonSimen06) to implement the SWAP test for task 1. Dario was also responsible for putting together and reviewing the final document with all four tasks, which can be found [here](https://docs.google.com/document/d/1944peQceYXhRA4Usp6ub_l2ms1xj8mXgseCgWpyBZOA)\n",
    "\n",
    "\n",
    "[Petar Korponaić](https://github.com/perak) was responsible for developing task 3.\n",
    "\n",
    "\n",
    "[Michał Stęchły](https://github.com/mstechly) was responsible for developing task 4.\n",
    "\n",
    "\n",
    "[Diego Emilio Serrano](https://github.com/diemilio) and [Stefano Mangini](https://github.com/stfnmangini) reviewed all tasks, and provided feedback for changes implemented in task 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TASK 1\n",
    "\n",
    "The [Swap test](https://en.wikipedia.org/wiki/Swap_test) is a simple quantum circuit which, given two states, allows to compute how much do they differ from each other.\n",
    "\n",
    "1) Provide a variational (also called parametric) circuit which is able to generate the most general 1 qubit state. By most general 1 qubit state we mean that there exists a set of the parameters in the circuit such that any point in the Bloch sphere can be reached. Check that the circuit works correctly by showing that by varying randomly the parameters of your circuit you can reproduce correctly the Bloch sphere.\n",
    "\n",
    "2) Use the circuit built in step 1) and, using the SWAP test, find the best choice of your parameters to reproduce a randomly generated quantum state made with 1 qubit.\n",
    "\n",
    "3) Suppose you are given with a random state, made by N qubits, for which you only know that it is a product state and each of the qubits are in the state | 0 > or | 1>. By product state we mean that it can be written as the product of single qubit states, without the need to do any summation. For example, the state\n",
    "|a> = |01>\n",
    "Is a product state, while the state\n",
    "|b> = |00> + |11>\n",
    "Is not.\n",
    "\n",
    "Perform a qubit by qubit SWAP test to reconstruct the state. This part of the problem can be solved via a simple grid search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TASK 2\n",
    "\n",
    "The bit-flip code and the sign-flip code (you can find a description of both [here](https://en.wikipedia.org/wiki/Quantum_error_correction)) are two very simple circuits able to detect and fix the bit-flip and the sign-flip errors, respectively.\n",
    "\n",
    "1) Build the following simple circuit to prepare the Bell state:\n",
    "\n",
    "<img src=\"images/error_correction.png\" width = 300/>\n",
    "\n",
    "2) Now add, right before the CNOT gate and for each of the two qubits, an arbitrary “error gate”. By error gate we mean that with a certain probability (that you can decide but must be non-zero for all the choices) you have a 1 qubit unitary which can be either the identity, or the X gate (bit-flip error) or the Z gate (sign-flip error).\n",
    "\n",
    "3) Encode each of the two qubits with a sign-flip or a bit-flip code, in such a way that all the possible choices for the error gates described in 2), occurring on the logical qubits, can be detected and fixed. Motivate your choice. This is the most non-trivial part of the problem, so do it with a lot of care!\n",
    "\n",
    "4) Test your solution by making many measurements over the final state and testing that the results are in line with the expectations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TASK 3\n",
    "\n",
    "Learning by doing: the best way to understand the basics of quantum computation is to implement a quantum circuit simulator. This task is suitable both for people from computer sciences who want to learn about quantum computing, and for people from math/physics who want to exercise coding.\n",
    "\n",
    "Detailed description of the task with some learning resources and examples can be found in this [jupyter notebook](https://github.com/quantastica/qosf-mentorship/blob/master/qosf-simulator-task.ipynb)\n",
    "\n",
    "It is expected that simulator can perform following:\n",
    "- initialize state\n",
    "- read program, and for each gate:\n",
    "    - calculate matrix operator\n",
    "    - apply operator (modify state)\n",
    "- perform multi-shot measurement of all qubits using weighted random technique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TASK 4\n",
    "\n",
    "The [MaxCut problem](https://en.wikipedia.org/wiki/Maximum_cut) is a well-known optimization problem in which the nodes of a given undirected graph have to be divided in two sets (often referred as the set of “white” and “black” nodes) such that the number of edges connecting a white node with a black node are maximized. The MaxCut problem is a problem on which the QAOA algorithm has proved to be useful (for an explanation of the QAOA algorithm you can read [this blogpost](https://www.mustythoughts.com/quantum-approximate-optimization-algorithm-explained)).\n",
    "\n",
    "At [this link](https://lucaman99.github.io/new_blog/2020/mar16.html) you can find an explicit implementation of the QAOA algorithm to solve the MaxCut problem for the simpler case of an unweighted graph. We ask you to generalize the above code to include also the solution for the case of weighted graphs. You can use the same code or you can also do an alternative implementation using, for example, qiskit. The important point is that you do not make use of any built-in QAOA functionalities."
   ]
  }
 ],
 "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
}