Obtaining gate $e^{-i\Delta t Z}$ from elementary gates

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 simulate more complicated extended Hamiltonians. Specifically, 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.

How can we obtain gate $$e^{-i\Delta t Z}$$ from elementary gates (for example from Toffoli gates)?

• Could you please explain what you don't understand about figure 4.19? Apr 22 '18 at 17:43
• Please note that the Toffoli gate alone is not universal for quantum computation (only for classical computation). For example, a universal gate set including the Toffoli gate is: Hadamard, Phase (S), CNOT and Toffoli. Apr 22 '18 at 18:50

One way order to perform Z rotations by arbitrary angles is to approximate them with a sequence of Hadamard and T gates. If you need the approximation to have maximum error $\epsilon$, there are known constructions that do this using roughly $3 \lg \frac{1}{\epsilon}$ T gates. See "Optimal ancilla-free Clifford+T approximation of z-rotations" by Ross et al.
The best published way to approximate arbitrary Z rotations, repeat-until-success circuits, takes a slightly more complicated approach but achieves an average of roughly $9 + 1.2 \lg \frac{1}{\epsilon}$ T gates.