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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.