# Circuit construction for Hamiltonian simulation

I would like to know how to design a quantum circuit that given a Hermitian matrix $$\hat{H}$$ and time $$t$$, maps $$|\psi\rangle$$ to $$e^{i\hat{H}t} |\psi\rangle$$. Thank you for your answer.

• There are many advanced algorithms for compiling a Hamiltonian into a series of gates; are you looking for a summary of some of the simpler approaches, or a list of resources to start you off? Feb 27 '19 at 16:44

## 2 Answers

An approach for Hamiltonian simulation:

Any Hermitian (Hamiltonian) matrix $$H$$ can be decomposed by the sum of Pauli products with real coefficients (see this thread). An example of 3 qubit Hamiltonian:

$$H = 11 \sigma_z \otimes \sigma_z + 7 \sigma_z \otimes \sigma_x - 5\sigma_z \otimes \sigma_x \otimes \sigma_y$$

The final circuit for $$e^{iHt}$$ can be simulated via Trotter decomposition (chapter 4.1 from the paper [1]):

$$e^{iHt} \approx \big(\prod_k e^{i c_k P_k t/N }\big)^{N}$$

where $$t$$ is a parameter that can have either positive or negative values, $$P_k$$ are the Pauli terms, $$c_k$$ are the coefficients of the corresponding $$P_k$$s, $$H = \sum_k c_k P_k$$, $$N$$ is the Trotter number. By increasing $$N$$ it is possible to decrease the error of the Trotter decomposition as much as desired [1]. If all $$P_k$$ Pauli terms are commuting to each other, then we can take $$N = 1$$ (no Trotter decomposition is needed). For this simulation, we need to know how to simulate individual Pauli products $$e^{iP_k t}$$. Let's start with the simplest one $$e^{i \sigma_z \otimes \sigma_z \otimes ... \otimes \sigma_z t}$$ (chapter 4.2 of the paper [1]). Here is the circuit for $$e^{i \sigma_z \otimes \sigma_z t}$$ from the paper [1]

Here $$R_z$$'s argument is $$-2t$$ ($$R_z(-2t) = e^{i\sigma_z t}$$). Before showing why this is true let's introduce 2 formulas that we will us. 4.2 exercise from the textbook [2]: Let $$t$$ be a real number and $$A$$ a matrix such that $$A^2 = I$$. Then

$$e^{iA t} = \cos(t) I + i \sin(t) A$$

For all Pauli terms, this $$P_k^2 =I$$ is true. So we can use this formula. For CNOT gate we have:

$$\mathrm{CNOT} = |0\rangle \langle 0 | \otimes I + |1\rangle \langle 1 | \otimes \sigma_x$$

By taking these formulas into account let's show that the circuit implements the $$e^{i \sigma_z \otimes \sigma_z t}$$ Pauli term:

\begin{align*} e^{i \sigma_z \otimes \sigma_z t} = \cos(t) I + i \sin(t) \sigma_z \otimes \sigma_z \end{align*}

The circuit:

\begin{align*} &\mathrm{CNOT} \left(I \otimes e^{i \sigma_z t}\right) \mathrm{CNOT}= \big[|0\rangle \langle 0 | \otimes I + |1\rangle \langle 1 | \otimes \sigma_x \big] \\ &\big[ \cos(t) I\otimes I + i \sin(t) I \otimes \sigma_z \big] \big[|0\rangle \langle 0 | \otimes I + |1\rangle \langle 1 | \otimes \sigma_x \big] = \\ &= \cos(t) I + i \sin(t) \sigma_z \otimes \sigma_z \end{align*}

So, the circuit implements what we want:

$$e^{i \sigma_z \otimes \sigma_z t} =\mathrm{CNOT} \left(I \otimes e^{i \sigma_z t}\right) \mathrm{CNOT}$$

The circuit for the $$e^{i \sigma_z \otimes \sigma_z \otimes \sigma_z t}$$ Pauli term from the same paper [1]:

This also can be shown the same way. Moreover, this solution can be generalized for $$e^{i \sigma_z \otimes \sigma_z \otimes ... \otimes \sigma_z t}$$ Pauli term.

Now, what if we have one $$\sigma_x$$ in the tensor product $$P = P_1 \otimes \sigma_x^{(n)} \otimes P_2$$, where $$P_1$$ and $$P_2$$ are also Pauli products, $$n$$ is the qubit number. Note that:

\begin{align*} e^{iP_1 \otimes \sigma_x^{(n)} \otimes P_2t} &= \cos(t) I + i \sin(t) P_1 \otimes \sigma_x^{(n)} \otimes P_2 = \\ &= \cos(t) I + i \sin(t) P_1 \otimes \left(H \sigma_z^{(n)} H\right) \otimes P_2 = \\ &= H^{(n)} e^{iP_1 \otimes \sigma_z^{(n)} \otimes P_2t} H^{(n)} \end{align*}

where $$H^{(n)}$$ is the Hadamard gate acting on $$n$$th qubit. The same can be shown for $$\sigma_y$$:

\begin{align*} e^{iP_1 \otimes \sigma_y^{(n)} \otimes P_2t} = H_y^{(n)} e^{iP_1 \otimes \sigma_z^{(n)} \otimes P_2t} H_y^{(n)} \end{align*}

where $$H_y$$ is a self-inverse gate (that was suggested here), which has this nice property $$\sigma_y = H_y \sigma_z H_y$$:

$$H_y = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & -i \\ i & -1 \end{pmatrix}$$

Now, we can simulate any Pauli term. For example, the circuit for $$e^{i \sigma_y \otimes \sigma_y \otimes \sigma_x}$$ will look like this:

$$e^{i \sigma_y \otimes \sigma_y \otimes \sigma_x} = \big[ H_y \otimes H_y \otimes H \big] e^{i \sigma_z \otimes \sigma_z \otimes \sigma_z} \big[H_y \otimes H_y \otimes H\big]$$

By applying appropriate rotations we can bring any Pauli term simulation problem to the simplest $$e^{i \sigma_z \otimes \sigma_z \otimes ... \otimes \sigma_z t}$$ Pauli term simulation problem, which solution we already know. With this approach, we can simulate any Pauli term, thus also any Hermitian operator.

Addition: $$I$$ operators in the Pauli product terms

Here we will try to show that we can ignore $$I$$ operators in the Pauli products when we try to construct circuits for them. For example, we will take $$\sigma_z \otimes I \otimes \sigma_z$$ operator and show that we can forget about the second qubit and simulate the circuit for $$e^{i\sigma_z \otimes \sigma_z t}$$ applied on the first and third qubits. We should proof that:

$$e^{i\sigma_z \otimes I \otimes \sigma_z t} = CNOT^{(1,3)}R_z^{(3)}(-2t)CNOT^{(1,3)}$$

For the left side we have:

$$e^{i\sigma_z \otimes I \otimes \sigma_z t} = \cos(t) I \otimes I \otimes I + \sin(t) \sigma_z \otimes I \otimes \sigma_z$$

For the right side:

\begin{align} &CNOT^{(1,3)}R_z^{(3)}(-2t)CNOT^{(1,3)} = \big[| 0 \rangle \langle 0 | \otimes I \otimes I + | 1 \rangle \langle 1 | \otimes I \otimes X \big] \\ &\big[ I \otimes I \otimes \big( \cos(t) I + i \sin(t) \sigma_z \big) \big] \big[ | 0 \rangle \langle 0 | \otimes I \otimes I + | 1 \rangle \langle 1 | \otimes I \otimes X \big]= \\ &= \cos(t) I \otimes I \otimes I + \sin(t) \sigma_z \otimes I \otimes \sigma_z \end{align}

So, they are equal to each other: we can forget about $$I$$ operator for constructing a circuit in this case. This solution can be generalized for $$n$$ $$I$$ operators between two $$\sigma_z$$ terms.

Also, let's proof that $$I \otimes P \otimes I$$ can be simulated by $$e^{i I \otimes P \otimes I t} = I \otimes e^{i P t} \otimes I$$, where $$P$$ is some Pauli product:

\begin{align} &e^{i I \otimes P \otimes I t} = \cos(t) I \otimes I \otimes I + i\sin(t) I \otimes P \otimes I \\ &= I \otimes \big( \cos(t) I + i \sin(t) P \big) \otimes = I \otimes e^{i P t} \otimes I \end{align}

In this manner, it can be shown for general cases that we can ignore $$I$$ operators when we simulate Pauli terms in the quantum circuits.

Qiskit implementations of the ideas described here can be found in this tutorial.

• I edited the answer with more detailed explanations. Now I don't have that step, instead, I have 3 steps in my answer. The first step is to describe $e^{i\sigma_z \otimes \sigma_z t}$ by using the Euler-like formula for Pauli matrices. In the second and third steps, I show that the presented circuit is equal to the $e^{i\sigma_z \otimes \sigma_z t}$. Also, I changed/corrected some notations. Apr 2 '20 at 9:46
• @David Khachatryan, I got it. Thank you very much Apr 2 '20 at 9:49
• Hi Davit, thanks for very clear introduction to Hamiltonian simulation. However, could you please show how a circuit look like in case there is a unit matrix in tensor product, for example $\sigma_z \otimes I \otimes I$? These terms appear in Ising Hamiltonians for spin glasses. Thanks. Apr 12 '20 at 16:01
• Hi @MartinVesely, I will try: $e^{i \sigma_z \otimes I \otimes I t} = \cos(t) I \otimes I \otimes I + i \sin(t) \sigma_z \otimes I \otimes I = (\cos(t) I + i \sin(t) \sigma_z) \otimes I \otimes I = R_z(-2t) \otimes I \otimes I$. Martin is this answers to your question? Apr 12 '20 at 16:29
• @MartinVesely, in the answer, I added a part about $I$ operators in the Pauli terms. Apr 12 '20 at 20:08

Controlled version of $$e^{iHt}$$:

Often in the algorithms (e.g. in HHL or PEA), we want to construct not the circuit for Hamiltonian simulation $$e^{iHt}$$, but the controlled version of it. For this, we will use the result obtained from the previous answer. First of all, note that if we have $$ABC$$ circuit, where $$A$$, $$B$$ and $$C$$ are operators, then the controlled version of that circuit will equal $$cA$$ $$cB$$ $$cC$$, where $$c$$ denotes control version of an operator. From the previous answer we know that $$e^{iHt}$$ consists of $$e^{iPt}$$ terms, where $$P$$ is some Pauli product. So, for solving the problem we should find a way for constructing controlled versions of $$e^{iPt}$$ terms. Here is a general form for the circuit that implements any given $$e^{iPt}$$ and the controlled version of it (like was done similarly in this paper [1]):

where $$O_i$$ are gates from this set $$\{I, H, H_y\}$$, and they are chosen differently for each Pauli term (see the previous answer). The right circuit in the picture implements the controlled version of the $$e^{iPt}$$, because, if control qubit is in the $$|0\rangle$$ state the $$R_z$$ gate will not work and the rest gates will cancel each other (they are self-inverse gates).

When we are talking about the controlled version of the circuit we shouldn't forget about $$e^{iIt}$$ term (the global phase in the $$e^{iHt}$$). We should also construct a circuit that implements controlled version of $$e^{iIt}$$. Let's call it controlled-global phase ($$CGP$$) gate and try to implement it. The effect of $$CGP$$ for controlled qubit $$\alpha|0_c\rangle + \beta|1_c\rangle$$ acting on multi-qubit $$| \psi \rangle$$ state:

$$CGP \left( \alpha|0_c\rangle + \beta|1_c\rangle \right) |\psi\rangle = \left( \alpha|0_c\rangle + e^{it}\beta|1_c\rangle \right) |\psi\rangle$$

where $$t$$ is the phase. This action can be done just by one Qiskit's $$u1$$ phase gate acting on the control qubit [2]:

$$u1(t) = \begin{pmatrix} 1 & 0 \\ 0 & e^{it}\end{pmatrix}$$