QXQ YLC Project ADVANCED - Grover for Graph Coloring STUDENT (1).ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[]},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","source":["# **Grover's Algorithm for Graph Coloring Problems**\n","---\n","\n","## **Introduction** \n","This project extends your work in Week 18 to use Grover's algorithm for more advanced problems known as Graph Coloring Problems. You will learn how to build your own an oracle and solve several types of problems that can all be reduced to Graph Coloring.\n","\n","<br>\n","\n","## **Description**\n","In Computer Science, Graph Coloring is one of many so-called \"graph problems\". Although the mathematical representation and analysis of these problems can get very complex, graph coloring is actually pretty simple. **We can view graph coloring as trying to answer the question, \"Can we color every country on a map without any touching countries having the same color, given *k* colors?\"**\n","\n","<br>\n","\n","It turns out that this problem is extremely powerful and can be used to represent many other problems including:\n","* Sudoku (numbers instead of colors in a 9X9 map)\n","* Scheduling\n","* Networking\n","* Machine Learning (ex: clustering)\n","\n","Therefore, solving such a problem is very important!\n","\n","<br>\n","\n","We will see how to use Grover's algorithm for this problem, particularly learning how to use Grover to search of a *list of solutions* instead of through a literal databse. This is actually believed to be the more likely use of Grover once we have fault tolerant computers, due to the difficulty of encoding databases into quantum states in part.\n","\n","We will follow these steps for building and solving a problem with Grover:\n","1. Create an initial state preparation circuit. This will put all possible solutions in equal superposition.\n","1. Create an oracle circuit. This will flip the phase of correct solutions and leave the rest alone. Defining this is often the hardest part.\n","1. Define the problem using Qiskit's `Amplification(...)` function.\n","1. Solve the problem using Qiskit's `Grover(...)` function. We usually have to run several times with different number of iterations to get a good result.\n","\n","\n","\n","**NOTE**: This project will involve looking at many histograms of results. As the size of the problems increase, so will the number of solutions we see in our graphs. If you start having trouble seeing the individual bars and states in the graphs, you can click on them to zoom in OR right click and press \"Save Image As...\" to download onto your computer and open it up in a larger window.\n","\n","<br>\n","\n","## **Key Questions**\n","In this project, you will answer the following questions:\n","1. When using Grover's algorithm, we do not get good results for too few *or* too many iterations. Rather, there is a \"sweet spot\" (a balanced number of iterations) right in the middle. Why is this?\n","2. How and why does having *multiple* correct answers change the number of iterations needed for Grover's algorithm?\n","3. The best classical algorithm that guarantees solutions to the 4 coloring problem has a Big-O complexity of $O(1.7272^n)$ where $n$ is the number of Countries to be colored (or Routes to be assigned planes). How does Grover's algorithm compare to this run time?\n","\n","<br>\n","\n","## **Structure**\n","This project is broken into 2 parts:\n","> **Part 1**: Grover for 2 Coloring Problems\n",">\n",">> **Part 1.1**: Building a Specific Problem\n",">>\n",">> **Part 1.2**: Building General Problems\n",">>\n",">> **Part 1.3**: Solving General Problems\n",">\n","> **Part 2**: Grover for 4 Coloring Problems\n",">\n",">> **Part 2.1**: A First Approach\n",">>\n",">> **Part 2.2**: A Faster Approach\n",">>\n",">> **Part 2.3**: Beyond Coloring\n",">\n","> **Wrapping Up**\n","\n","<br>\n","\n","## **Resources**\n","\n","* [Week 18 Lab Solutions (Grover's Algorithm for Searching Databases)](https://drive.google.com/file/d/1BAYHXCpXLp-iP2WyvamVbRchshwxOquM/view?usp=sharing)\n","* [Qiskit Textbook: Grover for Sudoku](https://qiskit.org/textbook/ch-algorithms/grover.html#sudoku)\n","* [Qiskit Documentation: Grover’s Algorithm and Amplitude Amplification](https://qiskit.org/documentation/tutorials/algorithms/06_grover.html)\n","* [Qiskit Documentation: `AmplificationProblem(...)`](https://qiskit.org/documentation/stubs/qiskit.algorithms.AmplificationProblem.html)\n","* [Qiskit Documentation: `Grover(...)`](https://qiskit.org/documentation/stubs/qiskit.algorithms.Grover.html)\n","* [Qiskit Documentation: `circuit.mct(...)`](https://qiskit.org/documentation/stubs/qiskit.circuit.QuantumCircuit.mct.html)\n","\n","**If you're curious to learn more:**\n","* [Youtube: The Four Color Theorem - What Counts as a Proof?](https://www.youtube.com/watch?v=42-ws3bkrKM)\n","\n","---"],"metadata":{"id":"Op_FbrczZGkf"}},{"cell_type":"markdown","metadata":{"id":"eb449362-eeb9-437f-a63c-84935c496bd1"},"source":["## **Part 0: Importing from Qiskit**\n","---\n","\n","**Run the code below to import everything needed for this lab.**"]},{"cell_type":"code","source":["!pip install qiskit\n","\n","from qiskit import QuantumCircuit, transpile, Aer, IBMQ\n","from qiskit.circuit import AncillaQubit\n","from qiskit.providers.aer import QasmSimulator\n","from qiskit.visualization import plot_histogram\n","\n","from qiskit.algorithms import AmplificationProblem\n","from qiskit.algorithms import Grover\n","\n","#provider = IBMQ.load_account()\n","\n","#import math\n","#from qiskit.quantum_info import Statevector\n","\n","import warnings\n","warnings.filterwarnings('ignore')\n","\n","\n","\n","def plot_results(result, satisfies_disagree_list):\n","\n","  # Plotting results\n","  counts = result.circuit_results[0]\n","  plot = plot_histogram(counts, figsize=(int(6*len(counts.keys())**(1/2)), 8), sort='value_desc')\n","  ax = plot.gca()\n","  ax.tick_params(axis='x', which='major', labelsize=10)\n","  ax.set_xlabel(\"State\", fontsize = 'x-large')\n","  ax.set_ylabel(\"Count\", fontsize = 'x-large')\n","\n","  # Marking correct (orange) vs. incorrect (blue) states\n","\n","  correct_count = 0\n","  states = ax.xaxis.get_ticklabels()\n","  for i in range(len(states)):\n","    if satisfies_disagree_list(states[i].get_text()):\n","      ax.containers[i][0].set(color = 'orange')\n","      correct_count += 1\n","    else:\n","      ax.containers[i][0].set(color = 'blue')\n","\n","  leg = plot.legend(['Incorrect (' + str(len(states) - correct_count) + ' counted)', \n","                     'Correct (' + str(correct_count) + ' counted)'], \n","                    fontsize = 'x-large',\n","                    loc = 'upper left')\n","  leg.legendHandles[0].set_color('blue')\n","  leg.legendHandles[1].set_color('orange')\n","\n","  display(plot)\n","\n","\n","print(\"Libraries Imported Successfully!\")"],"metadata":{"id":"_nvE4CopMt_N"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"xk3_cvzKQcab"},"source":["## **Part 1: Grover for 2 Coloring Problems**\n","---\n","\n","In this section, we will learn how to use Grover's algorithm to solve the 2 Coloring Problem. In other words, we are trying to color a map with just 2 colors available, which we will choose to be black and white. We will do so through these parts:\n","\n","**Part 1.1**: Building a Specific Problem\n","\n","**Part 1.2**: Building General Problems\n","\n","**Part 1.3**: Solving General Problems"]},{"cell_type":"markdown","source":["---\n","### **Part 1.1: Building a Specific Problem**\n","\n","\n","In this section, we will build and solve a specific 2 coloring problem: two bordering countries with two colors.\n","\n","**Country 0 | Country 1**\n","\n","<br>\n","\n","Therefore, the correct answers are:\n","\n","**White | Black**\n","\n","**Black | White**\n","\n","And the incorrect answers are:\n","\n","**White | White**\n","\n","**Black | Black**\n","\n","<br>\n","\n","We will use the following representation:\n","\n","* Each country is represented by a qubit.\n","* When a qubit is 0, that country is colored white.\n","* When a qubit is 1, that country is colored black.\n","\n","This means that the correct solutions correspond to 01 (white and black) and 10 (black and white) where the incorrect solutions correspond to 00 (white and white) and 11 (black and black).\n","\n","\n","<br>\n","\n","Lastly, we will follow these steps for building and solving this problem with Grover:\n","1. Create an initial state preparation circuit. This will put all possible solutions in equal superposition.\n","1. Create an oracle circuit. This will flip the phase of correct solutions and leave the rest alone. Defining this is often the hardest part.\n","1. Define the problem using Qiskit's `Amplification(...)` function.\n","1. Solve the problem using Qiskit's `Grover(...)` function. We usually have to run several times with different number of iterations to get a good result.\n","\n","<br>\n","\n","**NOTE**: We will provide you a lot of guidance in this section so that you can focus on implementing the code first. Then, we recommend you go back over this part to really understand it upon a second look."],"metadata":{"id":"H3gNn5rGTE11"}},{"cell_type":"markdown","source":["#### **Step #1: Create an initial state preparation circuit.**\n","\n","This circuit needs to put all possible solutions in equal superposition. Therefore, complete the code below so that:\n","* There is 1 qubit per country and no classical bits.\n","* Each qubit is put into superposition."],"metadata":{"id":"Oo95KzOmTxBe"}},{"cell_type":"code","source":["prep = QuantumCircuit(# COMPLETE THIS LINE\n","                      \n","prep.# COMPLETE THIS CODE\n","\n","\n","prep.draw()"],"metadata":{"id":"hVuttCBpuYUx"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Step #2: Create an oracle circuit.**\n","\n","We need to define a circuit that will flip the phase of correct solutions and leave the rest alone. In this particular case, that means:\n","\n","* If the two qubits disagree with each other (01 or 10), then we should flip the phase.\n","* Otherwise (00 or 11), leave the phase alone.\n","\n","In order to implement this, we will use two extra qubits:\n","* 1 qubit that says there's a valid solution (01 or 10) by flipping to 1.\n","* **The \"output\" bit**: 1 qubit that marks the state by flipping the phase, specifically changing from  $|-\\rangle$ to $-|-\\rangle$.\n","\n","This is broken down into 3 parts:\n","1. Initialize the oracle circuit.\n","1. Check if the current state is a solution.\n","1. Reset the extra bit for the next iteration."],"metadata":{"id":"d07zE8UtusRg"}},{"cell_type":"markdown","source":["##### **1. Initialize the oracle circuit.**\n","\n","Specifically, create a circuit such that:\n","* There's 4 qubits and no classical bits.\n","* The last qubit, $q_3$, is put into the $|-\\rangle$ state."],"metadata":{"id":"9FHmySffzHVQ"}},{"cell_type":"code","source":["oracle = # COMPLETE THIS LINE\n","oracle.# COMPLETE THIS LINE\n","oracle.# COMPLETE THIS LINE"],"metadata":{"id":"OqBS4hY8zl0T"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Check if the current state is a solution.**\n","\n","Specifically, apply gates as follows:\n","* **Flip $q_2$ if $q_0$ and $q_1$ disagree**: CX controlled by $q_0$ and targeting $q_2$ and a CX controlled by $q_1$ and targeting $q_2$. Technically, this calculates $q_2$ = XOR($q_0$, $q_1$).\n","* **Flip $q_3$ if $q_2$ has been activated**: CX controlled by $q_2$ and targeting $q_3$.\n","\n","**NOTE**: Before continuing, it is worth using pen, paper, and kets to understand how these gates accomplish their purposes stated above."],"metadata":{"id":"gGurRwyNzr4Z"}},{"cell_type":"code","source":["# Flip qubit 2 if qubits 0 and 1 disagree\n","oracle.# COMPLETE THIS LINE\n","oracle.# COMPLETE THIS LINE\n","\n","# Flip qubit 3 if qubit 2 has been activated\n","oracle.# COMPLETE THIS LINE"],"metadata":{"id":"mcTg-lp5zr4a"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **3. Reset the extra bit for the next iteration.**\n","\n","Since Grover's algorithm often requires multiple uses of the oracle, it is very important that we reset the extra qubit, $q_2$. Otherwise, we may accidentally mark states as valid or not based on what happened in the previous iteration. In practice, this is a matter of just undoing whatever we did to $q_2$.\n","\n","Specifically, **flip $q_2$ if $q_0$ and $q_1$ disagree**: CX controlled by $q_0$ and targeting $q_2$ and a CX controlled by $q_1$ and targeting $q_2$."],"metadata":{"id":"ZlOm3rOV1H0s"}},{"cell_type":"code","source":["# Undo flipping qubit 2 if qubits 0 and 1 disagree\n","oracle.# COMPLETE THIS LINE\n","oracle.# COMPLETE THIS LINE\n","\n","oracle.draw()"],"metadata":{"id":"Thji880C1H0t"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Step #3: Define the problem using Qiskit's Amplification(...) function.**\n","\n","Now that we have the state preparation and oracle circuits defined, we can setup the problem for Qiskit. We have provided this code for you, however, it will be valuable to understand this code before trying to solve other problems."],"metadata":{"id":"y1cxxJbJ2jQW"}},{"cell_type":"code","source":["# Function that takes a string representation of a state\n","# and checks if the bits disagree with each other\n","def check_disagreement(state):\n","  if state[0] == state[1]: return False\n","  else: return True\n","\n","# Setting up the problem with Qiskit's AmplificationProblem(...) function\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep, \n","                               is_good_state = check_disagreement, \n","                               objective_qubits = [0, 1])"],"metadata":{"id":"ZrWg3mUx20iN"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Step #4: Solve the problem using Qiskit's `Grover(...)` function.**\n","\n","We have provided you with the code below for 0 iterations, which means we don't check the oracle at all and just prepare an equal superposition of all solutions.\n","\n","**Run the code, increasing the number of iterations until only correct answers are shown.**"],"metadata":{"id":"X4KDiLrv3VRR"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"wmGC9bAt5kjc"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Draw the Full Circuit.**\n","\n","Just for reference, **run the code below to draw the full circuit after you have found the ideal number of iterations.**\n","\n","**NOTE**: The mysterious looking gates at the beginning, $U3(\\pi/2, 0, \\pi)$, are actually just another way to write H gates."],"metadata":{"id":"5W8Cc0097j3_"}},{"cell_type":"code","source":["grover.construct_circuit(problem, measurement = True).decompose(reps = 2).draw()"],"metadata":{"id":"aEtVLiD67BXN"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["---\n","### **Part 1.2: Building General Problems**\n","\n","\n","In this section, we will extend the approach we used below to solve general 2 color problems by placing this code into functions.\n","\n","\n","\n","**Start by running the code below to define an example problem (the same one as Part 1.1) using variables.**"],"metadata":{"id":"xqhh0HLI9Rye"}},{"cell_type":"code","source":["variable_qubits = [0, 1]\n","check_qubits = [2]\n","output_qubit = 3\n","disagree_list = [[0,1]]"],"metadata":{"id":"eL5bfomNGXYk"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #1**\n","\n","First, let us define a general initial state preparation circuit. Specifically, complete the code below to create a function that:\n","* Takes in the list of qubit numbers called `variable_qubits`.\n","* Initializes a quantum circuit with a qubit for every variable and no classical bits.\n","* Puts all the qubits in `variable_qubits` into equal superpositions."],"metadata":{"id":"_tXL9UKy9kg_"}},{"cell_type":"code","source":["def graph_color_prep(variable_qubits):\n","  \n","  num_vars = len(variable_qubits)\n","  prep = # COMPLETE THIS LINE\n","\n","  prep.h(# COMPLETE THIS CODE\n","\n","  return prep"],"metadata":{"id":"mmtp-Tad-N3W"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #2**\n","\n","Now let's work out the code for a general graph coloring oracle part by part. Specifically,\n","\n","1. Initializing a quantum circuit with the output bit in the $|-\\rangle$ state.\n","1. Checking if each pair of qubits in a given list, `disagree_list`, disagree with each other.\n","1. Flip the output bit if all disagreements are satisfied.\n","1. Resetting all the extra qubits for the next iteration."],"metadata":{"id":"k98G5bIp-78k"}},{"cell_type":"markdown","source":["##### **1. Initializing a quantum circuit with the output bit in the $|-\\rangle$ state.**"],"metadata":{"id":"f-buwxj3AlIJ"}},{"cell_type":"code","source":["num_vars = len(variable_qubits)\n","num_checks = len(check_qubits)\n","num_outputs = 1\n","\n","oracle = QuantumCircuit(# COMPLETE THIS LINE"],"metadata":{"id":"efnBDGdC_sCO"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Checking if each pair of qubits in a given list, `disagree_list`, disagree with each other.**\n","\n","Complete the code below to accomplish this. For reference:\n","* each element of `disagree_list` is a pair of qubits that we need to disagree with each other. This represents two spots on a map that must be colored differently.\n","* each element of `check_qubits` is the extra qubit to store the result of checking a pair from `disagree_list`.\n","\n","**NOTE**: This is a good time to stop and check that you understand what this code is doing before continuing."],"metadata":{"id":"GU1KrSJBAqu0"}},{"cell_type":"code","source":["for i in range(len(disagree_list)):\n","  oracle.cx(disagree_list[i][0], check_qubits[i])\n","  oracle.cx(# COMPLETE THIS LINE"],"metadata":{"id":"RMNPyItVAqu1"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **3. Flip the output bit if all disagreements are satisfied.**\n","\n","While the CNOT gate worked for the 2 qubit example, we need to generalize this so that there are any number of control qubits. Qiskit provides the multi-controlled target (`mct`) gate for just this purpose.\n","\n","For example,\n","\n","* `mct([0], 1) = cx(0, 1)` (CNOT)\n","* `mct([0, 1], 2) = ccx(0, 1, 2)` (Toffoli)\n","* `mct([0, 1, 2, 3, 4, 5], 6) = cccccx(0, 1, 2, 3, 4, 5, 6)` (no special name, need to use `mct`)\n","\n","\n","Use this gate specifically as follows:\n","* `check_qubits` are the controls.\n","* `output_qubit` is the target."],"metadata":{"id":"H_Uv3mxJAuHM"}},{"cell_type":"code","source":["oracle.mct(# COMPLETE THIS LINE"],"metadata":{"id":"8HjUIpEYAuHN"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **4. Resetting all the extra qubits for the next iteration.**\n","\n","Lastly, complete the code below to undo everything we did to the extra qubits.\n","\n","**Hint**: This is undoing the gates applied in 2."],"metadata":{"id":"Qksq5ojHAzQx"}},{"cell_type":"code","source":["for i in range(len(disagree_list)):\n","  oracle.# COMPLETE THIS LINE\n","  oracle.# COMPLETE THIS LINE\n","\n","oracle.draw()"],"metadata":{"id":"dULCVsLDAzQy"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #3**\n","\n","To truly make a general oracle, let's put this code into a function that we can call later on. Specifically, complete the code below by filling it in with each part of Exercise #2 and returning the oracle circuit."],"metadata":{"id":"t87faWvRE9d0"}},{"cell_type":"code","source":["def graph_color_oracle(disagree_list, variable_qubits, check_qubits, output_qubit):\n","\n","  # 1. Initializing a quantum circuit with the output bit in the |−⟩ state.\n","  # COMPLETE THIS CODE\n","\n","\n","  # 2. Checking if each pair of qubits in a given list, disagree_list, disagree with each other.\n","  # COMPLETE THIS CODE\n","\n","  \n","  # 3. Flip the output bit if all disagreements are satisfied.\n","  # COMPLETE THIS CODE\n","\n","\n","  # 4. Resetting all the extra qubits for the next iteration.\n","  # COMPLETE THIS CODE\n","\n","  \n","  return # COMPLETE THIS LINE"],"metadata":{"id":"EWCz2mfJFPmu"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #4**\n","\n","Lastly, we will define a useful function for verifying the correct states as follows:\n","* It takes in a string representation of a measured state, called `state`.\n","* It takes in `disagree_list`.\n","* It compares every pair of bits listed in the `disagree_list`.\n","* If any pair of bits are the same, then the function returns `False`.\n","* Otherwise, the function returns `True`."],"metadata":{"id":"3O1ysAogGsBf"}},{"cell_type":"code","source":["def check_disagree_list_general(state, disagree_list):\n","    \n","    for i in range(len(disagree_list)):\n","      if state[disagree_list[i][0]] == # COMPLETE THIS LINE\n","        return False\n","      \n","    return # COMPLETE THIS LINE"],"metadata":{"id":"dkGBibF3GsBg"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #5**\n","\n","Let's put these functions to use! Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem."],"metadata":{"id":"d1B1jbfXH0QB"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"Zv8-AfaLJxya"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1]\n","check_qubits = [2]\n","output_qubit = 3\n","disagree_list = [[0,1]]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(# COMPLETE THIS LINE\n","oracle = graph_color_oracle(# COMPLETE THIS LINE\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle,\n","                               state_preparation = # COMPLETE THIS LINE,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"RVuq1ehaH0QB"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**\n","\n","**Change the number of iterations to the number you found from Part 1.1 and run this code.**"],"metadata":{"id":"_cL_vJkIKHuM"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"ta42dy0HKHuM"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["---\n","### **Part 1.3: Solving General Problems**\n","\n","\n","So far, we have solved the same problem twice. Let's use the general functions we created above to solve more complicated problems."],"metadata":{"id":"6_aLE8KTLG14"}},{"cell_type":"markdown","source":["#### **Exercise #1**\n","\n","To start, let's solve a problem with just one more qubit (country to color) such that the countries border each other in a line as follows:\n","\n","**Country 0 | Country 1 | Country 2**\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 0 and 2 can be colored the same or differently since they don't border each other.\n","\n","And the correct solutions are: 010 and 101.\n","\n","<br>\n","\n","Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem."],"metadata":{"id":"C4QLCpzALTGH"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"nOboXdQULTGH"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2]\n","check_qubits = [2, 3]\n","output_qubit = 4\n","disagree_list = [[0,1], # COMPLETE THIS LINE TO SPECIFY WHICH PAIRS OF QUBITS MUST DISAGREE\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(# COMPLETE THIS LINE\n","oracle = graph_color_oracle(# COMPLETE THIS LINE\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle,\n","                               state_preparation = # COMPLETE THIS LINE,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"Mw5XC6E-LTGI"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**\n","\n","Increase the number of iterations to get the best results. \n","\n","**NOTE**: The theoretically optimal number of iterations is roughly $\\frac{\\pi}{4}\\sqrt{\\frac{\\text{Number of Possible Answers}}{\\text{Number of Correct Answers}}}$. As such, for small numbers there often isn't an exact integer number of iterations that will give 100% correct solutions. Instead, the game is to start at something close to this value and tweak it until you get the correct answer most of the time."],"metadata":{"id":"kEEWhJ1ILTGI"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"jVLXniXMLTGI"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #2**\n","\n","Now, solve a problem with 4 countries in the same arrangement:\n","\n","**Country 0 | Country 1 | Country 2 | Country 3**\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 2 and 3 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other.\n","\n","And the correct solutions are: 0101 and 1010\n","\n","<br>\n","\n","Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem."],"metadata":{"id":"5ITYdliPQDsC"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"pUhjzCW0QDsF"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3]\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = 7\n","disagree_list = [[0,1], # COMPLETE THIS LINE TO SPECIFY WHICH PAIRS OF QUBITS MUST DISAGREE\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(# COMPLETE THIS LINE\n","oracle = graph_color_oracle(# COMPLETE THIS LINE\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle,\n","                               state_preparation = # COMPLETE THIS LINE,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"h8J79JwQQDsF"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**\n","\n","Increase the number of iterations to get the best results."],"metadata":{"id":"qgfkODtcQDsF"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"_2YC925IQDsF"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #3**\n","\n","Now, solve a problem with 4 countries such that Countries 0 and 1 are in a line and Countries 1, 2, and 3 all border each other:\n","\n","**Country 0 | Country 1 | Country 2**\n","\n","**&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;Country 3**\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 1 and 3 must be colored differently.\n","* Countries 2 and 3 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other.\n","\n","This problem is particularly interesting since *there are no correct solutions with 2 colors*.\n","\n","<br>\n","\n","Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem."],"metadata":{"id":"iUq6QD5dTDIX"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"HD_NWmlhTDIY"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3]\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = 8\n","disagree_list = [[0,1], # COMPLETE THIS LINE TO SPECIFY WHICH PAIRS OF QUBITS MUST DISAGREE\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(# COMPLETE THIS LINE\n","oracle = graph_color_oracle(# COMPLETE THIS LINE\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle,\n","                               state_preparation = # COMPLETE THIS LINE,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"JsO28VYNTDIY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**\n","\n","Increase the number of iterations to get the best results."],"metadata":{"id":"nXxMXC7ATDIZ"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"GV6VMZ8DTDIZ"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Overconstrained and Underconstrained Problems**\n","\n","This is an example of an **overconstrained problem** where there are so many constraints that there are actually *no correct answers*. Every algorithm reacts differently to these types of problems. Can you determine what Grover's algorithm is doing using the results above and your understanding of the algorithm? This will be one of the questions to answer in your project summary.\n","\n","<br>\n","\n","Technically, all of the problems we have seen so far have been **underconstrained problems** because they had few enough constraints to allow for *multiple correct answers*.\n"],"metadata":{"id":"ijmBaJr2ViRw"}},{"cell_type":"markdown","source":["#### **Exercise #4**\n","\n","To wrap up, solve the following problem involving 6 countries:\n","\n","**Country 0 | Country 1 | Country 2**\n","\n","**Country 3 | Country 4 | Country 5**\n","\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 0 and 3 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 1 and 4 must be colored differently.\n","* Countries 2 and 5 must be colored differently.\n","* Countries 3 and 4 must be colored differently.\n","* Countries 4 and 5 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other.\n","\n","Can you determine what the correct answers are (if there are any)?\n","\n","<br>\n","\n","Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem."],"metadata":{"id":"eVTvlzBnWE9x"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"p-2jrVRtWE9y"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [# COMPLETE THIS LINE\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [# COMPLETE THIS LINE TO SPECIFY WHICH PAIRS OF QUBITS MUST DISAGREE\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(# COMPLETE THIS LINE\n","oracle = graph_color_oracle(# COMPLETE THIS LINE\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle,\n","                               state_preparation = # COMPLETE THIS LINE,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"wuVg2CzjWE9y"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**\n","\n","Increase the number of iterations to get the best results.\n","\n","**NOTE**: As the size of the problems increase, so will the number of solutions we see in our graphs. If you start having trouble seeing the individual bars and states in the graphs, you can click on them to zoom in OR right click and press \"Save Image As...* to download onto your computer and open it up in a larger window."],"metadata":{"id":"1eeLaPFFWE9y"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"PgeBOrgcWE9y"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"l6LLxP7cc6cI"},"source":["## **Part 2: Grover for 4 Coloring Problems**\n","---\n","\n","In this section, we will expand upon the approach we developed in Part 1 to tackle the 4 Coloring Problem. After centuries of debate, it was proven that *any* Graph Coloring problem can be solved with 4 colors. So, being able to use Grover's algorithm to solve the 4 Coloring Problem is enough to solve *any* Graph Coloring problem with Grover's algorithm.\n","\n","<br>\n","\n","We will do so through these parts:\n","\n","**Part 2.1**: A First Approach\n","\n","**Part 2.2**: A Faster Approach\n","\n","**Part 2.3**: Beyond Coloring"]},{"cell_type":"markdown","source":["---\n","### **Part 2.1: A First Approach**\n","\n","\n","To start, we will attempt taking a very similar approach to the one we developed above. There are two main adjustments that need to occur:\n","\n","* To represent 4 possible colors per Country, we need to use *2 qubits*. So now, each Country can be in any of these four states (the colors listed below are just for sake of example): \n","  * 00: White\n","  * 01: Red\n","  * 10: Orange\n","  * 11: Black\n","\n","* To make sure that two Countries are colored differently, we will compare each digit and make sure there is at least one difference. For instance, 00 01 is ok since the 2nd digit (0 and 1) is different in each number even though the first one is the same (0). This first approach will require the use of **ancilla** (extra) qubits.\n","\n","<br>\n","\n","We have provided the fully updated graph coloring oracle below. Over the first few exercises, you will define the necessary functions for this to work, `disagree_multi_q` and `undo_disagree_multi_q`.\n","\n","**Run the code below before moving onto Exercise #1.**"],"metadata":{"id":"mtJuA3AUL96z"}},{"cell_type":"code","source":["def graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit):\n","\n","  # 1. Initializing a quantum circuit with the output bit in the |−⟩ state.\n","  num_vars = len(variable_qubits)\n","  num_checks = len(check_qubits)\n","  num_outputs = 1\n","\n","  oracle = QuantumCircuit(num_vars + num_checks + num_outputs)\n","  oracle.x(output_qubit)\n","  oracle.h(output_qubit)\n","\n","\n","  # 2. Checking if each pair of qubits in a given list, disagree_list, disagree with each other.\n","  # Storing the ancilla qubits used for each check\n","  ancillas = []\n","  for i in range(len(disagree_list)):\n","    ancillas += [ disagree_check_4c(oracle,\n","                                  disagree_list[i][0], \n","                                  disagree_list[i][1], \n","                                  check_qubits[i]) ]\n","\n","  \n","  # 3. Flip the output bit if all disagreements are satisfied.\n","  oracle.mct(check_qubits, output_qubit)\n","\n","\n","  # 4. Resetting all the extra qubits for the next iteration.\n","  # Need to include the specific ancillas used for each check\n","  for i in range(len(disagree_list)):\n","    undo_disagree_check_4c(oracle, \n","                           disagree_list[i][0], \n","                           disagree_list[i][1], \n","                           check_qubits[i], \n","                           ancillas[i])\n","\n","  \n","  return oracle"],"metadata":{"id":"ey5XX7GzBvKm"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #1**\n","\n","To start, let's work out what the `disagree_check_4c(...)` function needs to do part by part and then we can put it into a function in Exercise #2. The overall goal of this function is to flip the check qubit if at least one pair of digits disagree. We will accomplish this as follows:\n","\n","1. Add 2 ancilla qubits to the circuit. This provides 1 per digit.\n","1. Check if the first digit of each state *agrees*.\n","1. Check if the second digit of each state *agrees*.\n","1. Flip the check bit if either *disagree*.\n","\n","**To get started, run the code below. You will refer to these variables throughout this exercise.**"],"metadata":{"id":"FCioZdjHL96z"}},{"cell_type":"code","source":["qc = QuantumCircuit(5)\n","qubits_a = [0, 1]\n","qubits_b = [2, 3]\n","check_qubit = 4"],"metadata":{"id":"MoViUAv3IJSE"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **1. Add 2 ancilla qubits to the circuit.**"],"metadata":{"id":"hpbTuKlPL96z"}},{"cell_type":"code","source":["ancillas = [AncillaQubit(), # COMPLETE THIS LINE\n","qc.add_bits(ancillas)\n","\n","qc.draw()"],"metadata":{"id":"_ZKqHxzbL960"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Check if the first digit of each state agrees.**\n","\n","The following information may be helpful for completing this code:\n","* The first digit is stored in the 0th index of each: `qubit_a[0]` and `qubit_b[0]`.\n","* The corresponding ancilla qubit, `ancillas[0]`, should store the result of this check.\n","* Checking for agreement is the same as checking for disagreement and then flipping the qubit.\n","* We checked for disagreement of qubits in Part 1 and have generally seen that the X gate can be used to flip qubit states."],"metadata":{"id":"GwGz57YIHjgX"}},{"cell_type":"code","source":["qc.# COMPLETE THIS LINE\n","qc.# COMPLETE THIS LINE\n","qc.# COMPLETE THIS LINE"],"metadata":{"id":"Vst7I_dLHjgY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **3. Check if the second digit of each state agrees.**\n","\n","Do the same as above, but for the 2nd digits."],"metadata":{"id":"LzjxTDuLHwtN"}},{"cell_type":"code","source":["qc.# COMPLETE THIS LINE\n","qc.# COMPLETE THIS LINE\n","qc.# COMPLETE THIS LINE"],"metadata":{"id":"Y6oveG80NJGz"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **4. Flip the check bit if either disagree.**\n","\n","The following information may be helpful for completing this code:\n","* It's easiest to first check if all the digits agree and then flip the output.\n","* The multi-controlled target gate allows for checking multiple qubits at once and storing the result.\n","* The ancillas store the results we need to check."],"metadata":{"id":"zeM5Ca5eH1Qc"}},{"cell_type":"code","source":["qc.# COMPLETE THIS LINE\n","qc.# COMPLETE THIS LINE\n","\n","qc.draw()"],"metadata":{"id":"azL4VqqAN-2I"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **If you happen to be curious about why we are taking this approach**: \n","\n","To allow for one pair of digits to agree and the other to disagree using quantum circuits, we take advantage of the fact that the following two statements are the same:\n","\n","1. ($q_0$ and $q_2$ disagree) OR ($q_1$ and $q_3$ disagree)\n","\n","1. NOT( ($q_0$ and $q_2$ agree) AND ($q_1$ and $q_3$ agree) )\n","\n","The second statement is easier to implement in quantum circuits directly because NOT can be encoded with an X gate and AND can be encoded with the multi-controlled gate (or a Toffoli since we have 2 ancilla qubits as our controls) amongst other approaches. The equivalence of those two statements is technically known as De Morgan's law."],"metadata":{"id":"u9ZymBLdLJVT"}},{"cell_type":"markdown","source":["#### **Exercise #2**\n","\n","Now, complete the code below by filling it in with the parts you developed in Exercise #1. The only addition is that you must also return the ancilla qubits so that this operation can be undone (reset) for future iterations."],"metadata":{"id":"Yun3CiubH5tI"}},{"cell_type":"code","source":["def disagree_check_4c(qc, qubits_a, qubits_b, check_qubit):\n","\n","  # 1. Add 2 ancilla qubits to the circuit. This provides 1 per digit.\n","  # COMPLETE THIS CODE\n","\n","\n","  # 2. Check if the first digit of each state agrees.\n","  # COMPLETE THIS CODE\n","\n","  # 3. Check if the second digit of each state agrees.\n","  # COMPLETE THIS CODE\n","\n","  # 4. Flip the check bit if either disagree.\n","  # COMPLETE THIS CODE\n","\n","\n","  # Return ancillas so that we can undo this operation later on\n","  return # COMPLETE THIS LINE"],"metadata":{"id":"qLcPDtVtIBGb"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #3**\n","\n","Next, we need to define the function that *undoes* this operation, `undo_disagree_check_4c(...)`. Instead of returning the ancillas, this function takes them in and uses them to make sure they get reset properly.\n","\n","**Complete the code below by applying the gates from `disagree_check_4c(...)` in the opposite order.**"],"metadata":{"id":"UIk4TjWvO4jc"}},{"cell_type":"code","source":["def undo_disagree_check_4c(qc, qubits_a, qubits_b, check_qubit, ancillas):\n","\n","  # 4. UNDO Flip the check bit if either disagree.\n","  # COMPLETE THIS CODE\n","\n","  # 3. UNDO Check if the second digit of each state agrees.\n","  # COMPLETE THIS CODE\n","\n","  # 2. UNDO Check if the first digit of each state agrees.\n","  # COMPLETE THIS CODE"],"metadata":{"id":"U2xVv02dO4jd"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #4**\n","\n","Lastly, we need to define an updated version of `check_disagree_list_general(...)` that accounts for the multiple digits: `check_disagree_list_general_4c(...)`.\n","\n","\n","As a reminder, this function was used for verifying the correct states as follows:\n","* It takes in a string representation of a measured state, called `state`.\n","* It takes in `disagree_list`.\n","* It compares every pair of bits listed in the `disagree_list`.\n","* If any pair of bits are the same, then the function returns `False`.\n","* Otherwise, the function returns `True`."],"metadata":{"id":"VTtvE-7yQY7q"}},{"cell_type":"code","source":["def check_disagree_list_general_4c(state, disagree_list):\n","\n","  for i in range(len(disagree_list)):\n","    \n","    if (state[disagree_list[i][0][0]] == state[disagree_list[i][1][0]] \n","        and state[disagree_list[i][0][1]] == state[disagree_list[i][1][1]]):\n","        return # COMPLETE THIS LINE\n","\n","  return # COMPLETE THIS LINE"],"metadata":{"id":"P8dsCO0IQY7r"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **Run the code below to verify that your function works properly.**"],"metadata":{"id":"QXEAHz86SiJx"}},{"cell_type":"code","source":["check1 = (check_disagree_list_general_4c('1111', [[[0, 1], [2, 3]]]) == False)\n","check2 = (check_disagree_list_general_4c('0111', [[[0, 1], [2, 3]]]) == True)\n","check3 = (check_disagree_list_general_4c('0110', [[[0, 1], [2, 3]]]) == True)\n","check4 = (check_disagree_list_general_4c('0101', [[[0, 1], [2, 3]]]) == False)\n","\n","if not check1:\n","  print(\"1111 Fails\")\n","\n","if not check2:\n","  print(\"0111 Fails\")\n","\n","if not check3:\n","  print(\"0110 Fails\")\n","\n","if not check4:\n","  print(\"0101 Fails\")\n","\n","if check1 and check2 and check3 and check4:\n","  print(\"Success, keep moving!\")"],"metadata":{"id":"FBsN97qlSAUu"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #5**\n","\n","Let's put these functions to use! Specifically,\n","\n","1. Define the problem.\n","1. Solve the problem.\n","\n","\n","The problem in this exercise is to color 3 countries that all border each other (something that is impossible to do with just 2 colors):\n","\n","\n","**Country 0 | Country 1**\n","\n","**&emsp;&emsp;Country 2**"],"metadata":{"id":"TeUE7SNiTlZh"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem.\n","\n","**NOTE**: The biggest adjustment here is that every country must be represented by two qubits, which will effect the initial variable defintions."],"metadata":{"id":"BU2cFzuhTlZi"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3, 4, 5]\n","check_qubits = [6, 7, 8]\n","output_qubit = 9\n","disagree_list = [ [[0, 1], [2, 3]],\n","                  [[0, 1], # COMPLETE THIS LINE,\n","                  # COMPLETE THIS LINE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"L0xj2qRpTlZi"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"pl-bklFXTlZi"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"24bRqD3STlZi"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #6**\n","\n","Now, solve the problem of coloring 4 countries such that the first 2 border each other and the second two border each other, but there is water between them:\n","\n","\n","**Country 0 | Country 1 ~ ~ water ~ ~ Country 2 | Country 3**\n","\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 2 and 3 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other.\n","\n","<br>\n","\n","**Question**: Is this problem over- or under- constrained (or is there exactly one solution)?"],"metadata":{"id":"sxD-wXfRZk7w"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"K8wQ-5_ZZk7x"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3, 4, 5, 6, 7]\n","check_qubits = [8, # COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ [[0, 1], [2, 3]],\n","                  # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"nL0isDQoZk7x"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"koX61efGZk7y"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"1XNKTEpTZk7y"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #7**\n","\n","Now, solve the problem of coloring 4 countries such that the first 3 are in the same arrangement as Exercise #5, but are now bordered on all sides by the last country:\n","\n","**&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;<font size=\"6\">Country 3</font>**\n","\n","**<font size=\"6\">Country 3</font> &ensp;| Country 0 | Country 1 | &ensp;<font size=\"6\">Country 3</font>**\n","\n","**&ensp;&ensp;&ensp;<font size=\"6\">Country 3</font>&ensp;&ensp;&ensp;| Country 2 | &ensp;&ensp;&ensp;<font size=\"6\">Country 3</font>**\n","\n","**&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;<font size=\"6\">Country 3</font>**\n","\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 0 and 2 must be colored differently.\n","* Countries 0 and 3 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 1 and 3 must be colored differently.\n","* Countries 2 and 3 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other.\n","\n","<br>\n","\n","\n","**NOTE**: Be patient! This is a large problem and may take several minutes to run."],"metadata":{"id":"5Edt6JZ1WlvB"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"V-PakuEMWlvC"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3, 4, 5, 6, 7]\n","check_qubits = [8, # COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ [[0, 1], [2, 3]],\n","                  # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"oYTsmxTVWlvC"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"xQBlbi-uWlvC"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"rU88DMBCWlvD"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Hitting Limits**\n","\n","The code above should be able to solve this problem within just 1 - 2 iterations. However, it takes almost 2 minutes per iteration. For computers, this is an unacceptably long time, particularly given that this problem is much smaller than many of the applications we might be interested in (most directly, imagine trying to color a map of Africa or the world)!\n","\n","\n","It is common in scientific research to first find something that works, just so you know it can be done, and then find ways to optimize (improve) it. Furthermore, there are often many ways to optimize an algorithm and choosing how much time and energy to spend on the different ways largely depends on what you need to accomplish in practice.\n","\n","In Part 2.2, we will explore one way to optimize this code, specifically making it run faster. We can verify that it is faster by trying it out on the exact same problem as above."],"metadata":{"id":"c7FL0qdxeWGz"}},{"cell_type":"markdown","source":["---\n","### **Part 2.2: A Faster Approach**\n","\n","\n","In this section, we will optimize our implementation of Grover's algorithm for the 4-coloring problem by determining one of the \"bottlenecks\" (parts that are slowing everything down) and attempting to improve upon it."],"metadata":{"id":"YHr2mRNZf2XT"}},{"cell_type":"markdown","source":["#### **Exercise #1**\n","\n","To start, we need to understand what is actually slowing this code down, called a [bottleneck](https://en.wikipedia.org/wiki/Bottleneck_(software)). In other words, we need to diagnose the problem. \n","\n","**Draw the prep and oracle circuits from the problem above to see what we are working with.**"],"metadata":{"id":"kpjPnSzygUpa"}},{"cell_type":"code","source":["# DRAW THE PREP CIRCUIT"],"metadata":{"id":"f7y8Ghq6g175"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# DRAW THE ORACLE CIRCUIT"],"metadata":{"id":"ojp_eOKahGE6"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Open Ended Question**\n","\n","We cannot do much to change the prep circuit unless we find an entirely different way to represent the problem.\n","\n","However, there's often more freedom to change the oracle circuit by representing the same logic in a different way. To see what we might change, consider the following question:\n","\n","***What are different ways we could change the oracle?***"],"metadata":{"id":"08Ev8JWjhYlL"}},{"cell_type":"markdown","source":["#### **Exercise #2**\n","\n","The particular way we will optimize the oracle here is to eliminate the need for ancilla qubits as they effectively double the size and complexity of the problem. For instance, the last problem from Part 2.1 had 12 ancilla qubits on top of the 14 \"core\" qubits.\n","\n","<br>\n","\n","To accomplish this, we will approach the disagreement checks completely differently. The logic we used before was very generallly encoding the idea of pairs of qubits disagreeing. However, with 4 colors it turns out that there are only ever 4 cases where all 4 qubits agree with each other. Here are the 4 cases explicitly:\n","\n","11 11\n","\n","01 01\n","\n","10 10\n","\n","00 00\n","\n","All (12) other states are acceptable! So, we've been using general logic to eliminate 4/16 or just 1/4 of the possibilities. Instead, let us specifically target these states as follows:\n","\n","1. Check if the qubits are in the 11 11 state.\n","2. Check if the qubits are in the 01 01 state.\n","3. Check if the qubits are in the 10 10 state.\n","4. Check if the qubits are in the 00 00 state.\n","5. If none of these states have been found, flip the output qubit.\n","\n","<br>\n","\n","**Run the code below to define variables that will be used throughout this exercise.**"],"metadata":{"id":"ChFRj_cehRJw"}},{"cell_type":"code","source":["qc = QuantumCircuit(5)\n","qubits_a = [0, 1]\n","qubits_b = [2, 3]\n","check_qubit = 4"],"metadata":{"id":"9-FJLTChnH5W"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **1. Check if the qubits are in the 11 11 state.**\n","\n","To get started, the code for this has been provided for you. Consider why this works to check if $q_0 q_1 q_2 q_3 = 1111$."],"metadata":{"id":"bA_hjgCCnH5W"}},{"cell_type":"code","source":["qc.mct(qubits_a + qubits_b, check_qubit)\n","\n","qc.barrier()\n","qc.draw()"],"metadata":{"id":"Ei0x_tu8nH5X"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Check if the qubits are in the 01 01 state.**\n","\n","This is a matter of modifying the approach above by flipping the appropriate qubits AND making sure that you undo any flips *right* after checking so that they are ready to be checked for the next case."],"metadata":{"id":"4NoGW81MnH5X"}},{"cell_type":"code","source":["qc.mct(qubits_a + qubits_b, check_qubit)\n","\n","qc.barrier()\n","qc.draw()"],"metadata":{"id":"PctPjodXnH5X"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **3. Check if the qubits are in the 10 10 state.**"],"metadata":{"id":"u-r8v7QfnH5X"}},{"cell_type":"code","source":["qc.mct(qubits_a + qubits_b, check_qubit)\n","\n","qc.barrier()\n","qc.draw()"],"metadata":{"id":"nhHt0ATAojfS"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **4. Check if the qubits are in the 00 00 state.**"],"metadata":{"id":"NDq3tLq4nH5Y"}},{"cell_type":"code","source":["qc.mct(qubits_a + qubits_b, check_qubit)\n","\n","qc.barrier()\n","qc.draw()"],"metadata":{"id":"yHkX8LKNoj3d"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **5. If none of these states have been found, flip the output qubit.**\n","\n","Now all 4 states have been checked and $q_4$ will be 1 if any of them have been found. However, we want to flip this logic so that $q_4$ is 1 if *none* of them have been found. Apply the necessary gate(s) below to accomplish this."],"metadata":{"id":"YsxZ_tZfngX4"}},{"cell_type":"code","source":["# COMPLETE THIS CODE\n","\n","qc.draw()"],"metadata":{"id":"OlpvhyMQngX4"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #3**\n","\n","Now, complete the code below by filling it in with the parts you developed in Exercise #2. Unlike in Part 2.1, we do not need to return anything from this function.\n","\n","<br>\n","\n","**IMPORTANT NOTE**: Qiskit does not cross barriers when trying to find optimal ways to simulate or compile quantum circuits. So, to make this code as efficient as possible **remove any calls to `qc.barrier()` or `qc.draw()`**."],"metadata":{"id":"MRPujs4Mpw_5"}},{"cell_type":"code","source":["def disagree_check_4c(qc, qubits_a, qubits_b, check_qubit):\n","\n","  # 1. Check if the qubits are in the 11 11 state.\n","  # COMPLETE THIS CODE\n","\n","  # 2. Check if the qubits are in the 01 01 state.\n","  # COMPLETE THIS CODE\n","\n","  # 3. Check if the qubits are in the 10 10 state.\n","  # COMPLETE THIS CODE\n","\n","  # 4. Check if the qubits are in the 00 00 state.\n","  # COMPLETE THIS CODE\n","\n","  # 5. If none of these states have been found, flip the output qubit.\n","  # COMPLETE THIS CODE"],"metadata":{"id":"2nZtUa1fpw_5"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #4**\n","\n","Lastly, we need to define the function that *undoes* this operation, `undo_disagree_check_4c(...)`.\n","\n","**Complete the code below by applying the gates from `disagree_check_4c(...)` in the opposite order.**"],"metadata":{"id":"O3H2y9_TrNEm"}},{"cell_type":"code","source":["def undo_disagree_check_4c(qc, qubits_a, qubits_b, check_qubit):\n","\n","  # 5. UNDO If none of these states have been found, flip the output qubit.\n","  # COMPLETE THIS CODE\n","\n","  # 4. UNDO Check if the qubits are in the 00 00 state.\n","  # COMPLETE THIS CODE\n","\n","  # 3. UNDO Check if the qubits are in the 10 10 state.\n","  # COMPLETE THIS CODE\n","\n","  # 2. UNDO Check if the qubits are in the 01 01 state.\n","  # COMPLETE THIS CODE\n","\n","  # 1. UNDO Check if the qubits are in the 11 11 state.\n","  # COMPLETE THIS CODE"],"metadata":{"id":"rn2kVYQNrNEm"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Updating the Oracle Function**\n","\n","Now that we are not using ancilla qubits, we need to slightly update the oracle function.\n","\n","**Run the code below to update the oracle function.**"],"metadata":{"id":"iZ6X9I8Ar43a"}},{"cell_type":"code","source":["def graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit):\n","\n","  # 1. Initializing a quantum circuit with the output bit in the |−⟩ state.\n","  num_vars = len(variable_qubits)\n","  num_checks = len(check_qubits)\n","  num_outputs = 1\n","\n","  oracle = QuantumCircuit(num_vars + num_checks + num_outputs)\n","  oracle.x(output_qubit)\n","  oracle.h(output_qubit)\n","\n","\n","  # 2. Checking if each pair of qubits in a given list, disagree_list, disagree with each other.\n","  for i in range(len(disagree_list)):\n","    disagree_check_4c(oracle,\n","                      disagree_list[i][0], \n","                      disagree_list[i][1], \n","                      check_qubits[i])\n","\n","  \n","  # 3. Flip the output bit if all disagreements are satisfied.\n","  oracle.mct(check_qubits, output_qubit)\n","\n","\n","  # 4. Resetting all the extra qubits for the next iteration.\n","  # Need to include the specific ancillas used for each check\n","  for i in range(len(disagree_list)):\n","    undo_disagree_check_4c(oracle, \n","                           disagree_list[i][0], \n","                           disagree_list[i][1], \n","                           check_qubits[i])\n","\n","  \n","  return oracle"],"metadata":{"id":"gIgrvtdFsGuT"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #5**\n","\n","Now, solve the problem from the last exercise of Part 2.1.\n","\n","As a reminder, it is the problem of coloring 4 countries such that the first 3 are in the same arrangement as Exercise #5, but are now bordered on all sides by the last country:\n","\n","**&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;<font size=\"6\">Country 3</font>**\n","\n","**<font size=\"6\">Country 3</font> &ensp;| Country 0 | Country 1 | &ensp;<font size=\"6\">Country 3</font>**\n","\n","**&ensp;&ensp;&ensp;<font size=\"6\">Country 3</font>&ensp;&ensp;&ensp;| Country 2 | &ensp;&ensp;&ensp;<font size=\"6\">Country 3</font>**\n","\n","**&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;<font size=\"6\">Country 3</font>**\n","\n","\n","<br>\n","\n","This means that:\n","* Countries 0 and 1 must be colored differently.\n","* Countries 0 and 2 must be colored differently.\n","* Countries 0 and 3 must be colored differently.\n","* Countries 1 and 2 must be colored differently.\n","* Countries 1 and 3 must be colored differently.\n","* Countries 2 and 3 must be colored differently.\n","* Any other pair of countries can be colored the same or differently since they do not border each other."],"metadata":{"id":"6cx9ujSus201"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"7NQkTfQ1s201"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3, 4, 5, 6, 7]\n","check_qubits = [8, # COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ [[0, 1], [2, 3]],\n","                  # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"XsykX1GWs201"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"0YtP3QsZs202"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"5TVvLa9qs202"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["---\n","### **Part 2.3: Beyond Coloring**\n","\n","\n","Now that we have found a faster way to solve the 4 Coloring problem, let's explore applications of this algorithm beyond the Coloring problem itself. In particular, we will look at **scheduling problems** framed as follows:\n","\n","> Given a schedule of flying routes and $k$ airplanes that are available to fly, create an assignment of airplanes to flights and timeslots.\n","\n","<br>\n","\n","\n","For example the following table shows $k = 4$ planes and 4 total routes to be assigned a plane:\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** |\n","|------------------|----------------------------|-------------------------------------|\n","| **9 am**         | Route 0    | Route 1             |\n","| **12 pm**        | Route 2    | Route 3             |\n","\n","\n","<br>\n","\n","Two possible solutions to this specific problem are:\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** |\n","|------------------|----------------------------|-------------------------------------|\n","| **9 am**         | Airplane 0                 | Airplane 1                          |\n","| **12 pm**        | Airplane 2                 | Airplane 3                          |\n","\n","\n","<br>\n","\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** |\n","|------------------|----------------------------|-------------------------------------|\n","| **9 am**         | Airplane 0                 | Airplane 1                          |\n","| **12 pm**        | Airplane 2                 | Airplane 0                          |\n","\n","\n","\n","<br>\n","\n","Most importantly, we can use Graph Coloring to solve this problem! This just requires thinking of the problem as follows:\n","* Instead of $k$ colors, we have $k$ airplanes.\n","* Instead of borders, we have restrictions based on the fact that each airplane can only fly one route at a time. In particular, this means:\n","  * Any airplanes taking off at the same time must be different.\n","  * An airplane can be used for multiple routes, but only if it has landed after any previous flights. So, the takeoff times and route times must be considered."],"metadata":{"id":"63dW93hin233"}},{"cell_type":"markdown","source":["#### **Exercise #1**\n","\n","Let's solve the problem given above and restated here:\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** |\n","|------------------|----------------------------|-------------------------------------|\n","| **9 am**         | Route 0    | Route 1             |\n","| **12 pm**        | Route 2    | Route 3             |\n","\n","<br>\n","\n","Since there are 4 possible planes to use, this is fundamentally a 4 Coloring Problem. So, we can use our Grover solver from above.\n","\n","The key to doing this is encoding the restrictions correctly:\n","* Route 0 and Route 1 must use different planes since they take off at the same time.\n","* Route 0 and Route 2 must use different planes since the plane flying Route 0 will not have time to return to Boston for Route 2.\n","* Route 1 and Route 2 must use different planes since the plane flying Route 1 will still be in the air when Route 2 is meant to start.\n","* Route 1 and Route 3 must use different planes for the same reason.\n","* Route 2 and 3 must use different planes since they take off at the same time.\n","* The only acceptable reuse of a plane is for Route 0 and 3 since the plane flying Route 0 will have been able to land in DC before Route 3 takes off."],"metadata":{"id":"6aP2VRjoubnY"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"Anei_CUKubnY"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [0, 1, 2, 3, 4, 5, 6, 7]\n","check_qubits = [8, # COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ [[0, 1], [2, 3]],\n","                  # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"gxQ1AWEKubnZ"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"s76Wz4d_ubnZ"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"13n5chryubnZ"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #2**\n","\n","Now, let's solve a bigger problem:\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** |\n","|-------------------|----------------------------|---------------------------------|\n","| **9 am**          | Route 0                    | Route 1                         |\n","| **12 pm**         | Route 2                    | Route 3                         |\n","| **3 pm**          | Route 4                    | Route 5                         |\n","\n","<br>\n","\n","The restrictions are the same as above, but now include:\n","* Route 1 and Route 4 must use different planes since the plane flying Route 1 will have just landed in Los Angeles and so cannot takeoff from Boston.\n","* Route 1 and Route 5 must use different planes for the same reason.\n","* Route 2 and Route 3 must use different planes since they take off at the same time.\n","* Route 2 and Route 4 must use different planes since the plane flying Route 2 will not have time to return to Boston for Route 4.\n","* Route 3 and Route 4 must use different planes since the plane flying Route 3 will still be in the air when Route 4 is meant to start.\n","* Route 3 and Route 5 must use different planes for the same reason.\n","* Route 4 and 5 must use different planes since they take off at the same time.\n","\n","<br>\n","\n","**NOTE**: The size of the problem and the fact there's multiple correct solutions means this problem may take a long time to run and, even more so, to solve well. As such it is ok if you do not get perfect results for this problem. Rather, we leave it to you to continue on after completing the project notebook to determine a way to get around these problems. This could include:\n","* Using a more efficient simulator.\n","* Considering if any variables can be removed from the problem. For instance, a Route that cannot overlap with *any* other Route can be assigned a plane and then both that Route and plane can be completely removed from the problem (meaning it is now a 3 Coloring Problem).\n","* Redefining the way we use Grover's algorithm."],"metadata":{"id":"QWHqRYy4y7JU"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"a6ynlEFcy7JY"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [# COMPLETE THIS LINE\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"rGdg7-ggy7JY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"PI_0vPuFy7JY"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"Nh6nuaIBy7JY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### **Exercise #3**\n","\n","Now, apply what you have learned so far to solving this problem:\n","\n","| **Time \\| Route** | **Boston to DC (2 hours)** | **DC to Los Angeles (6 hours)** | **DC to Boston (2 hours)** |\n","|-------------------|----------------------------|---------------------------------|----------------------------|\n","| **9 am**          | Route 0                    | Route 1                         | Route 2                    |\n","| **12 pm**         | Route 3                    | Route 4                         | Route 5                    |"],"metadata":{"id":"e0rq0t8B77VX"}},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"1DLtNtx-77VY"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [# COMPLETE THIS LINE\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"cKHmSWDk77VY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"N3nzLwgK77VY"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"XdpONF9X77VY"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **1. Define the problem.**\n","\n","Complete the code below to define this specific problem."],"metadata":{"id":"sGKvCSnr-iwu"}},{"cell_type":"code","source":["# DEFINE THE VARIABLES\n","variable_qubits = [# COMPLETE THIS LINE\n","check_qubits = [# COMPLETE THIS LINE\n","output_qubit = # COMPLETE THIS LINE\n","disagree_list = [ # COMPLETE THIS CODE\n","                 ]\n","\n","\n","# CREATE THE PREP AND ORACLE CIRCUITS\n","prep = graph_color_prep(variable_qubits)\n","oracle = graph_color_oracle_4c(disagree_list, variable_qubits, check_qubits, output_qubit)\n","\n","\n","# DEFINE THE AmplificationProblem\n","def check_disagreement(state): return check_disagree_list_general_4c(state, disagree_list)\n","\n","problem = AmplificationProblem(oracle, \n","                               state_preparation = prep,\n","                               objective_qubits = variable_qubits,\n","                               is_good_state = check_disagreement\n","                               )"],"metadata":{"id":"GhOSC-ER-iwu"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["##### **2. Solve the problem.**"],"metadata":{"id":"ssO9Jcng-iwu"}},{"cell_type":"code","source":["grover = Grover(iterations = 0, quantum_instance = Aer.get_backend('qasm_simulator'))\n","results = grover.amplify(problem)\n","\n","plot_results(results, check_disagreement)"],"metadata":{"id":"mRK4UoSp-iwu"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["## **Wrapping Up**\n","\n","*Congratulations!* You have built and used a way to solve the 4 Coloring Graph Problem using Grover's algorithm. This means you can technically now use Grover's algorithm to solve *all* Graph Coloring Problems! Furthermore, you have seen how to turn a very different sounding problem into a 4 coloring problem so that you can use this same algorithm.\n","\n","To wrap up, please make sure to write a summary of the concepts covered here, including answers to the following questions:\n","\n","1. When using Grover's algorithm, we do not get good results for too few *or* too many iterations. Rather, there is a \"sweet spot\" (a balanced number of iterations) right in the middle. Why is this?\n","2. How and why does having *multiple* correct answers change the number of iterations needed for Grover's algorithm?\n","3. The best classical algorithm that guarantees solutions to the 4 coloring problem has a Big-O complexity of $O(1.7272^n)$ where $n$ is the number of Countries to be colored (or Routes to be assigned planes). How does Grover's algorithm compare to this run time?"],"metadata":{"id":"BFajMb7xEL0B"}},{"cell_type":"markdown","metadata":{"id":"BF1dNzrLntod"},"source":["# End of Lab\n","\n","---\n","\n","© 2023 The Coding School, All rights reserved"]}]}