Hamiltonian simulation and Trotterization

07 Apr 2019

$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$ $\newcommand\bra[1]{\langle{#1}|}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$

The evolution of a quantum system is governed by the Schrödinger equation $i \dfrac{d\ket{\psi(t)}}{dt} = H \ket{\psi(t)}$. The solution of the Schrödinger equation ($\ket{\psi(t)} = e^{-iHt}\ket{0}$) is a description on what state a system will be in after a hamiltonian has been applied to it for a certain period of time. The problem of Hamiltonian simulation is thus stated as follows: Given a Hamiltonian $H$ and an evolution time $t$, output a sequence of computational gates that implement $U=e^{-iHt}$. This problem is meaningful because simulating the dynamics of a quantum system is an essential problem in quantum physics and quantum chemistry. It's widely believed that the Hamiltonian simulation problem can be solved with an exponential number of gates on a classical computer while requiring only a polynomial number on a quantum computer.

Hamiltonians are hermitian operators that are usually a sum of a large number of individual hamiltonians $H_{j}$. For example, a Hamiltonian $H$ can be equal to $ H_{1} + H_{2}$. This sum of 2 hamiltonians can be described by the Lie product formula $e^{-i(H_1+H_2)t} = \lim_{N \rightarrow \infty} (e^{-iH_1t/N}e^{-iH_2t/N})^N$. Since the limit of this formula is infinite, we have to truncate the series when implementing this formula on a quantum computer. The truncation introduces error in the simulation that we can bound by a maximum simulation error $\epsilon$ such that $\norm{ e^{-i H t} - U} \leq \epsilon$. This truncation is known as Trotterization and it's widely used to simulate non-commuting hamiltonians on quantum computers. The Trotterization formula is then $e^{-iHt} = (e^{-iH_{0}t/r} * e^{-iH_{1}t/r ....* e^{-iH_{d-1}}t/r })^r$ + $0$(some polynomial factors).

Suppose we want to simulate $H = X_{0} + Y_{1} + Z_{2}$ where X, Y and Z are Pauli matrices and the subscripts label the qubits that the hamiltonians apply to. We can't simulate each Hamiltonian separately because they don't commute. This is why we use Trotterization where we evolve the whole hamiltonian by repeatedly switching between evolving $X_{0}$, $Y_{1}$, and $Z_{2}$ each for a small period of time. The first step in deriving the circuit that will simulate this hamiltonian is finding the quantum gates that implement each of it's individual term. This case is simple since the quantum gates $R_{x}(\theta) = e^{-i \dfrac{\theta}{2}X}$, $R_{y}(\theta) = e^{-i \dfrac{\theta}{2}Y}$, $R_{z}(\theta) = e^{-i \dfrac{\theta}{2}Z}$ will implement the individual terms perfectly. $\theta$ specifies the angle by which to rotate the state in a specified axis; this is sort of synonymous with time since it specifies how "long" to apply the hamiltonian to the qubit ($\pi/2$ degrees could take 30 nanoseconds to rotate to, $\pi$ degress could take 60 nanoseconds, e.t.c). Since we don't care too much about the simulation error in this example, we will use $r = 2$ and $t=1$ in our Trotter formula to get $e^{X_{0} + Y_{1} + Z_{2}} = (e^{-iX_{0}} * e^{-iY_{1}} * e^{-iZ_{2}}) * (e^{-iX_{0}/2} * e^{-iY_{1}/2} * e^{-iZ_{2}/2}) $

Discuss on Github

References