# QAOA Circuit for MWIS

Hi thanks for taking a quick look!

I’ve got a question of how weights are implemented in the angles for gates in the QAOA.

I'm trying to solve the Maximum Weighted Independent Set Problem This is the problem as a binary optimisation: $$\max y\left(x_{1}, \ldots, x_{n}\right)=\sum_{i \in \mathrm{V}} c_{i} x_{i}-\sum_{(i,j) \in \mathrm{E}} J_{i j} x_{i} x_{j},$$

Where the first sum adds the weights the weight of the node $$c_{i}$$ only if the binary variable $$x_{i}$$ indicates it is in the set. The independence is assured by the sum over the edges, giving the penalty $$J_{ij}$$ if both nodes $$i$$ and $$j$$ are in the set. The necessary condition for the $$J_{ij}$$ is that it has to be greater than the smallest of the two node weights $$i$$ or $$j$$.

To convert this to a quantum Hamiltonian, we substitute in the standard Pauli-Z transformation, $$x_{i} = \frac{1}{2}(1-Z_{i})$$ giving:

$$H_c=\sum_{i \in \mathrm{V}}^{n} \frac{c_{i}}{2}(I-Z_{i}) +\sum_{i, j\ \in {E}}^{m} \frac{J_{i j}}{4}\left(I-Z_{i}\right)\left(I-Z_{j}\right) = \sum_{i \in \mathrm{V}}^{n} \frac{c_{i}}{2}(I-Z_{i}) - \sum_{i, j\ \in {E}}^{m}\frac{J_{i j}}{4}(I-Z_{i}-Z_{j}+Z_{i}Z_{j})$$

$$H_c= \sum_{i \in \mathrm{V}}^{n} \frac{c_{i}}{2}(I-Z_{i}) - \sum_{i, j\ \in {E}}^{m}\frac{J_{i j}}{4}(I+Z_{i}Z_{j})$$

Now we can cancel the constant terms to give: $$H_c= -\sum_{i \in \mathrm{V}}^{n} \frac{c_{i}}{2}Z_{i} - \sum_{i, j\ \in {E}}^{m}\frac{J_{i j}}{4}Z_{i}Z_{j} + const.$$

For QAOA, we put this $$H_c$$ into a unitary of form $$e^{-i \gamma H_{c}}$$.

The $$Z_{i}$$ and $$Z_{i}Z_{j}$$ terms commute, so we can split the unitaries into the form: $$\exp{\{ -i \gamma ( - \sum_{i \in \mathrm{V}}^{n} \frac{c_{i}}{2}Z_{i}) \}} \exp{\{ -i\gamma ( - \sum_{i, j\ \in {E}}^{m}\frac{J_{i j}}{4}Z_{i}Z_{j} )\}}$$.

Now I think we put through the minus signs and simplify. This means our cost operator now has these two parts.

The first for the node weight now looks like: $$\exp{\{ \frac{i \gamma}{2} \sum_{i \in \mathrm{V}}^{n} c_{i} Z_{i} \}} ,$$ where the minus sign has cancelled.

The second now looks like

$$\exp{\{ \frac{i \gamma}{4} \sum_{i, j\ \in {E}}^{m}J_{i j}Z_{i}Z_{j} \}}$$,

where the minus sign has again cancelled.

We know that gates wise, the single $$Z$$ term goes into an $$R_{z}$$ gate as so: $$e^{-ia Z t}=R_{z}(2 at)$$. Following through, this means that each qubit (representing the node $$i$$ with weight $$c_{i}$$) gets a gate of $$R_{z}(-\gamma c_{i})$$.

The double $$Z_{i}Z_{j}$$ are the same as MAXCUT and so are $$R_{z}$$ gates surrounded by two CNOTS controlled by the $$i$$th qubit. The gate is paramterised as so: $$R_{z}(-\gamma J_{ij}/2)$$.

The problem is that this approach doesn't seem to be working ! I've set $$J_{ij}$$ to a constant figure that is greater than all of the node weights but I'm having no luck.
Are there some in my logic?