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. [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 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. [1] proof assumes a computational model in which the initial and

ﬁnal Hamiltonians H

I

and H

F

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

F

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. [1] show that any quantum circuit C

f

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

5

/ expansion in problem size.

• ree-local Hamiltonians, with at most O.L

14

/ 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

F

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. [1] 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. [18] 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 [13] 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. [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.