0
$\begingroup$

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?

$\endgroup$

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.