# Implement a Hamiltonian in O(n) - exercise question

I have the following exercise to solve:

Consider the Boolean function $$f(x_1 . . . x_n) = x_1 \oplus \dots \oplus x_n$$ where $$x_1 \dots x_n$$ is an nbit string and $$\oplus$$ denotes addition mod $$2$$. Describe a circuit of $$2$$-qubit gates on $$n + 1$$ qubits that implements the transformation $$| x_1 \dots x_n \rangle | 0 \rangle \mapsto | x_1 \dots x_n \rangle | x_1 \oplus \dots \oplus x_n\rangle$$

By considering a relationship between $$f$$ and the $$n$$-qubit Hamiltonian $$Z \otimes \dots \otimes Z$$, show that $$V = \exp(i Z \otimes \dots \otimes Z t)$$, for any fixed $$t > 0$$, may be implemented on n qubit lines (with possible use of further ancillary lines) by a circuit of size $$O(n)$$ of $$1$$- and $$2$$-qubit gates.

My circuit for the first part of the question is just $$n$$ CNOT gates controlled by the first register and acting on the $$1$$-qubit register. So far so good. However, for the second part of the question, I don't understand the relation to the Hamiltonian. I understand that I could use $$H^{\otimes n}$$ to convert $$X$$ into $$Z$$ gates but still.

Any help appreciated.

Let's say that you want to implement $$V$$ on some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ You can fairly easily write down what that state produces. Think about the Hamiltonian $$Z^{\otimes n}$$. What eigenvalues does it have? $$\lambda=\pm 1$$. What are the eigenvectors? The computational basis states $$|x_1\ldots x_n\rangle$$. So, the output of $$V$$ is $$\sum_{x:\lambda_x=1}\alpha_xe^{i t}|x\rangle+\sum_{x:\lambda_x=-1}\alpha_xe^{-i t}|x\rangle$$ Hence, can you use your function $$f$$ to determine which eigenvalue a particular $$x$$ has? How do you then use tha to apply the correct phase for the evolution? Don't forget that if you use an ancilla qubit, you must undo any entanglement you may have created with it.
• perfect explanation, got it thanks, I just use my function to compute whether I have even or odd number of say 1 bits in my state, store this information in an ancilla qubit by the circuit of CX gates, then apply a phase gate to the ancilla, then I undo the first computation by applying the CNOT gates in reverse order (CNOT$^-1=$CNOT) and then I discard the ancilla, but the phase remains on my state?! – Marsl May 29 '19 at 9:52