{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# This cell is added by sphinx-gallery\n# It can be customized to whatever you like\n%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Intro to QAOA\n=============\n\n*Author: Jack Ceroni. Posted: 18 Nov 2020. Last updated: 11 Jan 2021.*\n\nThe Quantum Approximate Optimization Algorithm (QAOA) is a\nwidely-studied method for solving combinatorial optimization problems on\nNISQ devices. The applications of QAOA are broad and far-reaching, and\nthe performance of the algorithm is of great interest to the quantum\ncomputing research community.\n\n![](../demonstrations/qaoa_module/qaoa_circuit.png){width=\"90%\"}\n\nThe goal of this tutorial is to introduce the basic concepts of QAOA and\nto guide you through PennyLane's built-in QAOA functionality. You will\nlearn how to use time evolution to establish a connection between\nHamiltonians and quantum circuits, and how to layer these circuits to\ncreate more powerful algorithms. These simple ingredients, together with\nthe ability to optimize quantum circuits, are the building blocks of\nQAOA. By focusing on the fundamentals, PennyLane provides general and\nflexible capabilities that can be tailored and refined to implement QAOA\nfor a wide variety of problems. In the last part of the tutorial, you\nwill learn how to bring these pieces together and deploy a complete QAOA\nworkflow to solve the minimum vertex cover problem. Let's get started! \ud83c\udf89\n\nCircuits and Hamiltonians\n-------------------------\n\nWhen considering quantum circuits, it is often convenient to define them\nby a series of quantum gates. But there are many instances where it is\nuseful to think of a quantum circuit in terms of a\n[Hamiltonian](https://en.wikipedia.org/wiki/Hamiltonian_(quantum_mechanics)).\nIndeed, gates are physically implemented by performing time evolution\nunder a carefully engineered Hamiltonian. These transformations are\ndescribed by the time evolution operator, which is a unitary defined as:\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$U(H, \\ t) \\ = \\ e^{-i H t / \\hbar}.$$\n\nThe time evolution operator is determined completely in terms of a\nHamiltonian $H$ and a scalar $t$ representing time. In fact, any unitary\n$U$ can be written in the form $e^{i \\gamma H}$, where $\\gamma$ is a\nscalar and $H$ is a Hermitian operator, interpreted as a Hamiltonian.\nThus, time evolution establishes a connection that allows us to describe\nquantum circuits in terms of Hamiltonians. \ud83e\udd2f\n\nIn general, implementing a quantum circuit that exactly exponentiates a\nHamiltonian with many non-commuting terms, i.e., a Hamiltonian of the\nform:\n\n$$H \\ = \\ H_1 \\ + \\ H_2 \\ + \\ H_3 \\ + \\ \\cdots \\ + \\ H_N,$$\n\nis very challenging. Instead, we can use the\n[Trotter-Suzuki](https://en.wikipedia.org/wiki/Lie_product_formula)\ndecomposition formula\n\n$$e^{A \\ + \\ B} \\ \\approx \\ \\Big(e^{A/n} e^{B/n}\\Big)^{n},$$\n\nto implement an *approximate* time-evolution unitary:\n\n$$U(H, t, n) \\ = \\ \\displaystyle\\prod_{j \\ = \\ 1}^{n}\n \\displaystyle\\prod_{k} e^{-i H_k t / n} \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ H \\\n = \\ \\displaystyle\\sum_{k} H_k,$$\n\nwhere $U$ approaches $e^{-i H t}$ as $n$ becomes larger.\n\n![](../demonstrations/qaoa_module/ham_circuit.png){width=\"70%\"}\n\nIn PennyLane, this is implemented using the\n\\~.pennylane.templates.ApproxTimeEvolution template. For example, let's\nsay we have the following Hamiltonian:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import pennylane as qml\n\nH = qml.Hamiltonian(\n [1, 1, 0.5],\n [qml.PauliX(0), qml.PauliZ(1), qml.PauliX(0) @ qml.PauliX(1)]\n)\nprint(H)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can implement the approximate time-evolution operator corresponding\nto this Hamiltonian:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"dev = qml.device('default.qubit', wires=2)\n\nt = 1\nn = 2\n\n@qml.qnode(dev)\ndef circuit():\n qml.templates.ApproxTimeEvolution(H, t, n)\n return [qml.expval(qml.PauliZ(i)) for i in range(2)]\n\nprint(qml.draw(circuit)())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Layering circuits\n=================\n\nThink of all the times you have copied a text or image, then pasted it\nrepeatedly to create many duplicates. This is also a useful feature when\ndesigning quantum algorithms! The idea of repetition is ubiquitous in\nquantum computing: from amplitude amplification in [Grover\u2019s\nalgorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm) to layers\nin [quantum neural\nnetworks](https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.1.033063)\nand [Hamiltonian\nsimulation](https://en.wikipedia.org/wiki/Hamiltonian_simulation),\nrepeated application of a circuit is a central tool in quantum\nalgorithms.\n\n![](../demonstrations/qaoa_module/repeat.png){width=\"100%\"}\n\nCircuit repetition is implemented in PennyLane using the\n\\~.pennylane.layer function. This method allows us to take a function\ncontaining either quantum operations, a template, or even a single\nquantum gate, and repeatedly apply it to a set of wires.\n\n![](../demonstrations/qaoa_module/qml_layer.png){width=\"90%\"}\n\nTo create a larger circuit consisting of many repetitions, we pass the\ncircuit to be repeated as an argument and specify the number of\nrepetitions. For example, let's say that we want to layer the following\ncircuit three times:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def circ(theta):\n qml.RX(theta, wires=0)\n qml.Hadamard(wires=1)\n qml.CNOT(wires=[0, 1])\n\n@qml.qnode(dev)\ndef circuit(param):\n circ(param)\n return [qml.expval(qml.PauliZ(i)) for i in range(2)]\n\nprint(qml.draw(circuit)(0.5))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We simply pass this function into the \\~.pennylane.layer function:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef circuit(params, **kwargs):\n qml.layer(circ, 3, params)\n return [qml.expval(qml.PauliZ(i)) for i in range(2)]\n\nprint(qml.draw(circuit)([0.3, 0.4, 0.5]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have learned how time evolution can be used to create circuits from\nHamiltonians, and how these can be layered to create longer circuits. We\nare now ready to explore QAOA.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"QAOA\n====\n\nThe quantum approximate optimization algorithm (QAOA) is a general\ntechnique that can be used to find approximate solutions to\ncombinatorial optimization problems, in particular problems that can be\ncast as searching for an optimal bitstring. QAOA consists of the\nfollowing steps:\n\n1. Define a *cost Hamiltonian* $H_C$ such that its ground state encodes\n the solution to the optimization problem.\n2. Define a *mixer Hamiltonian* $H_M$.\n3. Construct the circuits $e^{-i \\gamma H_C}$ and $e^{-i\\alpha H_M}$.\n We call these the *cost* and *mixer layers*, respectively.\n4. Choose a parameter $n\\geq 1$ and build the circuit\n\n $$U(\\boldsymbol\\gamma, \\ \\boldsymbol\\alpha) \\ = \\ e^{-i \\alpha_n H_M}\n e^{-i \\gamma_n H_C} \\ ... \\ e^{-i \\alpha_1 H_M} e^{-i \\gamma_1 H_C},$$\n\n consisting of repeated application of the cost and mixer layers.\n\n5. Prepare an initial state, apply\n $U(\\boldsymbol\\gamma,\\boldsymbol\\alpha)$, and use classical\n techniques to optimize the parameters.\n6. After the circuit has been optimized, measurements of the output\n state reveal approximate solutions to the optimization problem.\n\nIn summary, the starting point of QAOA is the specification of cost and\nmixer Hamiltonians. We then use time evolution and layering to create a\nvariational circuit and optimize its parameters. The algorithm concludes\nby sampling from the circuit to get an approximate solution to the\noptimization problem. Let's see it in action! \ud83d\ude80\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Minimum Vertex Cover with QAOA\n==============================\n\nOur goal is to find the [minimum vertex\ncover](https://en.wikipedia.org/wiki/Vertex_cover) of a graph: a\ncollection of vertices such that each edge in the graph contains at\nleast one of the vertices in the cover. Hence, these vertices \"cover\"\nall the edges \ud83d\udc4d. We wish to find the vertex cover that has the smallest\npossible number of vertices.\n\nVertex covers can be represented by a bit string where each bit denotes\nwhether the corresponding vertex is present in the cover. For example,\nthe bit string 01010 represents a cover consisting of the second and\nfourth vertex in a graph with five vertices.\n\n![](../demonstrations/qaoa_module/minvc.png){width=\"90%\"}\n\nTo implement QAOA with PennyLane, we first import the necessary\ndependencies:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from pennylane import qaoa\nimport numpy as np\nfrom matplotlib import pyplot as plt\nimport networkx as nx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We also define the four-vertex graph for which we want to find the\nminimum vertex cover:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"edges = [(0, 1), (1, 2), (2, 0), (2, 3)]\ngraph = nx.Graph(edges)\n\nnx.draw(graph, with_labels=True)\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are two minimum vertex covers of this graph: the vertices 0 and 2,\nand the vertices 1 and 2. These can be respectively represented by the\nbit strings 1010 and 0110. The goal of the algorithm is to sample these\nbit strings with high probability.\n\nThe PennyLane QAOA module has a collection of built-in optimization\nproblems, including minimum vertex cover. For each problem, you can\nretrieve the cost Hamiltonian as well as a recommended mixer\nHamiltonian. This makes it straightforward to obtain the Hamiltonians\nfor specific problems while still permitting the flexibility to make\nother choices, for example by adding constraints or experimenting with\ndifferent mixers.\n\nIn our case, the cost Hamiltonian has two ground states, $|1010\\rangle$\nand $|0110\\rangle$, coinciding with the solutions of the problem. The\nmixer Hamiltonian is the simple, non-commuting sum of Pauli-X operations\non each node of the graph:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"cost_h, mixer_h = qaoa.min_vertex_cover(graph, constrained=False)\n\nprint(\"Cost Hamiltonian\", cost_h)\nprint(\"Mixer Hamiltonian\", mixer_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A single layer of QAOA consists of time evolution under these\nHamiltonians:\n\n![](../demonstrations/qaoa_module/layer.png){width=\"90%\"}\n\nWhile it is possible to use \\~.pennylane.templates.ApproxTimeEvolution,\nthe QAOA module allows you to build the cost and mixer layers directly\nusing the functions \\~.pennylane.qaoa.cost\\_layer and\n\\~.pennylane.qaoa.mixer\\_layer, which take as input the respective\nHamiltonian and variational parameters:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def qaoa_layer(gamma, alpha):\n qaoa.cost_layer(gamma, cost_h)\n qaoa.mixer_layer(alpha, mixer_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are now ready to build the full variational circuit. The number of\nwires is equal to the number of vertices of the graph. We initialize the\nstate to an even superposition over all basis states. For this example,\nwe employ a circuit consisting of two QAOA layers:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"wires = range(4)\ndepth = 2\n\ndef circuit(params, **kwargs):\n for w in wires:\n qml.Hadamard(wires=w)\n qml.layer(qaoa_layer, depth, params[0], params[1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that \\~.pennylane.layer allows us to pass variational parameters\n`params[0]` and `params[1]` into each layer of the circuit. That's it!\nThe last step is PennyLane's specialty: optimizing the circuit\nparameters.\n\nThe cost function is the expectation value of $H_C$, which we want to\nminimize. We use the function \\~.pennylane.expval which returns the\nexpectation value of the Hamiltonian with respect to the circuit's\noutput state. We also define the device on which the simulation is\nperformed. We use the PennyLane-Qulacs plugin to run the circuit on the\nQulacs simulator:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"dev = qml.device(\"qulacs.simulator\", wires=wires)\n\n@qml.qnode(dev)\ndef cost_function(params):\n circuit(params)\n return qml.expval(cost_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we optimize the cost function using the built-in\n\\~.pennylane.GradientDescentOptimizer. We perform optimization for\nseventy steps and initialize the parameters:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"optimizer = qml.GradientDescentOptimizer()\nsteps = 70\nparams = [[0.5, 0.5], [0.5, 0.5]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that we set each of the initial parameters to $0.5$. For\ndemonstration purposes, we chose initial parameters that we know work\nfairly well, and don't get stuck in any local minima.\n\nThe choice of initial parameters for a variational circuit is usually a\ndifficult problem, so we won't linger on it too much in this tutorial,\nbut it is important to note that finding an initial set of parameters\nthat work well for a few toy problems often yields good results for more\ncomplex instances of the algorithm as well.\n\nNow, we can optimize the circuit:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for i in range(steps):\n params = optimizer.step(cost_function, params)\n\nprint(\"Optimal Parameters\")\nprint(params)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With the optimal parameters, we can now reconstruct the probability\nlandscape. We redefine the full QAOA circuit with the optimal\nparameters, but this time we return the probabilities of measuring each\nbitstring:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef probability_circuit(gamma, alpha):\n circuit([gamma, alpha])\n return qml.probs(wires=wires)\n\n\nprobs = probability_circuit(params[0], params[1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we can display a bar graph showing the probability of measuring\neach bitstring:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"plt.style.use(\"seaborn\")\nplt.bar(range(2 ** len(wires)), probs)\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The states $|6\\rangle \\ = \\ |0110\\rangle$ and\n$|10\\rangle \\ = \\ |1010\\rangle$ have the highest probabilities of being\nmeasured, just as expected!\n\n![](../demonstrations/qaoa_module/graph.png){width=\"90%\"}\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Customizing QAOA\n================\n\nQAOA is not one-size-fits-all when it comes to solving optimization\nproblems. In many cases, cost and mixer Hamiltonians will be very\nspecific to one scenario, and not necessarily fit within the structure\nof the pre-defined problems in the \\~.pennylane.qaoa submodule. Luckily,\none of the core principles behind the entire PennyLane library is\ncustomizability, and this principle hold true for QAOA submodule as\nwell!\n\nThe QAOA workflow above gave us two optimal solutions:\n$|6\\rangle = |0110\\rangle$ and $|10\\rangle = |1010\\rangle$. What if we\nadd a constraint that made one of these solutions \"better\" than the\nother? Let's imagine that we are interested in solutions that minimize\nthe original cost function, *but also colour the first and third\nvertices* $1$. A constraint of this form will favour $|10\\rangle$,\nmaking it the only true ground state.\n\nIt is easy to introduce constraints of this form in PennyLane. We can\nuse the \\~.pennylane.qaoa.edge\\_driver cost Hamiltonian to \"reward\"\ncases in which the first and last vertices of the graph are $0$:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"reward_h = qaoa.edge_driver(nx.Graph([(0, 2)]), ['11'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We then weigh and add the constraining term to the original minimum\nvertex cover Hamiltonian:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"new_cost_h = cost_h + 2 * reward_h"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that PennyLane allows for simple addition and multiplication of\nHamiltonian objects using inline arithmetic operations \u2795 \u2796 \u2716\ufe0f\u2797! Finally,\nwe can use this new cost Hamiltonian to define a new QAOA workflow:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def qaoa_layer(gamma, alpha):\n qaoa.cost_layer(gamma, new_cost_h)\n qaoa.mixer_layer(alpha, mixer_h)\n\ndef circuit(params, **kwargs):\n for w in wires:\n qml.Hadamard(wires=w)\n qml.layer(qaoa_layer, depth, params[0], params[1])\n\n@qml.qnode(dev)\ndef cost_function(params):\n circuit(params)\n return qml.expval(new_cost_h)\n\nparams = [[0.5, 0.5], [0.5, 0.5]]\n\nfor i in range(steps):\n params = optimizer.step(cost_function, params)\n\nprint(\"Optimal Parameters\")\nprint(params)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We then reconstruct the probability landscape with the optimal\nparameters:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef probability_circuit(gamma, alpha):\n circuit([gamma, alpha])\n return qml.probs(wires=wires)\n\nprobs = probability_circuit(params[0], params[1])\n\nplt.style.use(\"seaborn\")\nplt.bar(range(2 ** len(wires)), probs)\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Just as we expected, the $|10\\rangle$ state is now favoured over\n$|6\\rangle$!\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Conclusion\n==========\n\nYou have learned how to use the PennyLane QAOA functionality, while also\nsurveying some of the fundamental features that make the QAOA module\nsimple and flexible. Now, it's your turn to experiment with QAOA! If you\nneed some inspiration for how to get started:\n\n- Experiment with different optimizers and different devices. Which\n ones work the best?\n- Play around with some of the other built-in cost and\n mixer Hamiltonians.\n- Try making your own custom constraining terms. Is QAOA properly\n amplifying some bitstrings over others?\n\n![](../demonstrations/qaoa_module/qaoa_circuit.png){width=\"90%\"}\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.2"
}
},
"nbformat": 4,
"nbformat_minor": 0
}