I am currently reading "Quantum Computation and Quantum Information" by Nielsen and Chuang. In the section about Quantum Simulation, they give an illustrative example (section 4.7.3), which I don't quite understand:
Suppose we have the Hamiltonian $$ H = Z_1 ⊗ Z_2 ⊗ \cdots ⊗ Z_n, \tag{4.113}$$ which acts on an $n$ qubit system. Despite this being an interaction involving all of the system, indeed, it can be simulated efficiently. What we desire is a simple quantum circuit which implements $e^{-iH\Delta t}$, for arbitrary values of $\Delta t$. A circuit doing precisely this, for $n = 3$, is shown in Figure 4.19. The main insight is that although the Hamiltonian involves all the qubits in the system, it does so in a classical manner: the phase shift applied to the system is $e^{-i\Delta t}$ if the parity of the $n$ qubits in the computational basis is even; otherwise, the phase shift should be $e^{i\Delta t}$. Thus, simple simulation of $H$ is possible by first classically computing the parity (storing the result in an ancilla qubit), then applying the appropriate phase shift conditioned on the parity, then uncomputing the parity (to erase the ancilla).
Furthermore, extending the same procedure allows us to ismulate more complicated extended Hamiltonians. Speciffically, we can efficiently simulate any Hamiltonian of the form $$H = \bigotimes_{k=1}^n\sigma_{c\left(k\right)}^k,$$ where $\sigma_{c(k)}^k$ is a Pauli matrix (or the identity) acting on the $k$th qubit, with $c(k) \in \{0, 1, 2, 3\}$ specifying one of $\{I, X, Y, Z\}$. The qubits upon which the identity operation is performed can be disregarded, and $X$ or $Y$ terms can be transformed by single qubit gates to $Z$ operations. This leaves us with Hamiltonian of the form of (4.113), which is simulated as described above.
What do we mean by the parity of the qubits here? Is it the number of qubits in the state $\lvert 1 \rangle$, and can it be even or odd?
