1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

Thus, if you care about the gap (which is a difference of two energies), there are always symmetric eigenstates with those energies, which is why you can restrict to symmetric states.

$\endgroup$
7
  • $\begingroup$ I would like to know why considering only the invariant states is sufficient. $\endgroup$ Jun 8 '16 at 22:03
  • 1
    $\begingroup$ @OmarShehab Sufficient for what? I assume it's talking about the ground state and/or its energy. With the above argument, these states allow you to obtain a ground state (and furthermore, if it is unique, it must be invariant). But you have to be more precise with your question if you want more precise answers. $\endgroup$ Jun 8 '16 at 22:15
  • $\begingroup$ I am sorry for not clarifying it. Now I have mentioned in the question that the purpose is to compute the energy gap between the ground and first excited states of the adiabatic Hamiltonian. $\endgroup$ Jun 9 '16 at 0:08
  • 1
    $\begingroup$ The gap is the difference of two eigen-energies. As I have explained before, for each eigenstate there is a symmetric one with the same energy. That's why you can restrict to symmetric ones. $\endgroup$ Jun 9 '16 at 9:23
  • $\begingroup$ In that last formula, $G|\chi\rangle = |\chi\rangle$ follows only if $G^2 = I$ (which it does), isn't it? $\endgroup$
    – udrv
    Jun 9 '16 at 22:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.