• Members 3 posts
    Nov. 21, 2021, 1:17 a.m.

    I’m trying to understand how QAOA solves the MIS problem. In the original paper on QAOA (arxiv:1411.4028), section VII seems to talk about how constraints can be imposed on the problem by choosing the mixer hamiltonian appropriately. I don’t understand how exactly this works though, so if someone could explain the math behind this (or point me to a relevant resource), that would be really great.

  • Members 11 posts
    Nov. 21, 2021, 7:59 p.m.

    The paper phrases the maximum independent set problem as
    maximize $\sum z_j$
    subject to
    ${z_i}$ represents an independent subset.
    Here the string z belonging to the independent subset is the constraint, where $\sum z_j$ is the objective.
    Hence $C=\sum z_j$ is one of the Hamiltonian.
    The other Hamiltonian $B$ connects an independent set to another one with Hamming distance 1.

    For example, if a graph of 3 vertices (0,1,2) has edges between 0 and 1. The possible independent set will be ${000,100,010,001,101,010}$. So $B$ will satisfy
    $\langle 000|B|100\rangle=1$, $\langle 000|B|010\rangle=1$, etc.

    So applying $B$ is sort of like a quantum walk.

    The algorithm then proceeds by alternatively evolving between $B$ and $C$, starting from $|0...0\rangle$. starting from the ground state of $C$, to the ground state of $-B$, to the ground state of $-C$.

    I have no idea how $B$ can be constructed, as it is the flip operator restricted to the set of independent sets.


    Below are my wild guess on how to construct it.
    I suppose $B$ can be formally written as $B=(\sum \sigma_x) P$, where $P$ is the projection from all possible strings to the set of independent sets. If one has the original graph, one can construct a two-body Hamiltonian where there is interaction between vertices if there is an edge between them. Then the projection operator is simply the projection to the zero eigenspace of this Hamiltonian...

  • Members 3 posts
    Nov. 22, 2021, 2:09 a.m.

    @eltonjohn007 Thanks for the reply! The part where you mentioned that we go from the ground state of $C$ to the ground state of $-B$ and in turn to the ground state of $-C$ was really insightful. But I still have doubts about our choice of $B$.
    I drew out the matrix for $B$ from your example and one thing that made sense to me is that the last two rows and columns corresponding to $110$ and $111$ are filled with 0s and that this would be true for any positive power of $B$ as well.
    $$B=\begin{bmatrix}
    0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
    1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
    1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
    0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
    \end{bmatrix}$$
    Since $e^{-iB\beta}$ is the Identity plus a linear combination of powers of $B$ (Taylor series expansion), we can be sure that this operator will never take a legal bitstring to an illegal bitstring. But then why do we worry about the Hamming distance when defining $B$? What if, for example, I replaced $B$ with a matrix whose entries were $1$ everywhere except where the row or column corresponds to that of an illegal bitstring?
    $$B=\begin{bmatrix}
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
    \end{bmatrix}$$
    Would this work just as well? I’m fairly certain I’m missing something.

  • Members 11 posts
    Nov. 22, 2021, 9:52 a.m.

    The part about going from the ground state of $C$ to the ground state of $-B$ and then to the ground state of $-C$ is really the intuition behind the adiabatic version. The QAOA version will probably never hit the ground state of $-B$.

    You are right that in the simple example I gave, the second $B$ would also work in principle. $B$ is a transition matrix we construct. If you write $B$ in Pauli basis, your $B$ will involve higher order terms, which might be difficult to implement. If $B$ is to transition between states of Hamming distance 1, then it is much easier to implement, it will be just like $\sum \sigma_x$ restricted to the valid states.

    Again I do not have any idea how to implement this in practise, especially the part on how to restrict to the valid states.

  • Members 3 posts
    Nov. 22, 2021, 12:05 p.m.

    I see. So it's a matter of convenience in the math and subsequent implementation. Thanks a lot for your responses :)