challenge-2021.01-jan/challenge-2021.01-jan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge 03: Minimum Makespan with Quantum Annealing\n",
    "\n",
    "### Introduction\n",
    "\n",
    "The core of this challenge is about translating a real-world problem into a mathematical representation that fits a quantum computer. In this challenge we encourage you to use two representations which even though equivalent, are used in different contexts. \n",
    "\n",
    "The first is Quadratic Unconstrained Binary Optimization (QUBO) which is used primarily for the quantum annealers (D-Wave) and the other is Ising Hamiltonian, which is often used with an algorithm called Quantum Approximate Optimization Algorithm (QAOA).\n",
    "\n",
    "This challenge might require spending some time going through the references (especially 1-3), as we are not aware of any \"quick introductions\" worth mentioning. If you have a hard time understanding something, feel free to reach out for help on [QOSF Slack](https://join.slack.com/t/qosf/shared_invite/zt-bw59w8b9-WJ~k0~FAMHukTZov4AnLfA).\n",
    "\n",
    "Unless you have a prior background with these kinds of problems, we encourage you to start from QUBO and then perhaps trying Ising Hamiltonians as well, as there are more materials about it.\n",
    "\n",
    "It is also worth mentioning that D-Wave allows you to use their machines for free for a limited amount of time, so you can try running your QUBO on a real machine after signing up [here](https://cloud.dwavesys.com/leap/signup/).\n",
    "\n",
    "### Problem\n",
    "\n",
    "Niranjan owns a catering service and receives orders one day in advance. Each of the chefs he employs is paid by the hour. In order to optimize the cost of running his business, every night, he looks at all of the dishes he needs to deliver for the next day and asks his employees to work the specific hours he requires them for.\n",
    "\n",
    "Given an order queue ($Q$) of length $N$ with each order $i$ taking $L_i$ time to prepare, if there are $m$ chefs, design a QUBO/Ising Hamiltonian to help Niranjan find the shortest time ($T$) it would take for the $m$ chefs to prepare all $N$ dishes. Assume each chef can only work on one dish at a time and each dish is worked on by only one chef. We can also safely assume that at any given point, all chefs can be actively working on a dish. \n",
    "\n",
    "Since Niranjan wants to ensure that he can run his algorithms on the near term devices, keep track and try to minimize the number of:\n",
    "1. Gates & Qubits (for Ising Hamiltonian)\n",
    "2. Variables (for QUBO. For embedding on a real machine also keep track of the lenghts of chains)\n",
    "\n",
    "**Optional:** \n",
    "For the advanced reader, you can also attempt to build the Cost Hamiltonian or Mixer Hamiltonian as described in [7,8].\n",
    "\n",
    "### Examples\n",
    "\n",
    "#### Case #1: \n",
    "\n",
    "*If,*\n",
    "\n",
    "$N = 5$\n",
    "\n",
    "$m = 1$\n",
    "\n",
    "Order Queue = {2, 3, 7, 2, 1}\n",
    "\n",
    "*then,*\n",
    "\n",
    "$T = 15$\n",
    "\n",
    "*since* there is only one chef, the shortest time it would take to complete all the orders is simply the sum of the times it would take for each individual order.\n",
    "\n",
    "#### Case #2:\n",
    "\n",
    "*If,*\n",
    "\n",
    "$N = 5$\n",
    "\n",
    "$m = 2$\n",
    "\n",
    "Order Queue = {2, 3, 7, 2, 1}\n",
    "\n",
    "*then,*\n",
    "\n",
    "$T = 8$\n",
    "\n",
    "*since* there are two chefs $m_1$ and $m_2$, the distribution that yields the shortest time is:\n",
    "\n",
    "$m_1 = \\{2, 3, 2\\}  $\n",
    "\n",
    "$m_2 = \\{ 7, 1 \\} $\n",
    "\n",
    "\n",
    "#### Case #3:\n",
    "\n",
    "*If,*\n",
    "\n",
    "$N = 5$\n",
    "\n",
    "$m = 3$\n",
    "\n",
    "Order Queue = {2, 3, 2, 2, 1}\n",
    "\n",
    "*then,*\n",
    "\n",
    "$T = 4$\n",
    "\n",
    "*since* there are three chefs $m_1$, $m_2$ and $m_3$, the distribution that yields the shortest time is:\n",
    "\n",
    "$m_1 = \\{3 \\} $\n",
    "\n",
    "$m_2 = \\{2,2 \\} $ \n",
    "\n",
    "$m_3 = \\{2,1 \\} $ \n",
    "\n",
    "Note that there could be another possible distribution of tasks, but the shortest time does not change:\n",
    "\n",
    "$m_1 = \\{3,1 \\} $ \n",
    "\n",
    "$m_2 = \\{2,2 \\} $ \n",
    "\n",
    "$m_3 = \\{2 \\} $\n",
    "\n",
    "\n",
    "### Resources\n",
    "\n",
    "\\[1\\] [D-Wave Problem Solving Handbook](https://docs.dwavesys.com/docs/latest/doc_handbook.html)\n",
    "\n",
    "\\[2\\] [Implementation of the Travelling Salesman Problem](https://github.com/mstechly/quantum_tsp_tutorials)\n",
    "\n",
    "\\[3\\] [Ising formulations of many NP problems](https://arxiv.org/pdf/1302.5843.pdf)\n",
    "\n",
    "\\[4\\] [D-Wave Examples](https://docs.ocean.dwavesys.com/en/stable/getting_started.html#examples)\n",
    "\n",
    "\\[5\\] [Quantum Approximate Optimization Algorithm explained](https://www.mustythoughts.com/quantum-approximate-optimization-algorithm-explained)\n",
    "\n",
    "\\[6\\] [Job Shop Scheduling Solver based on Quantum Annealing](https://arxiv.org/pdf/1506.08479.pdf)\n",
    "\n",
    "### References\n",
    "\n",
    "\\[7\\] [Quantum Algorithms for Scientific Computing and Approximate Optimization](https://arxiv.org/pdf/1805.03265.pdf)\n",
    "\n",
    "\\[8\\] [From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz](https://arxiv.org/pdf/1709.03489.pdf)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}