Circuit construction for Hamiltonian simulation

Question

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.

Answer 1

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.

[1] J.D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Molecular Physics, "Simulation of electronic structure Hamiltonians using quantum computers" (2011)

[2] M.A. Nielsen, I.L. Chuang, Cambridge University Press New York, "Quantum Computation and Quantum Information: 10th Anniversary Edition 10th" (2011)

Answer 2

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}$$

[1] J.D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Molecular Physics, "Simulation of electronic structure Hamiltonians using quantum computers" (2011)

[2] M.A. Nielsen, I.L. Chuang, Cambridge University Press New York, "Quantum Computation and Quantum Information: 10th Anniversary Edition 10th" (2011)