Where does AQC fit into the complexity classes of Figure 2.3? e main result in this area is
a proof by Aharonov et al. [1] 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. [36] 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. [105] have shown that an AQC algorithm for Grovers 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. [1] proof assumes a computational model in which the initial and
final Hamiltonians H
and 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 defined according to
topology: for example, the final Hamiltonian may be restricted to involve only interactions among
neighboring qubits in a grid.
Aharonov et al. [1] 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 different states.
Restrictions on the universal model. Published AQC algorithms use final Hamiltonians with
real-valued diagonal elements that exactly match the objective functions f .x/ and with off-
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 final Hamiltonians is
available in the general computational model; indeed Aharonov et al. [1] remark that their proof
of equivalence with the gate model assumes that the final Hamiltonian is not restricted to be
classical in this way.
Bravyi et al. [18] define a stoquastic Hamiltonian as one for which off-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 verifier).
Biamonte and Love [13] consider restrictions to the universal AQC model with an eye
toward realizability in physical machines. ey describe two categories of Hamiltonians that are
sufficient 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 specified
with reals on the diagonal and zeros on the off-diagonal, and have a connectivity structure that
is 2-local. erefore the proof of Aharonov et al. [1] 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.

Get Adiabatic Quantum Computation and Quantum Annealing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.