Under Qiskit QAOA's tutorial (https://qiskit.org/textbook/ch-applications/qaoa.html), the authors specify that a cost function $C(x)$ representing the optimization objective of a Binary Combinatorial Optimization problem (x is a vector or list of Boolean variables) can be mapped to a hamiltonian in $H^{2^n}$ via the transformation

$x_i \rightarrow \frac{1}{2}(1-Z_{i})$ where $x_i$ is a Boolean variable of $x$ and $Z_i$ is the pauli-Z operator applied to qubit i.

I was wondering what was the intuition behind the transformation and if there is a way to propose different alternatives.

Thank you!


The main thing that you're trying to do is create Hamiltonians whose ground states have a correspondence to basis vectors $|x\rangle$. So, the point of an operator $$ R=\frac12(1-Z)=\left(\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}\right) $$ is that it has two eigenvectors $|0\rangle$ and $|1\rangle$, so $R$ has a ground state $|0\rangle$ and $-R$ has a ground state $|1\rangle$. The 0 and 1 are the things you're trying to directly correspond to binary variables.

You might ask why one bothers to include the $I$ term as that only shifts the eigenvalues, it doesn't change the eigenvectors. Usually it's just for convenience. People often like to have the ground state to have 0 energy (in which case, you'd use $\frac12(I+Z)$ instead of $-R$ to get the $|1\rangle$ state as a ground state).

So, let's say I want to create a ground state corresponding to the binary string $x=01$. I can use a Hamiltonian $H=R_1-R_2$. (This is obviously diagonal, so the computational basis states are all eigenstates). In general, for any $x\in\{0,1\}^n$, I can use $$ H=\sum_{i=1}^n(-1)^{x_i}R_i $$ to make the ground state $|x\rangle$. (There are several other ways that we could construct a Hamiltonian with the correct ground state, but this is a particularly simple one.)

This is then the starting point of developing some logic. Let's say we don't know what basis state we want to be the ground state, but we want it to satisfy $x_1=x_2$. You could do something like $\frac12(I-Z_1Z_2)$. You find a ground state (with energy 0), perhaps $|11\rangle$, and that tells you $x=11$ is a solution to $x_1=x_2$.

If we take this a little further, you could ask if there's a satisfying formula $x_1=x_2$, $x_2=x_3$ and $x_3\neq x_1$ (OK, obviously not, but with more complex formulae, it's not so obvious). You'd set up a Hamiltonian $$ H=\frac12(I-Z_1Z_2)+\frac12(I-Z_2Z_3)+\frac12(I+Z_1Z_3), $$ and ask if it has a 0 energy eigenvalue. If not, there are no solutions to the given conditions. If so, the corresponding basis vector gives you a satisfying $x$.

| improve this answer | |
  • $\begingroup$ A very nice answer. Isn't the $\frac{1}{2} (I + Z_1 Z_3)$ (shouldn't there be a "+" sign instead of "-" sign) term in the Hamiltonian better choice for presenting $x_1 \ne x_3$? Because the eigenvalue of $\frac{1}{2} (I + Z_1 Z_3)$ is minimum when $x_1 \ne x_3$. $\endgroup$ – Davit Khachatryan Jun 11 at 7:28
  • $\begingroup$ oops, yes, bad typo! $\endgroup$ – DaftWullie Jun 11 at 7:41

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.