26 2. ADIABATIC QUANTUM COMPUTATION
2.4.1 AQC AND RELATED MODELS
Where does AQC ﬁt into the complexity classes of Figure 2.3? e main result in this area is
a proof by Aharonov et al.  that a universal version of AQC can simulate any computation
in the quantum gate model (QGC) with at most polynomial slowdown. Combined with the
result by Farhi et al.  that the quantum gate model can simulate any AQC computation, this
implies that AQC is polynomially equivalent to QGC. erefore AQC—which contains the set
of computable optimization problems—must also contain complexity classes analogous to QMA
and BQP, that contain NPO and FPTAS respectively.
Van Dam et al.  have shown that an AQC algorithm for Grover’s problem—searching
in an unordered set—exhibits quadratic speedup over classical algorithms, as is also the case with
the gate model.
Locality. e Aharonov et al.  proof assumes a computational model in which the initial and
ﬁnal Hamiltonians H
are k-local. A k-local Hamiltonian can be written as the sum of
independent Hamiltonians that each work on at most k qubits. For example, the EC algorithm
(2.31) is 2-local because H
is the sum of operators involving at most two qubits.
Local Hamiltonians are considered better candidates for realization on a physical quan-
tum computer which may have limited connectivity. Sometimes locality is deﬁned according to
topology: for example, the ﬁnal Hamiltonian may be restricted to involve only interactions among
neighboring qubits in a grid.
Aharonov et al.  show that any quantum circuit C
using at most L gates can be simu-
lated by an adabatic quantum computer using one of these models:
• Five-local Hamiltonians, with at most O.L
/ expansion in problem size.
• ree-local Hamiltonians, with at most O.L
/ problem overhead.
• Two-local Hamiltonians interacting on a 2D grid of qubit cells, assuming each cell can
represent six diﬀerent states.
Restrictions on the universal model. Published AQC algorithms use ﬁnal Hamiltonians with
real-valued diagonal elements that exactly match the objective functions f .x/ and with oﬀ-
diagonals equal to zero. is category of Hamiltonian H
creates a classical ground state (with
no superposition) at the time the solution is read. A much wider choice of ﬁnal Hamiltonians is
available in the general computational model; indeed Aharonov et al.  remark that their proof
of equivalence with the gate model assumes that the ﬁnal Hamiltonian is not restricted to be
classical in this way.
Bravyi et al.  deﬁne a stoquastic Hamiltonian as one for which oﬀ-diagonal elements
are real and non-positive. ey show that the problem of minimizing local stoquastic Hamilto-
nians is hard for the class AM (similar to MA, a probabilistic version of NP with two rounds of
communication between the prover and the veriﬁer).
2.4. COMPLEXITY CLASSES 27
Biamonte and Love  consider restrictions to the universal AQC model with an eye
toward realizability in physical machines. ey describe two categories of Hamiltonians that are
suﬃcient to achieve QMA-complete computation: this means the models can solve NP-hard
problems. ey also describe how to modify these models to achieve universal AQC computation.
e quantum annealing chips built by D-Wave require problem Hamiltonians speciﬁed
with reals on the diagonal and zeros on the oﬀ-diagonal, and have a connectivity structure that
is 2-local. erefore the proof of Aharonov et al.  of AQC equivalence with the quantum
gate model does not apply to these chips in their current design. e approximation problem
implemented in the D-Wave hardware topology has a classical PTAS; see Section 4.1 for more.