{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "SzKwuqYESWwm" }, "source": [ "##### Copyright 2021 The Cirq Developers" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "cellView": "form", "id": "4yPUsdJxSXFq" }, "outputs": [], "source": [ "# @title Licensed under the Apache License, Version 2.0 (the \"License\");\n", "# you may not use this file except in compliance with the License.\n", "# You may obtain a copy of the License at\n", "#\n", "# https://www.apache.org/licenses/LICENSE-2.0\n", "#\n", "# Unless required by applicable law or agreed to in writing, software\n", "# distributed under the License is distributed on an \"AS IS\" BASIS,\n", "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n", "# See the License for the specific language governing permissions and\n", "# limitations under the License." ] }, { "cell_type": "markdown", "metadata": { "id": "J3Ov8gwSTnHB" }, "source": [ "# Binary Paintshop Problem with Quantum Approximate Optimization Algorithm" ] }, { "cell_type": "markdown", "metadata": { "id": "zC1qlUJoSXhm" }, "source": [ "\n", " \n", " \n", " \n", " \n", "
\n", " View on QuantumAI\n", " \n", " Run in Google Colab\n", " \n", " View source on GitHub\n", " \n", " Download notebook\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "6lnV5PlLnjLk" }, "outputs": [], "source": [ "from typing import Sequence, Tuple\n", "import numpy as np\n", "\n", "try:\n", " import cirq\n", "except ImportError:\n", " print(\"installing cirq...\")\n", " !pip install --quiet cirq\n", " print(\"installed cirq.\")\n", " import cirq\n", "\n", "import cirq_ionq as ionq" ] }, { "cell_type": "markdown", "metadata": { "id": "LlhpXxx8HtqX" }, "source": [ "## Binary Paintshop Problem\n", "\n", "\n", "Assume an automotive paint shop and a random, but fixed sequence of 2*n cars. Each car has a identical partner that only differs in the color it has to be painted." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "kvMfI5pPoJ-N" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[4 2 9 0 0 4 3 7 5 6 5 3 8 9 8 7 1 2 6 1]\n" ] } ], "source": [ "CAR_PAIR_COUNT = 10\n", "car_sequence = np.random.permutation([x for x in range(CAR_PAIR_COUNT)] * 2)\n", "print(car_sequence)" ] }, { "cell_type": "markdown", "metadata": { "id": "YfL2r-WWOXrD" }, "source": [ " The task is to paint the cars such that in the end for every pair of cars one is painted in red and the other in blue. The objective of the following minimization procedure is to minimize the number of color changes in the paintshop. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Q3UfXJND3qF1" }, "outputs": [], "source": [ "def color_changes(paint_bitstring: Sequence[int], car_sequence: Sequence[int]) -> int:\n", " \"\"\"Count the number of times the color changes if the robots\n", " paint each car in car_sequence according to paint_bitstring,\n", " which notes the color for the first car in each pair.\n", "\n", " Args:\n", " paint_bitstring: A sequence that determines the color to\n", " paint the first car in pair i. For example, 0 for blue\n", " and nonzero for red.\n", " car_sequence: A sequence that determines which cars are\n", " paired together\n", "\n", " Returns:\n", " Count of the number of times the robots change the color\n", " \"\"\"\n", " color_sequence = []\n", " painted_once = set()\n", " for car in car_sequence:\n", " if car in painted_once:\n", " # paint the other color for the second car in the pair\n", " color_sequence.append(not paint_bitstring[car])\n", " else:\n", " # paint the noted color for the first car in the pair\n", " color_sequence.append(paint_bitstring[car])\n", " painted_once.add(car)\n", " paint_change_counter = 0\n", " # count the number of times two adjacent cars differ in color\n", " for color0, color1 in zip(color_sequence, color_sequence[1:]):\n", " if color0 != color1:\n", " paint_change_counter += 1\n", " return paint_change_counter" ] }, { "cell_type": "markdown", "metadata": { "id": "xF4t6p5NOhCE" }, "source": [ " If two consecutive cars in the sequence are painted in different colors the robots have to rinse the old color, clean the nozzles and flush in the new color. This color change procedure costs time, paint, water and ultimately costs money, which is why we want to minimize the number of color changes. However, a rearrangement of the car sequence is not at our disposal (because of restrictions that are posed by the remainig manufacturing processes), but we can decide once we reach the first car of each car pair which color to paint the pair first. When we have chosen the color for the first car the other car has to be painted in the other respective color. Obvious generalizations exist, for example more than two colors and groups of cars with more than 2 cars where it is permissible to exchange colors, however for demonstration purposes it suffices to consider the here presented binary version of the paintshop problem. It is NP-hard to solve the binary paintshop problem exactly as well as approximately with an arbitrary performance guarantee. A performance guarantee in this context would be a proof that an approximation algorithm never gives us a solution with a number of color changes that is more than some factor times the optimal number of color changes. This is the situation where substantial quantum speedup can be assumed (c.f. [Quantum Computing in the NISQ era and beyond](https://arxiv.org/abs/1801.00862)). The quantum algorithm presented here can deliver, on average, better solutions than all polynomial runtime heuristics specifically developed for the paintshop problem in constant time (constant query complexity) (c.f. [Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm](https://arxiv.org/abs/2011.03403))." ] }, { "cell_type": "markdown", "metadata": { "id": "5c6HZHMsUBAc" }, "source": [ "## Spin Glass \n", "To be able to solve the binary paintshop problem with the Quantum Approximate Optimization Algorithm (QAOA) we need to translate the problem to a spin glass problem. Interestingly, that is possible with no spatial overhead, i.e. the spin glass has as many spins as the sequence has car pairs. The state of every spin represents the color we paint the respective first car in the seqence of every car pair. Every second car is painted with the repsective other color. The interactions of the spin glass can be deduced proceeding through the fixed car sequence: If two cars are adjacent to each other and both of them are either the first or the second car in their respective car pairs we can add a ferromagnetic interaction to the spin glass in order to penalize the color change between these two cars. If two cars are next to each other and one of the cars is the first and the other the second in their respective car pairs we have to add a antiferromagnetic interaction to the spin glass in order to penalize the color change because in this case the color for the car that is the second car in its car pair is exactly the opposite. All color changes in the car sequence are equivalent which is why we have equal magnitude ferromagnetic and antiferromagnetic interactions and additionally we choose unit magnitude interactions." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "hr7TT_nq5aOP" }, "outputs": [], "source": [ "def spin_glass(car_sequence: Sequence[int]) -> Sequence[Tuple[int, int, int]]:\n", " \"\"\"Assign interactions between adjacent cars.\n", "\n", " Assign a ferromagnetic(1) interaction if both elements of the pair are\n", " the first/second in their respective pairs. Otheriwse, assign an antiferromagnetic(-1)\n", " interaction. Yield a tuple with the two paired cars followed by the\n", " chosen interaction.\n", " \"\"\"\n", " ferromagnetic = -1\n", " antiferromagnetic = 1\n", " appeared_already = set()\n", " for car0, car1 in zip(car_sequence, car_sequence[1:]):\n", " if car0 == car1:\n", " continue\n", " if car0 in appeared_already:\n", " appeared_already.add(car0)\n", " if car1 in appeared_already:\n", " yield car0, car1, ferromagnetic\n", " else:\n", " yield car0, car1, antiferromagnetic\n", " else:\n", " appeared_already.add(car0)\n", " if car1 in appeared_already:\n", " yield car0, car1, antiferromagnetic\n", " else:\n", " yield car0, car1, ferromagnetic" ] }, { "cell_type": "markdown", "metadata": { "id": "6x3QEHTrYGyM" }, "source": [ "## Quantum Approximate Optimization Algorithm\n", "We want to execute a one block version of the QAOA circuit for the binary\n", "paintshop instance with p = 1 on a trapped-ion\n", "quantum computer of IonQ. This device is composed of 11 fully connected qubits with average single- and two-qubit fidelities of 99.5% and 97.5% respectively ([Benchmarking an 11-qubit quantum computer](https://www.nature.com/articles/s41467-019-13534-2)).\n", "As most available quantum hardware, trapped ion\n", "quantum computers only allow the application of gates\n", "from a restricted native gate set predetermined by the\n", "physics of the quantum processor. To execute an arbitrary gate, compilation of the desired gate into available gates is required. For trapped ions, a generic native\n", "gate set consists of a parameterized two-qubit rotation, the Molmer Sorensen gate,\n", "$R_\\mathrm{XX}(\\alpha)=\\mathrm{exp}[-\\mathrm{i}\\alpha \\sigma_\\mathrm{x}^{(i)}\\sigma_\\mathrm{x}^{(j)}/2]$ and a parametrized single qubit rotation:\n", "\n", "$R(\\theta,\\phi)=\\begin{pmatrix}\n", "\\cos{(\\theta/2)} & -\\mathrm{i}\\mathrm{e}^{-\\mathrm{i}\\phi}\\sin{(\\theta/2)} \\\\-\\mathrm{i}\\mathrm{e}^{\\mathrm{i}\\phi}\\sin{(\\theta/2)} & \\cos{(\\theta/2)} \n", "\\end{pmatrix}$\n", "\n", "QAOA circuits employ parametrized two body $\\sigma_z$ rotations, $R_\\mathrm{ZZ}(\\gamma)=\\mathrm{exp}[-i\\gamma \\sigma_\\mathrm{z}^{(i)}\\sigma_\\mathrm{z}^{(j)}]$. To circumvent a compilation overhead and optimally leverage the Ion Trap, we inject pairs of Hadamard gates $H H^{\\dagger} = 1$ for every qubit in between the two body $\\sigma_z$ rotations. This means we are able to formulate the phase separator entirely with Molmer Sorensen gates. To support this, the QAOA circuit starts in the state where all qubits are in the groundstate $\\left| 0\\right\\rangle$ instead of the superposition of all computational basis states $\\left| + \\right\\rangle$," ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "uensYoJ1tUpB" }, "outputs": [], "source": [ "def phase_separator(\n", " gamma: float, qubit_register: Sequence[cirq.Qid], car_sequence: Sequence[int]\n", ") -> Sequence[cirq.Operation]:\n", " \"\"\"Yield a sequence of Molmer Sorensen gates to implement a\n", " phase separator over the ferromagnetic/antiferromagnetic\n", " interactions between adjacent cars, as defined by spin_glass\n", " \"\"\"\n", " for car_pair0, car_pair1, interaction in spin_glass(car_sequence):\n", " yield cirq.ms(interaction * gamma).on(\n", " qubit_register[car_pair0], qubit_register[car_pair1]\n", " )\n", "\n", "\n", "qubit_register = cirq.LineQubit.range(CAR_PAIR_COUNT)\n", "circuit = cirq.Circuit([phase_separator(0.1, qubit_register, car_sequence)])" ] }, { "cell_type": "markdown", "metadata": { "id": "5dnVhwjUk3GT" }, "source": [ "Because we replaced the two body $\\sigma_z$ rotations with Molmer Sorensen gates we also have to adjust the mixer slightly to account for the injected Hadamard gates." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "WSo8TGlOwgko" }, "outputs": [], "source": [ "def mixer(beta: float, qubit_register: Sequence[cirq.Qid]) -> Iterator[cirq.Operation]:\n", " \"\"\"Yield a QAOA mixer of RX gates, modified by adding RY gates first,\n", " to account for the additional Hadamard gates.\n", " \"\"\"\n", " yield cirq.ry(np.pi / 2).on_each(qubit_register)\n", " yield cirq.rx(beta - np.pi).on_each(qubit_register)" ] }, { "cell_type": "markdown", "metadata": { "id": "pQps4f3qLJ94" }, "source": [ "To find the right parameters for the QAOA circuit, we have to assess the quality of the solutions for a given set of parameters. To this end, we execute the QAOA circuit with fixed parameters 100 times and calculate the average number of color changes." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "3BkHML3qxcC4" }, "outputs": [], "source": [ "def average_color_changes(\n", " parameters: Tuple[float, float],\n", " qubit_register: Sequence[cirq.Qid],\n", " car_sequence: Sequence[int],\n", ") -> float:\n", " \"\"\"Calculate the average number of color changes over all measurements of\n", " the QAOA circuit, aross `repetitions` many runs, for provided parameters\n", " beta and gamma.\n", "\n", " Args:\n", " parameters: tuple of (`beta`, `gamma`), the two parameters for the QAOA circuit\n", " qubit_register: A sequence of qubits for the circuit to use.\n", " car_sequence: A sequence that determines which cars are paired together.\n", "\n", " Returns:\n", " A float average number of color changes over all measurements.\n", " \"\"\"\n", " beta, gamma = parameters\n", " repetitions = 100\n", " circuit = cirq.Circuit()\n", " circuit.append(phase_separator(gamma, qubit_register, car_sequence))\n", " circuit.append(mixer(beta, qubit_register))\n", " circuit.append(cirq.measure(*qubit_register, key=\"z\"))\n", " results = service.run(circuit, repetitions=repetitions)\n", " avg_cc = 0\n", " for paint_bitstring in results.measurements[\"z\"]:\n", " avg_cc += color_changes(paint_bitstring, car_sequence) / repetitions\n", " return avg_cc" ] }, { "cell_type": "markdown", "metadata": { "id": "d2ydfRBrLrnl" }, "source": [ "We optimize the average number of color changes by adjusting the parameters with scipy.optimzes function minimize. The results of these optimsation runs strongly depend on the random starting values we choose for the parameters, which is why we restart the optimization procedure for different starting parameters 10 times and take the best performing optimized parameters." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "xXPCgWMaSPqJ" }, "outputs": [ { "data": { "text/plain": [ "7.840000000000001" ] }, "execution_count": 17, "metadata": { "tags": [] }, "output_type": "execute_result" } ], "source": [ "from scipy.optimize import minimize\n", "\n", "service = cirq.Simulator()\n", "beta, gamma = np.random.rand(2)\n", "average_cc = average_color_changes([beta, gamma], qubit_register, car_sequence)\n", "optimization_function = lambda x: average_color_changes(x, qubit_register, car_sequence)\n", "for _ in range(10):\n", " initial_guess = np.random.rand(2)\n", " optimization_result = minimize(\n", " optimization_function, initial_guess, method=\"SLSQP\", options={\"eps\": 0.1}\n", " )\n", " average_cc_temp = average_color_changes(\n", " optimization_result.x, qubit_register, car_sequence\n", " )\n", " if average_cc > average_cc_temp:\n", " beta, gamma = optimization_result.x\n", " average_cc = average_cc_temp\n", "average_cc" ] }, { "cell_type": "markdown", "metadata": { "id": "y0tJ2GErNa7w" }, "source": [ "Note here that the structure of the problem graphs of the binary paintshop problem allow for an alternative technique to come up with good parameters independent of the specifics of the respective instance of the problem: [Training the quantum approximate optimization algorithm without access to a quantum processing unit](https://iopscience.iop.org/article/10.1088/2058-9565/ab8c2b)" ] }, { "cell_type": "markdown", "metadata": { "id": "WoBQG2f2L8HC" }, "source": [ "Once the parameters are optimised, we execute the optimised QAOA circuit 100 times and output the solution with the least color changes.\n", "Please replace `` with your IonQ API key and `` with the API endpoint." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "lfUmwcxdo79w" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The minimal number of color changes found by level-1 QAOA is: 6\n", "The first cars of the car pairs have to be painted with [0 1 0 0 0 0 0 0 0 0], with index i representing the paint of the first car on pair i.\n", "The other car in pair i is painted with the second color.\n" ] } ], "source": [ "repetitions = 100\n", "circuit = cirq.Circuit()\n", "circuit.append(phase_separator(gamma, qubit_register, car_sequence))\n", "circuit.append(mixer(beta, qubit_register))\n", "circuit.append(cirq.measure(*qubit_register, key=\"z\"))\n", "service = ionq.Service(\n", " remote_host=\"\", api_key=\"\", default_target=\"qpu\"\n", ")\n", "results = service.run(circuit, repetitions=repetitions)\n", "best_result = CAR_PAIR_COUNT\n", "for paint_bitstring in results.measurements[\"z\"]:\n", " result = color_changes(paint_bitstring, car_sequence)\n", " if result < best_result:\n", " best_result = result\n", " best_paint_bitstring = paint_bitstring\n", "print(f\"The minimal number of color changes found by level-1 QAOA is: {best_result}\")\n", "print(\n", " f\"The car pairs have to be painted according to {best_paint_bitstring}, with index i representing the paint of the first car of pair i.\"\n", ")\n", "print(f\" The other car in pair i is painted the second color.\")" ] }, { "cell_type": "markdown", "metadata": { "id": "ngLJ66wRPuh3" }, "source": [ "Note here, that in a future production environment the optimization and execution phase of the QAOA should be merged, i.e. we output in the end the best performing sample gathered during the training phase of the QAOA circuit. For educational purposes, we separated here the training and the evaluation phase of the QAOA." ] } ], "metadata": { "colab": { "collapsed_sections": [], "name": "binary_paintshop.ipynb", "toc_visible": true }, "kernelspec": { "display_name": "Python 3", "name": "python3" } }, "nbformat": 4, "nbformat_minor": 0 }