# Reason behind choosing the invariant states for an operator which commutes with an adiabatic Hamiltonian

In the section 4.1 of Quantum Computation by Adiabatic Evolution, Farhi et al proposes a quantum adiabatic algorithm to solve the $2$-SAT problem on a ring. To compute the complexity of the algorithm the authors computed the energy gap between the ground and first excited states of the adiabatic Hamiltonian.

The adiabatic Hamiltonian is defined as $$\tilde{H} (s) = (1-s) \sum^n_{j=1}(1-\sigma^{(j)}_x) + s \sum^n_{j=1}\frac{1}{2} (1-\sigma^{(j)}_z \sigma^{(j+1)}_z )$$

To prove the correctness of the algorithm, the authors consider an operator which negates the value of the bits. $$G = \prod^n_{j=1}\sigma^{(j)}_x$$

Then on page 13, it is mentioned that $[G, \tilde{H}(s)] = 0$. The authors say the following.

Since $G |x = 0\rangle = |x = 0\rangle$ and $[G, \tilde{H}(s)] = 0$, we can restrict our attention to states that are invariant under $G$ such as (4.4).

I do not follow the reasoning here. Why are $G |x = 0\rangle = |x = 0\rangle$ and $[G, \tilde{H}(s)] = 0$ sufficient reason to overlook other states while computing the energy gap between the ground and first excited states of the adiabatic Hamiltonian?

Let $[G,H]=0$, and consider an eigenstate $|\psi\rangle$ of $H$, $$H|\psi\rangle = E\psi\rangle\ .$$ Then, $|\psi'\rangle := G|\psi\rangle$ is also an eigenstate of $H$ with the same eigenvalue, since $$H|\psi'\rangle = HG|\psi\rangle = GH|\psi\rangle = EG|\psi\rangle = E|\psi'\rangle\ .$$ Thus, also $|\chi\rangle = \tfrac{1}{\sqrt{2}}(|\psi\rangle + |\psi'\rangle)$ is an eigenstate of $H$ with eigenvalue $E$, and $$G|\chi\rangle = \tfrac{1}{\sqrt{2}}(G|\psi\rangle + G|\psi'\rangle)= \tfrac{1}{\sqrt{2}}(|\psi'\rangle + |\psi\rangle) = |\chi\rangle\ ,$$ i.e., $|\chi\rangle$ is invariant under $G$.
• In that last formula, $G|\chi\rangle = |\chi\rangle$ follows only if $G^2 = I$ (which it does), isn't it?