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 in the $z$ axis. $$ G = \prod^n_{j=1}\sigma^{(j)}_x $$

Then the authors start the steps of Jordan-Wigner transformation. The fermionic operators are defined as follows.

$$ b_j = \sigma_x^1 \sigma_x^2 \ldots \sigma_x^{j-1} \sigma_-^{j} \mathbf{ 1}^{j+1} \ldots \mathbf{ 1}^n \\ b^\dagger_j = \sigma_x^1 \sigma_x^2 \ldots \sigma_x^{j-1} \sigma_+^{j} \mathbf{ 1}^{j+1} \ldots \mathbf{ 1}^n $$ where $$ \sigma_{\pm} = \sigma_x \pm i \sigma_y $$.

Then the authors keep mentioning few more identities. Then at the beginning of page 14, they say

Since we will restrict ourselves to the $G = 1$ sector, (4.10) and (4.11) are only consistent if $b_{n+1} = −b_1$ , so we take this as the definition of $b_{n+1}$.

My questions: I understand that $G$ is an operator which commutes with the adiabatic Hamiltonian and it negates the values of the qubits in the $z$ axis. But, I don't understand what the definition of the 'sector' of $G$ is, when the sector is $G = 1$, what other sectors are possible, and finally why $b_{n+1} = b_1$ cannot be true.

My attempt: In the computational basis i.e. along $z$ axis, $\sigma^x |1\rangle = 1\cdot|0\rangle$ and $\sigma^x |0\rangle = 1\cdot|1\rangle$. So, the eigenvalue is always $1$. Is this the sector, the authors are talking about?

$\endgroup$
  • 1
    $\begingroup$ Note that $ G^2=1$ so there are two eigenvalues that are +-1. To see the -1 sector, consider a singlet state. $\endgroup$ – Mikael Fremling Jun 9 '16 at 6:57
1
$\begingroup$

To see that there are two sector, corresponding to the eigenvalues of $G$ note that $G^2=1$ since

$$ G^2 = (\prod^n_{j=1}\sigma^{(j)}_x)^2 = \prod^n_{j=1}(\sigma^{(j)}_x)^2 = 1$$

Thus there are two eigenvalues to $G$ that are $\pm1$. These sectors need not be of the same size. Consider just 2 spins in theire singlet and triplet configurations.

The singlet is $$ |s\rangle = |\uparrow,\downarrow\rangle - |\downarrow,\uparrow\rangle$$ while the triplets are $$ |t,\pm\rangle = |\downarrow\downarrow\rangle \pm |\uparrow,\uparrow\rangle$$ $$ |t,0\rangle = |\uparrow,\downarrow\rangle + |\downarrow,\uparrow\rangle$$

The effect of $G$ on these are $$ G|s\rangle = |\downarrow,\uparrow\rangle-|\uparrow,\downarrow\rangle = -|s\rangle$$ and

$$ G|t,\pm\rangle = |\uparrow,\uparrow\rangle\pm|\downarrow\downarrow\rangle = \mp |t,\pm\rangle $$ $$ G|t,0\rangle = |\downarrow,\uparrow\rangle+|\uparrow,\downarrow\rangle = +|t,0\rangle $$

Which sows that it's easy to construct both positive and negative eigenvectors of $G$.

$\endgroup$

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.