Realizable Hamiltonians for universal adiabatic quantum computers
Jacob D. Biamonte1, ∗ and Peter J. Love2, †
Oxford University Computing Laboratory,
Wolfson Building, Parks Road, Oxford, OX1 3QD, United Kingdom.
Department of Physics, 370 Lancaster Ave., Haverford College, Haverford, PA USA 19041.
It has been established that local lattice spin Hamiltonians can be used for universal adiabatic
quantum computation. However, the 2-local model Hamiltonians used in these proofs are general
and hence do not limit the types of interactions required between spins. To address this concern,
the present paper provides two simple model Hamiltonians that are of practical interest to experi-
mentalists working towards the realization of a universal adiabatic quantum computer. The model
Hamiltonians presented are the simplest known quantum-Merlin-Arthur-complete (QMA-complete)
2-local Hamiltonians. The 2-local Ising model with 1-local transverse field which has been realized
using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be
universal for adiabatic quantum computation. We demonstrate that this model can be rendered
universal and QMA-complete by adding a tunable 2-local transverse σxσx coupling. We also show
the universality and QMA-completeness of spin models with only 1-local σz and σx fields and 2-local
σzσx interactions.
What are the minimal physical resources required for
universal quantum computation? This question is of in-
terest in understanding the connections between phys-
ical and computational complexity, and for any practi-
cal implementation of quantum computation. In 1982,
Barahona [1] showed that finding the ground state of the
random field Ising model is NP-hard. Such observations
fostered approaches to solving problems based on classi-
cal [2] and later quantum annealing [3]. The idea of using
the ground state properties of a quantum system for com-
putation found its full expression in the adiabatic model
of quantum computation [4]. This model works by evolv-
ing a system from the accessible ground state of an initial
Hamiltonian Hi to the ground state of a final Hamilto-
nian Hf, which encodes a problem’s solution. The evo-
lution takes place over parameters s ∈ [0, 1] as H(s) =
(1−s)Hi+sHf, where s changes slowly enough that tran-
sitions out of the ground state are suppressed [5]. The
simplest adiabatic algorithms can be realized by adding
non-commuting transverse field terms to the Ising Hamil-
tonian:
i hiσ
i ∆iσ
i,j Jijσ
j , (c.f. [6]).
However, it is unlikely that the Ising model with trans-
verse field can be used to construct a universal adiabatic
quantum computer [7].
What then are the simplest Hamiltonians that al-
low universal adiabatic quantum computation? For this
we turn to the complexity class quantum-Merlin-Arthur
(QMA), the quantum analog of NP, and consider the
QMA-complete problem k-local Hamiltonian [8]. One
solves k-local Hamiltonian by determining if there ex-
ists an eigenstate with energy above a given value or be-
low another—with a promise that one of these situations
is the case—when the system has at most k-local inter-
actions. A Yes instance is shown by providing a witness
∗Electronic address: jacob.biamonte@comlab.ox.ac.uk
†Electronic address: plove@haverford.edu
eigenstate with energy below the lowest promised value.
The problem 5-local Hamiltonian was shown to be
QMA-complete by Kitaev [8]. To accomplish this, Ki-
taev modified the autonomous quantum computer pro-
posed by Feynman [9]. This modification later inspired
a proof of the polynomial equivalence between quantum
circuits and adiabatic evolutions by Aharonov et al. [10]
(see also [11, 12]). Kempe, Kitaev and Regev subse-
quently proved QMA-completeness of 2-local Hamil-
tonian [14]. Oliveira and Terhal then showed that uni-
versality remains even when the 2-local Hamiltonians act
on particles in a subgraph of the 2D square lattice [15].
Any QMA-complete Hamiltonian may realize universal
adiabatic quantum computation, and so these results are
also of interest for the implementation of quantum com-
putation.
Since 1-local Hamiltonian is efficiently solvable,
an open question is to determine which combinations of
2-local interactions allow one to build QMA-complete
Hamiltonians. Furthermore, the problem of finding
the minimum set of interactions required to build a
universal adiabatic quantum computer is of practical, as
well as theoretical, interest: every type of 2-local inter-
action requires a separate type of physical interaction.
To address this question we prove the following theorems:
Theorem 1. The problem 2-local ZZXX Hamil-
tonian is QMA-complete, with the ZZXX Hamiltonian
given as:
HZZXX =
i + (1)
Theorem 2. The problem 2-local ZX Hamiltonian
http://arXiv.org/abs/0704.1287v2
mailto:jacob.biamonte@comlab.ox.ac.uk
mailto:plove@haverford.edu
is QMA-complete, with the ZX Hamiltonian given as
HZX =
i + (2)
a. Structure In the present paper we briefly review
the standard circuit to adiabatic construction to show
that 2-local Hamiltonian is QMA-complete when re-
stricted to real-valued Hamiltonians. We then show how
to approximate the ground states of such 2-local real
Hamiltonians by the ZX and ZZXX Hamiltonians. We
conclude this work by providing references confirming our
claim that the Hamiltonians in Eq. (1) and (2) are highly
relevant to experimentalists attempting to build a univer-
sal adiabatic quantum computer.
I. THE PROBLEM
The translation from quantum circuits to adiabatic
evolutions began when Kitaev [8] replaced the time-
dependence of gate model quantum algorithms with spa-
tial degrees of freedom using the non-degenerate ground
state of a positive semidefinite Hamiltonian:
0 = H |ψhist〉 = (3)
(Hin +Hclock +Hclockinit +Hprop)|ψhist〉.
To describe this, let T be the number of gates in the
quantum circuit with gate sequence UT · · ·U2U1 and let
n be the number of logical qubits acted on by the circuit.
Denote the circuit’s classical input by |x〉 and its output
by |ψout〉. The history state representing the circuit’s
entire time evolution is:
|ψhist〉 =
T + 1
|x〉 ⊗ |0〉⊗T + U1|x〉 ⊗ |1〉|0〉⊗T−1
+ U2U1|x〉 ⊗ |11〉|0〉⊗T−2
+ . . . (4)
+ UT · · ·U2U1|x〉 ⊗ |1〉⊗T
where we have indexed distinct time steps by a T qubit
unary clock. In the following, tensor product symbols
separate operators acting on logical qubits (left) and
clock qubits (right).
Hin acts on all n logical qubits and the first clock
qubit. By annihilating time-zero clock states coupled
with classical input x, Hin ensures that valid input state
(|x〉 ⊗ |0...0〉) is in the low energy eigenspace:
Hin =
(11 − |xi〉〈xi|) ⊗ |0〉〈0|1 (5)
(11 − (−1)xiσzi ) ⊗ (11 + σz1).
Hclock is an operator on clock qubits ensuring that
valid unary clock states |00...0〉, |10..0〉, |110..0〉 etc., span
the low energy eigenspace:
Hclock =
|01〉〈01|(t,t+1) (6)
(T − 1)11 + σz1 − σzT −
σzt σ
(t+1)
where the superscript (t, t+ 1) indicates the clock qubits
acted on by the projection. This Hamiltonian has a sim-
ple physical interpretation as a line of ferromagnetically
coupled spins with twisted boundary conditions, so that
the ground state is spanned by all states with a sin-
gle domain wall. The term Hclockint applies a penalty
|1〉〈1|t=1 to the first qubit to ensure that the clock is in
state |0〉⊗T− at time t = 0.
Hprop acts both on logical and clock qubits. It en-
sures that the ground state is the history state corre-
sponding to the given circuit. Hprop is a sum of T
terms, Hprop =
t=1Hprop,t, where each term checks
that the propagation from time t− 1 to t is correct. For
2 ≤ t ≤ T − 1, Hprop,t is defined as:
Hprop,t
= 11 ⊗ |t− 1〉〈t− 1| − Ut ⊗ |t〉〈t− 1|
− U †t ⊗ |t− 1〉〈t| + 11 ⊗ |t〉〈t|, (7)
where operators |t〉〈t− 1| = |110〉〈100|(t−1,t,t+1) etc., act
on clock qubits t−1, t, and t+1 and where the operator
Ut is the t
th gate in the circuit. For the boundary cases
(t = 1, T ), one writes Hprop,t by omitting a clock qubit
(t− 1 and t+ 1 respectively).
We have now explained all the terms in the Hamilto-
nian from Eq. (3)—a key building block used to prove the
QMA-completeness of 5-local Hamiltonian [8]. The
construction reviewed in the present section was also
used in a proof of the polynomial equivalence between
quantum circuits and adiabatic evolutions [10]. Which
physical systems can implement the Hamiltonian model
of computation from Eq. (3)? Ideally, we wish to find a
simple Hamiltonian that is in principle realizable using
current, or near-future technology. The ground states
of many physical systems are real-valued, such as the
ground states of the Hamiltonians from Eq. (1) and (2).
So a logical first step in our program is to show the QMA-
completeness of general real-valued local Hamiltonians.
A. The QMA-completeness of real-valued
Hamiltonians
Bernstein and Vazirani showed that arbitrary quan-
tum circuits may be represented using real-valued gates
operating on real-valued wave functions [17]. Using this
idea, one can show that 5-local real Hamiltonian
is already QMA-complete—leaving the proofs in [8] oth-
erwise intact and changing only the gates used in the
circuits. Hin from Eq. (5) and Hclock from Eq. (6) are al-
ready real-valued and at most 2-local. Now consider the
terms in Hprop from Eq. (7) for the case of self-inverse
elementary gates Ut = U
Hprop,t =
(11 − σz(t−1))(11 + σ
(t+1)) (8)
(11 − σz(t−1))σ
t (11 + σ
(t+1))
For the boundary cases (t = 1, T ), define:
Hprop,1 =
(11 + σz2) − U1 ⊗
(σx1 + σ
2) (9)
Hprop,T =
(11 − σz(T−1)) − UT ⊗
(σxT − σz(T−1)σ
The terms from Eq. (8) and (9) acting on the clock space
are already real-valued and at most 3-local. As an ex-
plicit example of the gates Ut, let us define a universal
real-valued and self-inverse 2-qubit gate:
Rij(φ) =
(11+σzi )+
(11−σzi )⊗ (sin(φ)σxi +cos(φ)σzj ).
The gate sequence Rij(φ)Rij(π/2) recovers the universal
gate from [18]. This is a continuous set of elementary
gates parameterized by the angle φ. Discrete sets of self
inverse gates which are universal are also readily con-
structed. For example, Shi showed that a set comprising
the C-NOT plus any one-qubit gate whose square does
not preserve the computational basis is universal [13]. We
immediately see that a universal set of self-inverse gates
cannot contain only the C-NOT and a single one-qubit
gate. However, the set {C-NOT, X, cosψX + sinψZ} is
universal for any single value of ψ which is not a multiple
of π/4.
A reduction from 5-local to 2-local Hamiltonian
was accomplished by the use of gadgets that reduced 3-
local Hamiltonian terms to 2-local terms [14]. From the
results in [14] (see also [15]) and the QMA-completeness
of 5-local real Hamiltonian, it now follows that 2-
local real Hamiltonian is QMA-complete and uni-
versal for adiabatic quantum computation. We note that
the real product σ
j , or tensor powers thereof, are not
necessary in any part of our construction, and so Hamil-
tonians composed of the following pairwise products of
real-valued Pauli matrices are QMA-complete and uni-
versal for adiabatic quantum computation[29]:
{11, 11 ⊗ σx, 11 ⊗ σz , σx ⊗ 11, (10)
σz ⊗ 11, σx ⊗ σz, σz ⊗ σx, σx ⊗ σx, σz ⊗ σz}.
To prove our Theorems (1) and (2), we will next show
that one can approximate all the terms from Eq. (10)
using either the ZX or ZZXX Hamiltonians—the Hamil-
tonians from Eq. (1) and (2) respectively. We do this
using perturbation theory [14, 15] to construct gadget
Hamiltonians that approximate the operators σzi σ
j and
σxi σ
i with terms from the ZZXX Hamiltonian as well as
the operators σzi σ
i and σ
j with terms from the ZX
Hamiltonian.
B. The ZZXX gadget
We use the ZZXX Hamiltonian from Eq. (1) to con-
struct the interaction σzi σ
j from σ
xσx and σzσz interac-
tions. Let Heff = αijσ
j ⊗ |0〉〈0|k, where qubit k is an
ancillary qubit and define the penalty Hamiltonian Hp
and corresponding Green’s function G(z) as follows:
Hp = δ|1〉〈1|k =
(11 − σzk) and (11)
= (z11 −Hp)−1.
Hp splits the Hilbert space into a degenerate low en-
ergy eigenspace L− = span{|sisj〉|0〉|∀si, sj ∈ {0, 1}}, in
which qubit k is |0〉, and a δ energy eigenspace L+ =
span{|sisj〉|1〉|∀si, sj ∈ {0, 1}}, in which qubit k is |1〉.
First, we give the ZZXX Hamiltonian which pro-
duces an effective σzσz interaction in the low energy
subspace. Let Y be an arbitrary ZZXX Hamiltonian
acting on qubits i and j and consider a perturbation
V = V1 + V2 + V3 that breaks the L− zero eigenspace
degeneracy by creating an operator O(ǫ) close to Heff in
this space:
V1 = [Y +D(σ
j + 11)] ⊗ 11k −Aσzi ⊗ |0〉〈0|k
V2 = B(σ
j + 11) ⊗ σxk (12)
V3 = Cσ
i ⊗ |1〉〈1|k.
The term V2 above allows the mediator qubit k to un-
dergo virtual excitations and applies an σx term to qubit
j during transitions between the L− and L+ subspaces.
During excitation into L+, the term V3 applies a σz term
to qubit i. This perturbation is illustrated in figure 1
FIG. 1: The ZZXX gadget used to approximate the operator
σzi σ
j using only σ
xσx and σzσz interactions. The present
figure presents a diagrammatic representation of the Pertur-
bation Hamiltonian V = V1 + V2 + V3 from Eq. (12) applied
to qubits i, j and k. Not shown in the present figure is an
overall constant energy shift of D.
Let Π± be projectors on L±; for arbitrary operator
O we define O±∓ = Π±OΠ∓ (O±± = Π±OΠ±) and let
λ(O) denote the lowest eigenvalue of O. One approxi-
mates λ(Htarg) of the desired low energy effective 2-local
Hamiltonian by a realizable 2-local physical Hamiltonian
H̃ = Hp + V , where λ(H̃) is calculated using perturba-
tion theory. The spectrum of H̃−− is approximated by
the projection of the self-energy operator Σ(z) for real-
valued z which has the following series expansion:
Σ−−(z) =
Hp– +
V−− +
︷ ︸︸ ︷
V−+G++(z)V+− (13)
+ V−+G++(z)V+G++(z)V+−
︸ ︷︷ ︸
‖V ‖4δ−3
+ · · ·
Note that with our penalty Hamiltonian H−− = 0,
and for the perturbing Hamiltonian V = V1 + V2 + V3
only V1 is nonzero in the low energy subspace, V1 and
V3 are nonzero in the high energy subspace, and only
V2 induces transitions between the two subspaces. The
non-zero projections are:
V1−− = [Y +Aσ
i +D(σ
j + 11)] ⊗ |0〉〈0|k
V2−+ = B(σ
j + 11) ⊗ |0〉〈1|k
V2+− = B(σ
j + 11) ⊗ |1〉〈0|k (14)
V3++ = V3
V+ = (Y + Cσ
i +D(σ
j + 11)) ⊗ |1〉〈1|k
The series expansion of the self-energy follows directly:
1st : (Y −Aσzi +D(σxj + 11)) ⊗ |0〉〈0|k
2nd :
z − δ
(σxj + 11)
2 ⊗ |0〉〈0|k (15)
3rd :
(z − δ)2
(σxj + 11)σ
j + 11) ⊗ |0〉〈0|k
(z − δ)2
(σxj + 11)Y (σ
j + 11) ⊗ |0〉〈0|k
(z − δ)2
(σxj + 11)
3 ⊗ |0〉〈0|k
The self-energy in the low energy subspace (where
qubit k is in state |0〉) is therefore:
Σ−−(z) ≃ Ỹ +
(z − δ)2
σzi (16)
z − δ
(z − δ)2
(σxj + 11)
(z − δ)2
σzi σ
‖V ‖4δ−3
+ · · ·
Ỹ is the interaction between qubits i and j which is the
original physical interaction dressed by the effect of vir-
tual excitations into the high energy subspace.
Ỹ = Y +
(z − δ)2 (σ
j + 11)Y (σ
j + 11) (17)
In practice there will always be some interaction be-
tween qubits i and j. We assume Y is a ZZXX Hamil-
tonian and express the dressed Hamiltonian Ỹ in terms
of modified coupling coefficients. Writing the physical
Hamiltonian:
Y = hiσ
i + hjσ
j + ∆iσ
i + ∆jσ
j + (18)
+ Jijσ
j +Kijσ
The new dressed coupling strengths are:
hi 7→ hi
(z − δ)2
∆i 7→ ∆i
(z − δ)2
(z − δ)2
∆j 7→ ∆j
(z − δ)2
Kij 7→ Kij
(z − δ)2
(z − δ)2
with additional couplings:
(z − δ)2
∆j11 +
(z − δ)2
j (20)
We see that the effect of the gadget on any existing phys-
ical interaction is to modify the coupling constants, add
an overall shift in energy, and to add a small correction
to the σzσz coupling which depends on the strength of
the σzi term in Y . If Y is regarded as the net uncontrolled
physical Hamiltonian coupling i and j (a source of error)
it is only the local σzi field which contributes to an error
in the σzσz coupling strength.
We make the following choices for our gadget parame-
ters A, B, C and D:
A = αij (21)
D = 2δ1/3Ē2/3
Where Ē is an energy scale parameter to be fixed later.
We expand the self-energy (16) in the limit where z is
constant (z = O(1) ≪ δ). Writing (z − δ)−1 ≃ − 1
) gives:
Σ(0)−− = Ỹ + αijσ
j (22)
Ē4/3
(σxj + 11)
‖V ‖4δ−3
+ · · ·
For the self-energy to become O(ǫ) close to Y +
j ⊗ |0〉〈0|k, the error terms in (22) must be
bounded above by ǫ through an appropriate choice of δ.
Define a lower bound on the spectral gap δ as an inverse
polynomial in ǫ: δ ≥ Ēǫ−r, where Ē is a constant and
integer r ≥ 1. Now bound r by considering the (weak)
upper bound on ‖V ‖:
‖V ‖ ≤ ‖Y ‖ + |αij | + 4δ1/3Ē2/3 (23)
+ 2Ē
|αij |
The largest term in δ−3‖V ‖4 is O(Ē(Ē/δ)1/3), and so
in order that δ−3‖V ‖4 < ǫ we require r ≥ 3. This also
bounds the term below fourth order, Ē4/3δ−1/3 = O(Ēǫ)
and so for z ≪ δ we obtain ‖Σ−−(z) −Heff‖ = O(ǫ). In
fact, Σ(0)−− = Heff + Ēǫ(σ
j + 11). Now apply Theorem
(3) from [14] and it follows that |λ(Heff)−λ(H̃)| = O(ǫ).
It also follows from Lemma (11) of [14] that the ground
state wavefunction ofHeff is also close to the ground state
of our gadget.
The ZZXX Hamiltonian (1) allows for the direct real-
ization of all terms in (10) except for σzσx and σxσz
interactions. These terms can be approximated with
only O(ǫ) error using the gadget in the present section—
thereby showing that the ZZXX Hamiltonian can effi-
ciently approximate all terms from (10). Similarly, the
ZX Hamiltonian allows for the direct realization of all
terms in (10) except for σzσz and σxσx interactions.
These terms will be approximated with only O(ǫ) er-
ror by defining gadgets in the coming sections—showing
that the ZX Hamiltonian can also be used to efficiently
approximate all terms from (10).
C. The ZZ from ZX gadget
We approximate the operator βijσ
j using the ZX
Hamiltonian in Eq. (2) by defining a penalty Hamiltonian
as in Eq. (11). The required perturbation is a sum of
terms V = V1 + V2:
V1 = Y +A|0〉〈0|k (24)
V2 = B(σ
i − σzj ) ⊗ σxk
The non-zero projections are:
V1++ = Y ⊗ |1〉〈1|k (25)
V1−− = (Y +A11 ⊗ |0〉〈0|k
V2+− = B(σ
i − σzj ) ⊗ |1〉〈0|k
V2−+ = B(σ
i − σzj ) ⊗ |0〉〈1|k
V1 does not couple the low and high energy subspaces and
V2 couples the subspaces but is zero in each subspace.
FIG. 2: The ZZ from ZX gadget: The present figure presents
a diagrammatic representation of the Perturbative Hamilto-
nian V = V1 + V2 from Eq. (24) applied to qubits i, j and k.
In addition to these terms shown in the present figure, there
is an overall energy shift of A/2.
The series expansion of the self-energy follows directly:
1st : (Y +A11) ⊗ |0〉〈0|k
2nd :
B2(σzi − σzj )2
(z − δ)
⊗ |0〉〈0|k (26)
3rd :
(z − δ)2
(σzi − σzj )Y (σzi − σzj ) ⊗ |0〉〈0|k
Note that in this case the desired terms appear at second
order in the expansion, rather than at third order as was
the case for the ZX from ZZXX gadget. The terms which
dress the physical hamiltonian Y coupling qubits i and j
appear at third order. The series expansion of the self-
energy in the low energy subspace is:
Σ(z)−− = (Ỹ +A11)
2B2(1 − σzi σzj )
(z − δ)
+ O(||V ||4δ−3)
where the dressed interaction Ỹ is defined:
Ỹ = Y +
(z − δ)2 (σ
i − σzj )Y (σzi − σzj ) (28)
We assume that the physical interaction Y between i and
j qubits is a ZX Hamiltonian and express the dressed
Hamiltonian in terms of modified coupling constants.
Writing the physical Hamiltonian:
Y = hiσ
i + hjσ
j + ∆iσ
i + ∆jσ
j (29)
+Jijσ
j +Kijσ
We obtain modified coupling strengths:
hi 7→ hi +
2B2(hi − hj)
(z − δ)2
hj 7→ hi +
2B2(hj − hi)
(z − δ)2 .
In this case only the local Z field strengths are modified.
We choose values for the perturbation interaction
strengths as follows: B =
and A = βij and ex-
pand the self-energy in the limit where z is constant
(z = O(1) ≪ δ):
Σ(0)−− = Ỹ + βijσ
+ O(||V ||4δ−3).
We again choose δ to be an inverse power in a small
parameter ǫ so that δ ≥ Ēǫ−s, and again use the (weak)
upper bound on ||V ||:
||V || ≤ ||Y || + βij +
2βijδ (32)
The largest term in ||V ||4δ−3 is 4β2ijδ−1, and so in order
that ||V ||4δ−3 < ǫ we require r ≥ 1.
Using the gadget defined in the present section, the ZX
Hamiltonian can now be used to efficiently approximate
all terms in (10) except for σxσx interactions. These
interactions can also be approximated with only O(ǫ)
error by defining an additional gadget in the next section.
D. The XX from ZX gadget
An σxσx coupling may be produced from the σzσx
coupling as follows. We define a penalty Hamiltonian
and corresponding Green’s function:
(11 − σxk ) = δ|−〉〈−|
G++ =
z − δ
|−〉〈−|k. (33)
This penalty Hamiltonian splits the Hilbert space into a
low energy subspace in which the ancilla qubit k is in
state |+〉 = (|0〉+ |1〉)/
2 and a high energy subspace in
which the ancilla qubit k is in state |−〉 = (|0〉− |1〉)/
The perturbation is a sum of two terms V = V1 + V2,
where V1 and V2 are given by:
V1 = Y ⊗ 11k +A|+〉〈+|k (34)
V2 = B(σ
i − σxj )σzk
The non-zero projections are:
V1++ = |−〉〈−|V1|−〉〈−|k (35)
= Y ⊗ |−〉〈−|k
V1−− = Y ⊗ |+〉〈+|k +A|+〉〈+|k
V2+− = |−〉〈−|V2|+〉〈+|k
= B(σxi − σxj )|−〉〈+|k
V2−+ = |+〉〈+|V2|−〉〈−|k
= B(σxi − σxj )|+〉〈−|k.
Once more we see that the perturbation V1 does not cou-
ple the subspaces, whereas V2 couples the subspaces but
FIG. 3: The XX from ZX gadget: The present figure
presents a diagrammatic representation of the Perturbative
Hamiltonian V = V1 + V2 from Eq. (34) applied to qubits
i, j and k. In addition to the terms shown in the present fig-
ure, there is an overall energy shift of A/2. The penalty term
applied to qubit k is the σx basis.
is zero in each subspace. This perturbation is illustrated
in Figure 3.
The series expansion of the self-energy follows:
1st : (Y +A11) ⊗ |+〉〈+|k (36)
2nd :
B2(σxi − σxj )2
(z − δ)
⊗ |+〉〈+|k
3rd :
(z − δ)2
(σxi − σxj )Y (σxi − σxj )
Again we see that the desired term appears at second
order, while the third order term is due to the dressing
of the physical interaction Y between qubits i and j. In
the low energy subspace the series expansion of the self-
energy to third order is:
Σ(z)−− = (Ỹ +A11) (37)
2B2(11 − σxi σxj )
(z − δ)
+ O(||V ||4δ−3)
where the dressed interaction Ỹ is defined:
Ỹ = Y +
(z − δ)2
(σxi − σxj )Y (σxi − σxj ). (38)
Once more we assume the physical Hamiltonian Y is a ZX
Hamiltonian 29 and we describe the effects of dressing to
low order in terms of the new dressed coupling strengths:
∆i 7→ ∆i +
2B2(∆i − ∆j)
(z − δ)2
∆j 7→ ∆i +
2B2(∆j − ∆i)
(z − δ)2
and in this case only the local X field strengths are mod-
ified.
Choosing values for our gadget parameters A = γij
and B =
and expanding the self-energy in the
limit where z is constant (z = O(1) ≪ δ) gives:
Σ(0)−− = Ỹ ⊗ |+〉〈+|k (40)
+ γijσ
j ⊗ |+〉〈+|k
+ O(||V ||4δ−3)
As before, this self-energy may be made O(ǫ) close to the
target Hamiltonian by a bound δ ≥ Ēǫ−1.
b. Summary The proof of Theorem (1) follows from
the simultaneous application of the ZZXX gadget illus-
trated in Fig. 1 to realize all σzσx terms in the target
Hamiltonian using a ZZXX Hamiltonian. Similarly, ap-
plication of the two gadgets illustrated in Fig. 2 and 3
to realize σxσx and σzσz terms in the target Hamilto-
nian proves the first part of Theorem (2). Our result is
based on Theorem (3) from [14] which allowed us to ap-
proximate (with O(ǫ) error) all the Hamiltonian terms
from Eq. (3) using either the ZZXX or ZX Hamiltonians.
It also follows from Lemma (11) of [14] that the ground
state wavefunction ofHeff is also close to the ground state
of our gadget. So to complete our proof, it is enough to
show that each gadget satisfies the criteria given in The-
orem (3) from [14].
II. CONCLUSION
The objective of this work was to provide simple model
Hamiltonians that are of practical interest for experi-
mentalists working towards the realization of a univer-
sal adiabatic quantum computer. Accomplishing such as
task also enabled us to find the simplest known QMA-
complete 2-local Hamiltonians. The σxσx coupler is re-
alizable using systems including capacitive coupling of
flux qubits [22] and spin models implemented with po-
lar molecules [23]. In addition, a σzσx coupler for flux
qubits is given in [24]. The ZX and ZZXX Hamiltonians
enable gate model [25], autonomous [26], measurement-
based [27] and universal adiabatic quantum computa-
tion [10, 14, 15], and may also be useful for quan-
tum annealing [28]. For these reasons, the reported
Hamiltonians are of interest to those concerned with the
practical construction of a universal adiabatic quantum
computer[30].
[1] F. Barahona, J. Phys. A: Math. Gen. 15, 3241 (1982).
[2] S. Kirkpatrick et al., Science 220, 671 (1983).
[3] J. Brooke, D. Bitko, T. Rosenbaum, and G. Aeppli, Sci-
ence 284, 779 (1999), cond-mat/0105238.
[4] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Sci-
ence 292, 472 (2000), quant-ph/0208135.
[5] A. Ambainis and O. Regev (2006), quant-ph/0411152.
[6] R. Harris et al., to appear in Phys. Rev. Lett. (2007),
cond-mat/0608253.
[7] S. Bravyi, D. DiVincenzo, R. Oliveira, and B. Terhal
(2006), quant-ph/0606140.
[8] A. Kitaev, A. Shen, and M. Vyalyi, AMS, Graduate
Studies in Mathematics 47 (2002).
[9] R. Feynman, Optics News (now OPN) 11, 11 (1982).
[10] D. Aharonov, W. van Dam, J. Kempe, Z. Landau,
S. Lloyd, and O. Regev (2005), quant-ph/0405098.
[11] M. S. Siu, Phys. Rev. A 71, 062314 (2005),
quant-ph/0409024.
[12] A. Mizel, D. A. Lidar, and M. Mitchell (2006),
quant-ph/0609067.
[13] Y. Shi (2002), quant-ph/0205115.
[14] J. Kempe, A. Kitaev, and O. Regev, SIAM J. Computing
35(5), 1070 (2006), quant-ph/0406180.
[15] R. Oliveira and B. Terhal (2006), quant-ph/0504050.
[16] D. Deutsch and R. Jozsa, Proc. R. Soc. London Ser. A,
439, 553 (1992).
[17] E. Bernstein and U. Vazirani, SIAM J. Computing 26,
1411 (1997), quant-ph/9701001.
[18] T. Rudolph and L. Grover (2002), quant-ph/0210187.
[19] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-
Gordon, Science 309, 1704 (2005), quant-ph/0604193.
[20] D. Nagaj and S. Mozes (2006), quant-ph/0612113.
[21] J. Kempe and O. Regev, Quantum Computation and In-
formation 3(3), 258 (2003), quant-ph/0302079.
[22] D. V. Averin and C. Bruder, Phys. Rev. Lett. 91, 057003
(2003), cond-mat/0304166.
[23] A. Micheli, G. Brennen, and P. Zoller, Nature Phys. 2,
341 (2006), quant-ph/0512222.
[24] T. P. Orlando, J. E. Mooij, L. Tian, C. H. van der Wal,
L. S. Levitov, S. Lloyd, and J. J. Mazo, Phys. Rev. B 60,
15398 (1999).
[25] A. Barenco, D. Deutsch, A. Ekert, and R. Jozsa, Phys.
Rev. Lett. 74, 4083 (1995), quant-ph/9503017.
[26] D. Janzing, Phys. Rev. A 75, 012307 (2007),
quant-ph/0506270.
[27] S. D. Bartlett and T. Rudolph, Phys. Rev. A 74, 040302
(2006), quant-ph/0609002.
[28] S. Suzuki, H. Nishimori, and M. Suzuki (2007),
quant-ph/0702214.
[29] The QMA-completeness of this subset of Hamiltonians
was found independently by D. Bacon; preprint, (2007).
[30] We thank C.J.S. Truncik, R.G. Harris, W.G. Macready,
M.H.S. Amin, A.J. Berkley, P. Bunyk, J. Lamothe, T.
Mahon and G. Rose. J.D.B. and P.J.L. completed parts
of this work well on staff as D-Wave Systems Inc.
http://arxiv.org/abs/cond-mat/0105238
http://arxiv.org/abs/quant-ph/0208135
http://arxiv.org/abs/quant-ph/0411152
http://arxiv.org/abs/cond-mat/0608253
http://arxiv.org/abs/quant-ph/0606140
http://arxiv.org/abs/quant-ph/0405098
http://arxiv.org/abs/quant-ph/0409024
http://arxiv.org/abs/quant-ph/0609067
http://arxiv.org/abs/quant-ph/0205115
http://arxiv.org/abs/quant-ph/0406180
http://arxiv.org/abs/quant-ph/0504050
http://arxiv.org/abs/quant-ph/9701001
http://arxiv.org/abs/quant-ph/0210187
http://arxiv.org/abs/quant-ph/0604193
http://arxiv.org/abs/quant-ph/0612113
http://arxiv.org/abs/quant-ph/0302079
http://arxiv.org/abs/cond-mat/0304166
http://arxiv.org/abs/quant-ph/0512222
http://arxiv.org/abs/quant-ph/9503017
http://arxiv.org/abs/quant-ph/0506270
http://arxiv.org/abs/quant-ph/0609002
http://arxiv.org/abs/quant-ph/0702214

  It has been established that local lattice spin Hamiltonians can be used for
universal adiabatic quantum computation. However, the 2-local model
Hamiltonians used in these proofs are general and hence do not limit the types
of interactions required between spins. To address this concern, the present
paper provides two simple model Hamiltonians that are of practical interest to
experimentalists working towards the realization of a universal adiabatic
quantum computer. The model Hamiltonians presented are the simplest known
QMA-complete 2-local Hamiltonians. The 2-local Ising model with 1-local
transverse field which has been realized using an array of technologies, is
perhaps the simplest quantum spin model but is unlikely to be universal for
adiabatic quantum computation. We demonstrate that this model can be rendered
universal and QMA-complete by adding a tunable 2-local transverse XX coupling.
We also show the universality and QMA-completeness of spin models with only
1-local Z and X fields and 2-local ZX interactions.

Realizable Hamiltonians for universal adiabatic quantum computers
Jacob D. Biamonte1, ∗ and Peter J. Love2, †
Oxford University Computing Laboratory,
Wolfson Building, Parks Road, Oxford, OX1 3QD, United Kingdom.
Department of Physics, 370 Lancaster Ave., Haverford College, Haverford, PA USA 19041.
It has been established that local lattice spin Hamiltonians can be used for universal adiabatic
quantum computation. However, the 2-local model Hamiltonians used in these proofs are general
and hence do not limit the types of interactions required between spins. To address this concern,
the present paper provides two simple model Hamiltonians that are of practical interest to experi-
mentalists working towards the realization of a universal adiabatic quantum computer. The model
Hamiltonians presented are the simplest known quantum-Merlin-Arthur-complete (QMA-complete)
2-local Hamiltonians. The 2-local Ising model with 1-local transverse field which has been realized
using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be
universal for adiabatic quantum computation. We demonstrate that this model can be rendered
universal and QMA-complete by adding a tunable 2-local transverse σxσx coupling. We also show
the universality and QMA-completeness of spin models with only 1-local σz and σx fields and 2-local
σzσx interactions.
What are the minimal physical resources required for
universal quantum computation? This question is of in-
terest in understanding the connections between phys-
ical and computational complexity, and for any practi-
cal implementation of quantum computation. In 1982,
Barahona [1] showed that finding the ground state of the
random field Ising model is NP-hard. Such observations
fostered approaches to solving problems based on classi-
cal [2] and later quantum annealing [3]. The idea of using
the ground state properties of a quantum system for com-
putation found its full expression in the adiabatic model
of quantum computation [4]. This model works by evolv-
ing a system from the accessible ground state of an initial
Hamiltonian Hi to the ground state of a final Hamilto-
nian Hf, which encodes a problem’s solution. The evo-
lution takes place over parameters s ∈ [0, 1] as H(s) =
(1−s)Hi+sHf, where s changes slowly enough that tran-
sitions out of the ground state are suppressed [5]. The
simplest adiabatic algorithms can be realized by adding
non-commuting transverse field terms to the Ising Hamil-
tonian:
i hiσ
i ∆iσ
i,j Jijσ
j , (c.f. [6]).
However, it is unlikely that the Ising model with trans-
verse field can be used to construct a universal adiabatic
quantum computer [7].
What then are the simplest Hamiltonians that al-
low universal adiabatic quantum computation? For this
we turn to the complexity class quantum-Merlin-Arthur
(QMA), the quantum analog of NP, and consider the
QMA-complete problem k-local Hamiltonian [8]. One
solves k-local Hamiltonian by determining if there ex-
ists an eigenstate with energy above a given value or be-
low another—with a promise that one of these situations
is the case—when the system has at most k-local inter-
actions. A Yes instance is shown by providing a witness
∗Electronic address: jacob.biamonte@comlab.ox.ac.uk
†Electronic address: plove@haverford.edu
eigenstate with energy below the lowest promised value.
The problem 5-local Hamiltonian was shown to be
QMA-complete by Kitaev [8]. To accomplish this, Ki-
taev modified the autonomous quantum computer pro-
posed by Feynman [9]. This modification later inspired
a proof of the polynomial equivalence between quantum
circuits and adiabatic evolutions by Aharonov et al. [10]
(see also [11, 12]). Kempe, Kitaev and Regev subse-
quently proved QMA-completeness of 2-local Hamil-
tonian [14]. Oliveira and Terhal then showed that uni-
versality remains even when the 2-local Hamiltonians act
on particles in a subgraph of the 2D square lattice [15].
Any QMA-complete Hamiltonian may realize universal
adiabatic quantum computation, and so these results are
also of interest for the implementation of quantum com-
putation.
Since 1-local Hamiltonian is efficiently solvable,
an open question is to determine which combinations of
2-local interactions allow one to build QMA-complete
Hamiltonians. Furthermore, the problem of finding
the minimum set of interactions required to build a
universal adiabatic quantum computer is of practical, as
well as theoretical, interest: every type of 2-local inter-
action requires a separate type of physical interaction.
To address this question we prove the following theorems:
Theorem 1. The problem 2-local ZZXX Hamil-
tonian is QMA-complete, with the ZZXX Hamiltonian
given as:
HZZXX =
i + (1)
Theorem 2. The problem 2-local ZX Hamiltonian
http://arXiv.org/abs/0704.1287v2
mailto:jacob.biamonte@comlab.ox.ac.uk
mailto:plove@haverford.edu
is QMA-complete, with the ZX Hamiltonian given as
HZX =
i + (2)
a. Structure In the present paper we briefly review
the standard circuit to adiabatic construction to show
that 2-local Hamiltonian is QMA-complete when re-
stricted to real-valued Hamiltonians. We then show how
to approximate the ground states of such 2-local real
Hamiltonians by the ZX and ZZXX Hamiltonians. We
conclude this work by providing references confirming our
claim that the Hamiltonians in Eq. (1) and (2) are highly
relevant to experimentalists attempting to build a univer-
sal adiabatic quantum computer.
I. THE PROBLEM
The translation from quantum circuits to adiabatic
evolutions began when Kitaev [8] replaced the time-
dependence of gate model quantum algorithms with spa-
tial degrees of freedom using the non-degenerate ground
state of a positive semidefinite Hamiltonian:
0 = H |ψhist〉 = (3)
(Hin +Hclock +Hclockinit +Hprop)|ψhist〉.
To describe this, let T be the number of gates in the
quantum circuit with gate sequence UT · · ·U2U1 and let
n be the number of logical qubits acted on by the circuit.
Denote the circuit’s classical input by |x〉 and its output
by |ψout〉. The history state representing the circuit’s
entire time evolution is:
|ψhist〉 =
T + 1
|x〉 ⊗ |0〉⊗T + U1|x〉 ⊗ |1〉|0〉⊗T−1
+ U2U1|x〉 ⊗ |11〉|0〉⊗T−2
+ . . . (4)
+ UT · · ·U2U1|x〉 ⊗ |1〉⊗T
where we have indexed distinct time steps by a T qubit
unary clock. In the following, tensor product symbols
separate operators acting on logical qubits (left) and
clock qubits (right).
Hin acts on all n logical qubits and the first clock
qubit. By annihilating time-zero clock states coupled
with classical input x, Hin ensures that valid input state
(|x〉 ⊗ |0...0〉) is in the low energy eigenspace:
Hin =
(11 − |xi〉〈xi|) ⊗ |0〉〈0|1 (5)
(11 − (−1)xiσzi ) ⊗ (11 + σz1).
Hclock is an operator on clock qubits ensuring that
valid unary clock states |00...0〉, |10..0〉, |110..0〉 etc., span
the low energy eigenspace:
Hclock =
|01〉〈01|(t,t+1) (6)
(T − 1)11 + σz1 − σzT −
σzt σ
(t+1)
where the superscript (t, t+ 1) indicates the clock qubits
acted on by the projection. This Hamiltonian has a sim-
ple physical interpretation as a line of ferromagnetically
coupled spins with twisted boundary conditions, so that
the ground state is spanned by all states with a sin-
gle domain wall. The term Hclockint applies a penalty
|1〉〈1|t=1 to the first qubit to ensure that the clock is in
state |0〉⊗T− at time t = 0.
Hprop acts both on logical and clock qubits. It en-
sures that the ground state is the history state corre-
sponding to the given circuit. Hprop is a sum of T
terms, Hprop =
t=1Hprop,t, where each term checks
that the propagation from time t− 1 to t is correct. For
2 ≤ t ≤ T − 1, Hprop,t is defined as:
Hprop,t
= 11 ⊗ |t− 1〉〈t− 1| − Ut ⊗ |t〉〈t− 1|
− U †t ⊗ |t− 1〉〈t| + 11 ⊗ |t〉〈t|, (7)
where operators |t〉〈t− 1| = |110〉〈100|(t−1,t,t+1) etc., act
on clock qubits t−1, t, and t+1 and where the operator
Ut is the t
th gate in the circuit. For the boundary cases
(t = 1, T ), one writes Hprop,t by omitting a clock qubit
(t− 1 and t+ 1 respectively).
We have now explained all the terms in the Hamilto-
nian from Eq. (3)—a key building block used to prove the
QMA-completeness of 5-local Hamiltonian [8]. The
construction reviewed in the present section was also
used in a proof of the polynomial equivalence between
quantum circuits and adiabatic evolutions [10]. Which
physical systems can implement the Hamiltonian model
of computation from Eq. (3)? Ideally, we wish to find a
simple Hamiltonian that is in principle realizable using
current, or near-future technology. The ground states
of many physical systems are real-valued, such as the
ground states of the Hamiltonians from Eq. (1) and (2).
So a logical first step in our program is to show the QMA-
completeness of general real-valued local Hamiltonians.
A. The QMA-completeness of real-valued
Hamiltonians
Bernstein and Vazirani showed that arbitrary quan-
tum circuits may be represented using real-valued gates
operating on real-valued wave functions [17]. Using this
idea, one can show that 5-local real Hamiltonian
is already QMA-complete—leaving the proofs in [8] oth-
erwise intact and changing only the gates used in the
circuits. Hin from Eq. (5) and Hclock from Eq. (6) are al-
ready real-valued and at most 2-local. Now consider the
terms in Hprop from Eq. (7) for the case of self-inverse
elementary gates Ut = U
Hprop,t =
(11 − σz(t−1))(11 + σ
(t+1)) (8)
(11 − σz(t−1))σ
t (11 + σ
(t+1))
For the boundary cases (t = 1, T ), define:
Hprop,1 =
(11 + σz2) − U1 ⊗
(σx1 + σ
2) (9)
Hprop,T =
(11 − σz(T−1)) − UT ⊗
(σxT − σz(T−1)σ
The terms from Eq. (8) and (9) acting on the clock space
are already real-valued and at most 3-local. As an ex-
plicit example of the gates Ut, let us define a universal
real-valued and self-inverse 2-qubit gate:
Rij(φ) =
(11+σzi )+
(11−σzi )⊗ (sin(φ)σxi +cos(φ)σzj ).
The gate sequence Rij(φ)Rij(π/2) recovers the universal
gate from [18]. This is a continuous set of elementary
gates parameterized by the angle φ. Discrete sets of self
inverse gates which are universal are also readily con-
structed. For example, Shi showed that a set comprising
the C-NOT plus any one-qubit gate whose square does
not preserve the computational basis is universal [13]. We
immediately see that a universal set of self-inverse gates
cannot contain only the C-NOT and a single one-qubit
gate. However, the set {C-NOT, X, cosψX + sinψZ} is
universal for any single value of ψ which is not a multiple
of π/4.
A reduction from 5-local to 2-local Hamiltonian
was accomplished by the use of gadgets that reduced 3-
local Hamiltonian terms to 2-local terms [14]. From the
results in [14] (see also [15]) and the QMA-completeness
of 5-local real Hamiltonian, it now follows that 2-
local real Hamiltonian is QMA-complete and uni-
versal for adiabatic quantum computation. We note that
the real product σ
j , or tensor powers thereof, are not
necessary in any part of our construction, and so Hamil-
tonians composed of the following pairwise products of
real-valued Pauli matrices are QMA-complete and uni-
versal for adiabatic quantum computation[29]:
{11, 11 ⊗ σx, 11 ⊗ σz , σx ⊗ 11, (10)
σz ⊗ 11, σx ⊗ σz, σz ⊗ σx, σx ⊗ σx, σz ⊗ σz}.
To prove our Theorems (1) and (2), we will next show
that one can approximate all the terms from Eq. (10)
using either the ZX or ZZXX Hamiltonians—the Hamil-
tonians from Eq. (1) and (2) respectively. We do this
using perturbation theory [14, 15] to construct gadget
Hamiltonians that approximate the operators σzi σ
j and
σxi σ
i with terms from the ZZXX Hamiltonian as well as
the operators σzi σ
i and σ
j with terms from the ZX
Hamiltonian.
B. The ZZXX gadget
We use the ZZXX Hamiltonian from Eq. (1) to con-
struct the interaction σzi σ
j from σ
xσx and σzσz interac-
tions. Let Heff = αijσ
j ⊗ |0〉〈0|k, where qubit k is an
ancillary qubit and define the penalty Hamiltonian Hp
and corresponding Green’s function G(z) as follows:
Hp = δ|1〉〈1|k =
(11 − σzk) and (11)
= (z11 −Hp)−1.
Hp splits the Hilbert space into a degenerate low en-
ergy eigenspace L− = span{|sisj〉|0〉|∀si, sj ∈ {0, 1}}, in
which qubit k is |0〉, and a δ energy eigenspace L+ =
span{|sisj〉|1〉|∀si, sj ∈ {0, 1}}, in which qubit k is |1〉.
First, we give the ZZXX Hamiltonian which pro-
duces an effective σzσz interaction in the low energy
subspace. Let Y be an arbitrary ZZXX Hamiltonian
acting on qubits i and j and consider a perturbation
V = V1 + V2 + V3 that breaks the L− zero eigenspace
degeneracy by creating an operator O(ǫ) close to Heff in
this space:
V1 = [Y +D(σ
j + 11)] ⊗ 11k −Aσzi ⊗ |0〉〈0|k
V2 = B(σ
j + 11) ⊗ σxk (12)
V3 = Cσ
i ⊗ |1〉〈1|k.
The term V2 above allows the mediator qubit k to un-
dergo virtual excitations and applies an σx term to qubit
j during transitions between the L− and L+ subspaces.
During excitation into L+, the term V3 applies a σz term
to qubit i. This perturbation is illustrated in figure 1
FIG. 1: The ZZXX gadget used to approximate the operator
σzi σ
j using only σ
xσx and σzσz interactions. The present
figure presents a diagrammatic representation of the Pertur-
bation Hamiltonian V = V1 + V2 + V3 from Eq. (12) applied
to qubits i, j and k. Not shown in the present figure is an
overall constant energy shift of D.
Let Π± be projectors on L±; for arbitrary operator
O we define O±∓ = Π±OΠ∓ (O±± = Π±OΠ±) and let
λ(O) denote the lowest eigenvalue of O. One approxi-
mates λ(Htarg) of the desired low energy effective 2-local
Hamiltonian by a realizable 2-local physical Hamiltonian
H̃ = Hp + V , where λ(H̃) is calculated using perturba-
tion theory. The spectrum of H̃−− is approximated by
the projection of the self-energy operator Σ(z) for real-
valued z which has the following series expansion:
Σ−−(z) =
Hp– +
V−− +
︷ ︸︸ ︷
V−+G++(z)V+− (13)
+ V−+G++(z)V+G++(z)V+−
︸ ︷︷ ︸
‖V ‖4δ−3
+ · · ·
Note that with our penalty Hamiltonian H−− = 0,
and for the perturbing Hamiltonian V = V1 + V2 + V3
only V1 is nonzero in the low energy subspace, V1 and
V3 are nonzero in the high energy subspace, and only
V2 induces transitions between the two subspaces. The
non-zero projections are:
V1−− = [Y +Aσ
i +D(σ
j + 11)] ⊗ |0〉〈0|k
V2−+ = B(σ
j + 11) ⊗ |0〉〈1|k
V2+− = B(σ
j + 11) ⊗ |1〉〈0|k (14)
V3++ = V3
V+ = (Y + Cσ
i +D(σ
j + 11)) ⊗ |1〉〈1|k
The series expansion of the self-energy follows directly:
1st : (Y −Aσzi +D(σxj + 11)) ⊗ |0〉〈0|k
2nd :
z − δ
(σxj + 11)
2 ⊗ |0〉〈0|k (15)
3rd :
(z − δ)2
(σxj + 11)σ
j + 11) ⊗ |0〉〈0|k
(z − δ)2
(σxj + 11)Y (σ
j + 11) ⊗ |0〉〈0|k
(z − δ)2
(σxj + 11)
3 ⊗ |0〉〈0|k
The self-energy in the low energy subspace (where
qubit k is in state |0〉) is therefore:
Σ−−(z) ≃ Ỹ +
(z − δ)2
σzi (16)
z − δ
(z − δ)2
(σxj + 11)
(z − δ)2
σzi σ
‖V ‖4δ−3
+ · · ·
Ỹ is the interaction between qubits i and j which is the
original physical interaction dressed by the effect of vir-
tual excitations into the high energy subspace.
Ỹ = Y +
(z − δ)2 (σ
j + 11)Y (σ
j + 11) (17)
In practice there will always be some interaction be-
tween qubits i and j. We assume Y is a ZZXX Hamil-
tonian and express the dressed Hamiltonian Ỹ in terms
of modified coupling coefficients. Writing the physical
Hamiltonian:
Y = hiσ
i + hjσ
j + ∆iσ
i + ∆jσ
j + (18)
+ Jijσ
j +Kijσ
The new dressed coupling strengths are:
hi 7→ hi
(z − δ)2
∆i 7→ ∆i
(z − δ)2
(z − δ)2
∆j 7→ ∆j
(z − δ)2
Kij 7→ Kij
(z − δ)2
(z − δ)2
with additional couplings:
(z − δ)2
∆j11 +
(z − δ)2
j (20)
We see that the effect of the gadget on any existing phys-
ical interaction is to modify the coupling constants, add
an overall shift in energy, and to add a small correction
to the σzσz coupling which depends on the strength of
the σzi term in Y . If Y is regarded as the net uncontrolled
physical Hamiltonian coupling i and j (a source of error)
it is only the local σzi field which contributes to an error
in the σzσz coupling strength.
We make the following choices for our gadget parame-
ters A, B, C and D:
A = αij (21)
D = 2δ1/3Ē2/3
Where Ē is an energy scale parameter to be fixed later.
We expand the self-energy (16) in the limit where z is
constant (z = O(1) ≪ δ). Writing (z − δ)−1 ≃ − 1
) gives:
Σ(0)−− = Ỹ + αijσ
j (22)
Ē4/3
(σxj + 11)
‖V ‖4δ−3
+ · · ·
For the self-energy to become O(ǫ) close to Y +
j ⊗ |0〉〈0|k, the error terms in (22) must be
bounded above by ǫ through an appropriate choice of δ.
Define a lower bound on the spectral gap δ as an inverse
polynomial in ǫ: δ ≥ Ēǫ−r, where Ē is a constant and
integer r ≥ 1. Now bound r by considering the (weak)
upper bound on ‖V ‖:
‖V ‖ ≤ ‖Y ‖ + |αij | + 4δ1/3Ē2/3 (23)
+ 2Ē
|αij |
The largest term in δ−3‖V ‖4 is O(Ē(Ē/δ)1/3), and so
in order that δ−3‖V ‖4 < ǫ we require r ≥ 3. This also
bounds the term below fourth order, Ē4/3δ−1/3 = O(Ēǫ)
and so for z ≪ δ we obtain ‖Σ−−(z) −Heff‖ = O(ǫ). In
fact, Σ(0)−− = Heff + Ēǫ(σ
j + 11). Now apply Theorem
(3) from [14] and it follows that |λ(Heff)−λ(H̃)| = O(ǫ).
It also follows from Lemma (11) of [14] that the ground
state wavefunction ofHeff is also close to the ground state
of our gadget.
The ZZXX Hamiltonian (1) allows for the direct real-
ization of all terms in (10) except for σzσx and σxσz
interactions. These terms can be approximated with
only O(ǫ) error using the gadget in the present section—
thereby showing that the ZZXX Hamiltonian can effi-
ciently approximate all terms from (10). Similarly, the
ZX Hamiltonian allows for the direct realization of all
terms in (10) except for σzσz and σxσx interactions.
These terms will be approximated with only O(ǫ) er-
ror by defining gadgets in the coming sections—showing
that the ZX Hamiltonian can also be used to efficiently
approximate all terms from (10).
C. The ZZ from ZX gadget
We approximate the operator βijσ
j using the ZX
Hamiltonian in Eq. (2) by defining a penalty Hamiltonian
as in Eq. (11). The required perturbation is a sum of
terms V = V1 + V2:
V1 = Y +A|0〉〈0|k (24)
V2 = B(σ
i − σzj ) ⊗ σxk
The non-zero projections are:
V1++ = Y ⊗ |1〉〈1|k (25)
V1−− = (Y +A11 ⊗ |0〉〈0|k
V2+− = B(σ
i − σzj ) ⊗ |1〉〈0|k
V2−+ = B(σ
i − σzj ) ⊗ |0〉〈1|k
V1 does not couple the low and high energy subspaces and
V2 couples the subspaces but is zero in each subspace.
FIG. 2: The ZZ from ZX gadget: The present figure presents
a diagrammatic representation of the Perturbative Hamilto-
nian V = V1 + V2 from Eq. (24) applied to qubits i, j and k.
In addition to these terms shown in the present figure, there
is an overall energy shift of A/2.
The series expansion of the self-energy follows directly:
1st : (Y +A11) ⊗ |0〉〈0|k
2nd :
B2(σzi − σzj )2
(z − δ)
⊗ |0〉〈0|k (26)
3rd :
(z − δ)2
(σzi − σzj )Y (σzi − σzj ) ⊗ |0〉〈0|k
Note that in this case the desired terms appear at second
order in the expansion, rather than at third order as was
the case for the ZX from ZZXX gadget. The terms which
dress the physical hamiltonian Y coupling qubits i and j
appear at third order. The series expansion of the self-
energy in the low energy subspace is:
Σ(z)−− = (Ỹ +A11)
2B2(1 − σzi σzj )
(z − δ)
+ O(||V ||4δ−3)
where the dressed interaction Ỹ is defined:
Ỹ = Y +
(z − δ)2 (σ
i − σzj )Y (σzi − σzj ) (28)
We assume that the physical interaction Y between i and
j qubits is a ZX Hamiltonian and express the dressed
Hamiltonian in terms of modified coupling constants.
Writing the physical Hamiltonian:
Y = hiσ
i + hjσ
j + ∆iσ
i + ∆jσ
j (29)
+Jijσ
j +Kijσ
We obtain modified coupling strengths:
hi 7→ hi +
2B2(hi − hj)
(z − δ)2
hj 7→ hi +
2B2(hj − hi)
(z − δ)2 .
In this case only the local Z field strengths are modified.
We choose values for the perturbation interaction
strengths as follows: B =
and A = βij and ex-
pand the self-energy in the limit where z is constant
(z = O(1) ≪ δ):
Σ(0)−− = Ỹ + βijσ
+ O(||V ||4δ−3).
We again choose δ to be an inverse power in a small
parameter ǫ so that δ ≥ Ēǫ−s, and again use the (weak)
upper bound on ||V ||:
||V || ≤ ||Y || + βij +
2βijδ (32)
The largest term in ||V ||4δ−3 is 4β2ijδ−1, and so in order
that ||V ||4δ−3 < ǫ we require r ≥ 1.
Using the gadget defined in the present section, the ZX
Hamiltonian can now be used to efficiently approximate
all terms in (10) except for σxσx interactions. These
interactions can also be approximated with only O(ǫ)
error by defining an additional gadget in the next section.
D. The XX from ZX gadget
An σxσx coupling may be produced from the σzσx
coupling as follows. We define a penalty Hamiltonian
and corresponding Green’s function:
(11 − σxk ) = δ|−〉〈−|
G++ =
z − δ
|−〉〈−|k. (33)
This penalty Hamiltonian splits the Hilbert space into a
low energy subspace in which the ancilla qubit k is in
state |+〉 = (|0〉+ |1〉)/
2 and a high energy subspace in
which the ancilla qubit k is in state |−〉 = (|0〉− |1〉)/
The perturbation is a sum of two terms V = V1 + V2,
where V1 and V2 are given by:
V1 = Y ⊗ 11k +A|+〉〈+|k (34)
V2 = B(σ
i − σxj )σzk
The non-zero projections are:
V1++ = |−〉〈−|V1|−〉〈−|k (35)
= Y ⊗ |−〉〈−|k
V1−− = Y ⊗ |+〉〈+|k +A|+〉〈+|k
V2+− = |−〉〈−|V2|+〉〈+|k
= B(σxi − σxj )|−〉〈+|k
V2−+ = |+〉〈+|V2|−〉〈−|k
= B(σxi − σxj )|+〉〈−|k.
Once more we see that the perturbation V1 does not cou-
ple the subspaces, whereas V2 couples the subspaces but
FIG. 3: The XX from ZX gadget: The present figure
presents a diagrammatic representation of the Perturbative
Hamiltonian V = V1 + V2 from Eq. (34) applied to qubits
i, j and k. In addition to the terms shown in the present fig-
ure, there is an overall energy shift of A/2. The penalty term
applied to qubit k is the σx basis.
is zero in each subspace. This perturbation is illustrated
in Figure 3.
The series expansion of the self-energy follows:
1st : (Y +A11) ⊗ |+〉〈+|k (36)
2nd :
B2(σxi − σxj )2
(z − δ)
⊗ |+〉〈+|k
3rd :
(z − δ)2
(σxi − σxj )Y (σxi − σxj )
Again we see that the desired term appears at second
order, while the third order term is due to the dressing
of the physical interaction Y between qubits i and j. In
the low energy subspace the series expansion of the self-
energy to third order is:
Σ(z)−− = (Ỹ +A11) (37)
2B2(11 − σxi σxj )
(z − δ)
+ O(||V ||4δ−3)
where the dressed interaction Ỹ is defined:
Ỹ = Y +
(z − δ)2
(σxi − σxj )Y (σxi − σxj ). (38)
Once more we assume the physical Hamiltonian Y is a ZX
Hamiltonian 29 and we describe the effects of dressing to
low order in terms of the new dressed coupling strengths:
∆i 7→ ∆i +
2B2(∆i − ∆j)
(z − δ)2
∆j 7→ ∆i +
2B2(∆j − ∆i)
(z − δ)2
and in this case only the local X field strengths are mod-
ified.
Choosing values for our gadget parameters A = γij
and B =
and expanding the self-energy in the
limit where z is constant (z = O(1) ≪ δ) gives:
Σ(0)−− = Ỹ ⊗ |+〉〈+|k (40)
+ γijσ
j ⊗ |+〉〈+|k
+ O(||V ||4δ−3)
As before, this self-energy may be made O(ǫ) close to the
target Hamiltonian by a bound δ ≥ Ēǫ−1.
b. Summary The proof of Theorem (1) follows from
the simultaneous application of the ZZXX gadget illus-
trated in Fig. 1 to realize all σzσx terms in the target
Hamiltonian using a ZZXX Hamiltonian. Similarly, ap-
plication of the two gadgets illustrated in Fig. 2 and 3
to realize σxσx and σzσz terms in the target Hamilto-
nian proves the first part of Theorem (2). Our result is
based on Theorem (3) from [14] which allowed us to ap-
proximate (with O(ǫ) error) all the Hamiltonian terms
from Eq. (3) using either the ZZXX or ZX Hamiltonians.
It also follows from Lemma (11) of [14] that the ground
state wavefunction ofHeff is also close to the ground state
of our gadget. So to complete our proof, it is enough to
show that each gadget satisfies the criteria given in The-
orem (3) from [14].
II. CONCLUSION
The objective of this work was to provide simple model
Hamiltonians that are of practical interest for experi-
mentalists working towards the realization of a univer-
sal adiabatic quantum computer. Accomplishing such as
task also enabled us to find the simplest known QMA-
complete 2-local Hamiltonians. The σxσx coupler is re-
alizable using systems including capacitive coupling of
flux qubits [22] and spin models implemented with po-
lar molecules [23]. In addition, a σzσx coupler for flux
qubits is given in [24]. The ZX and ZZXX Hamiltonians
enable gate model [25], autonomous [26], measurement-
based [27] and universal adiabatic quantum computa-
tion [10, 14, 15], and may also be useful for quan-
tum annealing [28]. For these reasons, the reported
Hamiltonians are of interest to those concerned with the
practical construction of a universal adiabatic quantum
computer[30].
[1] F. Barahona, J. Phys. A: Math. Gen. 15, 3241 (1982).
[2] S. Kirkpatrick et al., Science 220, 671 (1983).
[3] J. Brooke, D. Bitko, T. Rosenbaum, and G. Aeppli, Sci-
ence 284, 779 (1999), cond-mat/0105238.
[4] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Sci-
ence 292, 472 (2000), quant-ph/0208135.
[5] A. Ambainis and O. Regev (2006), quant-ph/0411152.
[6] R. Harris et al., to appear in Phys. Rev. Lett. (2007),
cond-mat/0608253.
[7] S. Bravyi, D. DiVincenzo, R. Oliveira, and B. Terhal
(2006), quant-ph/0606140.
[8] A. Kitaev, A. Shen, and M. Vyalyi, AMS, Graduate
Studies in Mathematics 47 (2002).
[9] R. Feynman, Optics News (now OPN) 11, 11 (1982).
[10] D. Aharonov, W. van Dam, J. Kempe, Z. Landau,
S. Lloyd, and O. Regev (2005), quant-ph/0405098.
[11] M. S. Siu, Phys. Rev. A 71, 062314 (2005),
quant-ph/0409024.
[12] A. Mizel, D. A. Lidar, and M. Mitchell (2006),
quant-ph/0609067.
[13] Y. Shi (2002), quant-ph/0205115.
[14] J. Kempe, A. Kitaev, and O. Regev, SIAM J. Computing
35(5), 1070 (2006), quant-ph/0406180.
[15] R. Oliveira and B. Terhal (2006), quant-ph/0504050.
[16] D. Deutsch and R. Jozsa, Proc. R. Soc. London Ser. A,
439, 553 (1992).
[17] E. Bernstein and U. Vazirani, SIAM J. Computing 26,
1411 (1997), quant-ph/9701001.
[18] T. Rudolph and L. Grover (2002), quant-ph/0210187.
[19] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-
Gordon, Science 309, 1704 (2005), quant-ph/0604193.
[20] D. Nagaj and S. Mozes (2006), quant-ph/0612113.
[21] J. Kempe and O. Regev, Quantum Computation and In-
formation 3(3), 258 (2003), quant-ph/0302079.
[22] D. V. Averin and C. Bruder, Phys. Rev. Lett. 91, 057003
(2003), cond-mat/0304166.
[23] A. Micheli, G. Brennen, and P. Zoller, Nature Phys. 2,
341 (2006), quant-ph/0512222.
[24] T. P. Orlando, J. E. Mooij, L. Tian, C. H. van der Wal,
L. S. Levitov, S. Lloyd, and J. J. Mazo, Phys. Rev. B 60,
15398 (1999).
[25] A. Barenco, D. Deutsch, A. Ekert, and R. Jozsa, Phys.
Rev. Lett. 74, 4083 (1995), quant-ph/9503017.
[26] D. Janzing, Phys. Rev. A 75, 012307 (2007),
quant-ph/0506270.
[27] S. D. Bartlett and T. Rudolph, Phys. Rev. A 74, 040302
(2006), quant-ph/0609002.
[28] S. Suzuki, H. Nishimori, and M. Suzuki (2007),
quant-ph/0702214.
[29] The QMA-completeness of this subset of Hamiltonians
was found independently by D. Bacon; preprint, (2007).
[30] We thank C.J.S. Truncik, R.G. Harris, W.G. Macready,
M.H.S. Amin, A.J. Berkley, P. Bunyk, J. Lamothe, T.
Mahon and G. Rose. J.D.B. and P.J.L. completed parts
of this work well on staff as D-Wave Systems Inc.
http://arxiv.org/abs/cond-mat/0105238
http://arxiv.org/abs/quant-ph/0208135
http://arxiv.org/abs/quant-ph/0411152
http://arxiv.org/abs/cond-mat/0608253
http://arxiv.org/abs/quant-ph/0606140
http://arxiv.org/abs/quant-ph/0405098
http://arxiv.org/abs/quant-ph/0409024
http://arxiv.org/abs/quant-ph/0609067
http://arxiv.org/abs/quant-ph/0205115
http://arxiv.org/abs/quant-ph/0406180
http://arxiv.org/abs/quant-ph/0504050
http://arxiv.org/abs/quant-ph/9701001
http://arxiv.org/abs/quant-ph/0210187
http://arxiv.org/abs/quant-ph/0604193
http://arxiv.org/abs/quant-ph/0612113
http://arxiv.org/abs/quant-ph/0302079
http://arxiv.org/abs/cond-mat/0304166
http://arxiv.org/abs/quant-ph/0512222
http://arxiv.org/abs/quant-ph/9503017
http://arxiv.org/abs/quant-ph/0506270
http://arxiv.org/abs/quant-ph/0609002
http://arxiv.org/abs/quant-ph/0702214
