# What do we mean by parity of qubits?

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?

In the computational $\left(Z\right)$ basis, the parity of a (classical) bit string is $0$ if the number of $1$s in the string is even (i.e. 'even parity'), or $1$ if the number of $1$s in the string is odd (i.e. 'odd parity').
The parity can be measured by applying CNOT gates from each qubit that you want to measure (the control qubits) to an ancilla qubit (the target, initially in state $\left|0\right>$). Measuring the parity of a (classical) input state $\left|x_1x_2\ldots x_n\right>$, gives the output of the ancilla as $\left|\bigoplus_{k=1}^nx_k\right>$, which is $\left|0\right>$ for even parity and $\left|1\right>$ for odd parity, as above.
The same process can be applied to quantum input states. As an example, calculating the parity of $\frac {1}{\sqrt{2}}\left(\left|00\right>+\left|11\right>\right)$, applying the CNOT gates gives the state of the overall system (including ancilla) as $\frac {1}{\sqrt{2}}\left(\left|00\right>+\left|11\right>\right)\left|0\right>$, which returns $0$, showing the input qubits have even parity. The converse of this is taking the input state as $\frac {1}{\sqrt{2}}\left(\left|01\right>+\left|10\right>\right)$, which gives the total state, after CNOTs, as $\frac {1}{\sqrt{2}}\left(\left|01\right>+\left|10\right>\right)\left|1\right>$, showing the input state has odd parity.
Yes. This is just checked on the computational basis of all n-bit strings and you can see it does the right thing there. It is acting by $(e^{\pm i \Delta t})$ for the respective parities of basis vectors so it is the circuit you wanted by checking on the basis.