6Hamiltonian simulation

III Quantum Computation

6 Hamiltonian simulation

So. Suppose we did manage to invent a usable quantum computer. What would

it be good for? Grover’s algorithm is nice, but it seems a bit theoretical. You

might say we can use Shor’s algorithm to crack encryption, but then if quantum

computers are available, then no one would be foolish enough to use encryption

that is susceptible to such attacks. So what can we actually do?

One useful thing would be to simulate physical systems. If we have a quantum

system and with n qubits, then we want to simulate its evolution over time, as

governed by Schr¨odinger’s equation. Classically, a

n

-qubit system is specified by

2

n

complex numbers, so we would expect any such algorithm to have performance

at best

O

(2

n

). However, one would imagine that to simulate a quantum

n

-qubit

system in a quantum computer, we only need

n

-qubits! Indeed, we will see that

we will be able to simulate quantum systems in polynomial time in n.

In a quantum physical system, the state of the system is given by a state

|ψi

, and the evolution is governed by a Hamiltonian

H

. This is a self-adjoint

(Hermitian) operator, and in physics, this represents the energy of the system.

Thus, we have

hψ|H |ψi = average value obtained in measurement of energy.

The time evolution of the particle is given by the Schr¨odinger equation

d

dt

|ψ(t)i = −iH |ψ(t)i.

We’ll consider only time-independent Hamiltonians

H

(

t

) =

H

. Then the solution

can be written down as

|ψ(t)i = e

−iHt

|ψ(0)i.

Here e

−iHt

is the matrix exponential given by

e

A

= I + A +

A

2

2

+ ··· ,

Thus, given a Hamiltonian

H

and a time

t

, we want to simulate

U

(

t

) =

e

−iHt

to suitable approximations.

Before we begin, we note the following useful definitions:

Definition (Operator norm). The operator norm of an operator A is

kAk = max

k|ψik=1

kA |ψik.

If A is diagonalizable, then this is the maximum eigenvalue of A.

The following properties are easy to see:

Proposition.

kA + Bk ≤ kAk+ kBk

kABk ≤ kAkkBk.

We now begin. There will be a slight catch in what we do. We will have

to work with special Hamiltonians known as

k

-local Hamiltonians for a fixed

k

.

Then for this fixed

k

, the time required to simulate the system will be polynomial

in

n

. However, we should not expect the complexity to grow nicely as we increase

k!

So what is a

k

-local Hamiltonian? This is a Hamiltonian in which each

interaction governed by the Hamiltonian only involves

k

qubits. In other words,

this Hamiltonian can be written as a sum of operators, each of which only

touches

k

qubits. This is not too bad a restriction, because in real life, most

Hamiltonians are indeed local, so that if each qubit represents a particle, then

the behaviour of the particle will only be affected by the particles near it.

Definition (k-local Hamiltonian). We say a Hamiltonian H is k-local (for k a

fixed constant) on n qubits if

H =

m

X

j=1

H

j

,

where each

H

j

acts on at most

k

qubits (not necessarily adjacent), i.e. we can

write

H

j

=

˜

H

j

⊗ I,

where

˜

H

j

acts on some k qubits, and I acts on all other qubits as the identity.

The number m of terms we need is bounded by

m ≤

n

k

= O(n

k

),

which is polynomial in n.

Example. The Hamiltonian

H = X ⊗ I ⊗ I −Z ⊗ I ⊗ Y

is 2-local on 3 qubits.

We write M

(i)

to denote the operator M acting on the ith qubit.

Example. We could write

X ⊗I ⊗ I = X

(1)

.

Example

(Ising model)

.

The Ising model on an

n × n

square lattice of qubits

is given by

H = J

n−1

X

i,j=1

Z

(i,j)

Z

i,j+1

+ Z

(i,j)

Z

(i+1,j)

.

Example (Heisenberg model). The Heisenberg model on a line is given by

H =

n−1

X

i=1

J

x

X

(i)

X

(i+1)

+ J

y

Y

(i)

Y

(i+1)

+ J

z

Z

(i)

Z

(i+1)

,

where J

x

, J

y

and J

z

are real constants.

This is useful in modelling magnetic system.

The idea is that we simulate each

e

iH

j

t

separately, and then put them together.

However, if {H

j

} doesn’t commute, then in general

e

−i

P

j

H

j

t

6=

Y

j

e

−iH

j

t

.

So we need to somehow solve this problem. But putting it aside, we can start

working on the quantum simulation problem.

We will make use of the following theorem:

Theorem (Solovay-Kitaev theorem). Let U be a unitary operator on k qubits

and

S

any universal set of quantum gates. Then

U

can be approximated to

within ε using O(log

c

1

ε

) from S, where c < 4.

In other words, we can simulate each

e

−iH

j

t

with very modest overhead in

circuit size for improved error, assuming we fix k.

Proof. Omitted.

We will also need to keep track of the accumulation of errors. The following

lemma will be useful:

Lemma. Let {U

i

} and {V

i

} be sets of unitary operators with

kU

i

− V

i

k ≤ ε.

Then

kU

m

···U

1

− V

m

···V

1

k ≤ mε.

This is remarkable!

Proof.

See example sheet 2. The idea is that unitary gates preserve the size of

vectors, hence do not blow up errors.

We start by doing a warm-up: we solve the easy case where the terms in the

Hamiltonian commute.

Proposition. Let

H =

m

X

j=1

H

j

be any k-local Hamiltonian with commuting terms.

Then for any t, e

−iHt

can be approximated to within ε by a circuit of

O

m poly

log

m

ε

gates from any given universal set.

Proof.

We pick

ε

0

=

ε

m

, and approximate

e

−iH

j

t

to within

ε

0

. Then the total

error is bounded by mε

0

= ε, and this uses

O

m poly

log

m

ε

gates.

We now do the full non-commutative case. To do so, we need to keep track

of how much e

iH

i

t

e

−iH

j

t

differs from e

i(H

i

+H

j

)t

.

Notation. For a matrix X, we write

X + O(ε)

for X + E with kEk = O(ε).

Then we have

Lemma

(Lie-Trotter product formula)

.

Let

A, B

be matrices with

kAk, kBk ≤

K < 1. Then we have

e

−iA

e

−iB

= e

−i(A+B)

+ O(K

2

).

Proof. We have

e

−iA

= 1 − iA +

∞

X

k=2

(iA)

k

k!

= I − iA + (iA)

2

∞

X

k=0

(−iA)

k

(k + 2)!

We notice that

k

(

iA

)

2

k ≤ K

2

, the final sum has norm bounded by

e

K

< e

. So

we have

e

−iA

= I − iA + O(K

2

).

Then we have

e

−iA

e

−iB

= (I − iA + O(K

2

))(I −iB + O(K

2

))

= I − i(A + B) + O(K

2

)

= e

−i(A+B)

+ O(K

2

).

Here we needed the fact that

kA

+

Bk ≤

2

K

=

O

(

K

) and

kABk ≤ K

2

=

O(K

2

).

We now apply this repeatedly to accumulate s ums

H

1

, H

2

, .., H

m

in the

exponent. First of all, we note that if each

kH

i

k < K

, then

kH

i

+

···

+

H

`

k < `K

.

We want this to be

<

1 for all

` ≤ m

. So for now, we assume

K <

1

m

. Also, we

take t = 1 for now. Then consider

e

−iH

1

e

−iH

2

···e

−iH

m

= (e

−i(H

1

+H

2

)

+ O(K

2

))e

−iH

3

···e

−iH

m

= e

−i(H

1

+H

2

)

e

−iH

3

···e

−iH

m

+ O(K

2

)

= e

−i(H

1

+H

2

+H

3

)

e

−iH

4

···e

−iH

m

+ O((2K)

2

) + O(K

2

)

= e

−i

P

H

j

+ O(m

3

K

2

),

where we used the fact that

1

2

+ 2

2

+ ··· + m

2

= O(m

3

).

We write the error as Cm

3

K

2

.

This is fine if

K

is super small, but it won’t be in general. For general

K

and t values, we introduce a large N such that

H

j

t

N

<

Kt

N

≤

˜

K < 1.

In other words, we divide time up into small

t

N

intervals. We then try to simulate

U = e

−i(H

1

+···+H

m

)t

=

e

−i

(

H

1

t

N

+...+

H

n

t

N

)

N

.

This equality holds because we know that

t

N

(

H

1

+

···

+

H

n

) commutes with

itself (as does everything in the world).

We now want to make sure the final error for

U

is

< ε

. So we know each

term

e

−i

(

H

1

t

n

+...+

H

n

t

n

)

needs to be approximated to

ε

N

. So using our previous

formula, we want that

Cm

3

˜

K

2

<

ε

N

,

Doing some algebraic manipulation, we find that we need

N >

Cm

3

K

2

t

2

ε

.

We now have Nm gates of the form e

iH

j

t/N

. So the circuit size is at most

O

m

4

(Kt)

2

ε

.

Recall for

n

-qubits, a general

k

-local Hamiltonian has

m

=

O

(

n

k

). So the circuit

size is

|C| = O

n

4k

(Kt)

2

ε

.

Now this is in terms of the number of

e

iH

j

t/N

gates. If we want to express this

in terms of universal gates, then each gate needs to be approximated to

O

(

ε/|C|

).

We then need

O

(

log

c

(

|C|

ε

)) gates for each, for some

c <

4. So we only get a

modest extra multiplicative factor in |C|.

Note that for a fixed

n

with a variable

t

, then a quantum process

e

−iHt

runs

in time

t

, but our simulation needs time

O

(

t

2

). This can be improved to

O

(

t

1+δ

)

for any δ > 0 by using “better” Lie-Trotter expansions.

Local Hamiltonian ground state problem

There are many other things we might want to do with a

k

-local Hamiltonian.

One question we might be interested in is the eigenvalues of

H

. Supp ose we are

given a 5-local Hamiltonian

H =

m

X

i=1

H

j

on

n

qubits (this was the original result proved). We suppose

kH

i

k <

1, and we

are given two numbers

a < b

, e.g.

a

=

1

3

and

b

=

2

3

. We are promised that the

smallest eigenvalue

E

0

of

H

is

< a

or

> b

. The problem is to decide whether

E

0

< a.

The reason we have these funny

a, b

is so that we don’t have to worry about

precision problems. If we only had a single

a

and we want to determine if

E

0

> a

or

E

0

< a

, then it would be difficult to figure out if

E

0

happens to be very close

to a.

Kitaev’s theorem says that the above problem is complete for a complexity

class known as

QMA

, i.e. it is the “hardest” problem in

QMA

. In other words,

any problem in QMA can be translated into a local Hamiltonian ground state

problem with polynomial overhead. A brief survey can be found on arXiv:quant-

ph/0210077.

What is this

QMA

? We will not go into details, but roughly, it is a quantum

version of

NP

. In c ase you are wondering, MA stands for Merlin and Arthur. . .