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. . .