QAOA Workflow: contradictory information

Codebook
1

I’m confused by two seemingly contradictory steps in the QAOA workflow.

  • Define the mixer Hamiltonion. . . A common choice for H_m is … \sum{X_j}
  • Initialize the quantum system in the ground state of H_m which is usually the equal superposition state
\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n - 1} \ket{x}

which is equivalent to \ket{+}^{\otimes n} = H^{\otimes n}\ket{0}^{\otimes n}

But that’s not a ground state of H_m. The value of the Hamiltonian at that state n. This is the highest possible value for the Hamiltonian. We want each qubit to be in state \ket{-} so that the Hamiltonian will be -n, the lowest possible value.

Should we be adding a minus sign to the Hamiltonian. It appears that qp.qaoa.mixer_layer and qp.qaoa.cost_layer are the same code under the covers (except for error checking), so there’s no negation being added to the former under the covers.

What am I missing? Or does it just work anyway, even not starting in the ground state?

2

Hi @fyellin ,

You are correct that we need to flip the sign of the mixer Hamiltonian so that the equal superposition state is in fact the ground state. I think the mixer in qp.qaoa is defined without the minus sign so that you add it on your code. I think it’s a matter of convention more than anything else.

For unconstrained problems the standard choice (ignoring the sign) is H_M = \sum_i X_i. PennyLane has it built in: qp.qaoa.mixers.x_mixer.

However, we must flip the overall sign of H_M because the adiabatic theorem requires you to start in the ground state of the initial Hamiltonian, and |+⟩^{\otimes n} (what Hadamards prepare) is the ground state of -\sum_i X_i, not +\sum_i X_i. The mixer you should actually use is thus H_M = -\sum_i X_i.

You can write it in code as H_M = -qp.qaoa.x_mixer(range(n_bits))

I hope this clarifies things!

3

If nothing else, can the QAOA workflow in the cookbook be fixed? If you follow its instructions, you end up with the wrong starting state.

4

Oh no, thanks for pointing it out @fyellin ! We’ll make sure to fix it.

5

Hi @fyellin ,

My colleague David actually looked deeper into this and figured out why the standard mixer Hamiltonian is described with a positive sign instead of a negative one. It turns out that the variational parameters end up absorbing the negative sign.

We’ve added a note about this in the QAOA workflow section of the Codebook (on the theory section on the right-hand side).

Hopefully this can clarify the use of the positive signs instead of the negative ones.

Thanks again for your feedback on this!