In the previous series, I gave the detailed explanation of the QAOA Algorithm with MaxCut problem for understanding followed by the workflow of the QAOA Algorithm. You can check both the articles at : <ul><li>QAOA explained with Maxcut problem : <a href="https://medium.com/mdr-inc/qaoa-explained-with-max-example-632a3f101f12" rel="noopener noreferrer" target="_blank">https://medium.com/mdr-inc/qaoa-explained-with-max-example-632a3f101f12</a></li><li>Workflow(QAOA Algorithm) : <a href="https://medium.com/mdr-inc/workflow-qaoa-algorithm-220049c1b51a" rel="noopener noreferrer" target="_blank">https://medium.com/mdr-inc/workflow-qaoa-algorithm-220049c1b51a</a></li></ul> Here, we will discuss solving Maxcut problem using QAOA programmed in Blueqat which is an open source python library for Quantum Computer. Python(ver 3.6+) is required for using the library. You can install it by using pip. <pre class="ql-syntax" spellcheck="false">pip install blueqat
</pre> <h2>The Maxcut problem</h2> The aim of Maxcut is to maximize the numbers of edges in a graph that are “cut” by given vertices into two sets.<img src="https://pro.blueqat.com/public/uploads/1602470102012.png"/>Here we divided the graph into two sets with the vertices 1 and 3 in one set and the vertices 0 and 2 in the other set. Looking at the figure we can see that the maximum number of vertices connecting these two sets are 4. In general sense, Consider a graph with n vertices and m edges which we call “the clauses”. The objective function being :<img src="https://pro.blueqat.com/public/uploads/1602470102015.png"/>where C counts the number of edges cut. Cα(z)=1 when one vertex in the α edge resides in one set and the other edge belongs to the other set. If both the vertices belong to the same set, then Cα(z)=0. The above problem being a NP-complete problem cannot be solved in polynomial time, so our best possible hope for a polynomial time algorithm is using approximation. We need to find a partition z which is gives a Cα(z) closest to the maximum possible value. We represent the bit string using z=z1…..zn, where zᵢ=0 is belongs to one set and zᵢ=1 if it belongs to the other set. For example in the above diagram we see that the value of the objective fucntion is 4 with 0 and 2 vertices belonging to one set and 1 and 3 vertices belonging to the other set. z=1010 is one solution for the above problem. <h2>Creating a circuit for QAOA :</h2> We will be implementing a circuit for QAOA using unitary gates to find the best possible approximate solution to the Maxcut Problem. We will be representing the partition using the computational basis |z&gt; where z belongs to {0,1}. The objective function will be the operators acting on the partition :<img src="https://pro.blueqat.com/public/uploads/1602470102017.png"/>where (j,k) vertices connect the α edge. Here Cα will have a value 1 only if j and k belong to different measurement on the z axis. The summation over all the edges will give us the objective function to be maximized. We start with taking a uniform superposition of the n qubit basis state :|ψ&gt; = ∑ Ai |z&gt;, where Ai is the uniform amplitude over the normalised superpositioned state. The |ψ&gt; state being:<img src="https://pro.blueqat.com/public/uploads/1602470102019.png"/>We aim to create a distribution of the bitstring states which being measured in the z basis will give the maximum probabaility for the Maxcut partition bitstring. Using the 2p angle parameters γ=γ1γ2….γn, β=β1β2….βn applying the series of the unitary gates on the state <h2>|γ,β&gt; = U(B,β)U(C,γ)p……U(B,β)U(C,γ)₂U(B,β)U(C,γ)₁|ψ&gt;.</h2> where the operators have the form : <img src="https://pro.blueqat.com/public/uploads/1602470102022.png"/>In easy words we create p steps for the above parametrized gates. The U(C,γ) gate can be constructed using a CNOT gate with j qubit as the control bit and k qubit being the target qubit followed by a Rz rotation about angle γ on the k qubit followed by another CNOT gate with the same control and target qubit. For the U(B,β) gate, we can construct a circuit which has Rx rotation about angle 2β on all the vertex qubits. <img src="https://pro.blueqat.com/public/uploads/1602470102024.png"/>The expectation value of the objective function being &lt;γ,β|C|γ,β&gt;. We use classical otimization like we did in the VQE algorithm before over the circuit parameters γ and β. The QAOA algorithm will try to evolve the initital state into the plane of the bitstring with the maximum partition. To get started we first import the libraries needed for the program : <pre class="ql-syntax" spellcheck="false">from blueqat import Circuit
import numpy as np
from scipy.optimize import minimize
</pre> We define the graph using the list graph and the number of qubits(vertices) being n. <pre class="ql-syntax" spellcheck="false">n=4
graph=[(0,1),(0,3),(1,2),(2,3)]
</pre> We are taking the graph in the above diagram as an example. Next we define the Unitary operators U(C,γ) acting on all the edges and the U(B,β) acting on the respective qubits (vertices). <pre class="ql-syntax" spellcheck="false">def U_C(state,gamma):
 for edge in graph:
 j=edge[0]
 k=edge[1]
 state.cx[j,k]
 state.rz(gamma)[k]
 state.cx[j,k]def U_B(state,beta):
 for i in range(n):
 state.rx(beta*2)[i]
</pre> Next we define the function for the state preparation where we take the Hadamard of the all the qubit states to create the initial state |ψ&gt; and we use the above operators U_C and U_B as ansatz. <pre class="ql-syntax" spellcheck="false">def state_preparation(state,gamma,beta):
 state.h[:]
 for i in range(steps):
 U_C(state,gamma[i])
 U_B(state,beta[i])
 return state
</pre> We now write the function for calculating the expectation value of the operator given the above parametrized states. The objective function being :<img src="https://pro.blueqat.com/public/uploads/1602470102028.png"/>where Cα(z) = 1/2 (I - σᶻⱼ⊗ σᶻᴋ ). We need to find the expecation value of σᶻⱼ⊗ σᶻᴋ which is being used in each term of the objective function. We take the number of shots being 1000. Below we see the function performing the respective task : <pre class="ql-syntax" spellcheck="false">def exp_val(state,edge):
 shots=1000
 c=state.run(shots=shots)
 expval=0
 for i in c:
 if (i[edge[0]]==&#39;0&#39; and i[edge[1]]==&#39;0&#39;) or (i[edge[0]]==&#39;1&#39; and i[edge[1]]==&#39;1&#39;):
 expval+=c[i]/shots
 
 else:
 expval-=c[i]/shots
 
 return expval
</pre> Here we use the formulation of finding the expectation value in the similar way as we did for the VQE problem <a href="https://medium.com/mdr-inc/vqe-example-using-blueqat-5764bc3ff0a3" rel="noopener noreferrer" target="_blank">here</a>.Now we define the main Maxcut function which brings together all these above functions needed to perform the task of getting the optimal Objective function. Here we sum over the expectaion value of the Objective function over the edges (j,k) and return the maximum value for the objective fucntion. We use a trick here. We perform a maximization of C by minimizing −C. <pre class="ql-syntax" spellcheck="false">def max_cut(params):
 gamma=[]
 beta=[]
 for i in range(len(params)):
 if i%2==0:
 gamma.append(params[i])
 else:
 beta.append(params[i])
 state=Circuit(n)
 circ=state_preparation(state,gamma,beta)
 circ.m[:]
 print(circ.run(shots=1000))
 obj=0
 for edge in graph:
 obj=obj - 0.5 * (1 - exp_val(circ,edge))
 return obj
</pre> Finally we optimize the objective over the angle parameters γ and β and even print the distribution of the bitstrings print(circ.run(shots=1000)) as stated in the above code. For the optimization we use the Scipy minimize function similar to the one we used in the VQE Problem. <pre class="ql-syntax" spellcheck="false">steps=2
init_params = 0.01 * np.random.rand(2,2)tol_val=1e-2 # The tolerance value for the optimization procedureresult=minimize(max_cut,init_params, method=&#34;Powell&#34; , tol=tol_val)print(f&#39;The Objective after optimization is {-result.fun}&#39;)
</pre> The output generated being (the last few steps of optimization): <pre class="ql-syntax" spellcheck="false">Counter({&#39;0101&#39;: 355, &#39;1010&#39;: 336, &#39;1011&#39;: 39, &#39;0010&#39;: 37, &#39;0001&#39;: 37, &#39;1110&#39;: 37, &#39;1101&#39;: 34, &#39;1000&#39;: 33, &#39;0111&#39;: 31, &#39;0100&#39;: 29, &#39;0000&#39;: 15, &#39;1111&#39;: 10, &#39;1001&#39;: 4, &#39;1100&#39;: 1, &#39;0110&#39;: 1, &#39;0011&#39;: 1})Counter({&#39;0101&#39;: 442, &#39;1010&#39;: 391, &#39;0011&#39;: 36, &#39;1100&#39;: 30, &#39;0110&#39;: 26, &#39;1001&#39;: 23, &#39;1000&#39;: 9, &#39;1110&#39;: 8, &#39;0001&#39;: 6, &#39;0000&#39;: 5, &#39;0010&#39;: 5, &#39;1011&#39;: 5, &#39;0100&#39;: 5, &#39;1101&#39;: 4, &#39;0111&#39;: 3, &#39;1111&#39;: 2})Counter({&#39;1010&#39;: 500, &#39;0101&#39;: 495, &#39;1100&#39;: 1, &#39;0111&#39;: 1, &#39;1011&#39;: 1, &#39;1101&#39;: 1, &#39;1000&#39;: 1})Counter({&#39;1010&#39;: 504, &#39;0101&#39;: 491, &#39;0011&#39;: 3, &#39;0110&#39;: 1, &#39;1001&#39;: 1})Counter({&#39;0101&#39;: 515, &#39;1010&#39;: 481, &#39;1100&#39;: 2, &#39;0011&#39;: 1, &#39;1001&#39;: 1})Counter({&#39;1010&#39;: 511, &#39;0101&#39;: 488, &#39;0011&#39;: 1})Counter({&#39;1010&#39;: 506, &#39;0101&#39;: 488, &#39;1000&#39;: 2, &#39;0110&#39;: 1, &#39;1100&#39;: 1, &#39;0010&#39;: 1, &#39;1001&#39;: 1})Counter({&#39;0000&#39;: 222, &#39;1111&#39;: 221, &#39;0110&#39;: 127, &#39;0011&#39;: 109, &#39;1001&#39;: 109, &#39;1100&#39;: 106, &#39;1010&#39;: 49, &#39;0101&#39;: 40, &#39;1011&#39;: 5, &#39;0001&#39;: 4, &#39;0010&#39;: 3, &#39;1101&#39;: 2, &#39;1110&#39;: 1, &#39;0100&#39;: 1, &#39;0111&#39;: 1})Counter({&#39;1010&#39;: 503, &#39;0101&#39;: 486, &#39;1100&#39;: 3, &#39;1110&#39;: 2, &#39;0011&#39;: 2, &#39;1001&#39;: 2, &#39;1101&#39;: 1, &#39;0110&#39;: 1})Counter({&#39;0101&#39;: 541, &#39;1010&#39;: 455, &#39;0011&#39;: 2, &#39;0100&#39;: 1, &#39;0010&#39;: 1})Counter({&#39;0000&#39;: 278, &#39;1111&#39;: 247, &#39;1100&#39;: 103, &#39;0011&#39;: 102, &#39;0110&#39;: 96, &#39;1001&#39;: 89, &#39;0101&#39;: 39, &#39;1010&#39;: 30, &#39;0001&#39;: 4, &#39;1000&#39;: 3, &#39;0111&#39;: 2, &#39;1101&#39;: 2, &#39;1011&#39;: 2, &#39;0100&#39;: 1, &#39;1110&#39;: 1, &#39;0010&#39;: 1})Counter({&#39;0101&#39;: 180, &#39;1010&#39;: 160, &#39;0011&#39;: 124, &#39;0110&#39;: 122, &#39;1001&#39;: 116, &#39;1100&#39;: 114, &#39;0000&#39;: 92, &#39;1111&#39;: 65, &#39;1000&#39;: 6, &#39;1011&#39;: 5, &#39;0111&#39;: 4, &#39;1110&#39;: 4, &#39;1101&#39;: 3, &#39;0100&#39;: 3, &#39;0010&#39;: 2})Counter({&#39;0101&#39;: 510, &#39;1010&#39;: 481, &#39;0011&#39;: 2, &#39;1001&#39;: 2, &#39;1100&#39;: 1, &#39;0110&#39;: 1, &#39;0001&#39;: 1, &#39;1101&#39;: 1, &#39;1011&#39;: 1})Counter({&#39;0101&#39;: 518, &#39;1010&#39;: 476, &#39;0010&#39;: 3, &#39;1100&#39;: 2, &#39;0110&#39;: 1})Counter({&#39;1010&#39;: 515, &#39;0101&#39;: 484, &#39;1000&#39;: 1})Counter({&#39;1010&#39;: 499, &#39;0101&#39;: 496, &#39;0110&#39;: 2, &#39;0011&#39;: 1, &#39;1001&#39;: 1, &#39;0001&#39;: 1})Counter({&#39;1111&#39;: 173, &#39;0000&#39;: 166, &#39;0101&#39;: 94, &#39;1010&#39;: 81, &#39;1000&#39;: 50, &#39;0100&#39;: 47, &#39;1100&#39;: 47, &#39;1110&#39;: 46, &#39;0111&#39;: 45, &#39;1001&#39;: 43, &#39;1101&#39;: 43, &#39;0011&#39;: 38, &#39;0010&#39;: 35, &#39;0110&#39;: 33, &#39;1011&#39;: 31, &#39;0001&#39;: 28})Counter({&#39;0000&#39;: 359, &#39;1111&#39;: 332, &#39;0110&#39;: 37, &#39;0100&#39;: 29, &#39;0001&#39;: 29, &#39;1000&#39;: 25, &#39;0111&#39;: 25, &#39;0011&#39;: 24, &#39;1011&#39;: 22, &#39;0010&#39;: 22, &#39;1001&#39;: 22, &#39;1110&#39;: 19, &#39;1101&#39;: 17, &#39;1100&#39;: 17, &#39;0101&#39;: 11, &#39;1010&#39;: 10})Counter({&#39;1010&#39;: 526, &#39;0101&#39;: 471, &#39;1000&#39;: 1, &#39;1101&#39;: 1, &#39;0011&#39;: 1})Counter({&#39;0101&#39;: 279, &#39;1010&#39;: 248, &#39;1001&#39;: 55, &#39;1100&#39;: 48, &#39;0000&#39;: 47, &#39;0011&#39;: 43, &#39;0110&#39;: 42, &#39;1111&#39;: 35, &#39;0001&#39;: 34, &#39;1110&#39;: 30, &#39;0111&#39;: 26, &#39;0100&#39;: 25, &#39;1101&#39;: 25, &#39;1011&#39;: 24, &#39;0010&#39;: 22, &#39;1000&#39;: 17})Counter({&#39;0101&#39;: 398, &#39;1010&#39;: 386, &#39;0100&#39;: 27, &#39;1110&#39;: 25, &#39;0001&#39;: 22, &#39;1101&#39;: 19, &#39;0011&#39;: 17, &#39;0111&#39;: 17, &#39;1011&#39;: 16, &#39;1001&#39;: 16, &#39;0010&#39;: 15, &#39;0110&#39;: 12, &#39;1100&#39;: 9, &#39;1000&#39;: 9, &#39;0000&#39;: 6, &#39;1111&#39;: 6})Counter({&#39;0101&#39;: 516, &#39;1010&#39;: 482, &#39;1001&#39;: 1, &#39;0110&#39;: 1})Counter({&#39;0101&#39;: 509, &#39;1010&#39;: 486, &#39;0011&#39;: 2, &#39;0110&#39;: 1, &#39;1100&#39;: 1, &#39;1101&#39;: 1})Counter({&#39;1010&#39;: 467, &#39;0101&#39;: 439, &#39;0110&#39;: 14, &#39;1100&#39;: 13, &#39;0011&#39;: 12, &#39;1001&#39;: 11, &#39;1011&#39;: 9, &#39;0100&#39;: 8, &#39;1101&#39;: 7, &#39;1000&#39;: 7, &#39;1110&#39;: 4, &#39;0111&#39;: 4, &#39;0001&#39;: 2, &#39;0010&#39;: 2, &#39;0000&#39;: 1})Counter({&#39;0101&#39;: 517, &#39;1010&#39;: 466, &#39;1001&#39;: 5, &#39;0110&#39;: 3, &#39;0001&#39;: 3, &#39;1100&#39;: 2, &#39;1011&#39;: 1, &#39;0010&#39;: 1, &#39;0100&#39;: 1, &#39;1000&#39;: 1})Counter({&#39;1010&#39;: 511, &#39;0101&#39;: 483, &#39;1100&#39;: 3, &#39;1001&#39;: 1, &#39;0011&#39;: 1, &#39;0110&#39;: 1})Counter({&#39;1010&#39;: 500, &#39;0101&#39;: 493, &#39;1001&#39;: 4, &#39;0011&#39;: 1, &#39;1100&#39;: 1, &#39;0111&#39;: 1})Counter({&#39;1010&#39;: 513, &#39;0101&#39;: 485, &#39;0010&#39;: 1, &#39;1001&#39;: 1})Counter({&#39;1010&#39;: 170, &#39;0101&#39;: 167, &#39;0000&#39;: 100, &#39;1100&#39;: 94, &#39;0110&#39;: 91, &#39;1111&#39;: 89, &#39;1001&#39;: 87, &#39;0011&#39;: 80, &#39;1011&#39;: 23, &#39;1101&#39;: 19, &#39;1110&#39;: 18, &#39;0010&#39;: 15, &#39;0100&#39;: 14, &#39;1000&#39;: 14, &#39;0111&#39;: 10, &#39;0001&#39;: 9})Counter({&#39;1010&#39;: 500, &#39;0101&#39;: 483, &#39;1101&#39;: 4, &#39;0110&#39;: 3, &#39;1011&#39;: 3, &#39;1001&#39;: 2, &#39;0111&#39;: 2, &#39;1000&#39;: 1, &#39;0100&#39;: 1, &#39;0001&#39;: 1})Counter({&#39;0101&#39;: 508, &#39;1010&#39;: 485, &#39;1001&#39;: 2, &#39;0110&#39;: 2, &#39;0011&#39;: 2, &#39;1110&#39;: 1})Counter({&#39;1010&#39;: 136, &#39;0101&#39;: 133, &#39;0110&#39;: 123, &#39;0000&#39;: 118, &#39;1100&#39;: 111, &#39;0011&#39;: 102, &#39;1111&#39;: 99, &#39;1001&#39;: 98, &#39;1000&#39;: 13, &#39;0111&#39;: 13, &#39;1101&#39;: 12, &#39;1011&#39;: 10, &#39;0001&#39;: 9, &#39;1110&#39;: 9, &#39;0100&#39;: 8, &#39;0010&#39;: 6})Counter({&#39;0101&#39;: 322, &#39;1010&#39;: 289, &#39;1000&#39;: 45, &#39;1011&#39;: 35, &#39;0100&#39;: 33, &#39;1110&#39;: 33, &#39;0111&#39;: 29, &#39;0001&#39;: 29, &#39;1100&#39;: 28, &#39;0000&#39;: 25, &#39;0110&#39;: 25, &#39;0010&#39;: 25, &#39;1101&#39;: 24, &#39;0011&#39;: 20, &#39;1111&#39;: 19, &#39;1001&#39;: 19})Counter({&#39;1010&#39;: 507, &#39;0101&#39;: 484, &#39;0011&#39;: 2, &#39;1100&#39;: 2, &#39;1001&#39;: 2, &#39;0100&#39;: 1, &#39;0111&#39;: 1, &#39;0001&#39;: 1})Counter({&#39;1010&#39;: 499, &#39;0101&#39;: 497, &#39;0110&#39;: 2, &#39;1001&#39;: 1, &#39;1110&#39;: 1})Counter({&#39;0101&#39;: 476, &#39;1010&#39;: 451, &#39;1000&#39;: 15, &#39;0111&#39;: 11, &#39;1101&#39;: 9, &#39;0001&#39;: 8, &#39;0100&#39;: 8, &#39;1011&#39;: 7, &#39;1110&#39;: 6, &#39;0010&#39;: 6, &#39;0011&#39;: 2, &#39;1001&#39;: 1})Counter({&#39;0101&#39;: 515, &#39;1010&#39;: 474, &#39;1001&#39;: 3, &#39;0111&#39;: 2, &#39;0001&#39;: 1, &#39;0010&#39;: 1, &#39;1000&#39;: 1, &#39;0011&#39;: 1, &#39;1011&#39;: 1, &#39;0100&#39;: 1})The Objective after optimization is 3.995
</pre> We see that the optimal Objective is C=4. So we are getting a very good approximation ratio here.We can also see the parametrized angles in each step by printing out gamma and beta in the max_cut function. Here we use steps=2 which give us a better result for the Objective function and the also a very good final distribution for the bitstrings. On using step=1 we get the objective fucntion to be approx 3 with high probabilities for 1010 and 0101. You can find the complete code at my github here. <a href="https://github.com/Grandgrv/Maxcut-QAOA-using-Blueqat" rel="noopener noreferrer" target="_blank">Github</a> References :<ul><li>Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv1411.4028.</li><li><a href="https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf" rel="noopener noreferrer" target="_blank">https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf</a></li></ul>

Understanding Maxcut Problem(QAOA) with Blueqat

Gaurav Singh