{
"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": [
"Feedback-Based Quantum Optimization (FALQON)\n============================================\n\n*Authors: David Wakeham and Jack Ceroni. Posted: 21 May 2021. Last\nupdated: 21 May 2021.*\n\n------------------------------------------------------------------------\n\nWhile the [Quantum Approximate Optimization Algorithm\n(QAOA)](https://pennylane.ai/qml/demos/tutorial_qaoa_intro.html) is one\nof the best-known processes for solving combinatorial optimization\nproblems with quantum computers, it has a major drawback: convergence\nisn't guaranteed, as the optimization procedure can become \"stuck\" in\nlocal minima.\n\n![](../demonstrations/falqon/global_min_graph.png){width=\"70%\"}\n\nThis tutorial explores the **FALQON** algorithm introduced in [a recent\npaper by Magann et al.](https://arxiv.org/pdf/2103.08619.pdf) It is\nsimilar in spirit to QAOA, but uses iterative feedback steps rather than\na global optimization over parameters, avoiding the use of a classical\noptimizer.\n\nIn this demo, we will implement FALQON to solve the MaxClique problem in\ngraph theory, perform benchmarking, and combine FALQON with QAOA to\ncreate a powerful optimization procedure.\n\n> **note**\n>\n> If you are not familiar with QAOA, we recommend checking out the\n>\n> : [Intro to QAOA\n> tutorial](https://pennylane.ai/qml/demos/tutorial_qaoa_intro.html),\n> since many of the same ideas carry over and will be used\n> throughout this demonstration.\n>\nTheory\n------\n\nTo solve a combinatorial optimization problem with a quantum computer, a\ntypical strategy is to encode the solution to the problem as the ground\nstate of a *cost Hamiltonian* $H_c$. Then, we use some procedure to\ndrive an initial state into the ground state of $H_c$. FALQON falls\nunder this broad scheme.\n\nConsider a quantum system governed by a Hamiltonian of the form\n$H = H_c + \\beta(t) H_d$. These kinds of Hamiltonians appear often in\nthe theory of [quantum\ncontrol](https://quantiki.org/wiki/quantum-control-theory), a field of\ninquiry which studies how a quantum system can be driven from one state\nto another. The choice of $\\beta(t)$ corresponds to a \"driving\nstrategy\", which partially determines how the system evolves with time.\n\nSuppose our objective is to drive some quantum system to the ground\nstate of $H_c$. It is a reasonable goal to construct a quantum control\nprocess such that the energy expectation $\\langle H_c \\rangle_t$\ndecreases with time:\n\n$$\\frac{d}{dt} \\langle H_c\\rangle_t = \\frac{d}{dt} \\langle \\psi(t)|H_c|\\psi(t)\\rangle = i \\beta(t)\\langle [H_d, H_c] \\rangle_t \\leq 0,$$\n\nwhere the product rule and [the Schr\u00f6dinger\nequation](https://en.wikipedia.org/wiki/Schr%C3%B6dinger_equation#Time-dependent_equation)\nare used to derive the above formula. If we pick\n$\\beta(t) = -\\langle i[H_d, H_c] \\rangle_t,$ so that\n\n$$\\frac{d}{dt} \\langle H_c\\rangle_t = -|\\langle i[H_d, H_c] \\rangle_t|^2 \\leq 0,$$\n\nthen $\\langle H_c \\rangle$ is guaranteed to strictly decrease, as\ndesired! Thus, if we evolve some initial state $|\\psi_0\\rangle$ under\nthe time evolution operator $U$ corresponding to $H$,\n\n$$U(T) = \\mathcal{T} \\exp \\Big[ -i \\displaystyle\\int_{0}^{T} H(t) \\ dt \\Big] \\approx \\mathcal{T} \\exp \\Big[ -i \\displaystyle\\sum_{k = 0}^{T/\\Delta t} H( k \\Delta t) \\Delta t \\Big],$$\n\nwhere $\\mathcal{T}$ is the [time-ordering\noperator](https://en.wikipedia.org/wiki/Path-ordering#Time_ordering) and\n$\\Delta t$ is some small time step, then the energy expectation will\nstrictly decrease, for a large enough value of $T$. This is exactly the\nprocedure used by FALQON to minimize $\\langle H_c \\rangle$. In general,\nimplementing a time evolution unitary in a quantum circuit is difficult,\nso we use a [Trotter-Suzuki\ndecomposition](https://en.wikipedia.org/wiki/Time-evolving_block_decimation#The_Suzuki%E2%80%93Trotter_expansion)\nto perform approximate time evolution. We then have\n\n$$U(T) \\approx \\mathcal{T} \\exp \\Big[ -i \\displaystyle\\sum_{k = 0}^{T/\\Delta t} H( k \\Delta t) \\Delta t \\Big] \\approx\n e^{-i\\beta_n H_d \\Delta t} e^{-iH_c \\Delta t} \\cdots e^{-i\\beta_1 H_d \\Delta t} e^{-iH_c \\Delta t} = U_d(\\beta_n) U_c \\cdots U_d(\\beta_1) U_c,$$\n\nwhere $n = T/\\Delta t$ and $\\beta_k = \\beta(k\\Delta t)$. For each layer\nof the time evolution, the value $\\beta_k$ is required. However,\n$\\beta_k$ is dependent on the state of the system at some time. Recall\nthat\n\n$$\\beta(t) = - \\langle \\psi(t) | i [H_d, H_c] | \\psi(t) \\rangle.$$\n\nWe let $A(t) := i\\langle [H_d, H_c] \\rangle_t$. Our strategy is to\nobtain the values $\\beta_k$ recursively, by finding the value of $A(t)$\nfor the **previous time step**. We then set\n\n$$\\beta_{k+1} = -A_k = -A(k\\Delta t).$$\n\nThis leads to the FALQON algorithm as a recursive process. On step $k$,\nwe perform the following three substeps:\n\n1. Prepare the state\n $|\\psi_k\\rangle = U_d(\\beta_k) U_c \\cdots U_d(\\beta_1) U_c|\\psi_0\\rangle$.\n2. Measure the expectation value\n $A_k = \\langle i[H_c, H_d]\\rangle_{k \\Delta t}$.\n3. Set $\\beta_{k+1} = -A_k$.\n\nWe repeat for all $k$ from $1$ to $n$, where $n$ is a hyperparameter. At\nthe final step we evaluate $\\langle H_c \\rangle$, which gives us an\napproximation for the ground state of $H_c$.\n\n![](../demonstrations/falqon/falqon.png){width=\"80%\"}\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Simulating FALQON with PennyLane\n================================\n\nTo begin, we import the necessary dependencies:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import pennylane as qml\nimport numpy as np\nfrom matplotlib import pyplot as plt\nfrom pennylane import qaoa as qaoa\nimport networkx as nx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this demonstration, we will be using FALQON to solve the [maximum\nclique (MaxClique)\nproblem](https://en.wikipedia.org/wiki/Clique_problem): finding the\nlargest complete subgraph of some graph $G$. For example, the following\ngraph's maximum clique is coloured in red:\n\n![](../demonstrations/falqon/max_clique.png){width=\"90%\"}\n\nWe attempt to find the maximum clique of the graph below:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"edges = [(0, 1), (1, 2), (2, 0), (2, 3), (1, 4)]\ngraph = nx.Graph(edges)\nnx.draw(graph, with_labels=True, node_color=\"#e377c2\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We must first encode this combinatorial problem into a cost Hamiltonian\n$H_c$. This ends up being\n\n$$H_c = 3 \\sum_{(i, j) \\in E(\\bar{G})} (Z_i Z_j - Z_i - Z_j) + \\displaystyle\\sum_{i \\in V(G)} Z_i,$$\n\nwhere each qubit is a node in the graph, and the states $|0\\rangle$ and\n$|1\\rangle$ represent whether the vertex has been marked as part of the\nclique, as is the case for [most standard QAOA encoding\nschemes](https://arxiv.org/abs/1709.03489). Note that $\\bar{G}$ is the\ncomplement of $G$: the graph formed by connecting all nodes that **do\nnot** share an edge in $G$.\n\nIn addition to defining $H_c$, we also require a driver Hamiltonian\n$H_d$ which does not commute with $H_c$. The driver Hamiltonian's role\nis similar to that of the mixer Hamiltonian in QAOA. To keep things\nsimple, we choose a sum over Pauli $X$ operations on each qubit:\n\n$$H_d = \\displaystyle\\sum_{i \\in V(G)} X_i.$$\n\nThese Hamiltonians come nicely bundled together in the PennyLane QAOA\nmodule:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"cost_h, driver_h = qaoa.max_clique(graph, constrained=False)\n\nprint(\"Cost Hamiltonian\")\nprint(cost_h)\nprint(\"Driver Hamiltonian\")\nprint(driver_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One of the main ingredients in the FALQON algorithm is the operator\n$i [H_d, H_c]$. In the case of MaxClique, we can write down the\ncommutator $[H_d, H_c]$ explicitly:\n\n$$[H_d, H_c] = 3 \\displaystyle\\sum_{k \\in V(G)} \\displaystyle\\sum_{(i, j) \\in E(\\bar{G})} \\big( [X_k, Z_i Z_j] - [X_k, Z_i]\n - [X_k, Z_j] \\big) + 3 \\displaystyle\\sum_{i \\in V(G)} \\displaystyle\\sum_{j \\in V(G)} [X_i, Z_j].$$\n\nThere are two distinct commutators that we must calculate, $[X_k, Z_j]$\nand $[X_k, Z_i Z_j]$. This is straightforward as we know exactly what\nthe [commutators of the Pauli\nmatrices](https://en.wikipedia.org/wiki/Pauli_matrices#Commutation_relations)\nare. We have:\n\n$$[X_k, Z_j] = -2 i \\delta_{kj} Y_k \\ \\ \\ \\text{and} \\ \\ \\ [X_k, Z_i Z_j] = -2 i \\delta_{ik} Y_k Z_j - 2i \\delta_{jk} Z_i Y_k,$$\n\nwhere $\\delta_{kj}$ is the [Kronecker\ndelta](https://en.wikipedia.org/wiki/Kronecker_delta). Therefore it\nfollows from substitution into the above equation and multiplication by\n$i$ that:\n\n$$i [H_d, H_c] = 6 \\displaystyle\\sum_{k \\in V(G)} \\displaystyle\\sum_{(i, j) \\in E(\\bar{G})} \\big( \\delta_{ki} Y_k Z_j +\n \\delta_{kj} Z_{i} Y_{k} - \\delta_{ki} Y_k - \\delta_{kj} Y_k \\big) + 6 \\displaystyle\\sum_{i \\in V(G)} Y_{i}.$$\n\nThis new operator has quite a few terms! Therefore, we write a short\nmethod which computes it for us, and returns a \\~.pennylane.Hamiltonian\nobject. Note that this method works for any graph:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def build_hamiltonian(graph):\n H = qml.Hamiltonian([], [])\n\n # Computes the complement of the graph\n graph_c = nx.complement(graph)\n\n for k in graph_c.nodes:\n # Adds the terms in the first sum\n for edge in graph_c.edges:\n i, j = edge\n if k == i:\n H += 6 * (qml.PauliY(k) @ qml.PauliZ(j) - qml.PauliY(k))\n if k == j:\n H += 6 * (qml.PauliZ(i) @ qml.PauliY(k) - qml.PauliY(k))\n # Adds the terms in the second sum\n H += 6 * qml.PauliY(k)\n\n return H\n\n\nprint(\"MaxClique Commutator\")\nprint(build_hamiltonian(graph))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now build the FALQON algorithm. Our goal is to evolve some\ninitial state under the Hamiltonian $H$, with our chosen $\\beta(t)$. We\nfirst define one layer of the Trotterized time evolution, which is of\nthe form $U_d(\\beta_k) U_c$. Note that we can use the\n\\~.pennylane.templates.ApproxTimeEvolution template:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def falqon_layer(beta_k, cost_h, driver_h, delta_t):\n qml.templates.ApproxTimeEvolution(cost_h, delta_t, 1)\n qml.templates.ApproxTimeEvolution(driver_h, delta_t * beta_k, 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We then define a method which returns a FALQON ansatz corresponding to a\nparticular cost Hamiltonian, driver Hamiltonian, and $\\Delta t$. This\ninvolves multiple repetitions of the \"FALQON layer\" defined above. The\ninitial state of our circuit is an even superposition:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def build_maxclique_ansatz(cost_h, driver_h, delta_t):\n def ansatz(beta, **kwargs):\n layers = len(beta)\n for w in dev.wires:\n qml.Hadamard(wires=w)\n qml.layer(\n falqon_layer,\n layers,\n beta,\n cost_h=cost_h,\n driver_h=driver_h,\n delta_t=delta_t\n )\n\n return ansatz\n\n\ndef expval_circuit(beta, measurement_h):\n ansatz = build_maxclique_ansatz(cost_h, driver_h, delta_t)\n ansatz(beta)\n return qml.expval(measurement_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we implement the recursive process, where FALQON is able to\ndetermine the values of $\\beta_k$, feeding back into itself as the\nnumber of layers increases. This is straightforward using the methods\ndefined above:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def max_clique_falqon(graph, n, beta_1, delta_t, dev):\n comm_h = build_hamiltonian(graph) # Builds the commutator\n cost_h, driver_h = qaoa.max_clique(graph, constrained=False) # Builds H_c and H_d\n cost_fn = qml.QNode(expval_circuit, dev) # The ansatz + measurement circuit is executable\n\n beta = [beta_1] # Records each value of beta_k\n energies = [] # Records the value of the cost function at each step\n\n for i in range(n):\n # Adds a value of beta to the list and evaluates the cost function\n beta.append(-1 * cost_fn(beta, measurement_h=comm_h)) # this call measures the expectation of the commuter hamiltonian\n energy = cost_fn(beta, measurement_h=cost_h) # this call measures the expectation of the cost hamiltonian\n energies.append(energy)\n\n return beta, energies"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that we return both the list of $\\beta_k$ values, as well as the\nexpectation value of the cost Hamiltonian for each step.\n\nWe can now run FALQON for our MaxClique problem! It is important that we\nchoose $\\Delta t$ small enough such that the approximate time evolution\nis close enough to the real time evolution, otherwise we the expectation\nvalue of $H_c$ may not strictly decrease. For this demonstration, we set\n$\\Delta t = 0.03$, $n = 40$, and $\\beta_1 = 0$. These are comparable to\nthe hyperparameters chosen in the original paper.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"n = 40\nbeta_1 = 0.0\ndelta_t = 0.03\n\ndev = qml.device(\"default.qubit\", wires=graph.nodes) # Creates a device for the simulation\nres_beta, res_energies = max_clique_falqon(graph, n, beta_1, delta_t, dev)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can then plot the expectation value of the cost Hamiltonian over the\niterations of the algorithm:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"plt.plot(range(n+1)[1:], res_energies)\nplt.xlabel(\"Iteration\")\nplt.ylabel(\"Cost Function Value\")\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The expectation value decreases!\n\nTo get a better understanding of the performance of the FALQON\nalgorithm, we can create a graph showing the probability of measuring\neach possible bit string. We define the following circuit, feeding in\nthe optimal values of $\\beta_k$:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef prob_circuit():\n ansatz = build_maxclique_ansatz(cost_h, driver_h, delta_t)\n ansatz(res_beta)\n return qml.probs(wires=dev.wires)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Running this circuit gives us the following probability distribution:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"probs = prob_circuit()\nplt.bar(range(2**len(dev.wires)), probs)\nplt.xlabel(\"Bit string\")\nplt.ylabel(\"Measurement Probability\")\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The bit string occurring with the highest probability is the state\n$|28\\rangle = |11100\\rangle$. This corresponds to nodes $0$, $1$, and\n$2$, which is precisely the maximum clique. FALQON has solved the\nMaxClique problem \ud83e\udd29.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"graph = nx.Graph(edges)\ncmap = [\"#00b4d9\"]*3 + [\"#e377c2\"]*2\nnx.draw(graph, with_labels=True, node_color=cmap)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Benchmarking FALQON\n===================\n\nAfter seeing how FALQON works, it is worth considering how well FALQON\nperforms according to a set of benchmarking criteria on a batch of\ngraphs. We generate graphs randomly using the [Erdos-Renyi\nmodel](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model),\nwhere we start with the complete graph on $n$ vertices and then keep\neach edge with probability $p$. We then find the maximum cliques on\nthese graphs using the [Bron-Kerbosch\nalgorithm](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm).\nTo benchmark FALQON, the relative error in the estimated minimum energy\n\n$$r_A = \\frac{\\langle H_C\\rangle - \\langle H_C\\rangle_\\text{min}}{|\\langle H_C\\rangle_\\text{min}|}$$\n\nmakes a good figure of merit.\n\nFinal results for $r_A$, along with $\\beta$, are plotted below, with the\nnumber of FALQON layers on the horizontal axis. We have averaged over\n$50$ random graphs per node size, for sizes $n = 6, 7, 8, 9$, with\nprobability $p = 0.1$ of keeping an edge. Running FALQON for $40$ steps,\nwith $\\Delta t = 0.01$, produces:\n\n![](../demonstrations/falqon/bench.png){width=\"60%\"}\n\nThe relative error decreases with the number of layers (as we expect\nfrom the construction) and graph size (suggesting the errors grows more\nslowly than the minimum energy). The exception is $n = 9$, where the\nstep size has become too large and the Trotter-Suzuki decomposition\nbreaks down. The rate of decrease also slows down. Even though the\nalgorithm will converge to the ground state, it won't always get there\nin a few time steps!\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Seeding QAOA with FALQON (Bird Seed \ud83e\udd85)\n======================================\n\n![](../demonstrations/falqon/bird_seed.png){width=\"90%\"}\n\nBoth FALQON and QAOA have unique benefits and drawbacks. While FALQON\nrequires no classical optimization and is guaranteed to decrease the\ncost function with each iteration, its circuit depth grows linearly with\nthe number of iterations. The benchmarking data also shows how the\nreduction in cost slows with each layer, and the additional burden of\ncorrectly tuning the time step. On the other hand, QAOA has a fixed\ncircuit depth, but does require classical optimization, and is therefore\nsubject to all of the drawbacks that come with probing a cost landscape\nfor a set of optimal parameters.\n\nQAOA and FALQON also have many similarities, most notably, their circuit\nstructure. Both involve alternating layers of time evolution operators\ncorresponding to a cost and a mixer/driver Hamiltonian. The FALQON paper\nraises the idea of combining FALQON and QAOA to yield a new optimization\nalgorithm that leverages the benefits of both. In this final section of\nthe tutorial, we will implement this procedure in PennyLane.\n\nSuppose we want to run a QAOA circuit of depth $p$. Our ansatz will be\nof the form\n\n$$U_{\\text{QAOA}} = e^{-i \\alpha_p H_m} e^{-i \\gamma_p H_c} \\cdots e^{-i \\alpha_1 H_m} e^{-i \\gamma_1 H_c},$$\n\nfor sets of parameters $\\{\\alpha_k\\}$ and $\\{\\gamma_k\\}$, which are\noptimized. If we run FALQON for $p$ steps, setting $H_d = H_m$, and use\nthe same cost Hamiltonian, we will end up with the following ansatz:\n\n$$U_{\\text{FALQON}} = e^{-i \\Delta t \\beta_p H_m} e^{-i \\Delta t H_c} \\cdots e^{-i \\Delta t \\beta_1 H_m} e^{-i \\Delta t H_c}.$$\n\nThus, our strategy is to initialize our QAOA parameters using the\n$\\beta_k$ values that FALQON yields. More specifically, we set\n$\\alpha_k = \\Delta t \\beta_k$ and $\\gamma_k = \\Delta t$. We then\noptimize over these parameters. The goal is that these parameters\nprovide QAOA a good place in the parameter space to begin its\noptimization.\n\nUsing the code from earlier in the demonstration, we can easily\nprototype this process. To illustrate the power of this new technique,\nwe attempt to solve MaxClique on a slightly more complicated graph:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"new_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (1, 4), (4, 5), (5, 2), (0, 6)]\nnew_graph = nx.Graph(new_edges)\nnx.draw(new_graph, with_labels=True, node_color=\"#e377c2\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now use the PennyLane QAOA module to create a QAOA circuit\ncorresponding to the MaxClique problem. For this demonstration, we set\nthe depth to $5$:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"depth = 5\ndev = qml.device(\"default.qubit\", wires=new_graph.nodes)\n\n# Creates the cost and mixer Hamiltonians\ncost_h, mixer_h = qaoa.max_clique(new_graph, constrained=False)\n\n# Creates a layer of QAOA\ndef qaoa_layer(gamma, beta):\n qaoa.cost_layer(gamma, cost_h)\n qaoa.mixer_layer(beta, mixer_h)\n\n# Creates the full QAOA circuit as an executable cost function\ndef qaoa_circuit(params, **kwargs):\n for w in dev.wires:\n qml.Hadamard(wires=w)\n qml.layer(qaoa_layer, depth, params[0], params[1])\n\n\n@qml.qnode(dev)\ndef qaoa_expval(params):\n qaoa_circuit(params)\n return qml.expval(cost_h)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now all we have to do is run FALQON for $5$ steps to get our initial\nQAOA parameters. We set $\\Delta t = 0.02$:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"delta_t = 0.02\n\nres, res_energy = max_clique_falqon(new_graph, depth-1, 0.0, delta_t, dev)\n\nparams = np.array([[delta_t for k in res], [delta_t * k for k in res]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we run our QAOA optimization procedure. We set the number of\nQAOA executions to $40$:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"steps = 40\n\noptimizer = qml.GradientDescentOptimizer()\n\nfor s in range(steps):\n params, cost = optimizer.step_and_cost(qaoa_expval, params)\n print(\"Step {}, Cost = {}\".format(s + 1, cost))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To conclude, we can check how well FALQON/QAOA solved the optimization\nproblem. We define a circuit which outputs the probabilities of\nmeasuring each bit string, and create a bar graph:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"@qml.qnode(dev)\ndef prob_circuit(params):\n qaoa_circuit(params)\n return qml.probs(wires=dev.wires)\n\nprobs = prob_circuit(params)\nplt.bar(range(2**len(dev.wires)), probs)\nplt.xlabel(\"Bit string\")\nplt.ylabel(\"Measurement Probability\")\nplt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The state $|112\\rangle = |1110000\\rangle$ occurs with highest\nprobability. This corresponds to nodes $0$, $1$, and $2$ of the graph,\nwhich is the maximum clique! We have successfully combined FALQON and\nQAOA to solve a combinatorial optimization problem \ud83c\udf89.\n\nReferences\n==========\n\nMagann, A. B., Rudinger, K. M., Grace, M. D., & Sarovar, M. (2021).\nFeedback-based quantum optimization. arXiv preprint\n[arXiv:2103.08619](https://arxiv.org/abs/2103.08619).\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
}