12
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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? $\endgroup$ – ahelwer Feb 27 '19 at 16:44
10
$\begingroup$

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)

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Davit Khachatryan Apr 2 at 9:46
  • 1
    $\begingroup$ @David Khachatryan, I got it. Thank you very much $\endgroup$ – Omkar Apr 2 at 9:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Vesely Apr 12 at 16:01
  • 1
    $\begingroup$ 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? $\endgroup$ – Davit Khachatryan Apr 12 at 16:29
  • 1
    $\begingroup$ @MartinVesely, in the answer, I added a part about $I$ operators in the Pauli terms. $\endgroup$ – Davit Khachatryan Apr 12 at 20:08
2
$\begingroup$

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)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.