<jupyter_start><jupyter_text>QAOA MAX CUTby <NAME> In this part of my reasearch I will touch the first application of the The Quantum Approximate Optimization Algorithm (QAOA) which is Maximum Cut problem (MAX CUT).The problem is to partition the nodes of a graph into two sets such that the number of edges connecting nodes in opposite sets (edges that are being "cut" by the division line of the sets) is maximized. Consider the example graphs below.I am given a graph with four nodes connected with each other through four edges, each vertex has been marked with numbers from zero through three. There are diferent ways I can cut the graph. My main goal is to find such a combination that would give me the maximum number of cuts of the edges. Let's consider case *A)*. In this case I would have only two cuts of the edges. Now, if I would cut as it shown in the case *B)*, the number of cuts would be four which is a maximum number I can have in this example.![picture](https://drive.google.com/uc?id=1FAcc9IN0HU3YhB4ReqcM93nfTMvkxJPj)Before we will dive deep inside the algorithm, let's discuss how we could potentialy represent the fact that two vertices of an edge are in opposite sets (blue set VS white set).  One of the ways of doing this is to use bitstring representation. Now, consider case *A)*, let `|1>` represent the fact the vertex is lying in the Blue color, `|0>` - that the vertex is in White color. Thus, for the case *A* we would have bitstring: `|1100>`. I will have a look at each of the edge and analyze its vertices.| Edge      |   (0, 1)   |  (0, 3)   |  (1, 2)   |   (2, 3) || :---      |  :---:     |   ---:    | ---:      | ----:    || Color     | Blue       | Blue/White| Blue/White|  White   || Cut       |     No     |   Yes     |  Yes      | No       |As you can see, the number of edges, vertices of which are in opposite sets, is two. I will introduce here a cost function ``` C(|z>) = 2 ``` which returns the number of cuts for the `|z>` graph.Let's analyze graph *B)* in the same way. The bitstring for this graph is `|0101>`.| Edge      |   (0, 1)   |  (0, 3)   |  (1, 2)   |   (2, 3) || :---      |  :---:     |   ---:    | ---:      | ----:    || Color     | Blue/White | Blue/White| Blue/White|Blue/White|| Cut       |     Yes    |   Yes     |  Yes      |   Yes    |In this case ``` C(|z>) = 4 ```.  Implementation of QAOA Max CutThe goal here is to find such a state vector (bitstring) of the quantum circuit that would maximize the cost (meaning number of cuts) `C(|z>)`. As discussed in the [A Quantum Approximate Optimization Algorithm](https://arxiv.org/pdf/1411.4028.pdf) and  [An Introduction toQuantum Optimization Approximation Algorithm](https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf), we can represent the whole graph and possible cuts through the quantum gates H, RX($\beta$),  RZ($\gamma$), CX, where ($\beta$, $\gamma$) are parameters which we have to optimize in order to receive the highest value of the cost function `C(|z>)`.Consider the example of the grapf below:```graph = [(0,1), (0,3), (1,2), (2,3)]```<jupyter_code># define graph
graph = [(0, 1), (0, 3), (1, 2), (2, 3)]

# More graphs to test on
# graph = [(0, 1), (0, 4), (1, 2), (1,4), (2, 3), (3,4)]
# graph = [(0, 1)]
# graph = [(0, 1), (0,2), (1,2)]

# find max number in the graph. Circuit size = max + 1
size = list(map(max, zip(*graph)))
cir_size = max(size) + 1<jupyter_output><empty_output><jupyter_text>Each pair of two numbers in the list represents an edge (e.g (0,1)), and each number in the pair represents a vertex of the graph (e.g. 0 and 1), or a qubit in the quantum circuit. The algorithm starts with putting all the qubits in the superposition state - we can do this by applying Hadamard gates on each of them.Now, let's discuss the role $(\beta, \gamma)$ parameters play in the QAOA Max Cut problem. First of all, I define two functions `UB_operator()` and `UC_operator()` which are going to depend on the said parameters.The `UC_operator` is defined as the following operation on qubits $j$ and $k$:$UC(j, k, \gamma) = e^{-i\gamma(I-\sigma_z^j\sigma_z^k)/2}$,where $\sigma_z = \begin{pmatrix}   1 & 0  \\  0 & -1 \end{pmatrix}$ - Pauli Z gate. This operation will be applied on every pair of $j$ and $k$ for which $(j, k)$ - edge of the graph.The `UB_operator` is defined as the following operation acting on each of the qubits:$UB(\beta) = \displaystyle\prod_{j=1}^{n}e^{-i\beta\sigma_x^j}$where $\sigma_x = \begin{pmatrix}   0 & 1  \\  1 & 0 \end{pmatrix}$ - Pauli X gate. Quantum circuit can be repsesented through $UC(j, k, \gamma)$ and $UB(\beta)$ as shown below:![](https://drive.google.com/uc?id=1buWO8d-aJIjaXX2CQXYeNUeibTqFUtIX)Using several transformations, we can represent both $UC(j, k, \gamma)$ and $UB(\beta)$ operators as combinations of the quantum gates defined in the `QCircuit` class.The `UC_operator` that acts on $j$ and $k$ with the angle $\gamma$ will be define as a sequence of three gates. Two of them are `CX` gates which take any of the two qubits, for example $j$ as a control gate, and $k$ - as a target. Third one is ` RZ` gate that rotates the target qubit $k$ on the given angle of $\gamma$.$UC(j, k, \gamma) = CX(j, k) * RZ(\gamma, k) * CX(j, k)$ Install frameworks, and import libraries<jupyter_code>!pip install tensornetwork jax jaxlib colorama qcircuit
from qcircuit import QCircuit as qc
import numpy as np
# unitary operator UC_operator with parameter gamma
# act on qubits whose corresponding vertices are joined by an edge in the graph
def UC_operator(gamma, circuit):
  """
    Apply CX, RZ quantum gates on circuit.
    Args:
      gamma: an angle in radians to turn the state vector around Z axis.
      circuit: an instance of the QCircuit class.
    Return:
      None.
  """
  for edge in graph:
      cont = edge[0]
      tar = edge[1]
      circuit.CX(control=[cont], target=tar)
      circuit.R(phi=gamma, target=tar)
      circuit.CX(control=[cont], target=tar)<jupyter_output><empty_output><jupyter_text>The UB_operator with the angle  𝛽  is defined through RX gate with the angle of  2𝛽 𝑈𝐵(𝛽)=𝑅𝑋(2𝛽,0),𝑅𝑋(2𝛽,1),...,𝑅𝑋(2𝛽,𝑛) , where  𝑛  is a number of qubits in the circuit.<jupyter_code># unitary operator UB_operator with parameter beta
#  act on individual qubit
def UB_operator(beta, circuit):
  """
    Apply RX quantum gate on circuit.
    Args:
      beta: an angle in radians to turn the state vector around X axis.
      circuit: an instance of the QCircuit class.
    Return:
      None.
  """
  for qbit in range(cir_size):
    circuit.RX(phi=2*beta, target=qbit)<jupyter_output><empty_output><jupyter_text>Being said, the quantum circuit below will represent the graph.![Max Cut Circuit](https://drive.google.com/uc?id=1ewXDlP473MhdtE3rou1iXyW4l04RcJ-W) *Important note: as we use the constant $e$ raised to the power of $iA$ for both of the operators, by the Euler's identity, they can be represented in terms of $cos$ and $sin$ fucntions. Because of that, both of my parameters - $\beta$ and $\gamma$ are periodical, means we don't have to check angles beyond [0, $2\pi$] for $\gamma$ and [0, $\pi$] for $\beta$ (as it is being multiplied by 2 when passed to the RX gate)*Now, when we have defined all of the operators, let's get back to the algorithm. After applying the Hadamard gates on all of the qubits, we iterate through each edge in the graph and apply `UC_operator` (CX, RZ). For example, if we take the first pair in the list `(0, 1)`, it means we have to apply CX on qubit zero and qubit one where controled is q0 and target - q1. Then we apply RZ gate on the target qubit (q1 in this case), and again CX gate. After we are done with each edge, we have to apply `UB_operator` (RX) on all qubits.After applying all the gates I will have the state vector and the bitstring assosiated with it. Analyzing the bitstring, we can now calculate the value of the cost function. The function `maxcut()` handles iteration through each edge in the graph. Since I have to find the maximum number of cuts, it is straightforward there exist a function which we can minimize, the function calls objective (`objective()`). The function will return minimized value for `ultimate_cost`:```ultimate_cost = ultimate_cost - cost ```Now, my last step is to initialize parameters $\beta$ and $\gamma$, iterate through the whole interval with a step, and find such values $(\beta, \gamma)$ that minimize the objective function.In short, steps for QAOA Max Cut:1.   Initialize parameters $\beta$ and $\gamma$ for RX and RZ gates, respectfully. Where $\beta = [0, \pi]$ and $\gamma = [0, 2\pi]$.2.   Bring the circuit to its superposition.3.   Constuct quantum circuit using *UC* and *UB* operators represented with CX, RX, and  RZ gates.4.   Get the bitstring and calculate the cost function.5.   Repeat steps from 1 to 4 to a number of times.<jupyter_code># build the quantum circuit
def q_circuit(gamma, beta, num_layers=1, edge=None):
  """
    Apply the sequences of UB and UC operations, get the bitstring
    of the final state, and calculate the counts of cuts.
    Args:
       gamma: an angle parameter for UC operator.
       beta: an angle parameter for UB operator.
       num_layers: numbers of layers to apply.
       edge: current edge in the graph.
    Return:
      cost: the value of the cost function (number of cuts).
  """

  # initialize quantum circuit
  circuit = qc.QCircuit(cir_size)

  # bring to the supperposition: apply the Hadamard gates
  for qbit in range(cir_size):
    circuit.H(target=qbit)
  
  UC_operator(gamma=gamma, circuit=circuit)
  UB_operator(beta=beta, circuit=circuit)
  
  # this part for the future implementations
  if edge is None:
    # measurement phase
    # print("in None")
    probab, bitstring = circuit.get_bitstring()
    return bitstring

  # apply Z gates on edges
  circuit.Z(target=edge[0])
  circuit.Z(target=edge[1])

  probab, bitstring = circuit.get_bitstring()
  
  # print("gama = ", gamma, "beta = ", beta, "max_probab = ", bitstring)
  bitstring = str(bitstring)
  if (bitstring[edge[0]] != bitstring[edge[1]]):
    cost = 1
  else:
    cost = 0

  return cost
def maxcut(num_of_layers=1):
  """
    Initialize beta and gamma parametes. Find such values of the parameters  
    that will minimize the objective function.
    Args:
       num_of_layers: number of layers to apply
    Return:
      Bitstring reflective maximum cut in the graph.
  """
  # print("layer = ", num_of_layers)
  
  def objective( params):
      ultimate_cost = 0
      gammas = params[0]
      betas = params[1]
      for edge in graph:
          # objective for the MaxCut problem
          c = q_circuit(gammas, betas, edge=edge, num_layers=num_of_layers)
          ultimate_cost -= c
      return ultimate_cost

  # initialize beta, gamma parameters.
  params = np.array([2*0.0*np.pi, 0.0*np.pi], dtype=np.float)

  # find optimal beta, gamma parameters
  min_cut = objective(params)
  gamma_min = 0
  beta_min = 0
  min_cut = 0
  for g in np.arange(0* np.pi, 2*np.pi, np.pi/10):
    for b in np.arange( 0, np.pi, np.pi/10):
      params[0] = g
      params[1] = b
      current_mincut = objective(params)
      if current_mincut < min_cut:
        min_cut = current_mincut
        gamma_min = g
        beta_min = b
  cut = q_circuit(gamma_min, beta_min, edge=None, num_layers=num_of_layers)
  return cut, min_cut
max_cut_str, obj = maxcut(1)
print("Max cut bitstring = ", max_cut_str)
print("Objective to minimize = ", obj)<jupyter_output>/usr/local/lib/python3.6/dist-packages/jax/lib/xla_bridge.py:123: UserWarning: No GPU/TPU found, falling back to CPU.
  warnings.warn('No GPU/TPU found, falling back to CPU.')
{'fraction_non_alphanumeric': 0.10570915004707696, 'fraction_numerical': 0.015235812719335787, 'mean_word_length': 3.5042405551272164, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 26, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '484860', 'license': 'Apache-2.0', 'n_tokens_mistral': 3802, 'n_tokens_neox': 3597, 'n_words': 1578, 'path': 'tutorials/QAOA_Max_Cut.ipynb', 'repo_name': 'MadhavJivrajani/QCircuit', 'size': '11687'}